CAS是Compare And Swap的缩写，翻译过来就是比较替换算法。
1. 什么叫做CAS
CAS机制就是使用了3个基本操作数：内存地址V的当前值，旧的预期值A，要修改的新值B。
当修改一个变量的时候，只有当变量的旧的预期值A和内存地址V当前值相同时，要修改的值B才会修改内存地址V的值
这个内存地址很关键呀。表明了它是操作系统层级的算法。Java内存模型中指出，Java内存模型规定了所有变量（不包括局部变量）存放在主存中，每条线程也有自己的工作内存。线程对变量的所有操作，均在工作内存中进行。
-
在内存地址V中，存储着值为10的变量。
原始内存地址 此时线程
001想把变量的值增加1，对于线程001来说，旧的预期值A=10，要修改的新值B=11。线程001在其自己的工作内存中将变量值修改成为了11。
- 在线程
001将数据flush到主内存之前，另一个线程002抢先一步，将线程002工作内存的值刷新到了主内存中。
---华丽分割线（CAS如何保证原子性呢）---
- 线程
001将工作内存的值刷新到主内存中时，首先进行旧预期值A和内存地址V进行比较，发现内存V上的不是A，提交失败。
线程001提交失败
---华丽的分割线（CAS算法结束）---
- 【自旋】（程序员设置死循环）线程
001没辙，重新获取内存地址V的当前值，并重新计算想要修改的值。对于线程1来说，A此时等于11，B=12。这个重新尝试的过程叫做自旋。
- 这一次比较幸运，没有其他线程改变
内存地址V的当前值，线程001进行比较，发现预期旧值A(11)和内存地址V当前值V(11)是相等的。于是进行替换。
从思想上来说，synchronize属于悲观锁，对外界的修改持悲观态度。具有独占性和排他性。而CAS属于乐观锁，乐观的认为程序中的并发情况不那么严重，所有让线程去不断的重试更新。
1.2 如何实现CAS算法？
CAS算法实现的关键就是“如何获取内存地址V的当前值”。
1. AtomicInteger的compareAndSet方法：
private static final Unsafe unsafe = Unsafe.getUnsafe();
//定义内存地址V
private static final long valueOffset;
//获取参数的内存地址V
static {
try {
valueOffset = unsafe.objectFieldOffset
(AtomicInteger.class.getDeclaredField("value"));
} catch (Exception ex) { throw new Error(ex); }
}
//保证内存地址V元素的可见性
private volatile int value;
//本质上获取的值均存入value中
public AtomicInteger(int initialValue) {
value = initialValue;
}
public AtomicInteger() {
}
public final int get() {
return value;
}
public final void set(int newValue) {
value = newValue;
}
//调用方法
public final boolean compareAndSet(int expect, int update) {
return unsafe.compareAndSwapInt(this, valueOffset, expect, update);
}
这个方法就是传入的expect（旧预期值）和内存地址valueOffset上当前值相比较。如果相等的话，那么就是要update来替换expect的值。
2. ReentrantLock.Sync的compareAndSetState方法：
实现CAS算法的关键是：
- 将（原子性）变量设置为volatile修饰，保证其可见性；
- 获取（原子性）变量的内存地址valueOffset。
- 进行CAS算比较。
private volatile int state;
private static final Unsafe unsafe = Unsafe.getUnsafe();
private static final long stateOffset;
static {
try {
stateOffset = unsafe.objectFieldOffset
(AbstractQueuedSynchronizer.class.getDeclaredField("state"));
} catch (Exception ex) { throw new Error(ex); }
}
protected final boolean compareAndSetState(int expect, int update) {
// See below for intrinsics setup to support this
return unsafe.compareAndSwapInt(this, stateOffset, expect, update);
}
即可实现CAS算法。
2. CAS的缺点
1. CPU开销大
在并发量比较高的情况下，如果大量线程反复重试更新某一个变量，却一直更新不成功，循环往复，会给CPU带来很大的压力。
2. 不能保证代码块的原子性
CAS机制所保证的只是一个变量的原子性操作，而不能保证整个代码块的原子性。如果需要保证3个变量共同进行原子性的更新，就不得不使用synchronize了。
3. ABA问题
这是CAS机制最大的问题所在。
下面来介绍CAS的底层实现：
- JAVA的CAS底层实现。
- CAS的ABA问题和解决方法。
public final int incrementAndGet() {
for (;;) {
int current = get();
int next = current + 1;
if (compareAndSet(current, next))
return next;
}
}
private volatile int value;
public final int get() {
return value;
}
这是一个死循环，也就是CAS自旋。循环体做了3件事：
- 获取当前值
【内存地址V的当前值，其实也就是旧预期值A的值】； - 当前值+1，计算出目标值
【要替换的值B】； - 进行CAS操作，如果成功则跳出循环，如果失败则重复上述步骤。
我们可以看到get()方法，这个方法的作用就是获取变量的当前值。
如何保证获取到的当前值是内存中的最新值呢？
小胖：可以使用关键字volatile来保证。
我们接着看下compareAndSet(int expect，int update)的实现。
public final boolean compareAndSet(int expect,
int update)如果当前值为 ==为预期值，则将该值原子设置为给定的更新值。
参数
expect - 预期值
update - 新价值
结果
true如果成功。 False return表示实际值不等于预期值。
private static final Unsafe unsafe = Unsafe.getUnsafe();
private static final long valueOffset;
static {
try {
valueOffset = unsafe.objectFieldOffset
(AtomicInteger.class.getDeclaredField("value"));
} catch (Exception ex) { throw new Error(ex); }
}
public final boolean compareAndSet(int expect, int update) {
return unsafe.compareAndSwapInt(this, valueOffset, expect, update);
}
compareAndSet方法很简单，只有一行代码，这里涉及到了两个重要的对象：
unsafe和valueOffset。
什么是unsafe呢？java语言不像C，C++那样可以直接访问底层操作系统，但是JVM为我们提供了一个后门，这就是unsafe。unsafe为我们提供硬件级别的原子操作。
至于valueOffset对象，是通过unsafe.ObjectFieldOffset方法得到，所代表的就是AtomicInteger对象value成员变量在内存中的偏移量。我们可以简单的把valueOffset理解为value变量的内存地址。
上面说过，CAS机制使用了3个基本操作数：内存地址V的当前值，旧的预期值A，要修改的新值B。
而unsafe的compareAndSwapInt方法的参数包括了这三个基本元素：valueOffset参数代表了V，expect参数代表A，update参数代表B。
正是unsafe的compareAndSwapInt方法保证了Compare
和Swap操作之间的原子性操作。
那什么是ABA问题呢？
假设有一个提款机的例子，假设有一个遵循CAS原理的提款机，小灰有100元存款，要用这个提款机来提款50元。
但是提款机硬件有一些问题，小灰的提款请求被同时提交了两次，开启了两个线程，两个线程都是获取当前值100元，要更新成50元。
线程1首先执行成功，把余额从100改成了50，线程2因为某些原因阻塞。这时，小灰的妈妈刚好给小灰汇款50元。
线程2仍然处于阻塞状态，线程3执行成功，把余额从50改成了100。
线程2恢复运行，由于阻塞之前获取了“当前值100”，并经过compare检测，此时存款实际值也是100，所有会成功的把变量值100更新成50元。
原本线程2应当提交失败的，小灰的正确余额应该保持100元，结果由于ABA问题提交成功了。
如何解决这个问题呢？
加个版本号就可以了。真正要做到严谨的CAS机制，我们在compare阶段不仅要比较1期望值A和地址V中的实际值，还要比较变量的版本号是否一致。
在Java中，AtomicStampedReference类就实现了用版本号做额外的CAS比较。
public static void main(String[] args) {
String oldStr = "aaa";
String newStr = "bbb";
//构造方法，传入引用和戳
AtomicStampedReference<String> reference =
new AtomicStampedReference<>(oldStr, 1);
//旧预期值，要替换的新值，旧时间戳，新时间戳
//如果A=V，那么将b更新到V，并更新时间戳。
reference.compareAndSet(oldStr, newStr, reference.getStamp(),
reference.getStamp() + 1);
System.out.println("内存V中的当前值：" + reference.getReference()
+ ",内存V中当前戳" + reference.getStamp());
//更新内存V中的时间戳
boolean result = reference.attemptStamp(newStr, reference.getStamp() + 1);
System.out.println("是否更新成功："+result);
System.out.println("内存V中的当前戳"+reference.getStamp());
}
}
运行结果：
内存V中的当前值：bbb,内存V中当前戳2
是否更新成功：true
内存V中的当前戳3
