Crazyfzw's blog

Return to base, step by step.

0%

深入浅出Java多线程-非阻塞同步-CAS

发表于 更新于 分类于 Valine：
本文字数： 5.5k 阅读时长 ≈ 5 分钟

乐观锁与悲观锁的概念

锁可以从不同的角度分类。其中，乐观锁和悲观锁是一种分类方式。

悲观锁：
悲观锁就是我们常说的锁。对于悲观锁来说，它总是认为每次访问共享资源时会发生冲突，所以必须对每次数据操作加上锁，以保证临界区的程序同一时间只能有一个线程在执行。互斥同步锁就属于悲观锁，比如， synchronized. 与 ReentrantLock.

乐观锁：
乐观锁又称为“无锁”，顾名思义，它是乐观派。乐观锁总是假设对共享资源的访问没有冲突，线程可以不停地执行，无需加锁也无需等待。而一旦多个线程发生冲突，乐观锁通常是使用一种称为CAS的技术来保证线程执行的安全性。

由于无锁操作中没有锁的存在，因此不可能出现死锁的情况，也就是说乐观锁天生免疫死锁。

乐观锁多用于“读多写少“的环境，避免频繁加锁影响性能；而悲观锁多用于”写多读少“的环境，避免频繁失败和重试影响性能。

CAS

互斥同步最主要的问题就是进行线程阻塞和唤醒所带来的性能问题，因此这种同步是阻塞同步，这是一种悲观的并发策略，总是认为只要不加锁那就肯定会出现问题，无论共享数据是否真多会出现竞争，它都要进行加锁。

而随着硬件指令集的发展，CAS得与实现，做法是先进行操作，如果没有其他线程争用共享数据，那操作就成功了，如果共享数据有争用，产生了冲突，那就再采取其他的补偿措施（最常见的补偿措施就是不断地重试，直到成功为止）

CAS的全称是：比较并交换（Compare And Swap）。在CAS中，有这样三个值：

  • V：要更新的变量(var)
  • E：预期值(expected)
  • N：新值(new)

比较并交换的过程如下：

判断V是否等于E，如果等于，将V的值设置为N；如果不等，说明已经有其它线程更新了V，则当前线程放弃更新，什么都不做。所以这里的预期值E本质上指的是“旧值”

以一个简单的例子来解释这个过程：
1.如果有一个多个线程共享的变量i原本等于5，我现在在线程A中，想把它设置为新的值6;
2.我们使用CAS来做这个事情；
3.首先我们用i去与5对比，发现它等于5，说明没有被其它线程改过，那我就把它设置为新的值6，此次CAS成功，i的值被设置成了6；
4.如果不等于5，说明i被其它线程改过了（比如现在i的值为2），那么我就什么也不做，此次CAS失败，i的值仍然为2。

在这个例子中，i就是V，5就是E，6就是N。

那有没有可能我在判断了i为5之后，正准备更新它的新值的时候，被其它线程更改了i的值呢？
不会的。因为CAS是一种原子操作，它是一种系统原语，是一条CPU的原子指令，从CPU层面保证它的原子性

当多个线程同时使用CAS操作一个变量时，只有一个会胜出，并成功更新，其余均会失败，但失败的线程并不会被挂起，仅是被告知失败，并且允许再次尝试，当然也允许失败的线程放弃操作。CAS 常常会搭配自旋使用

Java实现CAS的原理 - Unsafe类

CAS是一种原子操作。那么Java是怎样来使用CAS的呢？我们知道，在Java中，如果一个方法是native的，那Java就不负责具体实现它，而是交给底层的JVM使用c或者c++去实现。

在Java中，有一个Unsafe类，它在sun.misc包中。它里面是一些native方法，其中就有几个关于CAS的：

JDK1.7中

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
/**
 * Atomically update Java variable to <tt>x</tt> if it is currently
 * holding <tt>expected</tt>.
 * @return <tt>true</tt> if successful
 */
public final native boolean compareAndSwapObject(Object o, long offset,
                                                 Object expected,
                                                 Object x);

/**
 * Atomically update Java variable to <tt>x</tt> if it is currently
 * holding <tt>expected</tt>.
 * @return <tt>true</tt> if successful
 */
public final native boolean compareAndSwapInt(Object o, long offset,
                                              int expected,
                                              int x);

/**
 * Atomically update Java variable to <tt>x</tt> if it is currently
 * holding <tt>expected</tt>.
 * @return <tt>true</tt> if successful
 */
public final native boolean compareAndSwapLong(Object o, long offset,
                                               long expected,
                                               long x);

在 JDK11 中，则改成一下

1
2
3
4
5
6
7
8
9
@HotSpotIntrinsicCandidate
public final native boolean compareAndSetObject(Object var1, long var2, Object var4, Object var5);

@HotSpotIntrinsicCandidate
public final native boolean compareAndSetInt(Object var1, long var2, Object var4, Object var5);

 @HotSpotIntrinsicCandidate
public final native boolean compareAndSetLong(Object var1, long var2, long var4, long var6);

可以看出两个版本都是 native 的，Unsafe中对CAS的实现是C++写的，它的具体实现和操作系统、CPU都有关系。

Linux的X86下主要是通过cmpxchgl这个指令在CPU级完成CAS操作的，但在多处理器情况下必须使用lock指令加锁来完成。当然不同的操作系统和处理器的实现会有所不同。

