Yebangyu's Blog

Fond of Concurrency Programming, Distributed System and Performance Optimization.

Lock Free中的Epoch Based 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等。上回我们简单介绍了Hazard Pointer,本文我们介绍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