无锁并发

2015-10-01

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

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指针中包含它时,才执行真正的释放操作。

无锁CAS