【Java】锁

CAS(比较与交换,Compare and swap) 算法是一种有名的非阻塞算法(non-blocking algorithm),同时也是一种无锁算法(lock-free algorithm),即在没有锁的情况下实现同步,基于乐观锁(pessimistic locking)的思想。

java.util.concurrent包中的原子类(比如 AtomicInteger)就是通过CAS来实现乐观锁的。

当多个线程尝试使用 CAS 同时更新同一个变量时,只有其中一个线程能成功地更新变量的值,而其它线程都失败,失败的线程并不会被挂起,而是被告知这次竞争中失败,并可以再次尝试。

CAS 无锁算法的 C 实现如下:

1
2
3
4
5
6
7
8
9
int  (int* reg, int oldval, int newval) 
{
ATOMIC();
int old_reg_val = *reg;
if (old_reg_val == oldval)
*reg = newval;
END_ATOMIC();
return old_reg_val;
}

由于 CAS 需要以原子操作的方式更新 *reg 的值,因此 CAS 需要硬件指令的支持。

image-20190227160919664

就是指当两者进行比较时,如果相等,则证明共享数据没有被修改,因此可以替换成新值,然后继续往下运行;如果不相等,说明共享数据已经被修改,放弃已经所做的操作,然后重新执行刚才的操作。容易看出 CAS 操作是基于共享数据不会被修改的假设(即乐观锁思想),采用了类似于数据库的 commit-retry 的模式。当同步冲突出现的机会很少时,这种假设能带来较大的性能提升。

CAS 是怎么实现的

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
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 方法:

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

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

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

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

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

1
2
3
4
5
6
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有这样的代码:

1
2
3
4
5
6
7
8
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 信号保证其原子性

CAS 的权衡

轻度到中度的争用情况下,非阻塞算法的性能会超越阻塞算法,因为 CAS 的多数时间都在第一次尝试时就成功,而发生争用时的开销也不涉及线程挂起和上下文切换,只多了几个循环迭代。没有争用的 CAS 要比没有争用的锁便宜得多(这句话肯定是真的,因为没有争用的锁涉及 CAS 加上额外的处理),而争用的 CAS 比争用的锁获取涉及更短的延迟。

高度争用的情况下(即有多个线程不断争用一个内存位置的时候),基于锁的算法开始提供比非阻塞算法更好的吞吐率,因为当线程阻塞时,它就会停止争用,耐心地等候轮到自己,从而避免了进一步争用。但是,这么高的争用程度并不常见,因为多数时候,线程会把线程本地的计算与争用共享数据的操作分开,从而给其他线程使用共享数据的机会。

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

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

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

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

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

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

ABA问题

使用CAS方式更新有一个ABA问题,该问题是指,一个线程开始看到的值是A,随后使用CAS进行更新,它的实际期望是没有其他线程修改过才更新,但普通的CAS做不到,因为可能在这个过程中,已经有其他线程修改过了,比如先改为了B,然后又改回为了A。

一个通常的解决 ABA 问题的思路是增加时间戳,即在进行数据更新时,不仅仅对比当前值与开始操作之前的值是不是一致,还对比最后修改数据的时间戳是否一致。

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),则只有一个能够执行成功。

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

Reference