Java并发编程学习十一:CAS

一、CAS简介

CAS,全称是"Compare-And-Swap",中文翻译"比较并交换",是一种思想、算法。

在多线程并发的场景下,为了保证线程安全,可以采用同步互斥锁,典型的就是synchronized关键字。CAS则提供了另一种思路,它并不采用同步的方法,实现了无锁的线程安全。

CAS有三个操作数:内存值 V、预期值 A、要修改的值 B。CAS 最核心的思路就是,仅当预期值 A 和当前的内存值 V 相同时,才将内存值修改为 B。而当预期值 A 和当前的内存值 V 不相同时,认为这次操作失败,实际使用时可以结合自旋锁,循环尝试获取。

在大多数处理器的指令中,都会实现 CAS 相关的指令,这一条指令就可以完成“比较并交换”的操作,也正是由于这是一条(而不是多条)CPU 指令,所以 CAS 相关的指令是具备原子性的,这个组合操作在执行期间不会被打断。

二、CAS的应用

1. 并发容器

JUC并发包中大量使用了CAS技术,下面举例说明

a. ConcurrentHashMap

以该类的putVal 方法为例

final V putVal(K key, V value, boolean onlyIfAbsent) {
   
     
    if (key == null || value == null) throw new NullPointerException();
    int hash = spread(key.hashCode());
    int binCount = 0;
    for (Node<K,V>[] tab = table;;) {
   
     
        Node<K,V> f; int n, i, fh;
        if (tab == null || (n = tab.length) == 0)
            tab = initTable();
        else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
   
     
            if (casTabAt(tab, i, null,
                         new Node<K,V>(hash, key, value, null)))
                break;                   // no lock when adding to empty bin
        }
    //以下部分省略
    ...
}

其中的casTabAt 方法源码如下:

static final <K,V> boolean casTabAt(Node<K,V>[] tab, int i,
                                    Node<K,V> c, Node<K,V> v) {
   
     
    return U.compareAndSwapObject(tab, ((long)i << ASHIFT) + ABASE, c, v);
}

其中的U是 Unsafe 类型,Unsafe 类包含 compareAndSwapInt、compareAndSwapLong、compareAndSwapObject 等和 CAS 密切相关的 native 层的方法,其底层正是利用 CPU 对 CAS 指令的支持实现的。

b. ConcurrentLinkedQueue

以该类的offer()方法为例

public boolean offer(E e) {
   
     
    checkNotNull(e);
    final Node<E> newNode = new Node<E>(e);

    for (Node<E> t = tail, p = t;;) {
   
     
        Node<E> q = p.next;
        if (q == null) {
   
     
            if (p.casNext(null, newNode)) {
   
     
                if (p != t) 
                    casTail(t, newNode); 
                return true;
            }
        }
        else if (p == q)
            p = (t != (t = tail)) ? t : head;
        else
            p = (p != t && t != (t = tail)) ? t : q;
    }
}

其中的casNext 以及casTail ,其内部也是基于CAS实现的。

2. 数据库

数据库中的乐观锁,就是基于CAS实现的。具体做法是,引入version 字段,当获取完数据,并计算完毕,准备更新数据时,会检查现在的版本号与之前获取数据时的版本号是否一致,如果一致就说明在计算期间数据没有被更新过,可以直接更新本次数据;如果版本号不一致,则说明计算期间已经有其他线程修改过这个数据了,那就可以选择重新获取数据,重新计算,然后再次尝试更新数据。

3. 原子类

原子类中大部分都使用了CAS来实现线程安全,有关原子类内部具体的CAS实现,可以参考原子类部分的内容。

三、CAS的缺点

虽然CAS可以避免同步互斥锁,提高程序运行效率,但是它也有着明显的缺陷。

1. ABA问题

决定CAS 是否进行 swap 的判断标准是“当前的值和预期的值是否一致”。但是如果这个值从A 变成了 B,再由 B 变回了 A,CAS认为这个值并没有发生变化,和预期的值一致,不会发生swap操作。

当发生了 ABA 问题,线程根本无法知晓在计算过程中是否有其他线程把这个值修改过,由于当前值和预期值是相等的,它接下来的一些操作逻辑,是按照在此期间这个值没被修改过”的逻辑去处理的;但是实际上,应该是要求它执行其他的逻辑,比如本应该打印的是“本次修改过程受到了干扰”。

那么怎么解决这个问题呢?添加一个版本号就可以解决。

当添加一个版本号,原本A→B→A 就变成了 1A→2B→3A,就可以通过对比版本号来判断值是否变化过。

原子类中,AtomicStampedReference 就是利用版本号来解决 ABA 问题的,AtomicStampedReference 会维护一种类似 <Object,int> 的数据结构,其中的 int 就是用于计数的,也就是版本号,它可以对这个对象和 int 版本号同时进行原子更新,从而也就解决了 ABA 问题。因为我们去判断它是否被修改过,不再是以值是否发生变化为标准,而是以版本号是否变化为标准,即使值一样,它们的版本号也是不同的。

2. 自旋时间过长

实际在使用CAS时,常常会配合自旋锁,因为CAS失败,可以借助自旋锁循环尝试。但是如果线程竞争很激烈的时候,就有可能导致 CAS 一直都操作不成功,这样的话,循环时间就会越来越长。而且在此期间,CPU 资源也是一直在被消耗的,这会对性能产生很大的影响。

因此,CAS在高并发场景下的效率并不高。

3. 范围不能灵活控制

执行CAS 的时候,是针对某一个,而不是多个共享变量的,这个变量可能是 Integer 类型,也有可能是 Long 类型、对象类型等等,但是不能针对多个共享变量同时进行 CAS 操作,因为这多个变量之间是独立的,简单的把原子操作组合到一起,并不具备原子性。因此如果想对多个对象同时进行 CAS 操作并想保证线程安全的话,是比较困难的。

可行的解决方案是,利用一个新的类,来整合刚才这一组共享变量,这个新的类中的多个成员变量就是刚才的那多个共享变量,然后再利用 atomic 包中的 AtomicReference 来把这个新对象整体进行 CAS 操作,这样就可以保证线程安全。

相比之下,其他的线程安全技术调整线程安全的范围就可能变得非常容易,用 synchronized 关键字时,如果想把更多的代码加锁,那么只需要把更多的代码放到同步代码块里面就可以了。