JDK提供的原子操作类-AtomicInteger源码简析

由于 Unsafe 类不是提供给用户程序调用的类（Unsafe.getUnsafe()的代码中限制了只有启动类加载器 BootStrap ClassLoader 加载的 Class 才能访问它)，所以，JDK给我们提供了一些原子类的Java API来间接使用它，这些原子工具类在java.util.concurrent.atomic包下面。在JDK 11中，有如下17个类：
f0f475e608bc2a584e4d6214bab2b4d0.png

从名字就可以看得出来这些类大概的用途：

原子更新基本类型
原子更新数组
原子更新引用
原子更新字段（属性）

这里我们以AtomicInteger类的getAndAdd(int delta)方法为例，来看看Java是如何实现原子操作的。

先看看这个方法的源码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public final int getAndAdd(int delta) {
    return U.getAndAddInt(this, VALUE, delta);
}

@HotSpotIntrinsicCandidate
public final int getAndAddInt(Object o, long offset, int delta) {
int v;
do {
    v = getIntVolatile(o, offset); //对象o是this，也就是一个AtomicInteger对象。然后offset是一个常量VALUE。这个常量是在AtomicInteger类中声明的：
} while (!weakCompareAndSetInt(o, offset, v, v + delta));
    return v;
}

@HotSpotIntrinsicCandidate
public final boolean weakCompareAndSetIntRelease(Object o, long offset, int expected, int x) {
    return this.compareAndSetInt(o, offset, expected, x);
}

@HotSpotIntrinsicCandidate
public final native boolean compareAndSetInt(Object var1, long var2, int var4, int var5);

所以其实AtomicInteger类的getAndAdd(int delta)方法最终其实是调用的我们之前说到了CAS native方法来来实现的：对象o是this，也就是一个AtomicInteger对象。然后offset是对象字段偏移量。是通过 U.objectFieldOffset(AtomicInteger.class, “value”) 取得的。

CAS是“无锁”的基础，它允许更新失败。所以经常会与while循环搭配，在失败后不断去重试。这里使用的是do-while循环。这种循环不多见，它的目的是保证循环体内的语句至少会被执行一遍。这样才能保证return 的值v是我们期望的值。

而在JDk1.8 之前，比如JDK1.7中说通过for循环实现的：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
//JDK1.7中
//https://github.com/openjdk-mirror/jdk7u-jdk/blob/master/src/share/classes/java/util/concurrent/atomic/AtomicInteger.java
    
    /**
     * Atomically adds the given value to the current value.
     *
     * @param delta the value to add
     * @return the previous value
     */
    public final int getAndAdd(int delta) {
        for (;;) {
            int current = get();
            int next = current + delta;
            if (compareAndSet(current, next))
                return current;
        }
    }

可以看到，两个版本最终其实是调用的我们之前说到了CAS native方法。那为什么要经过一层weakCompareAndSetInt呢？

而在JDK 9开始，这两个方法上面增加了@HotSpotIntrinsicCandidate注解。这个注解允许HotSpot VM自己来写汇编或IR编译器来实现该方法以提供性能。也就是说虽然外面看到的在JDK9中weakCompareAndSet和compareAndSet底层依旧是调用了一样的代码，但是不排除HotSpot VM会手动来实现weakCompareAndSet真正含义的功能的可能性。

CAS实现原子操作的三大问题

ABA问题及解决

所谓ABA问题，就是一个值原来是A，变成了B，又变回了A。这个时候使用CAS是检查不出变化的，但实际上却被更新了两次。

ABA问题的解决思路是在变量前面追加上版本号或者时间戳。从JDK 1.5开始，JDK的atomic包里提供了一个类AtomicStampedReference类来解决ABA问题。

AtomicStampedReference类的compareAndSet方法的作用是首先检查当前引用是否等于预期引用，并且检查当前标志是否等于预期标志，如果二者都相等，才使用CAS设置为新的值和标志。

1
2
3
4
5
6
7
8
9
10
11
12
public boolean compareAndSet(V   expectedReference,
                             V   newReference,
                             int expectedStamp,
                             int newStamp) {
    Pair<V> current = pair;
    return
        expectedReference == current.reference &&
        expectedStamp == current.stamp &&
        ((newReference == current.reference &&
          newStamp == current.stamp) ||
         casPair(current, Pair.of(newReference, newStamp)));
}

它通控制变量的把那本来保证CAS的正确性，不过目前来说这个功能比较鸡肋，因为大部分情况下ABA问题不会影响程序并发的正确性，如果需要解决ABA问题，该用传统的互斥同步可能会比原子类更高效。

循环时间长开销大

CAS多与自旋结合。如果自旋CAS长时间不成功，会占用大量的CPU资源。

解决思路是让JVM支持处理器提供的pause指令：
pause指令能让自旋失败时cpu睡眠一小段时间再继续自旋，从而使得读操作的频率低很多,为解决内存顺序冲突而导致的CPU流水线重排的代价也会小很多

只能保证一个共享变量的原子操作

有两种解决方案：

  • 使用JDK 1.5开始就提供的AtomicReference类保证对象之间的原子性，把多个变量放到一个对象里面进行CAS操作；

  • 使用锁。锁内的临界区代码可以保证只有当前线程能操作。