大白话之CAS

概述

大家看下这张J.U.C包的实现示意图。

从整体来看：CAS作为一个基础类是并发包其他组件实现的基础。发包内的锁的实现、阻塞队列、同步器、线程池无一例外的使用到了它。可见它在并发编程的地位!

今天我们来一起聊一聊CAS这个话题，深入到操作系统层面，把它原理聊清楚。

背景

近年来，在并发算法领域的大多数研究都侧重于非阻塞算法，这种算法用底层的原子机器指令(例如：比较并交换、测试并设置、获取并递增）实现各种互斥，代替锁来确保数据在并发访问中的一致性！

非阻塞算法：

如果在某种算法中，一个线程的失败或挂起不会导致其他线程也失败或挂起，那么这种算法称为非阻塞算法。

如果在某个步骤中都存在某个线程能够执行下去，那么也被称作无锁算法-(Lock-Free)

什么是CAS

CAS 是一种系统原语，原语的执行必须是连续的，在执行过程中不允许被中断！

CAS（V,E,N）

1）V：要更新的变量

2）E 预期值

3）N新值

4）如果V等于E则更新成N，否则什么都不做

有什么用

·极大的减少调度开销。

·不存在死锁、其他活跃性问题

具体实现

操作系统

在针对多处理器操作而设计的机器指令,用于管理对共享数据的并发访问。

早期处理器中支持的机器指令： 1）原子的测试并设置(Test-And-Set) 2）获取并递增 3）交换(Swap)

操作系统和JVM使用这些指令来实现锁和并发的数据结构。

竞争失败的锁不会被挂起，而是被告知竞争失败，可以再次尝试。它可以决定是否重新尝试，或执行一些恢复操作，也或者不执行任何操作；大大减少了与锁相关活跃性风险！！！

在大多数处理器架构中(包括IA32和Sparc)中采用的方法是比较并交换来实现CAS。

compare-and-Swap（比较并交换）是一种原子的读-改-写指令。

Java内部的实现

java并发包内的atomic下的相关类是实现了CAS的。

protected final boolean compareAndSetState(int expect, int update) {
// See below for intrinsics setup to //support this
return unsafe.compareAndSwapInt(this, stateOffset,expect, update);

}

当且仅当V符合旧的预期值A时，处理器用新值替换B更新V；否则不执行更新，重试！

JDK1.5之后该操作由sun.misc.Unsafe里的compareAndSwapInt,compareAndSwapLong等几个方法包装提供，虚拟机内部对这些方法做了特殊处理，即使编译出来的结果就是一条平台相关的处理器CAS指令，没有方法调用的过程，或者可以认为是无条件内联进去了。

三大问题

ABA问题

ABA问题主要出现在检查的标准不够严谨，像这个思路A->B->A 如果中间有变过，CAS压根不知道。 解决方案是引出了一个类AtomicStampedReference类；通过检查当前引用是否等于预期引用,当前标志是否等于预期标志来解决。

循环时间开销大

自旋CAS如果长时间不成功，会造成极大的性能开销

只能保证一个共享的原子操作