lock-free线程安全算法

Lock-free 算法的基础是 CAS (Compareand-Swap) 原子操作。当某个地址的原始值等于某个比较值时，把值改成新值，无论有否修改，返回这个地址的原始值。目前的cpu 支持最多64位的CAS。并且指针 p 必须对齐。

 

 注：原子操作指一个cpu时钟周期内就可以完成的操作，不会被其他线程干扰。

 

 

一般的 CAS 使用方式是：

1. 假设有指针 p, 它指向一个 32 位或者64位数，复制p 的内容（*p）到比较量 cmp （原子操作）。
2. 基于这个比较量计算一个新值 xchg （非原子操作）。
3. 调用 CAS 比较当前 *p 和 cmp, 如果相等把 *p 替换成 xchg （原子操作）。
4. 如果成功退出，否则回到第一步重新进行。

其中，第3步的 CAS 操作保证了写入的同时 p 没有被其他线程更改。如果*p已经被其他线程更改，那么第2步计算新值所使用的值(cmp)已经过期了，因此这个整个过程失败，重新来过。多线程环境下，由于 3 是一个原子操作，那么起码有一个线程（最快执行到3）的CAS 操作可以成功，这样整体上看，就保证了所有的线程上在“前进”，而不需要使用效率低下的锁来协调线程，更不会导致死锁之类的麻烦。

 

 

lock-free的优点：

 

一个“锁无关”的程序能够确保执行它的所有线程中至少有一个能够继续往下执行。这便意味着有些线程可能会被任意地延迟，然而在每一步都至少有一个线程能够往下执行。因此这个系统作为一个整体总是在“前进”的，尽管有些线程的进度可能不如其它线程来得快。而基于锁的程序则无法提供上述的任何保证。一旦任何线程持有了某个互斥体并处于等待状态，那么其它任何想要获取同一互斥体的线程就只好等待；一般来说，基于锁的算法无法摆脱“死锁”或“活锁”的阴影。

 

 

ABA 问题

 

如果当 A 线程执行2的时候，被B 线程更改了 *p为x, 而 C 线程又把它改回了原始值，这时回到A 线程，A线程无法监测到原始值已经被更改过了，CAS 操作会成功（实际上应该失败）。ABA 大部分情况下会造成一些问题，因为 p 的内容一般不可能是独立的，其他内容已经更改，而A线程认为它没有更改就会带来不可预知的结果。

 

ABA 问题的解决一般是扩展 *p 的位数（比如从32扩展到64），使用多余的位来保存一个版本号，每次更改都修改版本号，从而保证这个线程能正确的监测到值的更改。

 

 

扩展

 

一个 32 位数无法携带太多信息，但是32位的C++ 环境中，这样的一个数已经可以代表很多东西了，比如——指针。

 

我们刚才保证了我们的线程可以安全读写一个 32 位的数，如果这个数是一个指针，指向了我们真实使用的对象。那么我们就可以创建了一个无锁而线程安全的对象。基本思想就是每次修改对象前，复制整个对象，然后更改完成以后用上面的算法使用新对象来替换旧对象（更改p的指向），当然，这个对象不能太大，否则lock-free的速度优势，就被复制操作消耗殆尽。

 

这里有个很大的问题，在于老的对象何时销毁。P 指向新的对象了，以后的操作都将会访问新的对象，但是老的对象还可能正被其他线程访问中。遗憾的是，我们还没有垃圾收集器，所以需要设计一个引用计数之类的策略来保护这个对象。

 

 

原文地址：http://blog.csdn.net/jadedrip/article/details/1731554