使用CAS实现lock-free的一个类比

CAS(CompareAndSwap),是用来实现lock-free编程的重要手段之一,多数处理器都支持这一原子操作。其用伪码描述如下,

template bool CAS(T* addr, T expected, T value)
{
   if (*addr == expected) {
      *addr = value;
      return true;
   }
   return false;
}

Herb在其一篇文章中提到,看到类如if(variable.compare_exchange(x,y))这样的表达式时, 你应该去习惯将其解读为,“是否我就是那个要把variable从x改为y的线程?”。

使用CAS实现lock-free的一般过程可描述为:

  1. 拷贝目标对象(原子性的,CAS仅支持可以cast到WORD的类型)
  2. 创建一个新的对象或另一个拷贝用于修改
  3. 用CAS对原始对象和拷贝对象进行比较,以完成更新,如果失败跳转到#1

你可能觉得这个过程有些眼熟,和C++里异常安全编码的规则有些类似,都是先得到目标对象的一份拷贝,然后对拷贝进行修改,最后通过一个不会抛出异常的swap(),将拷贝和目标对象进行置换。只不过这里多了一个CAS,判断目标对象是否已经被其他线程修改了。如果没有被修改过,则commit;否则,就要重做重试

这个过程有一个很实际的风险,就是人们常说的ABA问题,即在当前线程得到目标对象的拷贝并进行修改时,目标对象可能被另一个线程从A修改到B、进而又从B又修改到A了。解决ABA问题的方法是,为操作的对象加上一个版本号。大部分的处理器都支持CAS2,支持对两个连续的WORD进行比较和交换。对Intel/AMD的x86和x64处理器来说,CAS2分别对应的是8个byte和16个byte。

我一直在想,这个过程有没有一个比较直观、容易让人理解的类比。后来想到,作为程序员的我们,在使用版本管理系统进行合作开发时,其实经常遇到类似的问题。例如,我们可以把团队里的多个成员想象为多个线程,我们可能同时对一个源文件进行修改。作为个人,修改代码并最终提交的过程大概是这个样子的,

  1. 从代码仓库中检出或更新某个源代码文件
  2. 对本地的文件拷贝进行修改
  3. 在提交之前从代码仓库中update一下该文件,如果没有冲突,就可以提交了;否则,就要解决冲突再尝试提交

在步骤iii中,存在冲突的原因是,一定有其他同事(另一个线程)已经对这个文件进行了修改并提交;如果我们把解决冲突的过程描述为,重新拷贝目标源文件,并apply/merge步骤ii中得到的patch,这个过程和前面的那个过程非常接近了。

对于ABA问题,可以想象:另一个同事在我提交之前对文件进行了修改,然后又revert了自己的修改(A->B->A),虽然没有冲突,我们依然可以将步骤iii设想为重新拷贝新版本并apply patch的方式(虽然大多数版本管理工具是根据文件的checksum进行相等性比较的)。

如果在这个时间段,某同事快速不停地对该文件进行修改提交的话,我可能就一直处于“redo-retry”的状态而无法提交自己的代码了。这时,索性我就先把这个修改放到一边,去冲杯咖啡,溜达溜达,然后回来继续尝试。这个就是所谓“back-off”操作了,即如果CAS一直失败,就空闲一会儿,甚至将线程切换出去。

似乎基于CAS的lock-free结构和spin-lock也很相像,不都是一直自旋等待么,不也都是基于乐观性假设么?也对,spin-lock也有可能是用CAS来实现的呢。不过,spin-lock毕竟还是一个锁,因此也就沿袭了锁的一些问题,例如优先级反转、死锁等。而基于CAS的lock-free结构,这不会有这样的问题(虽然运行比较慢的、优先级比较低的线程依然可能被饿死),并且有更好的可伸缩性。

使用CAS实现lock-free的一个类比

2 thoughts on “使用CAS实现lock-free的一个类比

  1. 我感觉transaction的粒度要更大一些,但是意思应该是一致的 ...

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>

To submit your comment, click the image below where it asks you to...
Clickcha - The One-Click Captcha