背景

和Java这种提供自动gc的语言相比，C/C++程序员刀耕火种，得自己管理内存。当一个线程正在访问某块内存，而另外一个线程将它释放将是一个灾难行为。

场景如下：

• 线程 A 想替换该数据结构中的某个数据节点，线程 A 使用 newNode 原子替换了oldNode，并同时释放了oldNode，防止了内存泄露，这一切看起来没什么问题；
• 在线程 A 的上述操作中，若巧好有另一个线程 B 在线程 A 替换前便进行了读取（读到 oldNode 指针），但稍后线程 A 释放了 oldNode，那么线程 B 此时持有的便是一个悬空指针（一旦使用就 coredump 了）。

目标

在无 gc 的语言中实现一种无锁但支持并发的数据结构（可能是个map、也可能是个 array）：
对于 c/c++，则没有一种很好的方法应对这问题，除非 非gc语言也有一种延迟回收内存的机制，于是Epoch Based Reclamation作为其中一种方法应运而生。

目前用于lock free代码的内存回收的经典方法有：Lock Free Reference Counting、Hazard Pointer、Epoch Based Reclamation、Quiescent State Based Reclamation等。

关键词：

• 无锁且支持并发
• 共享数据结构无锁释放
• 多线程无锁操作共享数据

epoch-based reclaim

定义（what）

逻辑删除和物理删除

一个节点的删除包含 逻辑删除（delete/remove） 和 物理删除（free） 两个过程。

• 逻辑删除（delete/remove）

• 逻辑删除仅仅是在逻辑上删除该节点，该节点在被逻辑删除之时可能会有其他线程正在访问它.
• 逻辑删除之后不会再被线程访问到。
• 逻辑删除不回收内存空间。

• 物理删除（free / reclaim）
  物理释放则是将对应的内存空间回收。

宽限期（Grace Period）

• 宽限期的含义
  逻辑删除和物理删除之间的间隔，称之为宽限期（Grace Period），如图中的中间的黄色部分。从Remove到Reclaim，中间就隔了一个宽限期。

• 宽限期和逻辑删除、物理删除的关系

• 逻辑删除之时，有可能存在其他读者正在访问被删除对象（如：reader-3, reader-4, reader-5）。
• 逻辑删除之后，不会有其他的新增的读者访问被删除对象。
  注：逻辑删除之后，正在访问删除对象的读者可能还在访问。
• 宽限期之后，再也没有任何读者访问被删除对象。
  注：宽限期之后，就可以进行内存释放了。

因此，只有当宽限期结束后，才会触发回收的工作。宽限期的结束代表着Reader都已经退出了临界区，因此回收工作也就是安全的操作了。

临界区(critical section)

• 临界区(critical section)
  临界区是指包含有共享数据的一段代码，这些代码可能被多个线程访问 或修改。
  临界区的存在就是为了保证当有一个线程在临界区内执行的时候，不能有其他任何 线程被允许在临界区执行。

• 临界资源（critical resource）
  临界资源是一次仅允许一个进程使用的共享资源。

原理（why）

• 维护了一个全局的 epoch (取值为0、1、2)，epoch 的每个取值都对应一个 retire list（存放逻辑删除后待物理删除的指针）；
• 为每个线程维护一个局部的active flag和epoch(取值自然也为0、1、2)。
• 线程进入临界区前会设置 active flag = true，并设置自己的局部 epoch 为全局 epoch 的值，离开临界区时设置 active flag = false；
• 线程删除数据时，先放入对应的 retire_list [global_epoch]（线程局部 epoch 等于 global epoch）；
• 全局 epoch （假设为 E）的增长规则，若所有活跃线程的 epoch 是否都等于 E 时，置换 E = (E + 1) % 3；

注：
epoch计数循环增长，如012012012012…
active表示该线程是否处于临界区，即是否正在访问共享数据。任一线程在进入临界区时，先置active=true， e = E，退出临界区时，置active=false.

读线程

首先设置自己的active flag 为true，表明自己需要访问共享内存。然后将自己的局部的epoch设置为全局的epoch值。这之后线程就进入临界区，可以放心的读取资源了，不用担心内存会被回收。离开临界区时，将自己的active flag设置为false即可。

写线程

注：这里说的写线程是指会对资源进行删除的线程。首先进行逻辑删除，然后尝试对它进行物理删除，也就是回收。
任一线程，如果其对共享数据做出了更改，则需要删除的数据（如上例种的oldNode），不会直接删除，而是将其放入对应e的回收队列中。

