乐观锁比较并交换机制——CAS(Compare And Swap)
Diego38 79 1

1. 前言

前面我们学习了线程安全满足的两大条件,一是可见性,二是原子性。解决可见性根据不同场景我们可以使用锁、volatile、final,解决原子性问题我们可以使用锁。

实际上针对单个变量的操作,我们还可以使用 CAS 来保证原子性,CAS 是相比 Synchronized 同步锁来说是一种乐观锁,它更加轻量高效,是基于比较交换的算法(Compare And Swap)来解决线程冲突的。

乐观锁:假设多线程并发的事务在处理时不会彼此互相影响,各事务能够在不产生锁的情况下处理各自影响的那部分数据。 -- 维基百科

本节我们就学习 CAS 的使用和实现。

2. CAS 的定义和使用

CAS 是 Compare And Swap 的缩写。CAS 操作在一定情况下是比 Synchronized 同步锁更加轻量的锁,在 JUC 包中使用非常普遍。对一个变量进行进行 CAS 操作(比较并交换),需要传入三个参数:

  • 内存位置
  • 预期原值
  • 新值

对应的伪代码如下

  compareAndSwap(long memoryAddress, long expect, long newValue)

假设我们对 Long 类型进行 CAS 操作,如果内存位置的值与预期原值相等,那么处理器会自动将该位置值更新为新值。否则,处理器不做任何操作。

CAS 操作是利用了处理器提供的 CMPXCHG 指令实现的;CAS 操作有可能成功,也有可能失败,在失败后继续做 CAS 操作,直到成功为止,这种操作就叫做自旋 CAS。CAS 的底层指令有效避免了并发冲突,将读取后写入转换成原子操作,规避了同步锁带来的开销。

CAS 底层是借助魔法类 Unsafe 类实现的,Unsafe 通过本地方法调用 (JNI), 使得 CAS 算法可以在 java 程序中使用。Unsafe 常见的 JNI 接口有 compareAndSwapInt 和 compareAndSwapLong。

CAS 在 Atomic 类应用较多,一般我们在代码里面不会直接调用 Unsafe 操作 CAS,而是通过比如 AtomicInteger、AtomicReference 这些原子类来实现 CAS。下面我就看一个 CAS 操作实例。

2.1 CAS 的应用

我们看一个借助 AtomicInteger 类对整形变量进行 CAS 操作的例子:

public class CASTest {

    /** Atomc计数器 */
    public static AtomicInteger atomicCount = new AtomicInteger(0);
    /** 普通计数器 */
    public static Integer count = 0;
    public static class TicketWindow implements Runnable {
        @Override
        public void run() {
           for (int i = 0; i < 1000 ; i ++) {
               //做计数
               atomicCount.incrementAndGet();
               count ++;
           }
        }
    }

    public static void main(String[] args) throws InterruptedException {
        //启动线程1计数
        Thread thread1 = new Thread(new TicketWindow());
        thread1.start();
        //启动线程2计数
        Thread thread2 = new Thread(new TicketWindow());
        thread2.start();
        //启动线程3计数
        Thread thread3 = new Thread(new TicketWindow());
        thread3.start();

        //等待三个线程执行完成
        thread1.join();
        thread2.join();
        thread3.join();

        System.out.println("普通计数器:" + count + " atomic计数器:" + atomicCount);
    }
}

上述代码中,展示 2 个计数器,一个是普通计数器 count,另一个是 Atomic 计数器 atomicCount, 变量类型是 AtomicInteger。然后使用 3 个线程同时对这两种计数器继续做计数加一的操作,每个线程执行 1000 次,三个线程加起来就是 3000。

执行结果后我们发现,普通计数器总是计算出错误的结果,而 atomic 计数器每次都输出正确的结果 3000。说明 AtomicInteger 可以保证整形变量的可见性和操作原子性。

