Epoch Base Reclamation

楔子

一般认为，用C/C++编写Lock Free代码非常困难，主要原因无非是两个：

• 内存模型

• 内存回收

C++11引入了标准的内存模型，在此之前，C++程序员依赖于具体的体系结构特点和编译器提供的feature来保证正确的内存访问语义。C++11出来后，程序员编写健壮的、可移植的lock free代码成为可能。

但是内存回收问题依旧存在。我们知道，和Java这种提供自动gc的语言相比，C++程序员刀耕火种，得自己管理内存。当一个线程正在访问某块内存，而另外一个线程将它释放将是一个灾难行为。解决内存回收问题在lock free里显得更加困难。

目前用于lock free代码的内存回收的经典方法有：Lock Free Reference Counting、Hazard Pointer、Epoch Based Reclamation、Quiescent State Based Reclamation等。本文我们介绍Epoch Based Reclamation方法。据我所知，这是第一篇介绍这个方法的中文资料。

概念

1，逻辑删除和物理删除：逻辑删除仅仅是在逻辑上删除该节点，该节点在被逻辑删除之时可能会有其他线程正在访问它，而逻辑删除之后不会再被线程访问到。逻辑删除不回收内存空间。物理删除则是将对应的内存空间回收。一般逻辑删除对应delete，物理删除对应free或者reclaim。

2，Grace Period：记时间段T＝[t1,t2]，如果t1之前逻辑删除的节点，都可以在t2之后安全的回收，那么称T是一个Grace Period。t2之后保证不会有任何线程会访问在t1之前逻辑删除的节点。

3，临界区：在本文，临界区指的是线程访问共享内存资源的代码段。和传统上所说的临界区意义不同。

实现

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

也请注意，以下伪代码只起示范作用，离真正生产环境实现还差很远。尽管如此，我们还是提供了一些实现细节和关键点(参考最后的思考一节)。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52

#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;
}

原理

算法维护了一个全局的epoch(取值为0、1、2)和三个全局的retire_list（每个全局的epoch对应一个retire list, retire list 存放逻辑删除后待回收的节点指针）。除此之外我们为每个线程维护一个局部的active flag和epoch(取值自然也为0、1、2)。

读线程

首先设置自己的active flag 为true，表明自己需要访问共享内存。然后将自己的局部的epoch设置为全局的epoch值。

这之后线程就进入临界区，可以放心的读取资源了，不用担心内存会被回收。

离开临界区时，将自己的active flag设置为false即可。

写线程

这里说的写线程是指会对资源进行删除的线程。首先进行逻辑删除，然后尝试对它进行物理删除，也就是回收。

令全局的epoch值为e。首先检查，如果存在活动线程的局部epoch值不等于全局epoch值，那么可以回收retire_list[(e+1) % 3]。

如果不存在，那么我们把全局epoch的值更新为(e+1)%3，然后再回收对应的retire list。

有点绕？这里关键是理清线程局部epoch和全局epoch的关系：在这个算法里，任何时刻，全局epoch的值如果为e，那么线程的局部epoch值要么也为e，要么为e-1，不可能为e+1。

所以[epoch, epoch + 2]（模3）构成了一个Grace Period。

当全局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中，回收操作可能被读延迟的原因所在。

思考

1，代码中8、9两行是写一个变量(active[i])，读另外一个变量(global_epoch)，在x86下可能会乱序，这里是否需要一个cpu级别的memory barrier？如果被乱序，有没有影响？

2，retire_list[global_epoch].push_back(tmp); 能否改为 retire_list[epoches[thread_id]].push_back(tmp); ？也就是说这里能否改为使用线程局部epoch值？

3，和Hazard Pointer相比，Epoch Based Reclamation 有什么优点和缺点？

4，为什么epoch有三个取值0、1、2？能不能仅使用两个？

5，线程局部变量我们使用了active数组和epoches数组，这里会有性能问题，为什么？提示：False Sharing