CAS乐观锁的实现与问题

1.乐观锁CAS和悲观锁synchronized

Compare and Swap，简称CAS，是一种通过乐观锁保证变量操作原子性的机制。

我们通常熟悉的加锁方式是通过synchronized关键字，可以很方便地给实例方法、静态方法和代码块加锁，保证操作的原子性。

synchronized锁是是悲观的，是同步锁，它假定更新很可能冲突，所以先获取锁，得到锁后才更新。

synchronized代表一种阻塞式算法，得不到锁的时候，进入锁等待队列，等待其他线程唤醒，有上下文切换开销。原子变量的更新逻辑是非阻塞式的，更新冲突的时候，它就重试，不会阻塞，不会有上下文切换开销。

与synchronized锁相比，CAS原子更新方式代表一种不同的思维方式。

悲观锁更新的思维方式认为，在更新数据的时候大概率会有其他线程去争夺共享资源，所以悲观锁的做法是，第一个获取资源的线程会将资源锁定起来，其他没争夺到资源的线程只能进入阻塞队列，等第一个获取资源的线程释放锁之后，这些线程才能有机会重新争夺资源。

synchronized就是java中悲观锁的典型实现，synchronized的优点是使用起来非常简单方便，但缺点是会使没争抢到资源的线程进入阻塞状态，线程在阻塞状态和Runnable状态之间切换效率较低（比较慢）。

在更新操作非常快的情况下，仍然用synchronized将其他线程都锁住，现场状态切换的成本就变得非常高，线程从Blocked状态切换回Runnable花费的时间可能比更新操作的时间还要长。

乐观锁更新的思维方式认为，在更新数据的时候其他线程争抢这个共享变量的概率非常小，所以更新数据的时候不会对共享数据加锁，但在正式更新数据之前会检查数据是否被其他线程改变过，如果未被其他线程改变过就将共享变量更新成最新值，如果发现共享变量已经被其他线程更新过了就重试，直到成功为止。CAS机制就是乐观锁的典型实现。在并发量不是很高的情况下，或者线程对共享资源的占用时间不是很长，由于避免了频繁切换线程状态，因此使用CAS机制的效率会比synchronized锁更高。

2.原子变量CAS原理

Java的原子变量内部就是通过CAS指令来实现的。

原子变量的更新逻辑是乐观的，它假定冲突比较少，但使用CAS更新，也就是进行冲突检测，如果确实冲突了，那也没关系，继续尝试就好了。

对于大部分比较简单的操作，无论是在低并发还是高并发情况下，这种乐观非阻塞方式的性能都远高于悲观阻塞式方式。

Java并发包中的基本原子变量类型有以下几种:

1. AtomicBoolean：原子Boolean类型，常用来在程序中表示一个标志位。
   
2. AtomicInteger：原子Integer类型。
   
3. AtomicLong：原子Long类型，常用来在程序中生成唯一序列号。
   
4. AtomicReference：原子引用类型，用来以原子方式更新复杂类型。
   
5. LongAdder、LongAccumulator、Double-Adder和DoubleAccumulator：Java 8增加，适合高并发统计汇总的场景。

原子变量相对比较简单，但对于复杂一些的数据结构和算法，非阻塞方式往往难于实现和理解，幸运的是，Java并发包中已经提供了一些非阻塞容器，我们只需要会使用就可以了，比如：

• ConcurrentLinkedQueue和ConcurrentLinkedDeque：非阻塞并发队列。
  
• ConcurrentSkipListMap和ConcurrentSkipListSet：非阻塞并发Map和Set。
  
• AtomicLongArray、AtomicReferenceArray：如针对数组类型的类。
  
• AtomicIntegerFieldUpdater、AtomicReferenceFieldUpdater：原子方式更新对象中的字段。
• 
  

AtomicInteger包含一些以原子方式实现组合操作的方法，部分方法如下：

//以原子方式获取旧值并设置新值publicfinalintgetAndSet(intnewValue) 
//以原子方式获取旧值并给当前值加1publicfinalintgetAndIncrement()
//以原子方式获取旧值并给当前值减1publicfinalintgetAndDecrement()
//以原子方式获取旧值并给当前值加deltapublicfinalintgetAndAdd(intdelta)
//以原子方式给当前值加1并获取新值publicfinalintincrementAndGet()
//以原子方式给当前值减1并获取新值publicfinalintdecrementAndGet()
//以原子方式给当前值加delta并获取新值public final intaddAndGet(intdelta)
//compareAndSet是一个非常重要的方法，比较并设置，我们以后将简称为CAS。//该方法有两个参数expect和update，以原子方式实现了如下功能：// 如果当前值等于expect，则更新为update，否则不更新，// 如果更新成功，返回true，否则返回false。publicfinalbooleancompareAndSet(intexpect, intupdate)

以incrementAndGet方法为例，代码主体是个死循环，先获取当前值current，计算期望的值next，然后调用CAS方法进行更新，如果更新没有成功，说明value被别的线程改了，则再去取最新值并尝试更新直到成功为止。

源码如下：

publicfinalintincrementAndGet() {
for (;;) {
intcurrent=get();
intnext=current+1;
if(compareAndSet(current, next)){
returnnext;
        }
    }
}

synchronized是悲观的，它假定更新很可能冲突，所以先获取锁，得到锁后才更新。

原子变量的更新逻辑是乐观的，它假定冲突比较少，但使用CAS更新，也就是进行冲突检测，如果确实冲突了，那也没关系，继续尝试就好了。

synchronized代表一种阻塞式算法，得不到锁的时候，进入锁等待队列，等待其他线程唤醒，有上下文切换开销。

