算法描述
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操作可以成功，这样整体上看，就保证了所有的线程上在“前进”，而不需要使用效率低下的锁来协调线程，更不会导致死锁之类的麻烦。
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 指向新的对象了，以后的操作都将会访问新的对象，但是老的对象还可能正被其他线程访问中。遗憾的是，我们还没有垃圾收集器，所以需要设计一个引用计数之类的策略来保护这个对象。
待续……
参考：
锁无关的（Lock-Free）数据结构
多核编程中的任务随机竞争模式的概率分析