锁无关的数据结构与Hazard指针
来源:百度文库 编辑:神马文学网 时间:2024/04/29 14:19:00
操纵有限的资源
By Andrei Alexandrescu and Maged Michael
刘未鹏(pp_liu@msn.com) 译
Andrei Alexandrescu是华盛顿大学计算机科学系的在读研究生,也是《Modern C++ Design》一书的作者。他的邮箱是andrei@metalanguage.com。
Maged Michael是IBM的Thomas J.Watson研究中心的研究员。
首先,我很荣幸向大家介绍Maged Michael,Maged Michael和我共同撰写了本期的Generic,他是锁无关(Lock-Free)算法方面的权威,而且对一些困难问题[3]提出了令人惊讶的独创性方案。在你将要阅读的这篇文章中我们就会向你呈上这么一项激动人心的技术。下文将要介绍的算法通过操纵手头有限的资源,以一种近乎神奇的方式达到了其目的。
如果把Generic栏目比作肥皂剧的话,这一集中那些反派角色将会被轰走(译注:很遗憾,这位C++大师的幽默水平似乎很crappy,每当看到这类joke我都只能无语)。为了帮你回忆一下这里所谓的“反派角色”是谁,我们回顾一下上期的文章[1]。(下面我先帮你做一个简要回顾,但再后面的内容要求你对上期的文章至少做过一遍粗略的阅读,并且大致知道我们要去解决的问题是什么。)
上期的文章中,在引入了锁无关编程的概念之后我们曾实现了一个锁无关的WRRM(Write-Rarely-Read-Many)Map。我们经常看到这类数据结构以全局表、工厂对象、高速缓存(cache)等形式出现。我们遇到的问题在于内存的回收:既然我们的数据结构得是锁无关的,那么我们该如何来回收内存呢?正如前面讨论过的,这是个棘手的问题,因为锁无关意味着任何线程在任何时候都有不受限的机会去操作任何对象。为了解决这一问题,上篇文章中曾作了以下几点尝试:
对map使用引用计数。该策略是注定要失败的,因为它要求对指针和引用计数变量(它们在内存中处于不同的地方)同时进行(原子地)更新。尽管有少数论文使用了DCAS(Double Compare-And-Swap,该指令的行为正是这里所需要的),然而这个东西从来也没能流行起来,因为没有它我们照样能够做许多事情,而且它也没有强大到能够高效地实现出任意事务的程度。参考[2]关于DCAS的用途的讨论。
等待并delete。一旦“清理”线程知道某个指针要被delete掉了,它就可以等待一段“足够长的时间”然后delete它。然而问题是这段“足够长的时间”到底应该有多长呢?所以说这个方案听上去跟“分配一块足够大的缓冲区”一样蹩脚,后者怎么样大家是知道的。
将引用计数跟指针紧挨着存放在一起。这个方案使用了要求较少,可以合理实现的CAS2原语,CAS2能够原子地Compare-and-Swap内存中的两个紧邻的字。大多数32位机器都支持这一原语,只不过支持它的64位机器倒没那么多了,不过对于后一种情况我们可以在指针内的位上面做点文章来解决这个问题)。
上面提到的最后一个方案被证明是可行的,只不过它却将我们的漂亮的WRRM Map变成了一个粗陋的WRRMBNTM(Write-Rarely-Read-Many-But-Not-Too-Many) Map,因为其写操作需要等到绝对没有任何读操作正在进行的时候才会去写。这就意味着,只要有一个读操作在所有其它读操作结束之前开始了,写操作就只能干等。而这就不能算是锁无关了。
Bullet探长走进了他的债务人的办公室,坐下,点燃一枝雪茄,以一种绝对冷静的、足以将整个沸腾的办公室冰冻住的声音说道:“除非拿回我的钱,否则我是不会走的。”
基于引用计数的一个可行方案是将引用计数变量跟指针分离开来。这样写操作就不再被读操作所阻塞了,不过它们仍只能在引用计数降为0时才能去delete旧的map[5]。此外,如果采用此方案,我们就只需使用针对单字的CAS,这就使我们的技术可移植于不同的硬件架构之间,包括那些不支持CAS2的。然而,该方案仍存在问题:即我们并没有消除等待,而只不过是将它延期了,这便增加了内存占用方面的问题发生的几率。
Bullet探长怯怯地敲开他的债务人的办公室的门,吞吞吐吐的问:“您现在可以还我的19,990块钱了吗?没有?噢,好吧,好吧。这里是我仅剩的10块钱,给。过些时日我再过来,看看你有没有我的20,000块钱。”
在这种方案下,写函数可能会保留任意多个未被回收的旧map,并眼巴巴的等着(可能会一直等下去)它们的引用计数变成0。换句话说,即使仅有一个读线程被延迟也可能会导致任意量的内存无法被回收,而且该线程拖得越久,情况就越遭。
我们真正需要的是这么一种机制,基于它,读线程可以告诉写线程别在它们的眼皮子底下回收某些旧map,同时读线程还不能强迫写线程在那等着释放一堆也许是任意数量的旧map。实际上,存在着一个不仅是锁无关、而且还是等待无关的解决方案。(回忆一下上期文章中的定义:锁无关意味着系统中总存在某个线程能够得以继续执行;而等待无关则是一个更强的条件,它意味着所有线程都能往下进行。)而且该方案并不要求用到什么特殊的操作,如DCAS、CAS2之类,它只需使用我们可以信赖的CAS原语即可。开始感到有点意思了吧?那就继续往下读。
Hazard指针
回顾一下上期文章中的代码,我们有一个模板的WRRMMap,它内部有一个指向某个经典的单线程Map对象(如std::map)的指针,同时它还向外界提供了一个多线程的、锁无关的访问接口:
template
class WRRMMap {
Map * pMap_;
...
};
每当WRRMMap需要更新的时候,想要对它进行更新的线程就会首先创建它的一个完整的副本,更新副本,然而再将pMap_指向该副本,最后delete掉pMap_原先所指的旧map。我们认为这种做法算不上低效,因为WRRMMap通常只是被读取,很少被更新。然而,麻烦的问题是我们怎样才能妥善地将旧的pMap_销毁掉,因为任何时候都可能有其它线程正在对它们进行读取。
Hazard指针就是我们所采用的技术,借助于Hazard指针,线程就得以安全高效地将它们的内存使用告知所有其它线程。每一读线程都拥有一个“单个写线程/多个读线程”的共享指针,这便是所谓的“Hazard指针”。当一个读线程将一个map的地址赋给它的hazard指针时,即意味着它在向其它(写)线程宣称:“我正在读该map,如果你原意,你可以将它替换掉,但别改动它的内容,当然更不要去delete它。”
而站在写线程的立场来看,写线程在delete任何被替换下来的旧map之前须得检查读线程的hazard指针(看看该旧的map是否仍在被使用)。也就是说,如果一个写线程是在一个(或多个)读线程已将某个特定map挂到它(们)的hazard指针上之后才将该map替换下来的,那么该写线程就只有等到那些读线程的hazard指针被release之后才能去delete被替换掉的旧map。
每当一个写线程替换某个map的时候,它会将替换下来的旧map放入一个私有链表中。直到该链表中的旧map达到一定数量的时候(待会我们会讨论这个数量的上限是如何选取的),写线程就会扫描读线程的hazard指针,看看旧map列表中有哪些是与这些hazard指针匹配的。如果某个旧map不与任何读线程的hazard指针匹配,那么销毁该map就是安全的。否则写线程就会仍将其保留在链表中,直到下次扫描。
下面就是我们将要使用的数据结构。主要的共享结构是一个关于hazard指针(HPRecType)的单链表,由pHead_所指向。该链表中的每一项都包含一个hazard指针(pHazard_)、一个标志着该hazard指针是否正处于使用中的flag(active_)、以及一个指向下一节点的指针(pNext_)。
HPRecType类提供了两个原语:Acquire和Release。HPRecType::Acquire返回一个指向一个HPRecType节点的指针,姑且称其为p。如此一来,获取了该指针的线程就可以设置p->pHazard_,并以此确保其它线程会小心对待该指针。而当该线程不再使用该指针时,它就会调用HPRecType::Release(p)。
// Hazard pointer record
class HPRecType {
HPRecType * pNext_;
int active_;
// Global header of the HP list
static HPRecType * pHead_;
// The length of the list
static int listLen_;
public:
// Can be used by the thread
// that acquired it
void * pHazard_;
static HPRecType * Head() {
return pHead_;
}
// Acquires one hazard pointer
static HPRecType * Acquire() {
// Try to reuse a retired HP record
HPRecType * p = pHead_;
for (; p; p = p->pNext_) {
if (p->active_ ||
!CAS(&p->active_, 0, 1))
continue;
// Got one!
return p;
}
// Increment the list length
int oldLen;
do {
oldLen = listLen_;
} while (!CAS(&listLen_, oldLen,
oldLen + 1));
// Allocate a new one
HPRecType * p = new HPRecType;
p->active_ = 1;
p->pHazard_ = 0;
// Push it to the front
do {
old = pHead_;
p->pNext_ = old;
} while (!CAS(&pHead_, old, p));
return p;
}
// Releases a hazard pointer
static void Release(HPRecType* p) {
p->pHazard_ = 0;
p->active_ = 0;
}
};
// Per-thread private variable
__per_thread__ vector
By Andrei Alexandrescu and Maged Michael
刘未鹏(pp_liu@msn.com) 译
Andrei Alexandrescu是华盛顿大学计算机科学系的在读研究生,也是《Modern C++ Design》一书的作者。他的邮箱是andrei@metalanguage.com。
Maged Michael是IBM的Thomas J.Watson研究中心的研究员。
首先,我很荣幸向大家介绍Maged Michael,Maged Michael和我共同撰写了本期的Generic
如果把Generic
上期的文章中,在引入了锁无关编程的概念之后我们曾实现了一个锁无关的WRRM(Write-Rarely-Read-Many)Map。我们经常看到这类数据结构以全局表、工厂对象、高速缓存(cache)等形式出现。我们遇到的问题在于内存的回收:既然我们的数据结构得是锁无关的,那么我们该如何来回收内存呢?正如前面讨论过的,这是个棘手的问题,因为锁无关意味着任何线程在任何时候都有不受限的机会去操作任何对象。为了解决这一问题,上篇文章中曾作了以下几点尝试:
对map使用引用计数。该策略是注定要失败的,因为它要求对指针和引用计数变量(它们在内存中处于不同的地方)同时进行(原子地)更新。尽管有少数论文使用了DCAS(Double Compare-And-Swap,该指令的行为正是这里所需要的),然而这个东西从来也没能流行起来,因为没有它我们照样能够做许多事情,而且它也没有强大到能够高效地实现出任意事务的程度。参考[2]关于DCAS的用途的讨论。
等待并delete。一旦“清理”线程知道某个指针要被delete掉了,它就可以等待一段“足够长的时间”然后delete它。然而问题是这段“足够长的时间”到底应该有多长呢?所以说这个方案听上去跟“分配一块足够大的缓冲区”一样蹩脚,后者怎么样大家是知道的。
将引用计数跟指针紧挨着存放在一起。这个方案使用了要求较少,可以合理实现的CAS2原语,CAS2能够原子地Compare-and-Swap内存中的两个紧邻的字。大多数32位机器都支持这一原语,只不过支持它的64位机器倒没那么多了,不过对于后一种情况我们可以在指针内的位上面做点文章来解决这个问题)。
上面提到的最后一个方案被证明是可行的,只不过它却将我们的漂亮的WRRM Map变成了一个粗陋的WRRMBNTM(Write-Rarely-Read-Many-But-Not-Too-Many) Map,因为其写操作需要等到绝对没有任何读操作正在进行的时候才会去写。这就意味着,只要有一个读操作在所有其它读操作结束之前开始了,写操作就只能干等。而这就不能算是锁无关了。
Bullet探长走进了他的债务人的办公室,坐下,点燃一枝雪茄,以一种绝对冷静的、足以将整个沸腾的办公室冰冻住的声音说道:“除非拿回我的钱,否则我是不会走的。”
基于引用计数的一个可行方案是将引用计数变量跟指针分离开来。这样写操作就不再被读操作所阻塞了,不过它们仍只能在引用计数降为0时才能去delete旧的map[5]。此外,如果采用此方案,我们就只需使用针对单字的CAS,这就使我们的技术可移植于不同的硬件架构之间,包括那些不支持CAS2的。然而,该方案仍存在问题:即我们并没有消除等待,而只不过是将它延期了,这便增加了内存占用方面的问题发生的几率。
Bullet探长怯怯地敲开他的债务人的办公室的门,吞吞吐吐的问:“您现在可以还我的19,990块钱了吗?没有?噢,好吧,好吧。这里是我仅剩的10块钱,给。过些时日我再过来,看看你有没有我的20,000块钱。”
在这种方案下,写函数可能会保留任意多个未被回收的旧map,并眼巴巴的等着(可能会一直等下去)它们的引用计数变成0。换句话说,即使仅有一个读线程被延迟也可能会导致任意量的内存无法被回收,而且该线程拖得越久,情况就越遭。
我们真正需要的是这么一种机制,基于它,读线程可以告诉写线程别在它们的眼皮子底下回收某些旧map,同时读线程还不能强迫写线程在那等着释放一堆也许是任意数量的旧map。实际上,存在着一个不仅是锁无关、而且还是等待无关的解决方案。(回忆一下上期文章中的定义:锁无关意味着系统中总存在某个线程能够得以继续执行;而等待无关则是一个更强的条件,它意味着所有线程都能往下进行。)而且该方案并不要求用到什么特殊的操作,如DCAS、CAS2之类,它只需使用我们可以信赖的CAS原语即可。开始感到有点意思了吧?那就继续往下读。
Hazard指针
回顾一下上期文章中的代码,我们有一个模板的WRRMMap,它内部有一个指向某个经典的单线程Map对象(如std::map)的指针,同时它还向外界提供了一个多线程的、锁无关的访问接口:
template
class WRRMMap {
Map
...
};
每当WRRMMap需要更新的时候,想要对它进行更新的线程就会首先创建它的一个完整的副本,更新副本,然而再将pMap_指向该副本,最后delete掉pMap_原先所指的旧map。我们认为这种做法算不上低效,因为WRRMMap通常只是被读取,很少被更新。然而,麻烦的问题是我们怎样才能妥善地将旧的pMap_销毁掉,因为任何时候都可能有其它线程正在对它们进行读取。
Hazard指针就是我们所采用的技术,借助于Hazard指针,线程就得以安全高效地将它们的内存使用告知所有其它线程。每一读线程都拥有一个“单个写线程/多个读线程”的共享指针,这便是所谓的“Hazard指针”。当一个读线程将一个map的地址赋给它的hazard指针时,即意味着它在向其它(写)线程宣称:“我正在读该map,如果你原意,你可以将它替换掉,但别改动它的内容,当然更不要去delete它。”
而站在写线程的立场来看,写线程在delete任何被替换下来的旧map之前须得检查读线程的hazard指针(看看该旧的map是否仍在被使用)。也就是说,如果一个写线程是在一个(或多个)读线程已将某个特定map挂到它(们)的hazard指针上之后才将该map替换下来的,那么该写线程就只有等到那些读线程的hazard指针被release之后才能去delete被替换掉的旧map。
每当一个写线程替换某个map的时候,它会将替换下来的旧map放入一个私有链表中。直到该链表中的旧map达到一定数量的时候(待会我们会讨论这个数量的上限是如何选取的),写线程就会扫描读线程的hazard指针,看看旧map列表中有哪些是与这些hazard指针匹配的。如果某个旧map不与任何读线程的hazard指针匹配,那么销毁该map就是安全的。否则写线程就会仍将其保留在链表中,直到下次扫描。
下面就是我们将要使用的数据结构。主要的共享结构是一个关于hazard指针(HPRecType)的单链表,由pHead_所指向。该链表中的每一项都包含一个hazard指针(pHazard_)、一个标志着该hazard指针是否正处于使用中的flag(active_)、以及一个指向下一节点的指针(pNext_)。
HPRecType类提供了两个原语:Acquire和Release。HPRecType::Acquire返回一个指向一个HPRecType节点的指针,姑且称其为p。如此一来,获取了该指针的线程就可以设置p->pHazard_,并以此确保其它线程会小心对待该指针。而当该线程不再使用该指针时,它就会调用HPRecType::Release(p)。
// Hazard pointer record
class HPRecType {
HPRecType * pNext_;
int active_;
// Global header of the HP list
static HPRecType * pHead_;
// The length of the list
static int listLen_;
public:
// Can be used by the thread
// that acquired it
void * pHazard_;
static HPRecType * Head() {
return pHead_;
}
// Acquires one hazard pointer
static HPRecType * Acquire() {
// Try to reuse a retired HP record
HPRecType * p = pHead_;
for (; p; p = p->pNext_) {
if (p->active_ ||
!CAS(&p->active_, 0, 1))
continue;
// Got one!
return p;
}
// Increment the list length
int oldLen;
do {
oldLen = listLen_;
} while (!CAS(&listLen_, oldLen,
oldLen + 1));
// Allocate a new one
HPRecType * p = new HPRecType;
p->active_ = 1;
p->pHazard_ = 0;
// Push it to the front
do {
old = pHead_;
p->pNext_ = old;
} while (!CAS(&pHead_, old, p));
return p;
}
// Releases a hazard pointer
static void Release(HPRecType* p) {
p->pHazard_ = 0;
p->active_ = 0;
}
};
// Per-thread private variable
__per_thread__ vector
锁无关的数据结构与Hazard指针
指针与数组的异同
【精华】数据结构和算法版旧的精华贴 数据结构与算法 第二帖
算法与数据结构——高德纳的二十年计划
c++中引用与指针的区别
指向数组的指针与多维数组
结构体与函数指针的特
与时间无关的成长
与 事 无关的读书
女人的品味与年龄无关,与相貌无关,与金钱无关
多维数组与指针
有关数据结构方面的基本概念
有关数据结构方面的基本概念
成员函数指针与高性能的c委托
成员函数指针与高性能的C++委托
结构体与函数指针的特殊应用
“无奈的闲暇”与黄金周无关
与北京猿人无关的爱情技术工具
困惑的解除与年龄无关
婚姻 一场与爱情无关的赌局
婚姻--- ---一场与爱情无关的赌局
与黄金美女无关的读书
与黄金美女无关的读书.
与黄金美女无关的读书