[译]理解compare-and-swap（CAS）

compare-and-swap (CAS) 指令是一个不可中断的操作（原子操作），它读取一个内存地址，把读取到的值和一个期望值进行比较，当读取的值和期望值相等的时候，就把该内存地址的值更新为一个新的值，否则就什么也不做。这个过程根据不同的微处理器指令可能有些许不同（比如，如果 CAS 成功的话返回 true，否则返回 false，而不是下面实例中的做法——返回读取的值）。

微处理器 CAS 指令：

现代的微处理器本省提供了某种 CAS 指令。比如说，Intel 微处理器提供了 cmpxchg 指令族，而 PowerPC 微处理器提供了 load-link（e.g., lwarx）和 store-conditional（e.g., stwcx）指令用于相同的目的。

CAS 使得 read-modify-write 操作序列作为原子操作成为可能。通常我们会按照如下过程使用 CAS：

1. 从地址X读取值v
2. 执行一个多步计算得到一个新的值v2
3. 使用CAS尝试把地址X上的值从v改成v2，当执行这些步骤时X的值未更改，则CAS执行成功。

为了搞清楚CAS是怎样比synchronization提供更好的性能（和可扩展性），举个例子：有一个计数器，允许你读它的当前值并且对值进行累加。下面的类基于synchronization实现了一个计数器：

// Counter.java
public class Counter 
{
   private int value;

   public synchronized int getValue() 
   { 
      return value; 
   }

   public synchronized int increment() 
   { 
      return ++value; 
   }
}

monitor lock 的高竞争会导致大量的上下文切换，从而使所有的线程延迟，并导致应用程序无法很好地扩展。

取而代之的是使用 CAS 的代码实现compare-and-swap操作。下面的类模拟了 CAS ，但是使用的是synchronized而不是实际的硬件指令，用于简化代码:

// EmulatedCAS.java
public class EmulatedCAS
{
   private int value;

   public synchronized int getValue()
   { 
      return value; 
   }

   public synchronized int compareAndSwap(int expectedValue, int newValue) 
   {
      int readValue = value;
      if (readValue == expectedValue)
         value = newValue;
      return readValue;
   }
}

其中，value代表了一个内存地址，可以通过getValue()方法获取值。相应地，compareAndSwap()实现了 CAS 算法。

下面一个类使用EmulatedCAS实现了一个non-synchronized的计数器（这里假设EmulatedCAS不需要synchronized）:

// Counter.java (version 2)
public class Counter 
{
   private EmulatedCAS value = new EmulatedCAS();

   public int getValue() 
   {
      return value.getValue();
   }

   public int increment() 
   {
      int readValue = value.getValue();
      while (value.compareAndSwap(readValue, readValue+1) != readValue)
         readValue = value.getValue();
      return readValue+1;
   }
}

Counter封装了EmulatedCAS实例，并且通过这个实例提供的功能声明了用于获取值和增加计数器值的方法。即，getValue()获取该实例的“当前计数器值”，increment()安全地增加计数器的值。

increment()重复调用compareAndSwap() 直到 readValue的值不再改变，然后就可以改变这个值了。当没有锁牵涉其中的时候，就可以避免竞争以及随之而来的大量上下文切换了。这样性能和代码的可扩展性就能得到提高。

你可能之前了解到ReentrantLock 在高线程争用情况下能够比 synchronized提供更好的性能表现。为了提高性能，ReentrantLock的同步是通过抽象类java.util.concurrent.locks.AbstractQueuedSynchronizer的一个子类来管理的。进一步地，该类利用了未开源的sun.misc.Unsafe类中的compareAndSwapInt()这个 CAS 实现。

原文地址