CAS 全称 Compare And Swap(比较与交换), 在不使用锁的情况下实现多线程之间的变量同步. 属于硬件同步原语, 处理器提供了基本内存操作的原子性保证. juc 包中的原子类就是通过 CAS 来实现了乐观锁.
CAS 算法涉及到三个操作数:
需要读写的内存值 V.
进行比较的旧值 A (期望操作前的值)
要写入的新值 B.
当且仅当 V 的值等于 A 时, CAS 通过原子方式用新值 B 来更新 V 的值 ("比较 + 更新" 整体是一个原子操作), 否则不会执行任何操作.
一般情况下,"更新" 是一个不断重试的过程.
JAVA 中的 sun.misc.Unsafe 类, 提供了
- compareAndSwapInt
- compareAndSwapLong
等方法实现 CAS.
示例
J.U.C 包内的原子操作封装类
看一下 AtomicInteger 的源码定义:
- public class AtomicInteger extends Number implements java.io.Serializable {
- private static final long serialVersionUID = 6214790243416807050L;
- // setup to use Unsafe.compareAndSwapInt for updates
- 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); }
- }
- private volatile int value;
各属性的作用:
unsafe: 获取并操作内存的数据
valueOffset: 存储 value 在 AtomicInteger 中的偏移
value: 存储 AtomicInteger 的 int 值, 该属性需要借助 volatile 关键字保证其在线程间的可见性
接着查看自增方法 incrementAndGet 的源码时, 发现自增函数底层调用的是 unsafe.getAndAddInt.
但是由于 JDK 本身只有 Unsafe.class, 只通过 class 文件中的参数名, 并不能很好的了解方法的作用, 所以我们通过 OpenJDK 8 来查看 Unsafe 的源码:
- // ------------------------- JDK 8 -------------------------
- // AtomicInteger 的自增方法
- public final int incrementAndGet() {
- return unsafe.getAndAddInt(this, valueOffset, 1) + 1;
- }
- // Unsafe.class
- public final int getAndAddInt(Object var1, long var2, int var4) {
- int var5;
- do {
- var5 = this.getIntVolatile(var1, var2);
- } while(!this.compareAndSwapInt(var1, var2, var5, var5 + var4));
- return var5;
- }
- // ------------------------- OpenJDK 8 -------------------------
- // Unsafe.java
- public final int getAndAddInt(Object o, long offset, int delta) {
- int v;
- do {
- v = getIntVolatile(o, offset);
- } while (!compareAndSwapInt(o, offset, v, v + delta));
- return v;
- }
由源码可看出, getAndAddInt() 循环获取给定对象 o 中的偏移量处的值 v, 然后判断内存值是否等于 v.
如果相等则将内存值设置为 v + delta
否则返回 false, 继续循环进行重试, 直到设置成功才能退出循环, 并且将旧值返回
整个 "比较 + 更新" 操作封装在 compareAndSwapInt() 中, 通过 JNI 使用 CPU 指令完成的, 属于原子操作, 可以保证多个线程都能够看到同一个变量的修改值.
JDK 通过 CPU 的 cmpxchg 指令, 去比较寄存器中的 A 和 内存中的值 V. 如果相等, 就把要写入的新值 B 存入内存中. 如果不相等, 就将内存值 V 赋值给寄存器中的值 A. 然后通过 Java 代码中的 while 循环再次调用 cmpxchg 指令进行重试, 直到设置成功为止.
CAS 的问题
循环 + CAS
自旋的实现让所有线程都处于高频运行, 争抢 CPU 执行时间的状态. CAS 操作如果长时间不成功, 会导致其一直自旋, 如果操作长时间不成功, 会带来很大的 CPU 资源消耗.
只能保证一个共享变量的原子操作
对一个共享变量执行操作时, CAS 能够保证原子操作, 但是对多个共享变量操作时, CAS 是无法保证操作的原子性的.
Java 从 1.5 开始 JDK 提供了 AtomicReference 类来保证引用对象之间的原子性, 可以把多个变量放在一个对象里来进行 CAS 操作.
ABA 问题 (无法体现数据的变动)
CAS 需要在操作值的时候检查内存值是否发生变化, 没有发生变化才会更新内存值. 但是如果内存值原来是 A, 后来变成了 B, 然后又变成了 A, 那么 CAS 进行检查时会发现值没有发生变化, 但是实际上是有变化的.
ABA 问题的解决思路就是在变量前面添加版本号, 每次变量更新的时候都把版本号加一, 这样变化过程就从 "A-B-A" 变成了 "1A-2B-3A".
JDK 从 1.5 开始提供了 AtomicStampedReference 类来解决 ABA 问题, 具体操作封装在 compareAndSet() 中.
compareAndSet() 首先检查当前引用和当前标志与预期引用和预期标志是否相等, 如果都相等, 则以原子方式将引用值和标志的值设置为给定的更新值.
不过目前来说这个类比较 "鸡肋", 大部分情况下 ABA 问题并不会影响程序并发的正确性, 如果需要解决 ABA 问题, 使用传统的互斥同步可能比原子类更加高效.
只能保证一个共享变量的原子操作. 对一个共享变量执行操作时, CAS 能够保证原子操作, 但是对多个共享变量操作时, CAS 是无法保证操作的原子性的.
Java 从 1.5 开始 JDK 提供了 AtomicReference 类来保证引用对象之间的原子性, 可以把多个变量放在一个对象里来进行 CAS 操作.
Java 8 更新
当然这都是由 Doug Lea 大佬亲自为 Java 操刀
更新器
DoubleAccumulator
LongAccumulator
计数器
DoubleAdder
LongAdder
计数器增强版, 高并发下性能更好
频繁更新但不太频繁读取的汇总统计信息时使用分成多个操作单元, 不同线程更新不同的单元
只有需要汇总的时候才计算所有单元的操作
T1 执行后, A 变成了 B
T3 又开始执行了, B 变成了 A
T2 开始执行, A 变成了 C
问题点:
经历的 A -> B -> A 过程, 但是对于线程 2, 无法感知数据发生了变化
来源: http://www.jianshu.com/p/e071623e86f9