无锁数据结构和传统的数据结构在内存管理有一点区别是：当数据不用了，需要释放内存时，传统数据结构直接调用free()就可以了，但是无锁数据结构不行。举个例子，如下图所示，T1正在读取b1的时候，T2释放了b1，T1中的指针就变成了野指针，造成不安全的内存访问。

image-20220410114205442

因此，在无锁数据结构中，内存的释放操作一般要延后执行，即保证没有线程能够访问到该片内存后，再执行内存回收。这种方式被称作Safe Memory Reclamation（SMR）。

从上述例子中，我们可以从两个方面去理解一个SMR算法：

  1. 如何保护正在使用的数据不被释放？
  2. 什么时候能安全地释放已经被标记为需要释放的内存？

下面介绍两种常用的SMR算法：

  1. Hazard Pointers（Protected Pointers）
  2. Epoch-Based Reclamation（基于代际的内存释放）

image-20220411074041712

Hazard Pointers#

Hazard Pointers的基本思想是线程访问数据块时会将指针记录下来，其它线程尝试释放内存时会感知到数据块引用的存在，从而延迟释放内存，直到所有线程对该数据块的访问结束。

image-20220411083606925

如上图所示，使用hazard pointers有如下几个步骤：

  1. 在线程访问共享数据时，先调用reserve()方法，将指针记录在一个list内；
  2. T2线程尝试释放释放b1时，调用retire()，因为检测到还有线程访问b1，延迟释放内存；
  3. 因为内存没有真正释放，T1能在b1 retire后继续访问b1。访问结束后，T1调用unreserve()将指针从list中移除；
  4. T3调用gc()（可以周期性运行，也可以事件触发），遍历所有retired的数据块，如果list内没有指向数据块的指针，即可以真正回收内存。

Hazard Pointers有些致命的缺点：

  1. 不够快。因为reserve()保护的指针需要立即被gc()感知到，所以，两个函数都需要引入开销非常大的store-load fence。在遍历整个数据结构时，每个数据块都会调用reserve()，导致遍历效率降低；
  2. 并不是所有的数据结构都适用Hazard Pointers。在前文的Lock-free Linked List中，我们也提过Harris-Michael‘s traversing是为了专门支持Hazard Pointers的。Harris’s traversing会retire一个连续的数据块，这样，即便T1线程保护了其中一个数据块，gc()仍然可以回收其它的数据块内存，T1线程访问next指针时，仍然会出现问题。

Epoch-Based Reclamation#

Hazard Pointers只保护无锁数据结构中真正被访问的那部分数据，这也导致了上文中Hazard Pointers的两个缺陷。与Hazard Pointers不同的是，EBR保护的是数据结构中所有可能潜在的访问。这样也就不需要频繁地在线程间同步。

image-20220413090336739

每个线程在访问数据结构前都会开启一个代际（epoch）。T1在代际e中retire了b1和b2。那么什么时候能安全地reclaim b1和b2的内存呢？

如上图，我们在这个EBR算法中规定了一个代际一致性规则：并发的代际之间最多只能相差1。也就是说，只要T1还没有调用set_quiescent()结束掉e代，那么其它线程通过set_active()开启的代际号只能是e+1。而所有的e+1代的线程是有可能引用到b1和b2的。当e代结束，T2开启e+2代时，因为e+2代和e代不存在同时发生的可能性（通过代际一致性规则保证），所以在e+2代是不可能访问到e代retire的b1和b2的。到了e+3代，表示所有可能访问到b1和b2的e+1代都已经结束，此时即可安全地回收b1和b2内存。

不同的代际一致性规则，可以安全回收的代际是不一样的。