Android 并发之CAS（原子操作）简单介绍（五）

Android 线程简单分析（一）
Android 并发之synchronized锁住的是代码还是对象（二）
Android 并发之CountDownLatch、CyclicBarrier的简单应用（三）
Android 并发HashMap和ConcurrentHashMap的简单应用（四）(待发布)
Android 并发之Lock、ReadWriteLock和Condition的简单应用(五)
Android 并发之CAS（原子操作）简单介绍（六）
Android 并发Kotlin协程的重要性（七）(待发布)
Android 并发之AsyncTask原理分析（八）(待发布)
Android 并发之Handler、Looper、MessageQueue和ThreadLocal消息机制原理分析（九）
Android 并发之HandlerThread和IntentService原理分析（十）

Java中的并发，锁相关的的介绍，一共有几种锁？

平锁/非公平锁
可重入锁
互斥锁/读写锁
独享锁/共享锁
分段锁
偏向锁/轻量级锁/重量级锁

公平锁、非公平锁

1、公平锁是指多线程按照申请锁的顺序来获取锁；
2、非公平锁是指多个线程获取锁的顺序不是按照申请锁的顺序，有可能后申请的优先于先申请的线程获取锁，有可能造成优先级反转或者饥饿现象，饥饿现象指优先级高的线程一直抢占优先级低线程的资源，导致低优先级线程无法得到执行，这就是饥饿，与死锁不同的是饥饿在以后一段时间内还是能够得到执行的。
3、对于ReentranLock而言，通过构造方法指定是否是公平锁，默认是非公平锁。非公平锁的有点在于吞吐量比公平锁大。Synchronized也是非公平锁，它不像ReentranLock是通过AQS实现线程调度，所以Synchronized并没有任何办法去变成公平锁。

可重入锁

1、可重入锁又称递归锁，是指在同一个线程在外层方法获取锁的时候，在进入内层方法会自动获取锁，前提是同一个锁对象，举个栗子？

public synchronized void entranslock1(){    Log.e("tag", "来了老弟A");    entranslock2();}public synchronized void entranslock2() {    Log.e("tag", "来了老弟B");}

对于Java ReentrantLock而言, 他的名字就可以看出是一个可重入锁，其名字是Re entrant Lock重新进入锁。
对于Synchronized而言,也是一个可重入锁。可重入锁的一个好处是可一定程度避免死锁。如果不是可重入锁的话，entranslock2可能不会被当前线程执行，可能造成死锁。

独享锁/共享锁

独享锁是指该锁一次只能被一个线程所持有。
共享锁是指该锁可被多个线程所持有。

ReentrantLock是独享锁。但是对于Lock的另一个实现类ReadWriteLock，其读锁是共享锁，其写锁是独享锁。
读锁的共享锁可保证并发读是非常高效的，读写，写读，写写的过程是互斥的。
独享锁与共享锁也是通过AQS来实现的，通过实现不同的方法，来实现独享或者共享。Synchronized也是独享锁。

互斥锁/读写锁

上面讲的独享锁/共享锁就是一种广义的说法，互斥锁/读写锁就是具体的实现。

互斥锁在Java中的具体实现就是ReentrantLock
读写锁在Java中的具体实现就是ReadWriteLock

乐观锁/悲观锁

乐观锁与悲观锁不是指具体的什么类型的锁，而是指看待并发同步的角度。

悲观锁认为对于同一个数据的并发操作，一定是会发生修改的，哪怕没有修改，也会认为修改。因此对于同一个数据的并发操作，悲观锁采取加锁的形式。悲观的认为，不加锁的并发操作一定会出问题。
乐观锁则认为对于同一个数据的并发操作，是不会发生修改的。在更新数据的时候，会采用尝试更新，不断重新的方式更新数据。乐观的认为，不加锁的并发操作是没有事情的。

从上面的描述我们可以看出，悲观锁适合写操作非常多的场景，乐观锁适合读操作非常多的场景，不加锁会带来大量的性能提升。
悲观锁在Java中的使用，就是利用各种锁。
乐观锁在Java中的使用，是无锁编程，常常采用的是CAS算法，典型的例子就是原子类，通过CAS自旋实现原子操作的更新。

分段锁

分段锁其实是一种锁的设计，并不是具体的一种锁，如ConcurrentHashMap其并发的实现就是通过分段锁的形式来实现高效的并发操作。

