介绍CAS原理和底层实现 通过查看gcc源码

转自源码剖析sun.misc.Unsafe && Compare And Swap(CAS)操作
转自Java 并发的底层实现
转自Java魔法类：sun.misc.Unsafe

• CAS含义
• 从 AtomicInteger.java 的 getAndIncrement 开始
• 进入 Unsafe.java 的 compareAndSwapInt 方法
• 通过JNI 调用 natUnsafe.cc
  • spinlock
• _Jv_ThreadYield
• __sync_bool_compare_and_swap或调用汇编cmpxchg实现CAS

CAS含义

Compare And Swap(CAS) 即 比较并交换。

CAS 操作包含三个操作数 —— 内存位置（V）、期望值（原值A）和更新值(B)。
如果内存位置的值与预期原值相匹配，那么处理器会自动将该位置值更新为新值。
否则，处理器不做任何操作。

无论哪种情况，它都会在 CAS 指令之前返回该位置的值。

CAS 有效地说明了“我认为位置 V 应该包含值 A；如果包含该值，则将 B 放到这个位置；否则，不要更改该位置，只告诉我这个位置现在的值即可。

” Java并发包(java.util.concurrent)中大量使用了CAS操作,涉及到并发的地方都调用了sun.misc.Unsafe类方法进行CAS操作。

从 AtomicInteger.java 的 getAndIncrement 开始

AtomicInteger.java in github
AtomicInteger.java in xuzhihuaBlog

// AtomicInteger.java
private static final Unsafe unsafe = Unsafe.getUnsafe();
public final int getAndIncrement() {
    for (;;) {
        int current = get();
        int next = current + 1;
        if (compareAndSet(current, next))
            return current;
    }
}

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

留意这个for循环，只有在compareAndSet成功时才会返回。否则就一直compareAndSet。

调用了compareAndSet实现。此处，我注意到 Oracle JDK的实现是略有不同的，如果你查看JDK下的src，你可以看到Oracle JDK是调用的Unsafe的getAndIncrement()，但我相信Oracle JDK实现Unsafe.java的时候应该也是只调用compareAndSet，因为一个compareAndSet就可以实现增加、减少、设值的原子操作了。

进入 Unsafe.java 的 compareAndSwapInt 方法

Unsafe.java in github
Unsafe.java in xuzhihuaBlog

// Unsafe.java
public native boolean compareAndSwapInt(Object obj, long offset,
                                          int expect, int update);

通过JNI 调用 natUnsafe.cc

通过JNI(Java Native Interface)调用C++的实现

natUnsafe.cc in github
natUnsafe.cc in xuzhihuaBlog

//natUnsafe.cc
jboolean
sun::misc::Unsafe::compareAndSwapInt (jobject obj, jlong offset,
                                      jint expect, jint update)
{
    jint *addr = (jint *)((char *)obj + offset);
    return compareAndSwap (addr, expect, update);
}

static inline bool
compareAndSwap (volatile jint *addr, jint old, jint new_val)
{
    jboolean result = false;
    spinlock lock;
    if ((result = (*addr == old)))
    *addr = new_val;
    return result;
}

Unsafe::compareAndSwapInt调用 static 函数 compareAndSwap。
而compareAndSwap又使用spinlock作为锁。这里的spinlock有LockGuard的意味，构造时加锁，析构时释放。

我们需要聚焦在spinlock里。这里是保证spinlock释放之前都是原子操作的真正实现。

spinlock

什么是spinlock

spinlock，即自旋锁，一种循环等待(busy waiting)以获取资源的锁。不同于mutex的阻塞当前线程、释放CPU资源以等待需求的资源，spinlock不会进入挂起、等待条件满足、重新竞争CPU的过程。这意味着只有在 等待锁的代价小于线程执行上下文切换的代价时,Spinlock才优于mutex。

// natUnsafe.cc
class spinlock
{
    static volatile obj_addr_t lock;
    
    public:
    spinlock ()
    {
        while (! compare_and_swap (&lock, 0, 1))
            _Jv_ThreadYield ();
    }
    ~spinlock ()
    {
        release_set (&lock, 0);
    }
};

以一个静态变量 static volatile obj_addr_t lock; 作为标志位，通过C++　RAII实现一个Guard，所以所谓的锁其实是 静态成员变量obj_addr_t lock，C++中volatile 并不能保证同步，保证同步的是构造函数里调用的 compare_and_swap和一个static变量lock.这个lock变量是1的时候，就需要等;是0的时候，就通过原子操作把它置为1，表示自己获得了锁。

这里会用一个static变量实在是一个意外，如此相当于所有的无锁结构都共用同一个变量(实际就是size_t)来区分是否加锁。当这个变量置为1时，其他用到spinlock的都需要等。

_Jv_ThreadYield

\_Jv\_ThreadYield 在下面的文件里，通过系统调用sched_yield(man 2 sched_yield)让出CPU资源。宏HAVE_SCHED_YIELD在configure里定义，意味着编译时如果取消定义，spinlock就称为真正意义的自旋锁了。

posix-threads.h in github

// posix-threads.h
inline void
_Jv_ThreadYield (void)
{
#ifdef HAVE_SCHED_YIELD
  sched_yield ();
#endif /* HAVE_SCHED_YIELD */
}

__sync_bool_compare_and_swap或调用汇编cmpxchg实现CAS

这个lock.h在不同平台有着不同的实现，我们以ia64(Intel AMD x64)平台举例，其他的实现可以在 这里 看到。

lock.h in github

// lock.h
typedef size_t obj_addr_t;
inline static bool
compare_and_swap(volatile obj_addr_t *addr,
                          obj_addr_t old,
                          obj_addr_t new_val)
{
  return __sync_bool_compare_and_swap (addr, old, new_val);
}

inline static void
release_set(volatile obj_addr_t *addr, obj_addr_t new_val)
{
  __asm__ __volatile__("" : : : "memory");
  *(addr) = new_val;
}

__sync_bool_compare_and_swap 是gcc内建函数，汇编指令"memory"完成内存屏障。

1. 一般地，如果CPU硬件支持指令 cmpxchg (该指令从硬件保障原子性，毫无疑问十分高效)，那么__sync_bool_compare_and_swap就应该是用cmpxchg来实现的。
2. 不支持cmpxchg的CPU架构 可以用lock指令前缀，通过锁CPU总线的方式实现。
3. 如果连lock指令都不支持，有可能通过APIC实现

总之，硬件上保证多核CPU同步，而Unsafe的实现也是尽可能的高效。GCC-java的还算高效，相信Oracle 和 OpenJDK不会更差。