无锁并发

写一点无锁和并发相关的东西。

func CompareAndSwapInt32(addr *int32, old, new int32) (swapped bool)

Go的atomic包中这个函数的功能是比较addr地址内的值，如果它等于old，则将它更新为new。CAS操作在x86的指令集上都是有提供支持的，汇编是CMPXCHG指令，用于无锁并发。

CAS操作是实现无锁链表的基础。假如我们在链表的prev和next两个结点之间，插入结点p：

p->next = next;
cas(prev->next, next, p);

第二步操作不是直接执行prev->next = p;，而是做一个CAS操作。为什么呢？因为在多线程并发操作时，可能有其它线程已经在prev和next之间插入结点了。所以CAS这个原子操作保证如果失败了，就不会执行第二步。

一般CAS是放在一个循环中去做的，不停地尝试，总有一个线程能够成功。比锁的粒度要小，因为加锁的代码会造成线程切换。

ABA是CAS存在的一个问题，大概描述是这样：

1. 线程P1读共享变量得到A
2. 线程切换，P1被切出去了，P2执行
3. P2把共享变量的值从A改成了B，再改回到A，线程切换，P1执行
4. P1看到共享变量的值没变过，CAS操作成功

ABA问题有什么影响呢？简单的理解，假设我们在实现一个无锁的栈，当前栈项的内容是A。一个线程要往里面原子性插入C，它用CAS操作来保证这种原子性，想当然地认为，只要当前的栈还是A，并且CAS是原子性的，就能保证整个操作的原子性。可是万万没想到，这期间另一个线程，push了一个B，又push了一个A。栈的内容就不是前面那个线程想象的样子了。

更复杂的场景，比如说内存分配算法可能会重用内存空间，前面的

cas(prev->next, next, p);

操作成功，并不能保证原子性，一种可能的情况是：prev的next被删除了，又执行过一些其它操作，后来分配一个新结点重用了next的空间，这个结点又正好插入prev后面。CAS成功返回了，但这不是我们要的。

ABA还在一些其它的场景，可能会导致内存泄漏之类的问题。并发的世界充满意想不到的“惊喜”。

前面在prev和next之前插入结点的操作中，没有考虑到一个问题：如果做插入操作的时候，prev结点被从链表中删除了怎么办？更可怕的是，如果prev结点分配的内存空间被释放了怎么办？在没有GC的语言中，必须自己释放内存。事实上，无锁操作中的内存回收跟预防ABA问题一样是一个难点。

Hazard指针可以用于解决这种问题。每个线程保存一份当前线程正在使用的hazard指针的链表。这个链表中的hazard指针不能被别的线程修改或者释放。当一个读线程将某个地址赋给它的hazard指针时，即意味着它在向其它（写）线程宣称：“我正在访问这个地址，如果你原意，你可以将它替换掉，但别改动它的内容，当然更不要去delete它。”

一个线程想释放一块内存时，不会立即释放它，而是放在一个链表中，等到没有任何其它的线程的hazard指针中包含它时，才执行真正的释放操作。