原子变量的更新逻辑是非阻塞式的，更新冲突的时候，它就重试，不会阻塞，不会有上下文切换开销。对于大部分比较简单的操作，无论是在低并发还是高并发情况下，这种乐观非阻塞方式的性能都远高于悲观阻塞式方式。

原子变量相对比较简单，但对于复杂一些的数据结构和算法，非阻塞方式往往难于实现和理解，幸运的是，Java并发包中已经提供了一些非阻塞容器，我们只需要会使用就可以了，比如：

ConcurrentLinkedQueue和ConcurrentLinkedDeque：非阻塞并发队列。 ConcurrentSkipListMap和ConcurrentSkipListSet：非阻塞并发Map和Set。

compareAndSet是怎么实现的呢？我们看代码：

publicfinalbooleancompareAndSet(intexpect, intupdate) {
returnunsafe.compareAndSwapInt(this, valueOffset, expect, update);
}

它调用了unsafe的compareAndSwapInt方法。

unsafe是什么呢？它的类型为sun.misc.Unsafe，定义为：

privatestaticfinalUnsafeunsafe=Unsafe.getUnsafe();

它是Sun的私有实现，从名字看，表示的也是“不安全”，一般应用程序不应该直接使用。

原理上，一般的计算机系统都在硬件层次上直接支持CAS指令，而Java的实现都会利用这些特殊指令。

从程序的角度看，可以将compareAndSet视为计算机的基本操作，直接接纳就好。

基于CAS，除了可以实现乐观非阻塞算法之外，还可以实现悲观阻塞式算法，比如锁。

实际上，Java并发包中的所有阻塞式工具、容器、算法也都是基于CAS的（不过，也需要一些别的支持）。

用AtomicInteger实现一个锁MyLock：

publicclassMyLock {
privateAtomicintegerstatus=newAtomicInteger(0);
publicvoidlock() {
while(!status.compareAndSet(0, 1)) {
Thread.yield();
        }
    }
publicvoidunlock() {
status.compareAndSet(1, 0);
    }
}

在MyLock中，使用status表示锁的状态，0表示未锁定，1表示锁定，lock（）、unlock（）使用CAS方法更新，lock（）只有在更新成功后才退出，实现了阻塞的效果，不过一般而言，这种阻塞方式过于消耗CPU，MyLock只是用于演示基本概念，实际开发中应该使用Java并发包中的类，如ReentrantLock。

3.CAS的问题与解决

CAS比悲观锁的效率高，从阻塞机制变成了非阻塞机制，减少了线程之间等待的时间，有一个前提，就是并发量不大。

因为在线程之间竞争程度大的时候，如果使用CAS，每次都有很多的线程在竞争，也就是说CAS机制不能更新成功。这种情况下CAS机制会一直重试，这样就会比较耗费CPU。

因此可以看出，如果线程之间竞争程度小，使用CAS是一个很好的选择；但是如果竞争很大，使用锁可能是个更好的选择。

在并发量非常高的环境中，如果仍然想通过原子类来更新的话，可以使用AtomicLong的替代类：LongAdder。

除了在高并发场景下耗费CPU的问题，使用CAS方式更新还有一个ABA问题。

该问题是指，假设当前值为A，如果另一个线程先将A修改成B，再修改回成A，当前线程的CAS操作无法分辨当前值发生过变化。

ABA是不是一个问题与程序的逻辑有关，即B之前的A和B之后的A不影响程序逻辑，ABA也就不是问题。

而如果确实有问题，解决方法是使用AtomicStampedReference，在修改值的同时附加一个时间戳，只有值和时间戳都相同才进行修改，其CAS方法声明为：

publicbooleancompareAndSet(VexpectedReference, VnewReference,                             intexpectedStamp, intnewStamp) 
{    
Pair<V>current=pair;    
returnexpectedReference==current.reference&&expectedStamp==current.stamp&&     ((newReference==current.reference&&newStamp==current.stamp) ||casPair(current, Pair.of(newReference, newStamp)));
}

AtomicStampedReference在compareAndSet中要同时修改两个值：一个是引用，另一个是时间戳。

它怎么实现原子性呢？实际上，内部AtomicStampedReference会将两个值组合为一个对象，修改的是一个值，我们看代码：

publicbooleancompareAndSet(VexpectedReference, VnewReference,                             intexpectedStamp, intnewStamp) 
{    
Pair<V>current=pair;    
returnexpectedReference==current.reference&&expectedStamp==current.stamp&&     ((newReference==current.reference&&newStamp==current.stamp) ||casPair(current, Pair.of(newReference, newStamp)));
}

这个Pair是AtomicStampedReference的一个内部类，成员包括引用和时间戳，具体定义为：

privatestaticclassPair<T> {
finalTreference;    
finalintstamp;    
privatePair(Treference,intstamp) {       
this.reference=reference;        
this.stamp=stamp;    
}    
static<T>Pair<T>of(Treference, intstamp) {        
returnnewPair<T>(reference, stamp);    
}
}

AtomicStampedReference将对引用值和时间戳的组合比较和修改转换为了对这个内部类Pair单个值的比较和修改。

对于并发环境中的计数、产生序列号等需求，应该使用原子变量而非锁，CAS是Java并发包的基础，基于它可以实现高效的、乐观、非阻塞式数据结构和算法，它也是并发包中锁、同步工具和各种容器的基础。

4.参考资料

• 《并发编程的基石——CAS机制》 www.cnblogs.com/54chensongx…
• 《synchronized详解 》www.cnblogs.com/three-fight…
• 《Java编程的逻辑》豆瓣：book.douban.com/subject/301…