网站制作手机,做外贸怎么网站找客户信息,溧阳手机网站哪里做,珠宝网站方案//
C/C Users Journal October, 2004 锁无关的#xff08;Lock-Free#xff09;数据结构 在避免死锁的同时确保线程继续 Andrei Alexandrescu 刘未鹏 译 Andrei Alexandrescu是华盛顿大学计算机科学系的在读研究生#xff0c;也是《Modern C Design》一书的…//
C/C Users Journal October, 2004 锁无关的Lock-Free数据结构 在避免死锁的同时确保线程继续 Andrei Alexandrescu 刘未鹏 译 Andrei Alexandrescu是华盛顿大学计算机科学系的在读研究生也是《Modern C Design》一书的作者。他的邮箱是 andreimetalanguage.com。 在GenericProgramming沉默了一期之后(研究生的学业总是使人不得不投入百分之百的精力),这一期文章的可写内容突然多得令人似乎有点无所适从.例如,其中之一就是关于构造函数的讨论,特别是转发构造函数(forwarding constructor),(构造函数中的)异常处理,以及两段式(two-stage)对象构造.另一个可选主题是创建不完全类型的容器(例如list、vector或map)顺便再回顾一下Yanslander技术[2]这一任务可以借助于一些有趣的技巧来完成当下的标准库容器并不能保证可存放不完全类型的对象。 虽说以上两个候选主题都挺诱人不过跟所谓的“锁无关Lock-Free”数据结构一比就只能靠边站了后者是多线程编程的极重要技术之一。在今年的“Programming Language Design and Implementation”大会(http://www.cs.umd.edu/~pugh/pldi04/)上Michael Maged展示了世界上第一个锁无关的(lock-free)内存分配器[7]跟那些小心翼翼地设计的、基于锁(lock-based)的同时也更为复杂的内存分配器相比Michael的锁无关的内存分配器在诸多测试下都表现得更为优越。 Michael的锁无关内存分配器代表着近来出现的许多锁无关数据结构和算法的最新进展。 什么是“锁无关(lock-free)” 不久前这个问题正是我想要问的。作为一个真正的主流多线程程序员我对基于锁的多线程算法并不感到陌生。在经典的基于锁的多线程程序设计中只要你需要共享某些数据你就应当将对它的访问串行化。修改共享数据的操作必须以原子操作的形式出现这样才能保证没有其它线程能在中途插一脚来破坏相应数据的不变式invariant。即便像count_(count_是整型变量)这样的简单操作也得加锁因为增量操作实际上是分三步进行的读、改、写回而这显然不是原子的。 简而言之在基于锁的多线程编程中你得确保任何针对共享数据的、且有可能导致竞争条件race conditions的操作都被做成了原子操作通过对一个互斥体mutex进行加锁解锁。从好的一面来说只要互斥体是在锁状态你就可以放心地进行任何操作不用担心其它线程会闯进来搞坏你的共享数据。 然而正是这种在互斥体的锁状态下可以为所欲为的事实同样也带来了问题。例如你可以在锁期间读键盘或进行某些耗时较长的I/O操作这便意味着其它想要占用你正占用着的互斥体的线程只能被晾在一旁等着。更糟的是此时你可能会试图对另一个互斥体进行加锁后者彼时或许已经被另一个线程占用了而这个线程倒过来又试图去获取已然被你的线程所占用的互斥体如此一来两个线程全都陷在那里动弹不得死锁 而在锁无关多线程编程的世界里几乎任何操作都是无法原子地完成的。只有很小一集操作可以被原子地进行这一限制使得锁无关编程的难度大大地增加了。实际上世界上肯定有不少锁无关编程专家而我则不在此列。不过幸运的是这篇文章中所提供的基本工具、内容以及热情可能会激发你成为一个这方面的专家。锁无关编程带来的好处是在线程进展和线程交互方面借助于锁无关编程你能够对线程的进展和交互提供更好的保证。但话说回来刚刚我们所谓的“很小一集可以被原子地进行的操作”又是指哪些操作呢实际上这个问题相当于最少需要一集什么样的原语才能够允许我们实现出任何锁无关的算法如果存在这么一个“最小集”的话 如果你认为这个问题的基础性使得它的解决者理当获得奖赏的话你并不是唯一一个这么认为的。2003年Maurice Herlihy因他在1991年发表的开创性论文“Wait-Free Synchronization” http://www.podc.org/dijkstra/2003.html而获得了分布式编程的Edsger W. Dijkstra奖。在论文中Herlihy证明了哪些原语对于构造锁无关数据结构来说是好的哪些则是不好的。他的论述使得一些看似漂亮的硬件架构突然变得一钱不值同时他的论文还指明了在将来的硬件中应当实现哪些同步原语。 例如Herlihy的论文指出像test-and-set、swap、fetch-and-add、甚至原子队列这样的看似强大的工具都不足以良好地同步两个以上的线程这一结果很是令人惊讶因为带有原子push和pop操作的队列看上去提供了一个相当强大的抽象。从好的一面来说Herlihy同样给出了一般性结论他证明了一些简单的结构就足以实现出任何针对任意数目的线程的锁无关算法。 最简单、也是最普遍的一个通用原语就是CAS操作Compare-And-Swap这也是我一直使用的原语 template class T bool CAS(T* addr, T expected, T value) { if (*addr expected) { *addr value; return true; } return false; } CAS原语负责比较某个内存地址处的内容与一个期望值如果比较成功则将该内存地址处的内容替换为一个新值。这整个操作是原子的。许多现代处理器都实现了不同位长度的CAS或其等价原语这里我用模板来表达它正是由于这个原因我们可以假定一个具体的实现使用元编程来限制可能的T。作为一个原则CAS能够操作的位数越多使用它来实现锁无关数据结构就越容易。如今的32位处理器实现了64位的CAS例如Intel汇编指令中称它为CMPXCHG8你得跟这些汇编助记符多亲近亲近。 一点告诫 通常一篇C文章中会伴随着C代码片断和示例。理想情况下这些代码会是符合标准C规范的而且GenericProgramming专栏的确尽量做到了这一点。 然而当文章涉及的内容是多线程编程时给出符合标准C的示例代码就是不可能的了因为标准C中根本就没有线程的概念而你无法编码不存在的东西。因此这篇文章中的代码某种意义上只不过是“伪码”而并非可移植的标准C代码。例如内存屏障memory barriers对于本文中描述的算法来说真正的实现代码要么是汇编写的要么得在C代码中到处插入所谓的“内存屏障”“内存屏障”是一种处理器相关的机制它能够强制内存读写的顺序性。为了不失讨论重点这里我并不打算对内存屏障多作介绍有兴趣的读者可以参考Butenhof的著作[3]或者在下面的注中提到的一篇关于它的简单介绍[6]。为了方便讨论这里我假定我们的编译器和硬件都没有进行过分的优化例如消除某些“冗余”的变量读取这在单线程环境下的确是个有效的优化。从技术上来讲这即是说一个“顺序一致”的模型其中读和写操作的执行顺序跟它们在源代码中的顺序是完全一样的[8]。 等待无关Wait-Free/锁无关Lock-Free与基于锁Lock-Based的比较 一个“等待无关”的程序可以在有限步之内结束而不管其它线程的相对速度如何。 一个“锁无关”的程序能够确保执行它的所有线程中至少有一个能够继续往下执行。这便意味着有些线程可能会被任意地延迟然而在每一步都至少有一个线程能够往下执行。因此这个系统作为一个整体总是在“前进”的尽管有些线程的进度可能不如其它线程来得快。而基于锁的程序则无法提供上述的任何保证。一旦任何线程持有了某个互斥体并处于等待状态那么其它任何想要获取同一互斥体的线程就只好站着干瞪眼一般来说基于锁的算法无法摆脱“死锁”或“活锁”的阴影前者如两个线程互相等待另一个所占有的互斥体后者如两个线程都试图去避开另一个线程的锁行为就像两个在狭窄走廊里面撞了个照面的家伙都试图去给对方让路结果像跳交谊舞似的摆来摆去最终还是面对面走不过去。当然对于我们人来说遇到这种情况打个哈哈就行了但处理器却不这么认为它会不知疲倦地就这样干下去直到你强制重启。 等待无关和锁无关算法的定义意味着它们有更多的优点 线程中止免疫杀掉系统中的任何线程都不会导致其它线程被延迟。 信号免疫C和C标准禁止在信号或异步中断中调用某些系统例程如malloc。如果中断与某个被中断线程同时调用malloc的话结果就会导致死锁。而锁无关例程则没有这一问题线程可以自由地互相穿插执行。 优先级倒置免疫所谓“优先级倒置”就是指一个低优先级线程持有了一个高优先级线程所需要的互斥体。这种微妙的冲突必须由OS内核来解决。而等待无关和锁无关算法则对此免疫。 一个锁无关的WRRM Map 写专栏文章的好处之一就是你可以定义自己的缩写所以就让我们来定义WRRMWrite Rarely Read Many这一缩写一个WRRM Map是一个被读比被写的次数多得多的map。例如对象工厂[1]观察者模式的许多具体实例[5]以及一个将币种跟汇率联系在一起的map许多时候你只是对它进行读取而只有很少的时候才会更新当然还有许许多多其它的查找表。 WRRM Map可以通过std::map或“准标准”的unordered_maphttp://www.open-std.org/jtcl/sc22/wg21/docs/papers/2004/n1647.pdf来予以实现不过正如我在Modern C Design中所说的assoc_vector一个已序的vectorpair也是一个不错的候选因为它用更新速度换取了查找速度。总而言之锁无关性质是与具体的数据结构选择无关正交的我们姑且就称后者为MapKey,Value。同样出于这篇文章的意图当我说map时就是指那些提供了根据key来查找并能够更新key-value对的表下文将不再重申这一点。 让我们来回顾一下一个基于锁的WRRMMap是怎样实现的我们将一个Map对象与一个Mutex对象结合起来像这样 // WRRMMap的一个基于锁的实现 template class K, class V class WRRMMap { Mutex mtx_; MapK, V map_; public: V Lookup(const K k) { Lock lock(mtx_); return map_[k]; } void Update(const K k, const V v) { Lock lock(mtx_); map_[k] v; } }; 为了避免所有权问题以及无效引用问题这两个问题后面会给我们带来大麻烦Lookup按值返回其结果。这一做法虽说稳妥但有代价。每次查找都会导致对Mutex加锁/解锁而实际上一是平行的查找并不需要相互加锁二是Update比Lookup发生的频率要小得多。那么现在就让我们来实现一个更好的WRRMMap吧。 垃圾收集你在何方 对实现一个锁无关的WRRMMap的第一番尝试停在下面这几个问题上 读取操作(Read)没有任何锁。 更新操作(Update)对整个map作一份拷贝然后更新这份拷贝最后再用这份拷贝来替换掉原来的旧map通过CAS原语来进行。如果最后一步的CAS操作没有成功的话就循环尝试“拷贝/更新/CAS回去”这一步骤直到成功。 由于CAS原语所能操作的字节数是有限制的所以WRRMMap存放指向实际Map的指针而不是一个Map。 // WRRMMap的首个锁无关的实现 // 只有当你有GC的时候才行 template class K, class V class WRRMMap { MapK, V* pMap_; public: V Lookup (const K k) { // 瞧没有锁 return (*pMap_) [k]; } void Update(const K k, const V v) { MapK, V* pNew 0; do { MapK, V* pOld pMap_; delete pNew; pNew new MapK, V(*pOld); (*pNew) [k] v; } while (!CAS(pMap_, pOld, pNew)); // 别 delete pMap_; } }; 这行得通在一个循环当中Update()例程对整个map作了一份拷贝并往该副本中加入了一个新项最后再尝试交换新旧两个map的指针。这里最后一步一定要使用CAS原语而不是简单的赋值这很关键否则像下面这样的一个执行序列将会破坏该map 线程A对该map作了一份副本 线程B对该map作了一份副本并更新了副本 线程A往其副本中加入新项 线程A用其改写后的副本替换原有map这里线程A的改写后的副本中没有线程B所作的任何改动。 而通过CAS一切都能够优雅地完成因为每个线程都相当于作了如下的陈述“假设该map自从我上次观察它以来并没有任何更动那么就进行CAS写回改动后的新map。否则一切从头来过。” 根据定义这就使得Update成了一个锁无关的算法但它并不是等待无关的。例如如果若干线程同时调用Update那么它们每一个都可能会循环尝试不确定的次数然而总会有某个线程能够确保成功更新该map因而整体上的进度总是在继续的。另外幸运的是Lookup是等待无关的。 在一个拥有垃圾收集的环境中我们的工作就算完成了而这篇文章也将在一片欢欣鼓舞中结束。然而事实是我们并没有垃圾收集因而只得面对麻烦了。麻烦就是我们不能简单地就将旧的pMap_扔掉意即delete——译注如果正当你试图delete它的时候一帮其它线程冲上来想要访问它里面的数据Lookup该怎么办呢你是知道的垃圾收集器可以访问所有线程的数据及私有栈所以它对于“哪些pMap_所指的map不再被使用了”这个问题有更清晰的认识而且它也能够优雅地将这些不再被使用的map清理掉。而如果没有垃圾收集器的帮助事情可就没那么简单了。实际上是难得多而且看起来确定性的内存归还在锁无关数据结构方面是个基础问题。 写锁定(Write-Locked)的WRRM Map 为了弄清我们遇到的问题有多棘手让我们先来试试用经典的引用计数技术来实现WRRMMap看看这有何不可。那么考虑将一个引用计数器跟map的指针绑定在一起并让WRRMMap保存一个指向如此构造出的数据结构的指针。 template class K, class V class WRRMMap { typedef std::pairMapK, V*, unsigned Data; Data* pData_; ... }; 嗯看上去不赖。现在Lookup会先递增pData_-second然后在map中进行查找最后再递减pData_-second。当pData_-second计数器的值下降到0的时候pData_-first就可以被delete掉了接着pData_自己也就可以被delete掉了。看起来简单稳妥是不是只不过…只不过它是幼稚的。试想下面这种情况正当某个线程注意到引用计数器的值下降到0并着手delete pData_时另一个线程或另一堆线程插进来拽住了垂死的pData_并准备从它进行读取不管你怎么聪明地安排你的策略你都逃不开一个基本的问题即要想读取数据的指针你得先递增引用计数但引用计数又必须得是你要读取的数据的一部分因此倘不先读取那个指针你就无法访问到该引用计数。这就好比一个将开关安放在其顶端的带电铁丝网要想安全的爬上去你就得先将开关关掉但要想将开关关掉你就得先安全地爬上去啊 那么就让我们来看看有没有其它方法能够正确地delete旧的map。一个方案是等待然后delete。考虑到随着处理器时间毫秒计的推移旧的pMap_对象会被越来越少的线程所访问这是因为新的访问是对新的map进行的于是一旦那些在CAS操作之前开始的Lookup操作结束了对应的旧pMap_也就可以去见阎王了。因此我们的一个解决方案就是将旧的pMap_推入一个队列并由一个专门的清理线程每隔比如说200毫秒醒来一次delete掉队列中待得最久的一个pMap_。 但这并非一个理论上安全的方案尽管从实际上来说它可能绝大多数情况下都不会出什么意外。比如说由于某种原因一个进行Lookup的线程被延迟了那么清理线程就会在该线程的眼皮子底下delete掉它正在访问的map。这可以通过总是给清理线程赋予一个比任何线程低的优先级来予以避免然而总的来说这个方案骨子里的劣根性是难以清除的。如果你也同意对于这样一个技术我们没法为其作任何正儿八经的辩护的话我们就继续往下。 其它的方案[4]则依赖于一个扩展的DCAS原子操作该操作能够compare-and-swap内存中的两个不必连续的字 template class T1, class T2 bool DCAS(T1* p1, T2* p2, T1 e1, T2 e2, T1 v1, T2 v2) { if (*p1 e1 *p2 e2) { *p1 v1; *p2 v2; return true; } return false; } 这里所说的两个字当然是指map的指针以及引用计数器。DCAS已经由摩托罗拉68040处理器非常低效地实现了然而其它处理器并没有实现它。因此基于DCAS的解决方案主要是被当成理想方案来考虑的。 那么在确定性析构的大背景下我们对于该问题的尝试首先是求助于不像DCAS那么要求苛刻的CAS2操作。再次说明许多32位的机器都实现了64位的CAS操作被称为CAS2CAS2仅操作连续的字所以它的能力显然不及DCAS强大。作为开始让我们将引用计数跟它所“保卫”的map指针紧挨着存放在内存中 template class K, class V class WRRMMap { typedef std::pairMapK, V*, unsigned Data; Data data_; ... }; 注意这一次引用计数与它所保护的指针紧挨在一起了这就消除了我们前面提到的“带电铁丝网-开关”的尴尬问题。待会你就会看到这样做的代价。 那么让我们修改Lookup从而使其能够在访问map之前先递增引用计数并在访问结束之后将其递减回去。在下面的代码片断中为了简洁起见我并没有考虑异常安全问题这个问题可以用标准技术来解决。 V Lookup(const K k) { Data old; Data fresh; do { old data_; fresh old; fresh.second; } while (CAS(data_, old, fresh)); V temp (*fresh.first)[k]; do { old data_; fresh old; --fresh.second; } while (CAS(data_, old, fresh)); return temp; } 最后Update负责将该map替换为一个新的——仅当其引用计数为1的时候。 void Update(const K k, const V v) { Data old; Data fresh; old.second 1; fresh.first 0; fresh.second 1; MapK, V* last 0; do { old.first data_.first; if (last ! old.first) { delete fresh.first; fresh.first new MapK, V(old.first); fresh.first-insert(make_pair(k, v)); last old.first; } } while (!CAS(data_, old, fresh)); delete old.first; // whew } Update是这样工作的首先它定义old和fresh两个变量我们现在应该非常熟悉这两个变量了。只不过这次old.second并非由data_.second赋值而来而是始终为1。这意味着Update会一直循环直到它等到data_.first指针的引用计数变成1此时没有任何线程在读并将其替换为另一个引用计数为1的新map的指针。说白了这相当于如下的陈述“我将会把旧的map替换成一个更新过的而且我会留神其它对于该map的更新不过仅当现有map的引用计数为1的时候我才会进行替换。”变量last及其相关代码只不过是个优化技巧当旧map并没有被改动而只是其引用技术被改动的时候last可以帮助避免我们重建同一个map。 挺漂亮的手法对不对只可惜事实并非如此。Update现在实际上是基于锁的它得等待所有Lookup结束之后才能去更新该map。而锁无关数据结构的好处就在于一切都能够如行云流水般进行。特别地在这种实现下Update很容易就可以被饿死你只需足够频繁地进行Lookup就行了让它的引用计数永不降为1。总而言之到目前为止我们得到的并非一个WRRM Map而是一个WRRMBNTMWrite-Rarely-Read-Many-But-Not-Too-Many Map。
本文来自CSDN博客转载请标明出处http://blog.csdn.net/bearinmind/archive/2008/10/29/3166409.aspx // 1 LONG InterlockedExchangeAdd ( LPLONG Addend, LONG Increment ); Addend为长整型变量的地址Increment为想要在Addend指向的长整型变量上增加的数值可以是负数。这个函数的主要作用是保证这个加操作为一个原子访问。 2 LONG InterlockedExchange( LPLONG Target, LONG Value ); 用第二个参数的值取代第一个参数指向的值。函数返回值为原始值。 3 PVOID InterlockedExchangePointer( PVOID *Target, PVOID Value ); 用第二个参数的值取代第一个参数指向的值。函数返回值为原始值。 4 LONG InterlockedCompareExchange( LPLONG Destination, LONG Exchange, LONG Comperand ); 如果第三个参数与第一个参数指向的值相同那么用第二个参数取代第一个参数指向的值。函数返回值为原始值。 5 PVOID InterlockedCompareExchangePointer ( PVOID *Destination, PVOID Exchange, PVOID Comperand ); 如果第三个参数与第一个参数指向的值相同那么用第二个参数取代第一个参数指向的值。函数返回值为原始值。 //
疑问
1在多核系统下或者多 CPU 系统下即使原子操作也可能并行
2接上在多核系统下或者多 CPU 系统下lock-free 是不是废了或者必须保证操作的变量在内存中才能互斥
3接上使用 InterlockedCompareExchange 实现 lock-free 是不是必须申明共享变量为 volatile
4接上即使 vilatile 避免了寄存器但是 cache 中的副本呢InterlockedCompareExchange 保证会刷新另一cpu的cache吗 我的看法1并行2应该必须保证在内存interlock 指令由 CPU 保证该内存地址访问的互斥3必须申明为 volatile4cache 的一致性由 cpu 保证
