CAS真的无锁吗

CAS 真的是无锁吗？

前言

我们平时经常看到一些文章说 CAS 是无锁编程。那么在多CPU下，它是怎么保证原子性的呢？

一、CAS 底层实现

我们通过 Java 中的 AtomicInteger类中的 getAndIncrement()来看下 CAS 底层是怎么实现的。

public final int getAndIncrement() {
        return unsafe.getAndAddInt(this, valueOffset, 1);
    }
1
2
3

可以看到它是调用的Unsafe类的getAndAddInt方法，

public final int getAndAddInt(Object obj, long offset, int delta) {
    int value;
    do {
        value= this.getIntVolatile(obj, offset);
    } while(!this.compareAndSwapInt(obj, offset, value, value + delta));

    return v;
}
1
2
3
4
5
6
7
8

可以看到该方法内部是先获取到该对象的偏移量对应的值(value)，然后调用 compareAndSwapInt 方法通过对比来修改该值，如果这个值和value一样，说明此过程中间没有
人修改该数据，此时可以将该地址的值改为 value+delta, 返回true,结束循环。否则，说明有人修改该地址处的值，返回false，继续下一次循环。
那么是怎么保证 compareAndSwapInt(CAS)的原子性呢？这个就由操作系统底层来提供了，要不然就无限套娃了。

compareAndSwapInt 是一个 native 方法，
我们看下 Hotspot 源码中 对 compareAndSwapInt的实现：

UNSAFE_ENTRY(jboolean, Unsafe_CompareAndSwapInt(JNIEnv *env, jobject unsafe, jobject obj, jlong offset, jint e, jint x))
  UnsafeWrapper("Unsafe_CompareAndSwapInt");
  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
1
2
3
4
5
6

可以看到这里最后调用了Atomic::cmpxchg方法，我们来看下linux下atomic_linux_x86.inline.hpp这个方法的实现

inline jint  Atomic::cmpxchg    (jint     exchange_value, volatile jint*     dest, jint     compare_value) {
        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;
        }
1
2
3
4
5
6
7
8

is_MP() 是判断是否有多个CPU，如果是多个CPU返回1，单个CPU返回0

可以看下 LOCK_IF_MP 方法，
LOCK_IF_MP(%4) 入参是第四个参数，

“r” (exchange_value),// 第一个参数

“a” (compare_value), // 第二个参数

“r” (dest), // 第三个参数

“r” (mp) // 第四个参数

#define LOCK_IF_MP(mp) "cmp $0, " #mp "; je 1f; lock; 1: "

可以看到 如果 mp 不为0，这里加了 lock 指令，加了 lock 指令会对总线加锁，其他CPU的请求将被阻塞，当前CPU是可以独占共享内存的。

无锁编程

既然CAS在多CPU情况下会加lock汇编指令，那我们为什么还说CAS 是无锁呢？首先我们来看下 lock-free programming(无锁编程)

可以看到如果当前线程不会阻塞其他线程，我们就可以认为是无锁编程。

总线锁的开销比较大，那为什么没用缓存锁呢？ 缓存锁会对CPU中的缓存行进行锁定，在锁定期间，其它CPU不能同时缓存此数据，在修改之后，
通过缓存一致性协议来保证修改的原子性。
《Java并发编程的艺术》第二章第三小节讲了两种不能使用缓存锁的情况：

1. 当操作的数据不能被缓存在处理器内部，或者操作的数据跨多个缓存行
2. 有些处理器（比较旧的处理器）不支持缓存锁定
   所以我个人觉得这里使用总线锁应该是为了保持统一。

总结

小结：如果是多CPU，CAS 底层是加了 lock 汇编指令来保障原子操作的。那么为什么我们说它是无锁呢，主要是因为它在编程语言层面上没有阻塞其他线程。

参考：

1. 维基百科
2. 无锁编程介绍
3. 《Java并发编程的艺术》

好了，这篇文章就到这里了，感谢大家的观看！如有错误，请及时指正！欢迎大家关注我的公众号：贾哇技术指南。