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 的逻辑：
- 先获取当前的value值
- 对value加一
- 第三步是关键步骤，调用
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大性能杀手：
- 大量线程导致的线程切换开销
- 锁
- 非必要的内存拷贝
在高并发下，对于纯内存操作来说，单线程是要比多线程快的。
可以比较一下多线程程序在压力测试下 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
- 非阻塞同步算法与CAS(Compare and Swap)无锁算法 - https://www.cnblogs.com/Mainz/p/3546347.html
- JAVA 中的 CAS - https://juejin.im/post/5a75db20f265da4e826320a9