CAS操作与ABA问题

发表于： 2020-04-02 分类于：计算机基础科学

字数： 2269 阅读：≈ 5分钟浏览：评论：

我们在使用锁时，线程获取锁是一种悲观锁策略，即假设每一次执行临界区代码都会产生冲突，所以当前线程获取到锁的时候同时也会阻塞其他线程获取该锁。而CAS操作(又称为无锁操作)是一种乐观锁策略，它假设所有线程访问共享资源的时候不会出现冲突，既然不会出现冲突自然而然就不会阻塞其他线程的操作。因此，线程就不会出现阻塞停顿的状态。那么，如果出现冲突了怎么办？无锁操作是使用CAS(compare and swap)又叫做比较交换来鉴别线程是否出现冲突，出现冲突就重试当前操作直到没有冲突为止。

CAS的操作过程

CAS即Compare and Swap，CAS比较交换的过程可以通俗的理解为CAS(V、A、B)，包含三个值分别为: V内存中实际值、 A预期原值(旧值) 、B更新的新值。当V和A相同时，也就是说旧值和内存中实际的值相同表明该值没有被其他线程更改过，即该旧值A就是目前来说最新的值了，自然而然可以将新值B赋值给V。反之，V和A不相同，表明该值已经被其他线程改过了则该旧值A不是最新版本的值了，所以不能将新值B赋给V，返回V即可。当多个线程使用CAS操作一个变量时，只有一个线程会成功，并成功更新，其余会失败。失败的线程会重新尝试，当然也可以选择挂起线程。

CAS的实现需要硬件指令集的支撑，在JDK1.5后虚拟机才可以使用处理器提供的CMPXCHG指令实现。CAS支持原子更新操作，适用于计数器，序列发生器等场景（序列发生器就是用来给变量自增的工具），CAS属于乐观锁机制，号称lock-free（其实只是上层感知无锁，底层还是有加锁操作的）。CAS操作失败时由开发者决定是继续尝试还是执行别的操作。

基于CAS实现的工具

java.util.concurrent包都中的实现类都是基于volatile和CAS来实现的。尤其java.util.concurrent.atomic包下的原子类。就拿AtomicInteger来说：

可以看到 AtomicInteger 底层用的是volatile的变量和CAS来进行更改数据的。volatile保证可见性，多线程并发时，一个线程修改数据，可以保证其它线程立马看到修改后的值，CAS则保证数据更新的原子性。

CAS多数情况下对开发者来说是透明的。J.U.C的atomic包提供了常用的原子性数据类型以及引用、数组等相关原子类型和更新操作工具，是很多线程安全程序的首选。Unsafe类虽提供CAS服务，但因能够操纵任意内存地址读写而有隐患。JDK9以后，可以使用Variable Handle API来替代Unsafe

模拟实现CAS

CAS需要硬件层面的支持，所以模拟还是用synchronized来实现一下：

 1public class TestImplementCAS {
 2    public static void main(String[] args) {
 3        final CompareAndSwap cas = new CompareAndSwap();
 4        
 5        for (int i = 0; i < 10; i++) {
 6            new Thread(()->{
 7                int expectedValue = cas.get();
 8                boolean b = cas.compareAndSet(expectedValue, (int)(Math.random() * 101));
 9                System.out.println(b);
10            }).start();
11        }
12    }
13}
14
15class CompareAndSwap{
16    private int value;
17
18    //获取内存值
19    public synchronized int get(){
20        return value;
21    }
22
23    //比较
24    public synchronized int compareAndSwap(int expectedValue, int newValue){
25        int oldValue = value;
26
27        if(oldValue == expectedValue){
28            this.value = newValue;
29        }
30
31        return oldValue;
32    }
33
34    //设置
35    public synchronized boolean compareAndSet(int expectedValue, int newValue){
36        return expectedValue == compareAndSwap(expectedValue, newValue);
37    }
38}

CAS的缺点

1、ABA问题

因为CAS会检查旧值有没有变化，这里存在这样一个有意思的问题。比如一个旧值A变为了成B，然后再变成A，刚好在做CAS时检查发现旧值并没有变化依然为A，但是实际上的确发生了变化。解决方案可以沿袭数据库中常用的乐观锁方式，添加一个版本号可以解决。在JDK1.5后的atomic包中提供了AtomicStampedReference来解决ABA问题，解决思路就是这样的。如果需要解决ABA问题，互斥与同步可能比CAS更高效。

2、自旋会浪费大量的处理器资源与线程阻塞相比，自旋会浪费大量的处理器资源。这是因为当前线程仍处于运行状况，只不过跑的是无用指令。它期望在运行无用指令的过程中，锁能够被释放出来。JVM给出的方案是自适应自旋，根据以往自旋等待时能否获取锁，来动态调整自旋的时间。

3、公平性问题自旋状态还带来另外一个副作用，不公平的锁机制。处于阻塞状态的线程，无法立刻竞争被释放的锁。然而，处于自旋状态的线程，则很有可能优先获得这把锁。内建锁无法实现公平机制，而lock体系可以实现公平锁。

解决ABA问题

在JDK1.5后的atomic包中提供了AtomicStampedReference来解决ABA问题，它通过包装[E，Integer]的元组来对对象标记版本stamp，从而避免ABA问题。在了解AtomicStampedReference之前我们可以先分析一下AtomicReference。

 1import java.util.concurrent.atomic.AtomicReference;
 2
 3public class AtomicReferenceDemo {
 4    public static void main(String[] args) {
 5        AtomicReference<String> atomicReference = new AtomicReference<>();
 6        atomicReference.set("AAA");
 7        
 8        //CAS操作更新
 9        boolean result = atomicReference.compareAndSet("AAA", "BBB");
10        System.out.println(result + " " + atomicReference.get());
11        
12        //CAS操作更新
13        result = atomicReference.compareAndSet("AAA", "CCC");
14        System.out.println(result + " " + atomicReference.get());
15    }
16}

AtomicReference的成员变量

1//Unsafe类提供CAS操作
2private static final Unsafe unsafe = Unsafe.getUnsafe();
3
4//value变量的偏移地址，这个偏移地址在static块里初始化
5private static final long valueOffset;
6
7//实际传入需要原子操作的那个类实例
8private volatile V value;

compareAndSet方法是基于Unsafe提供的compareAndSwapObject方法，这里的compareAndSet方法即CAS操作本身是原子的，但是在某些场景下会出现异常场景，也就是ABA问题。我们使用AtomicStampedReference来解决这个问题，下面是AtomicStampedReference的关键结构：

 1public class AtomicStampedReference<V> {
 2    private static class Pair<T> {
 3        final T reference;  //维护对象引用
 4        final int stamp;  //用于标志版本
 5        
 6        private Pair(T reference, int stamp) {
 7            this.reference = reference;
 8            this.stamp = stamp;
 9        }
10        
11        static <T> Pair<T> of(T reference, int stamp) {
12            return new Pair<T>(reference, stamp);
13        }
14    }
15    
16    private volatile Pair<V> pair;
17    ...
18}