CAS算法解析

Posted on | In
Words count in article: 817 | Reading time ≈ 3

CAS算法

CAS（比较与交换，Compare and swap） 是一种有名的无锁算法。无锁编程，即不使用锁的情况下实现多线程之间的变量同步，也就是在没有线程被阻塞的情况下实现变量的同步，所以也叫非阻塞同步（Non-blocking Synchronization）。实现非阻塞同步的方案称为“无锁编程算法”（ Non-blocking algorithm）。
CAS, CPU指令，在大多数处理器架构，包括IA32、Space中采用的都是CAS指令，CAS的语义是“我认为V的值应该为A，如果是，那么将V的值更新为B，否则不修改并告诉V的值实际为多少”，CAS是项 乐观锁 技术，当多个线程尝试使用CAS同时更新同一个变量时，只有其中一个线程能更新变量的值，而其它线程都失败，失败的线程并不会被挂起，而是被告知这次竞争中失败，并可以再次尝试。CAS有3个操作数，内存值V，旧的预期值A，要修改的新值B。当且仅当预期值A和内存值V相同时，将内存值V修改为B，否则什么都不做。

示例

java.util.concurrent.atomic中的AtomicXXX，都使用了这些底层的JVM支持为数字类型的引用类型提供一种高效的CAS操作，而在java.util.concurrent中的大多数类在实现时都直接或间接的使用了这些原子变量类，这些原子变量都调用了 sun.misc.Unsafe 类库里面的 CAS算法，用CPU指令来实现无锁自增

下面就以AtomicInteger类为例，看看它是如何使用CAS算法来提升效率的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/**
     * Atomically increments by one the current value.
     *
     * @return the previous value
     */
    public final int getAndIncrement() {
        return unsafe.getAndAddInt(this, valueOffset, 1);
    }

/**
     * Atomically decrements by one the current value.
     *
     * @return the previous value
     */
    public final int getAndDecrement() {
        return unsafe.getAndAddInt(this, valueOffset, -1);
    }

摘取了两个AtomicInter类中自增1和自减1的方法来做说明，它们都是调用了UnSave封装的CAS操作来实现的。

UnSave类相关信息可参见文章UnSave类解析

CAS算法存在的问题

CAS算法存在一个ABA问题。

假设有如下操作：

  1. 假设有两个线程T1，T2正在操作一个字符C，此时C的值为A。
  2. 在某一时刻，T1和T2都要修改C的值，于是，它们将C当前值A拷贝一份过去。
  3. 由于线程调度，T2将C的值修改为B，
  4. 由于线程调度，T2又将C的值修改回A。
  5. T1准备修改C的值。它把C的当前值和自己保存的值进行比较，发现一致，认为C的值从它取值之后就没有发生过变更
  6. T1修改C的值为D，结束。

对T1来说，C的值就从来没有变过，但实际上C的值已经变化了两次，只是变回了原值而已。

在Java 1.5开始，atomic包中引入了一个类AtomicStampedReference来解决ABA问题。这个类中的compareAndSet方法不仅会检查当前引用是否等于预期引用，还会检查当前的stamp（版本号、时间戳）是否和预期的相等。只要有一个不一致，就认为值已经发生过变更。CAS操作就做失败处理。

0%