转载

Lock Free程序中Hazard Pointer的应用

废话不多说了，直接开始讨论。

首先看以下的程序，有问题吗？

#include<iostream> #include<thread> //C++11中的多线程基础设施 using namespace std; int *p = new int(2); void reader() {   if (nullptr != p) { //nullptr是C++11中引入的     cout << *p << endl;   } } void writer() {   delete p;   p = nullptr; } int main() {   thread t1(reader);   thread t2(writer);   t1.join();   t2.join();   return 0; }

答案当然是有问题。这个程序存在可怕的 race condition ：如果当线程 reader 判断完 p 发现它不是 nullptr 后，还未执行第 8 行就被调度出去，轮到线程 writer 执行，它执行完 13 、 14 行后，又继续调度线程 reader ，此时执行第 8 行导致程序崩溃。

这里的本质是对象的生命周期问题，表述为：多线程程序中，某线程通过一个指针访问一段内存时，如何保证指针所指向的内存是有效的？

这当然有多种方法，加一把互斥锁就万事大吉了。不过本文讨论的是 Lock Free 情况下的内存管理，因此我们要讨论的是 2004 年（其实在 2002 年就有人独立提出类似方法）提出的 Hazard Pointer 大法。接着看以下代码：

#include<thread> #include<iostream> #define Strong_Memory_Barrier __sync_synchronize #define ACCESS_ONCE(x) (* (volatile typeof(x) *) &(x)) using namespace std; struct HazardPointer {   HazardPointer() :p_(nullptr){}   int *p_; //Hazard Pointer封装了原始指针 };  int *p = new int(2); //原始指针  HazardPointer *hp = new HazardPointer(); //只有一个线程可以写  class Writer { public:   void retire(int **tmp) {     *retire_list = *tmp;//设置要释放的指针   }   void gc() {     if (*retire_list == hp->p_) {       //说明有读者正在使用它，不能释放     } else {       //可以安全地释放       delete *retire_list;       *retire_list = nullptr;     }   }   void write() {     //....     retire(&p);     gc();   } private:   int **retire_list;//记录待释放的指针 }; class Reader { public:   void acquire(int *tmp) {     hp->p_ = tmp;   }   void release() {     hp->p_ = nullptr;   }   void read() {     int *tmp = nullptr;     do     {       tmp = ACCESS_ONCE(p);     Strong_Memory_Barrier();       acquire(tmp); //封装。这是告诉Writer：我要读，别释放！     } while (tmp != ACCESS_ONCE(p));//仔细想想，为什么这里还要判断？     if (nullptr != tmp) { //再想想，这里为嘛也要判断？       //it is safe to access *tmp from now on       cout << *tmp << endl;//没问题~     }     //when you finish reading it, just release it .     release();//其实就是告诉Writer：用完啦，要释放要保留，悉听尊便。   } }; int main() {   thread t1(&Reader::read, Reader());   thread t2(&Writer::write, Writer());   t1.join();   t2.join();   return 0; }