使用CAS进行无锁编程

CAS（Compare And Swap）是一种无锁算法，该算法关键依赖两个值——期望值（旧值）和新值，底层CPU利用原子操作判断内存原值与期望值是否相等，如果相等就给内存地址赋新值，否则不做操作。

使用CAS进行无锁编程的步骤大致如下：

1）获得字段的期望值（oldValue）。

2）计算出需要替换的新值（newValue）。

3）通过CAS将新值（newValue）放在字段的内存地址上，如果CAS失败就重复第一步和第二步，一直到CAS成功，这种重复俗称CAS自旋。

使用CAS进行无锁编程的伪代码如下：

下面用一个简单的例子对以上伪代码进行举例说明。

假如某个内存地址（某对象的属性）的值为100，现在有两个线程（线程A和线程B）使用CAS无锁编程对该内存地址进行更新，线程A欲将其值更新为200，线程B欲将其值更新为300，如下图所示：

线程是并发执行的，谁都有可能先执行。但是CAS是原子操作，对同一个内存地址的CAS操作在同一时刻只能执行一个。因此，在这个例子中，要么线程A先执行，要么线程B先执行。假设线程A的CAS(100,200)执行在前，由于内存地址的旧值100与该CAS的期望值100相等，因此线程A会操作成功，内存地址的值被更新为200。

线程A执行CAS(100,200)成功之后，内存地址的值如下图所示：

接下来执行线程B的CAS(100,300)操作，此时内存地址的值为200，不等于CAS的期望值100，线程B操作失败。线程B只能自旋，开始新的循环，这一轮循环首先获取到内存地址的值200，然后进行CAS(200,300)操作，这一次内存地址的值与CAS的预期值（oldValue）相等，线程B操作成功。

当CAS将内存地址的值与预期值进行比较时，如果相等，就证明内存地址的值没有被修改，可以替换成新值，然后继续往下运行；如果不相等，就说明内存地址的值已经被修改，放弃替换操作，然后重新自旋。当并发修改的线程少，冲突出现的机会少时，自旋的次数也会很少，CAS的性能会很高；当并发修改的线程多，冲突出现的机会多时，自旋的次数也会很多，CAS的性能会大大降低。所以，提升CAS无锁编程效率的关键在于减少冲突的机会。