java cas算法实现乐观锁 (Compare and Swap 比较并交换)

在Java中java.util.concurrent.atomic包下面的原子变量类就是使用了乐观锁的一种实现方式CAS实现的。

　　CAS：

　　　　CAS是乐观锁技术，当多个线程尝试使用CAS同时更新同一个变量时，只有其中一个线程能更新变量的值，而其它线程都失败，失败的线程并不会被挂起，而是被告知这次竞争中失败，并可以再次尝试。　　　

　　　　CAS 操作中包含三个操作数 —— 需要读写的内存位置（V）、进行比较的预期原值（A）和拟写入的新值(B)。如果内存位置V的值与预期原值A相匹配，那么处理器会自动将该位置值更新为新值B。否则处理器不做任何操作。无论哪种情况，它都会在 CAS 指令之前返回该位置的值。（在 CAS 的一些特殊情况下将仅返回 CAS 是否成功，而不提取当前值。）CAS 有效地说明了“ 我认为位置 V 应该包含值 A；如果包含该值，则将 B 放到这个位置；否则，不要更改该位置，只告诉我这个位置现在的值即可。 ”这其实和乐观锁的冲突检查+数据更新的原理是一样的。

　　　　这里再强调一下，乐观锁是一种思想。CAS是这种思想的一种实现方式。

　　JAVA对CAS的支持：

　　　　在JDK1.5 中新增 java.util.concurrent (J.U.C)就是建立在CAS之上的。相对于对于 synchronized 这种阻塞算法，CAS是非阻塞算法的一种常见实现。所以J.U.C在性能上有了很大的提升。

　　　　以 java.util.concurrent 中的 AtomicInteger 为例，看一下在不使用锁的情况下是如何保证线程安全的。主要理解 getAndIncrement 方法，该方法的作用相当于 i++操作。

public class AtomicInteger extends Number implements java.io.Serializable {  
     private volatile int value; 
 
     public final int get() {  
         return value;  
     }  
 
     public final int getAndIncrement() {  
         for (;;) {  
             int current = get();  
             int next = current + 1;  
             if (compareAndSet(current, next))  
                 return current;  
         }  
     }  
 
     public final boolean compareAndSet(int expect, int update) {  
         return unsafe.compareAndSwapInt(this, valueOffset, expect, update);  
     }  
 }

　在没有锁的机制下,字段value要借助volatile原语，保证线程间的数据是可见性。这样在获取变量的值的时候才能直接读取。然后来看看 ++i 是怎么做到的。

　　　  getAndIncrement 采用了CAS操作，每次从内存中读取数据然后将此数据和 +1 后的结果进行CAS操作，如果成功就返回结果，否则重试直到成功为止。

　　　  而 compareAndSet 利用JNI（Java Native Interface）来完成CPU指令的操作：

public final boolean compareAndSet(int expect, int update) {   
     return unsafe.compareAndSwapInt(this, valueOffset, expect, update);
 }　

　　　　其中unsafe.compareAndSwapInt(this, valueOffset, expect, update);类似如下逻辑：

 if (this == expect) {
     this = update
     return true;
 } else {
     return false;
 }

那么比较this == expect，替换this = update，compareAndSwapInt实现这两个步骤的原子性呢？ 参考CAS的原理

　　CAS原理：

　　　　CAS通过调用JNI的代码实现的。而compareAndSwapIn