素心如何天上月

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. 拷贝目标对象
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结构，这不会有这样的问题（虽然运行比较慢的、优先级比较低的线程依然可能被饿死），并且有更好的可伸缩性。