我们进入 AtomicInteger 源码一探究竟

 /**
     * Atomically increments by one the current value.
     *
     * @return the updated value
     */
    public final int incrementAndGet() {
        return unsafe.getAndAddInt(this, valueOffset, 1) + 1;
    }

上例的 valueOffset 实际上是 AtomicInteger 内置 value 的内存地址,通过 unsafe 的 jni 方法 objectFieldOffset 来获得:

  static {
        try {
            valueOffset = unsafe.objectFieldOffset
                (AtomicInteger.class.getDeclaredField("value"));
        } catch (Exception ex) { throw new Error(ex); }
    }

    private volatile int value;

调用了 unsafe 的 getAndAddInt

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;
    }

我们看到 compareAndSwapInt 就是一个 CAS 操作,getIntVolatile 获取每次最新的值,然后将预期值 var5 与更新值 var5 + var4 传入 compareAndSwapInt,其中 var1 和 var2 组合起来可以作为地址参数,当执行 CAS 操作 compareAndSwapInt 失败后,说明其他线程也在做 CAS 操作,当前线程会继续执行,直到成功为止。

2.2 CAS 的底层 Unsafe

CAS 操作底层是通过 Unsafe 来实现的,Unsafe 是位于 sun.misc 包下的一个类,比如内存操作,线程调度,对象操作和数组操作。 image

由于该类默认 BootstrapClassLoader 加载的,虽然 Unsafe 提供了 getUnsafe 的方法,但 getUnsafe 方法内部会对调用来源类做校验,调用来源类也必须是由 BootstrapClassLoader,但用户代码使用的类加载器肯定 AppClassLoader,如果我们代码里面要获取 Unsafe 只能通过反射的方式。

@CallerSensitive
    public static Unsafe getUnsafe() {
        Class var0 = Reflection.getCallerClass();
        if (!VM.isSystemDomainLoader(var0.getClassLoader())) {
            throw new SecurityException("Unsafe");
        } else {
            return theUnsafe;
        }
    }

反射获取 Unsafe 的代码如下:

Field theUnsafeField = Unsafe.class.getDeclaredField("theUnsafe");
theUnsafeField.setAccessible(true);
Unsafe unsafe = (Unsafe) theUnsafeField.get(null);
System.out.println(unsafe);

3. CAS 操作面临的问题

CAS 能够实现单一变量的原子操作,但它也有三个局限性

  • ABA 问题 CAS 操作是检查值没有发生变化则更新,如果一个值初始值是 A,之后变成 B,又变成 A, 使用 CAS 做检查时是不会发生变化的,CAS 操作依然是成功的,当然 ABA 在绝大多数场景是可以容忍的,只有少数场景在比如保险箱中的被盗又被还了回来,说明保险箱已经不够安全了。 Atomic 类中提供了解决 ABA 问题的方案,通过 AtomicStampedReference 类对变量前面追击版本号,每次更新版本号加 1。

  • 自旋 CAS 消耗 CPU CAS 失败会重试,在多线程同时对同一变量做频繁操作时,CAS 失败的概率会增加,循环重试次数也会随着增多,导致 CPU 消耗增加。我们在利用 CAS 做无所编程时需要注意这一点

  • 只能保证单一共享变量的原子性 CAS 操作无法保证多个变量的原子性,如果涉及到多个共享变量,需要使用锁来实现原子操作。

4. 总结

CAS 操作借助系统的比较并交换机制 (Compare And Swap) 可以实现单变量的原子操作,相比加锁更加轻量,并且 CAS 操作是实现无锁化编程的基础,Java 并发包中很多类都使用自旋 CAS 来实现原子操作,比如 LinkedTransferQueue 类的 Xfer 方法。但它同时有三个局限性分别是 ABA 问题、自旋 CAS 消耗 CPU、只能保证单一共享变量的原子性。

在后续的章节,也会介绍到时 Atomic 类 CAS 更高级的包装方法,比如 AtomicInteger 的 updateAndGet。 image

参考

  1. 维基百科
预览图
评论区

索引目录