我们以ConcurrentHashMap来说一下分段锁的含义以及设计思想，ConcurrentHashMap中的分段锁称为Segment，它即类似于HashMap的结构，即内部拥有一个Entry数组，数组中的每个元素又是一个链表；同时又是一个ReentrantLock（Segment继承了ReentrantLock)。
当需要put元素的时候，并不是对整个hashmap进行加锁，而是先通过hashcode来知道他要放在那一个分段中，然后对这个分段进行加锁，所以当多线程put的时候，只要不是放在一个分段中，就实现了真正的并行的插。
但是，在resize的时候，获取hashmap全局信息的时候，就需要获取所有的分段锁才能resize。
分段锁的设计目的是细化锁的粒度，当操作不需要更新整个数组的时候，就仅仅针对数组中的一项进行加锁操作。

偏向锁/轻量级锁/重量级锁

这三种锁是指锁的状态，并且是针对Synchronized。在Java 5通过引入锁升级的机制来实现高效Synchronized。这三种锁的状态是通过对象监视器在对象头中的字段来表明的。

偏向锁是指一段同步代码一直被一个线程所访问，那么该线程会自动获取锁。降低获取锁的代价。
轻量级锁是指当锁是偏向锁的时候，被另一个线程所访问，偏向锁就会升级为轻量级锁，其他线程会通过自旋的形式尝试获取锁，不会阻塞，提高性能。
重量级锁是指当锁为轻量级锁的时候，另一个线程虽然是自旋，但自旋不会一直持续下去，当自旋一定次数的时候，还没有获取到锁，就会进入阻塞，该锁膨胀为重量级锁。重量级锁会让其他申请的线程进入阻塞，性能降低。

自旋锁

在Java中，自旋锁是指尝试获取锁的线程不会立即阻塞，而是采用循环的方式去尝试获取锁，这样的好处是减少线程上下文切换的消耗，缺点是循环会消耗CPU。

什么是 CAS 机制？

先看一段代码：

