AtomicInteger实现机制

• 问题背景

　　最近在看LinkedBlockingQueue看到了其中的count使用AtomicInteger修饰，之前也看过AtomicInteger的一些解释，也是似懂非懂的，今天深入的了解了其实现方式，学到了很多东西。

• 基础介绍

 　　要对AtomicInteger有一个深入的认识，就必须要了解一下悲观锁和乐观锁。cpu是时分复用的，也就是把cpu的时间片，分配给不同的线程/进程轮流执行，时间片与时间片之间，需要进行cpu切换，也就是会发生进程的切换。切换涉及到清空寄存器，缓存数据。然后重新加载新的thread所需数据。当一个线程被挂起时，加入到阻塞队列，在一定的时间或条件下，在通过notify()，notifyAll()唤醒回来。在某个资源不可用的时候，就将cpu让出，把当前等待线程切换为阻塞状态。等到资源(比如一个共享数据）可用了，那么就将线程唤醒，让他进入runnable状态等待cpu调度。这就是典型的悲观锁的实现。独占锁是一种悲观锁，synchronized就是一种独占锁，它假设最坏的情况，并且只有在确保其它线程不会造成干扰的情况下执行，会导致其它所有需要锁的线程挂起，等待持有锁的线程释放锁。

　　但是，由于在进程挂起和恢复执行过程中存在着很大的开销。当一个线程正在等待锁时，它不能做任何事，所以悲观锁有很大的缺点。举个例子，如果一个线程需要某个资源，但是这个资源的占用时间很短，当线程第一次抢占这个资源时，可能这个资源被占用，如果此时挂起这个线程，可能立刻就发现资源可用，然后又需要花费很长的时间重新抢占锁，时间代价就会非常的高。

　　 所以就有了乐观锁的概念，他的核心思路就是，每次不加锁而是假设没有冲突而去完成某项操作，如果因为冲突失败就重试，直到成功为止。在上面的例子中，某个线程可以不让出cpu,而是一直while循环，如果失败就重试，直到成功为止。所以，当数据争用不严重时，乐观锁效果更好。比如我们要说的AtomicInteger底层同步CAS就是一种乐观锁思想的应用。

　　CAS就是Compare and Swap的意思，比较并操作。很多的cpu直接支持CAS指令。CAS是项乐观锁技术，当多个线程尝试使用CAS同时更新同一个变量时，只有其中一个线程能更新变量的值，而其它线程都失败，失败的线程并不会被挂起，而是被告知这次竞争中失败，并可以再次尝试。CAS有3个操作数，内存值V，预期值A，要修改的新值B。当且仅当预期值A和内存值V相同时，将内存值V修改为B，否则什么都不做。

　　 在CAS操作中，会出现ABA问题。就是如果V的值先由A变成B，再由B变成A，那么仍然认为是发生了变化，并需要重新执行算法中的步骤。有简单的解决方案：不是更新某个引用的值，而是更新两个值，包括一个引用和一个版本号，即使这个值由A变为B，然后为变为A，版本号也是不同的。

• AtomicInteger分析

　　Atomic包下类的理解：

　　Atomic包是Java.util.concurrent下的另一个专门为线程安全设计的Java包，包含多个原子操作类。这个包里面提供了一组原子变量类。其基本的特性就是在多线程环境下，当有多个线程同时执行这些类的实例包含的方法时，具有排他性，即当某个线程进入方法，执行其中的指令时，不会被其他线程打断，而别的线程就像自旋锁一样，一直等到该方法执行完成，才由JVM从等待队列中选择一个另一个线程进入，这只是一种逻辑上的理解。实际上是借助硬件的相关指令来实现的，不会阻塞线程(或者说只是在硬件级别上阻塞了)。可以对基本数据、数组中的基本数据、对类中的基本数据进行操作。原子变量类相当于一种泛化的volatile变量，能够支持原子的和有条件的读-改-写操作。——  引自@chenzehe 的博客。

　　先来看一下AtomicInteger中getAndIncrement（）方法的实现：

1 public final int getAndIncrement() {
2         for (;;) {
3             int current = get();
4             int next = current + 1;
5             if (compareAndSet(current, next))
6                 return current;
7         }
8 }

　　这个方法的做法为先获取到当前的 value 属性值，然后将 value 加 1，赋值给一个局部的 next 变量，然而，这两步都是非线程安全的，但是内部有一个死循环，不断去做compareAndSet操作，直到成功为止，也就是修改的根本在compareAndSet方法里面，compareAndSet()方法的代码如下：

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

　　compareAndSet 传入的为执行方法时获取到的 value 属性值，next 为加 1 后的值， compareAndSet所做的为调用 Sun 的 UnSafe 的 compareAndSwapInt 方法来完成，此方法为 native 方法，compareAndSwapInt 基于的是CPU 的 CAS指令来实现的。所以基于 CAS 的操作可认为是无阻塞的，一个线程的失败或挂起不会引起其它线程也失败或挂起。并且由于 CAS 操作是 CPU 原语，所以性能比较好。

　　下面以具体的例子分析下AtomicInteger的实现：

　　计数器（Counter），采用Java里比较方便的锁机制synchronized关键字，初步的代码如下：

 1 public class Counter {
 2     private int value;  
 3       
 4     public synchronized int getValue() {  
 5         return value;  
 6     }  
 7   
 8     public synchronized int increment() {  
 9         return ++value;  
10     }  
11   
12     public synchronized int decrement() {  
13         return --value;  
14     }  
15 }

　　synchronized关键字是基于阻塞的锁机制，也就是说当一个线程拥有锁的时候，访问同一资源的其它线程需要等待，直到该线程释放锁，这也就我们前面所说的悲观锁。这里会有些问题：首先，如果被阻塞的线程优先级很高很重要怎么办？其次，如果获得锁的线程一直不释放锁怎么办？（这种情况是非常糟糕的）。还有一种情况，如果有大量的线程来竞争资源，那CPU将会花费大量的时间和资源来处理这些竞争（事实上CPU的主要工作并非这些），同时，还有可能出现一些例如死锁之类的情况，最后，其实锁机制是一种比较粗糙，粒度比较大的机制，相对于像计数器这样的需求有点儿过于笨重，因此，对于这种需求我们期待一种更合适、更高效的线程安全机制。

　　下面我们就以模拟CAS机制来实现Counter的例子：

 　　CAS类：

 1 public class SimpleCAS {
 2     private volatile int value;
 3     public synchronized int getValue(){
 4         return value;  
 5     } 
 6     public synchronized boolean comperaAndSwap(int expectedValue,int newValue){
 7         int oldValue = value;
 8         if(oldValue == expectedValue){
 9             value = newValue;
10             return true;
11         }else{
12             return false;
13         }
14     }
15 }

　　CASCounter类：

 1 public class CASCounter {
 2     private SimpleCAS cas;  
 3     public int getValue(){
 4         return cas.getValue();
 5     }
 6     public int increment(){
 7         int olevalue = cas.getValue();
 8         for (; ;) {
 9             if(cas.comperaAndSwap(olevalue, olevalue+1)){
10                 return cas.getValue();
11             }
12         }
13          
14     }
15 }

　　上面的模拟不是CSA的真正实现，其实我们在语言层面是没有做任何同步的操作的，大家也可以看到源码没有任何锁加在上面，可它为什么是线程安全的呢？这就是Atomic包下这些类的奥秘：语言层面不做处理，我们将其交给硬件—CPU和内存，利用CPU的多处理能力，实现硬件层面的阻塞，再加上volatile变量的特性即可实现基于原子操作的线程安全。所以说，CAS并不是无阻塞，只是阻塞并非在语言、线程方面，而是在硬件层面，所以无疑这样的操作会更快更高效！

　　总结一下，AtomicInteger基于冲突检测的乐观并发策略。 可以想象，这种乐观在线程数目非常多的情况下，失败的概率会指数型增加。