并发策略-CAS算法
对于并发控制而言，我们平时用的锁（synchronized，lock）是一种悲观的策略。它总是假设每一次临界区操作会产生冲突，因此，必须对每次操作都小心翼翼。如果多个线程同时访问临界区资源，就宁可牺牲性能让线程进行等待，所以锁会阻塞线程执行。
与之相对的有一种乐观的策略，它会假设对资源的访问是没有冲突的。既然没有冲突也就无需等待了，所有的线程都在不停顿的状态下持续执行。那如果遇到问题了无锁的策略使用一种叫做比较交换（cas compare and swap）来鉴别线程冲突，一旦检测到冲突产生，就重试当前操作直到没有冲突。cas算法是非阻塞的，它对死锁问题天生免疫，而且它比基于锁的方式拥有更优越的性能。
cas算法的过程是这样：它包含三个参数 cas（v,e,n）。v表示要更新的变量，e表示预期的值，n表示新值。仅当v值等于e值时，才会将v的值设置成n，否则什么都不做。最后cas返回当前v的值。cas算法需要你额外给出一个期望值，也就是你认为现在变量应该是什么样子，如果变量不是你想象的那样，那说明已经被别人修改过。你就重新读取，再次尝试修改即可。
jdk并发包有一个atomic包，里面实现了一些直接使用cas操作的线程安全的类型。其中最常用的一个类应该就是atomicinteger。我们以此为例来研究一下没有锁的情况下如何做到线程安全。
private volatile int value;
这是atomicinteger类的核心字段，代表当前实际取值，借助volatile保证线程间数据的可见性。
获取内部数据的方法：
public final int get() {
return value;
}
我们从源码的实现看看incrementandget()的内部实现
public final int incrementandget() {
for (;;) {
int current = get();
int next = current + 1;
if (compareandset(current, next))
return next;
}
}
代码第二行使用了一个死循环，原因是：
cas的操作未必都是成功的，因此对于不成功的情况，我们就需要进行不断的尝试。
第三行取得当前值，接着+1得到新值next。
这里我们使用cas必需的两个参数：期望值以及新值。
使用compareandset()将新值next写入。成功的条件是在写入的时刻当前的值应该要等于刚刚取到的current。如果不是这样则说明atomicinteger的值在第3行到第5行之间被其他线程修改过了。当前看到的状态是一个过期的状态，因此返回失败，需要进行下一次重试，直到成功为止。
public final boolean compareandset(int expect, int update) {
return unsafe.compareandswapint(this, valueoffset, expect, update);
}
整体的过程就是这样子，利用cpu的cas指令，同时借助jni来完成java的非阻塞算法。其它原子操作都是利用类似的特性完成的。大概的逻辑应该是这样：
if (this == expect) {
this = update return true;
} else {
return false;
}
cas虽然能高效的解决原子问题，但是cas也会带来1个经典问题即aba问题：
因为cas需要在操作值的时候检查下值有没有发生变化，如果没有发生变化则更新，但是如果一个值原来是a，变成了b，又变成了a，那么使用cas进行检查时会发现它的值没有发生变化，但是实际上却变化了。
aba问题的解决思路就是使用版本号。在变量前面追加上版本号，每次变量更新的时候把版本号加一，那么a－b－a 就会变成1a-2b－3a。
从java1.5开始jdk的atomic包里提供了一个类atomicstampedreference来解决aba问题。这个类在内部不仅维护了对象值，还维护了一个时间戳（可以是任意的一个整数来表示状态值）。当设置对象值时，对象值和状态值都必须满足期望值才会写入成功。因此即使对象被反复读写，写会原值，只要状态值发生变化，就能防止不恰当的写入。
/**
* @param expectedreference 期望值
* @param newreference 写入新值
* @param expectedstamp 期望状态值
* @param newstamp 新状态值
* @return true if successful
*/
public boolean compareandset(v expectedreference,
v newreference,
int expectedstamp,
int newstamp) {
pair<v> current = pair;
return expectedreference == current.reference &&
expectedstamp == current.stamp &&
((newreference == current.reference &&
newstamp == current.stamp) ||
caspair(current, pair.of(newreference, newstamp)));
}
个人公众号：java日知录 ,