for (int i = 0; i < 2; i++) {        new Thread() {            @Override            public void run() {                Log.e("tag", "" + Thread.currentThread().getName());                try {                    Thread.sleep(100);                } catch (InterruptedException e) {                    e.printStackTrace();                }                for (int i = 0; i < 10; i++) {                    atomicVar++;//每个线程中atomicVar 加1                    Log.e("tag", "" + Thread.currentThread().getName() + "  : " + atomicVar);                }            }        }.start();    }    try {        Thread.sleep(5000);        Log.e("tag", "" + atomicVar);    } catch (InterruptedException e) {        e.printStackTrace();    }

启动两个线程，让每个线程中对atomicVar循环累加10次，由于线程安全导致结果atomicVar<20。

再聊看看加了synchronized的：

 for (int i = 0; i < 2; i++) {        new Thread() {            @Override            public void run() {                Log.e("tag", "" + Thread.currentThread().getName());                try {                    Thread.sleep(100);                } catch (InterruptedException e) {                    e.printStackTrace();                }                for (int i = 0; i < 10; i++) {                    synchronized (MainActivity.this) {//减小锁的粒度                        atomicVar++;//每个线程中atomicVar 加1                        Log.e("tag", "" + Thread.currentThread().getName() + "  : " + atomicVar);                    }                }            }        }.start();    }    try {        Thread.sleep(5000);        Log.e("tag", "" + atomicVar);    } catch (InterruptedException e) {        e.printStackTrace();    }

这次由于加了synchronized之后，atomicVar自增的操作变成了原子性操作，所以最终的输出一定是atomicVar =20，最终保证线程安全。

虽然synchronized保证了线程安全，但是在某些场景下并不是最优解。Synchronized会让没有得到锁资源的线程进入阻塞（block）状态，进入锁池，而后在争夺到锁资源后恢复为可运行（runnable）状态等待CPU再次调度，这个过程中涉及到线程的调度代价比较高。尽管Java1.6为Synchronized做了优化，增加了从偏向锁到轻量级锁再到重量级锁的过度，但是在最终转变为重量级锁之后，性能仍然较低。

上面说了在某些场景下并不是最优解，所以有没有最优解？那就是原子操作，原子操作类指的是java.util.concurrent.atomic包下，一系列以Atomic开头的包装类。例如AtomicBoolean，AtomicInteger，AtomicLong,AtomicXxx。它们分别用于Boolean，Integer，Long类型的原子性操作。

举个栗子

    for (int i = 0; i < 2; i++) {        new Thread() {            @Override            public void run() {                Log.e("tag", "" + Thread.currentThread().getName());                try {                    Thread.sleep(100);                } catch (InterruptedException e) {                    e.printStackTrace();                }                for (int i = 0; i < 10; i++) {                    atomicVar.incrementAndGet();//每个线程中atomicVar 加1                    Log.e("tag", "" + Thread.currentThread().getName() + "  : " + atomicVar);                }            }        }.start();    }    try {        Thread.sleep(5000);        Log.e("tag", "" + atomicVar.get());    } catch (InterruptedException e) {        e.printStackTrace();    }

使用AtomicInteger之后，最终的输出结果同样可以保证是20。并且在某些情况下，代码的性能会比Synchronized更好。

那到底什么是CAS？

CAS是英文单词Compare And Swap的缩写，比较并替换。

CAS机制当中使用了3个基本操作数：内存地址V，旧的预期值V1，要修改的新值V2。更新一个变量的时候，只有当变量的预期值V1和内存地址V当中的实际值相同时，才会将内存地址V对应的值修改为V2。

cas.png

Synchronized属于悲观锁，悲观地认为程序中的并发情况严重，所以严防死守。CAS属于乐观锁，乐观地认为程序中的并发情况不那么严重，所以让线程不断去尝试更新。

那是不是线程安全都是用CAS不用Synchronized？

其实这两种机制没有绝对的好与坏，关键得看场景，在并发量高的情况下，反而使用使用Synchronize更合适。

那些地方使用CAS？

比如JDK中的Atomic以及Lock的底层实现也是用CAS机制。

CAS的缺点：

CPU开销较大
在并发量比较高的情况下，如果许多线程反复尝试更新某一个变量，却又一直更新不成功，循环往复，会给CPU带来很大的压力。
不能保证代码块的原子性
CAS机制所保证的只是一个变量的原子性操作，而不能保证整个代码块的原子性。比如需要保证3个变量共同进行原子性的更新，就不得不使用Synchronized了。

接下来看看AtomicInteger的源码：

public final int incrementAndGet() {    return U.getAndAddInt(this, offset, 1) + 1;}

incrementAndGet方法实际上调用了Unsafe中的getAndAddInt方法

看看getAndAddInt方法如何实现的：
对象，偏移量，期望值，修改值

 public final int getAndAddInt(Object obj, long offset, int increment) {    int expected;    do {        //获取对象中offset偏移地址对应的整型field的值expected，该变量使用了Volatile，可见性，也就是对其他线程可见        expected= this.getIntVolatile(obj, offset);      //如果对象偏移量上的值（x）= 期待值（expected），更新为expected+increment    } while(!this.compareAndSwapInt(obj, offset, expected, expected+increment));    return expected;}

getIntVolatile(Object o, long offset)方法

该方法获取对象中offset偏移地址对应的整型field的值,支持volatile getBooleanVolatile等等
```
public native Object getIntVolatile(Object o, long offset); 
```

compareAndSwapInt(Object o, long offset, int expected, int x)方法

CAS操作，如果对象偏移量上的值（x）= 期待值（expected），更新为x,返回true.否则false.类似的有compareAndSwapInt,compareAndSwapLong,compareAndSwapBoolean,compareAndSwapChar等等。
```
  //对象，偏移量，期望值，修改值  public final native boolean compareAndSwapInt(Object o, long offset,  int expected, int x/*expected+increment*/);    
```

在getAndAddInt方法中是一个无限循环，也就是CAS的自旋。循环体当中做了三件事：
1.获取对象中offset偏移地址对应的整型field的值，是获取的是当前变量在内存中的值，并使用volatile关键字保证变量在内存中。
2.在compareAndSwapInt方法中，做CAS操作，如果对象偏移量上的值（offsetValue主存中的）= 期待值（expected即该线程私有内存中旧的值），更新为expected+increment,返回true.否则false。
3.当compareAndSwapInt方法返回true，incrementAndGet做自增+1，如果失败则重复上述步骤。

什么是ABA问题？

加入有三个线程分别为线程1、线程2和线程3，主存中的变量值为V = 100，操作数Expt = 50，此时线程1想要把V更新为50（当前值减Expt ），线程2想要把V更新为50（当前值减Expt ），线程3想要把V更新为 100,（即加Expt ）。
1、线程1，获取当前值V=100，成功更新为50，已完成；
2、线程2，获取当前值v=100，期望更新为更新为50；
3、线程3，获取当前值50，成功更新100；
4、最后线程2恢复运行状态，由于阻塞之前的为100，那么这时候它比较成功，并把V值更新为50；

这个例子并不直观，看看提款机的栗子：
1、线程1（取款），获取当前值余额V=100，成功更新为50，已完成；
2、线程2（取款），获取当前值v=100，期望更新为更新为50，block状态；
3、线程3（存款）获取当前值50，成功更新100；

最后线程2恢复运行状态，由于阻塞之前的为100，那么这时候它比较成功，并把余额更新为50，明显结果本该余额是100的，结果是50，本该线程2的操作应该失败的，由于ABA的问题线程2的操作成功。

总结

Java语言CAS底层利用unsafe提供原子操作方法。
当一个值从A变为B，又更新回A，普通的CAS机制会误判通过检测。解决办法就是利用版本号可以有效的解决ABA问题，Java中就提供AtomicStampedReference类实现版本号比较的CAS机制。