【Java】锁 - CAS 无锁算法

Posted by 西维蜀黍 on 2019-02-27, Last Modified on 2021-09-21

CAS 是怎么实现的

以 Atomic 类中的 incrementAndGet() 方法为例,其内部就调用了Unsafe中的 native 方法(CompareAndSet)以实现递增数值:

private volatile int value;
public final int get() {
        return value;
    }
/**
 * Atomically increments by one the current value.
 *
 * @return the updated value
 */
public final int incrementAndGet() {
    for (;;) {
        int current = get();
        int next = current + 1;
        if (compareAndSet(current, next))
            return next;
    }
}
public final boolean compareAndSet(int expect, int update) {
    return unsafe.compareAndSwapInt(this, valueOffset, expect, update);
}

我们来分析下 incrementAndGet 的逻辑:

  1. 先获取当前的value值
  2. 对value加一
  3. 第三步是关键步骤,调用compareAndSet方法来进行一个原子更新操作,这个方法的语义是:先检查当前value是否等于current,如果相等,则意味着value没被其他线程修改过,更新并返回true。如果不相等,compareAndSet则会返回false,然后循环继续尝试更新。

继续往下,就能发现unsafe对象其实是 sum.misc.Unsafe 这个类的单例实例。看名称 Unsafe 就是一个不安全的类,这个类是利用了 Java 的类和包在可见性的的规则中的一个恰到好处的漏洞。Unsafe 这个类为了速度,在Java的安全标准上做出了一定的妥协。

再往下寻找我们发现 Unsafe 类的 compareAndSwapInt() 方法是一个 Native 方法:

public final native boolean compareAndSwapInt(Object var1, long var2, int var4, int var5);

也就是说,这几个 CAS 的方法应该是使用了本地的方法。所以这几个方法的具体实现需要我们自己去 JDK 的源码中搜索。

于是我下载一个 OpenJDK 的源码继续向下探索,我们发现在 /jdk9u/hotspot/src/share/vm/unsafe.cpp 中有这样的代码:

{CC "compareAndSetInt",   CC "(" OBJ "J""I""I"")Z",  FN_PTR(Unsafe_CompareAndSetInt)},

这个涉及到,JNI 的调用,感兴趣的同学可以自行学习。我们搜索 Unsafe_CompareAndSetInt 后发现:

UNSAFE_ENTRY(jboolean, Unsafe_CompareAndSetInt(JNIEnv *env, jobject unsafe, jobject obj, jlong offset, jint e, jint x)) {
  oop p = JNIHandles::resolve(obj);
  jint* addr = (jint *)index_oop_from_field_offset_long(p, offset);

  return (jint)(Atomic::cmpxchg(x, addr, e)) == e;
} UNSAFE_END

最终我们终于看到了核心代码 Atomic::cmpxchg

继续向底层探索,在文件java/jdk9u/hotspot/src/os_cpu/linux_x86/vm/atomic_linux_x86.hpp有这样的代码:

inline jint     Atomic::cmpxchg    (jint     exchange_value, volatile jint*     dest, jint     compare_value, cmpxchg_memory_order order) {
  int mp = os::is_MP();
  __asm__ volatile (LOCK_IF_MP(%4) "cmpxchgl %1,(%3)"
                    : "=a" (exchange_value)
                    : "r" (exchange_value), "a" (compare_value), "r" (dest), "r" (mp)
                    : "cc", "memory");
  return exchange_value;
}

我们通过文件名可以知道,针对不同的操作系统,JVM 对于 Atomic::cmpxchg 应该有不同的实现。由于我们服务基本都是使用的是64位linux,所以我们就看看linux_x86 的实现。

我们继续看代码:

  • __asm__ 的意思是这个是一段内嵌汇编代码。也就是在 C 语言中使用汇编代码。
  • 这里的 volatile和 JAVA 有一点类似,但不是为了内存的可见性,而是告诉编译器对访问该变量的代码就不再进行优化。
  • LOCK_IF_MP(%4) 的意思就比较简单,就是如果操作系统是多线程的,那就增加一个 LOCK。
  • cmpxchgl 就是汇编版的“比较并交换”。但是我们知道比较并交换,有三个步骤,不是原子的。所以在多核情况下加一个 LOCK,由CPU硬件保证他的原子性。
  • 我们再看看 LOCK 是怎么实现的呢?我们去Intel的官网上看看,可以知道LOCK在的早期实现是直接将 CPU 的总线阻塞,这样的实现可见效率是很低下的。后来优化为 X86 CPU 有锁定一个特定内存地址的能力,当这个特定内存地址被锁定后,它就可以阻止其他的系统总线读取或修改这个内存地址。

关于 CAS 的底层探索我们就到此为止。我们总结一下 Java 的 CAS 是怎么实现的:

  • Java 的 CAS 利用的的是 unsafe 这个类提供的 CASS 操作。
  • unsafe 的 CAS 依赖了的是 JVM 针对不同的操作系统实现的 Atomic::cmpxchg
  • Atomic::cmpxchg 的实现使用了汇编的 CASS 操作,并使用 CPU 硬件提供的 lock 信号保证其原子性

高并发环境下优化锁或无锁(lock-free)的设计思路

服务端编程的3大性能杀手:

  1. 大量线程导致的线程切换开销
  2. 非必要的内存拷贝

在高并发下,对于纯内存操作来说,单线程是要比多线程快的。

可以比较一下多线程程序在压力测试下 CPU 的sy和ni百分比。高并发环境下要实现高吞吐量和线程安全,两个思路:一个是用优化的锁实现,一个是lock-free的无锁结构。但非阻塞算法要比基于锁的算法复杂得多。开发非阻塞算法是相当专业的训练,而且要证明算法的正确也极为困难,不仅和具体的目标机器平台和编译器相关,而且需要复杂的技巧和严格的测试。

虽然 lock-Free 编程非常困难,但是它通常可以带来比基于锁编程更高的吞吐量。所以 lock-Free 编程是大有前途的技术。它在线程中止、优先级倒置以及信号安全等方面都有着良好的表现。

CAS 算法在 JDK中的应用

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

在java.util.concurrent.atomics.AtomicInteger中就使用和提供了很多CAS方法。如下面的方法,比较当前AtomicInteger的值,如果等于expect则并交换成update, 整体是一个原子方法,如果当前值是1并且有其他线程同时在执行compareAndSet(1, 2),则只有一个能够执行成功。

public final boolean compareAndSet(int expect, int update) {
    return unsafe.compareAndSwapInt(this, valueOffset, expect, update);
}

Reference