令全局的epoch值为e。
如果存在活动线程的局部epoch值不等于全局epoch值，那么可以回收retire_list[(e+1) % 3]。
如果不存在，那么我们把全局epoch的值更新为(e+1)%3，然后再回收对应的retire list。

线程局部 epoch 和全局 epoch 的关系

任何时刻，全局epoch的值如果为e，那么线程的局部epoch值要么也为e，要么为e-1（即e的前一个数），不可能为e+1（e的后一个数）。

当全局epoch的值为1的时候，线程的局部epoch要么是1，要么是0，不可能是2。因此[2,1]构成了一个Grace Period，也就是说2对应的retire list这时候可以放心的回收了。
当全局epoch的值为0的时候，线程的局部epoch要么是0，要么是2，不可能是1。因此[1,0]构成了一个Grace Period，也就是说1对应的retire list这时候可以放心的回收了。
当全局epoch的值为2的时候，线程的局部epoch要么是2，要么是1，不可能是0。因此[0,2]构成了一个Grace Period，也就是说0对应的retire list这时候可以放心的回收了。

因此，当全局epoch值为2时，如果存在部分活跃线程的局部epoch等于1，那么retire_list[1]将不能立马回收。如果这些活跃线程不退出临界区（在里面不断的读、疯狂的读，或者死了），那么retire_list[1]纪录的那些内存将一直无法回收。这也就是在Epoch Based Reclamation中，回收操作可能被读延迟的原因所在。

全局epoch取值	局部epoch可能取值	grace period	可回收的retire list
0	2、0	[1, 0]	1
1	0、1	[2, 1]	2
2	1、2	[0, 2]	0

前面说到 当全局 epoch = E 时， 活跃线程的 epoch 只能是 E 或 E - 1，当最后一个 e = E -1 的线程完成了临界区操作，也即所有活跃线程中 epoch 计数都等于E的时候，也就是说 E - 2（也即 E + 1）对应的回收队列 retireList 中的节点再也没有任何一个线程访问了，故而retireList[E - 2] 中的数据可以真正的释放了。如此做后，全局计数E = E + 1

使用（how）

范例

这里为了能focus我们的主题，我们刻意简化为四个线程，其中三个读线程，它们对数据都是只读的；而只有一个写线程可以对资源进行改写和删除，因此不需要加锁。

#define N_THREADS 4 //一共4个线程
bool active[N_THREADS] = {false};
int epoches[N_THREADS] = {0};
int global_epoch = 0;
vector<int*> retire_list[3];

void read(int thread_id)
{
  active[thread_id] = true;
  epoches[thread_id] = global_epoch;
  //进入临界区了。可以安全的读取
  //...... 
  //读取完毕，离开临界区
  active[thread_id] = false;
}

void logical_deletion(int thread_id)
{
  active[thread_id] = true;
  epoches[thread_id] = global_epoch;
  //进入临界区了，这里，我们可以安全的读取
  //好了，假如说我们现在要删除它了。先逻辑删除。
  //而被逻辑删除的tmp指向的节点还不能马上被回收，因此把它加入到对应的retire list
  retire_list[global_epoch].push_back(tmp);
  //离开临界区
  active[thread_id] = false;
  //看看能不能物理删除
  try_gc();
}

bool try_gc()
{
  int &e = global_epoch;
  for (int i = 0; i < N_THREADS; i++) {
    if (active[i] && epoches[i] != e) {
        //还有部分线程没有更新到最新的全局的epoch值
        //这时候可以回收(e + 1) % 3对应的retire list。
        free((e + 1) % 3);//不是free(e)，也不是free(e-1)。参看下面
        return false;
    }
  }
  //更新global epoch
  e = (e + 1) % 3;
  //更新之后，那些active线程中，部分线程的epoch值可能还是e - 1（模3）
  //那些inactive的线程，之后将读到最新的值，也就是e。
  //不管如何，(e + 1) % 3对应的retire list的那些内存，不会有人再访问到了，可以回收它们了
  //因此epoch的取值需要有三种，仅仅两种是不够的。
  free((e + 1) % 3);//不是free(e)，也不是free(e-1)。参看下面
}

bool free(int epoch)
{
  for each pointer in retire_list[epoch]
    if (pointer is not NULL)
      delete pointer;
}

参考

http://www.yebangyu.org/blog/2016/09/09/epochbasedreclamation/
https://www.cnblogs.com/chenny7/p/14780109.html