这篇文章给大家介绍crossbeam-epoch中基于epoch的无锁垃圾收集原理是什么，内容非常详细，感兴趣的小伙伴们可以参考借鉴，希望对大家能有所帮助。
成都创新互联公司是专业的嘉鱼网站建设公司，嘉鱼接单;提供网站制作、成都网站建设,网页设计,网站设计,建网站,PHP网站建设等专业做网站服务;采用PHP框架,可快速的进行嘉鱼网站开发网页制作和功能扩展;专业做搜索引擎喜爱的网站,专业的做网站团队,希望更多企业前来合作!
crossbeam提供了一个基于epoch的“垃圾收集”(epoch based reclamation)库。首先来简单的说一下这一垃圾回收的原理。
基于epoch的“垃圾回收”
这一算法主要在Keir Fraser的
博士论文
中有涉及。我们从之前无锁并发栈的简单实现中看到，并发环境中的数据结构的容器（比如包含了出栈元素的那个节点），会在一个线程中完成它的使命然后准备被释放。但是这个时候可能还有其他线程还持有其快照（主要是为了进行CAS）。不过不会再有新的线程还会继续取得其快照了。那么只要等到所有对该容器取得快照的线程都完成操作，就可以安心的释放这个容器了。
算法大概是这样的：当一个线程需要对某个数据结构操作时，它先将自己的标识符设置为活跃，然后将本地epoch计数器更新为全局epoch计数器。而如果线程需要从数据结构中删除一个节点，它会把该节点加入当前epoch的垃圾列表。当线程完成对数据结构的操作时，线程将自己标记为不活跃。然后当需要收集垃圾的时候，一个线程会遍历所有线程并检查是否所有活跃的线程的epoch都和当前全局的epoch相同，如果是那么全局epoch计数将会+1，同时2个epoch前的垃圾可以被回收。事实上，当处于epoch N+2的时候，由于所有对数据进行操作（活跃）的线程都在epoch N+1之后，可以安全的清理epoch N的垃圾列表。crossbeam-epoch的API
Guard
使用
pin
可以产生
Guard
，这将当前线程标识为活跃
use crossbeam_epoch as epoch;
let guard = &epoch::pin();
defer_destroy
则将数据放入垃圾列表，等待2个epoch之后就可以被清理了
pub unsafe fn defer_destroy(&self, ptr: Shared)
Shared
我们刚刚在
defer_destroy
的函数签名中看到了
Shared
，这是一个被Guard的生命周期
'g
所保护的指针类型，相当于
&'g T
。它保证了Guard存在期间数据的可访问。Owned
这相当于
Box
，是一个不会被其他线程接触到的量。Atomic
这是一个可以在线程间交换的原子指针。可以在
Guard
的保护下从中读出
Shared
pub fn load(&self, ord: Ordering, &'g Guard) -> Shared<'g, T>
也可以将
Owned
或者
Shared
（即
Pointer
）存入
pub fn store(&self, new: P, ord: Ordering)where P: Pointer,
pub fn compare_and_set( &self, current: Shared, new: P, ord: O, &'g Guard) -> Result, CompareAndSetError<'g, T, P>>where O: CompareAndSetOrdering, P: Pointer,
实现并发栈
有了这些API，我们就可以实现一个无锁的MPMC的Treiber栈了。
use std::mem::ManuallyDrop;use std::ptr;use std::sync::atomic::Ordering::{Acquire, Relaxed, Release};
use crossbeam_epoch::{self as epoch, Atomic, Owned};
#[derive(Debug)]pub struct TreiberStack { head: Atomic>,}
#[derive(Debug)]struct Node { data: ManuallyDrop, // 告诉编译器该变量不需要自动Drop next: Atomic>,}
impl TreiberStack { pub fn new() -> TreiberStack { TreiberStack { head: Atomic::null(), } }
pub fn push(&self, t: T) { let mut n = Owned::new(Node { data: ManuallyDrop::new(t), next: Atomic::null(), });
let guard = epoch::pin(); // 标记当前线程为活跃
loop { let head = self.head.load(Relaxed, &guard); n.next.store(head, Relaxed);
match self.head.compare_and_set(head, n, Release, &guard) { // CAS Ok(_) => break, Err(e) => n = e.new, } } }
pub fn pop(&self) -> Option { let guard = epoch::pin(); // 标记当前线程为活跃 loop { let head = self.head.load(Acquire, &guard);
match unsafe { head.as_ref() } { Some(h) => { let next = h.next.load(Relaxed, &guard);
if self .head .compare_and_set(head, next, Relaxed, &guard) // CAS .is_ok() { unsafe { guard.defer_destroy(head); // 将垃圾加入列表 return Some(ManuallyDrop::into_inner(ptr::read(&(*h).data))); // 返回节点中的数据 } } } None => return None, } } }
pub fn is_empty(&self) -> bool { let guard = epoch::pin(); self.head.load(Acquire, &guard).is_null() }}
impl Drop for TreiberStack { fn drop(&mut self) { while self.pop().is_some() {} }}
关于crossbeam-epoch中基于epoch的无锁垃圾收集原理是什么就分享到这里了，希望以上内容可以对大家有一定的帮助，可以学到更多知识。如果觉得文章不错，可以把它分享出去让更多的人看到。
分享文章：crossbeam-epoch中基于epoch的无锁垃圾收集原理是什么
转载源于：
http://www.cdkjz.cn/article/gpgjhj.html
