lock-free线程安全算法
Lock-free 算法的基础是 CAS (Compareand-Swap) 原子操作。当某个地址的原始值等于某个比较值时，把值改成新值，无论有否修改，返回这个地址的原始值。目前的cpu 支持最多64位的CAS。并且指针 p 必须对齐。
注：原子操作指一个cpu时钟周期内就可以完成的操作，不会被其他线程干扰。
一般的 CAS 使用方式是：
- 假设有指针 p, 它指向一个 32 位或者64位数，复制p 的内容（*p）到比较量 cmp （原子操作）。
- 基于这个比较量计算一个新值 xchg （非原子操作）。
- 调用 CAS 比较当前 *p 和 cmp, 如果相等把 *p 替换成 xchg （原子操作）。
- 如果成功退出，否则回到第一步重新进行。
其中，第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 指向新的对象了，以后的操作都将会访问新的对象，但是老的对象还可能正被其他线程访问中。遗憾的是，我们还没有垃圾收集器，所以需要设计一个引用计数之类的策略来保护这个对象。