Simply Understanding Compare-And-Swap

0x00. TOC

0x01.简介
0x02.应用
0x03.ABA问题
0x04.实现
0x05.Java中的CAS
0x06.参考

0x01. 简介

比较并交换(compare and swap, CAS)，是原子操作的一种，可用于在多线程编程中实现不被打断的数据交换操作，从而避免多线程同时改写某一数据时由于执行顺序不确定性以及中断的不可预知性产生的数据不一致问题。该操作通过将内存中的值与指定数据进行比较，当数值一样时将内存中的数据替换为新的值。

无锁（lock-free）的非阻塞算法 CAS是项乐观锁技术，当多个线程尝试使用CAS同时更新同一个变量时，只有其中一个线程能更新变量的值，而其它线程都失败，失败的线程并不会被挂起，而是被告知这次竞争中失败，并可以再次尝试。CAS无锁算法的C语言实现如下：

int cas(long *addr, long old, long new) {
    /* Executes atomically. */
    ATOMIC();
    if(*addr != old)
        return 0;
    *addr = new;
    END_ATOMIC();
    return 1;
}

在使用上，通常会记录下某块内存中的旧值，通过对旧值进行一系列的操作后得到新值，然后通过CAS操作将新值与旧值进行交换。如果这块内存的值在这期间内没被修改过，则旧值会与内存中的数据相同，这时CAS操作将会成功执行使内存中的数据变为新值。如果内存中的值在这期间内被修改过，则一般来说旧值会与内存中的数据不同，这时CAS操作将会失败，新值将不会被写入内存。

0x02. 应用

在应用中CAS可以用于实现无锁数据结构，常见的有

无锁队列(先入先出)
无锁堆(先入后出)
对于可在任意位置插入数据的链表以及双向链表，实现无锁操作的难度较大。

0x03. ABA问题

ABA问题是无锁结构实现中常见的一种问题，可基本表述为：

进程P1读取了一个数值A
P1被挂起(时间片耗尽、中断等)，进程P2开始执行
P2修改数值A为数值B，然后又修改回A
P1被唤醒，比较后发现数值A没有变化，程序继续执行。

对于P1来说，数值A未发生过改变，但实际上A已经被变化过了，继续使用可能会出现问题。在CAS操作中，由于比较的多是指针，这个问题将会变得更加严重。试想如下情况：

有一个堆(先入后出)中有top和节点A，节点A目前位于堆顶top指针指向A，这时堆结构图1所示。现在有一个进程P1想要pop一个节点，因此按照如下无锁操作进行

pop()
{
  do{
    ptr = top;            	// ptr = top = NodeA
    next_prt = top->next; 	// next_ptr = NodeX
  } while(CAS(top, ptr, next_ptr) != true);
  return ptr;   
}

而进程P2在执行CAS操作之前打断了P1，并对堆进行了一系列的pop和push操作，使堆结构如图2所示：

进程P2首先pop出NodeA，之后又Push了两个NodeB和C，由于内存管理机制中广泛使用的内存重用机制，导致NodeC的地址与之前的NodeA一致。

这时P1又开始继续运行，在执行CAS操作时，由于top依旧指向的是NodeA的地址(实际上已经变为NodeC)，因此将top的值修改为了NodeX，这时堆结构图3所示。
经过CAS操作后，top指针错误的指向了NodeX而不是NodeB。

0x04. 实现

CAS操作基于CPU提供的原子操作指令实现。对于Intel X86处理器，可通过在汇编指令前增加LOCK前缀来锁定系统总线，使系统总线在汇编指令执行时无法访问相应的内存地址。而各个编译器根据这个特点实现了各自的原子操作函数。

C语言，C11的头文件。由GNU提供了对应的__sync系列函数完成原子操作。
C++11，STL提供了atomic系列函数。
JAVA，sun.misc.Unsafe提供了compareAndSwap系列函数。
C#，通过Interlocked方法实现。
Go，通过import “sync/atomic”包实现。
Windows，通过Windows API实现了InterlockedCompareExchangeXYZ系列函数。

0x05. Java中的CAS

独占锁（悲观锁）与乐观锁 在多线程编程的时候，为了保证多个线程对一个对象可以安全进行访问时，我们需要加同步锁synchronized，保证对象的在使用时的正确性。synchronized就是一种独占锁，它会导致所有需要此锁的线程挂起，等待锁的释放。

加锁会导致一下问题：

加多线程竞争下，加锁和释放锁会导致较多的上下文切换，引起性能问题。
多线程可以导致死锁的问题。
多线程持有的锁会导致其他需要此锁的线程挂起。

乐观锁（如CAS）的思想却是不加锁，那不加锁如何确保某一变量的操作没有被其他线程修改过？

这里就需要CAS操作（CompareAndSwap）来实现。CAS有三个操作参数：内存地址，期望值，要修改的新值，当期望值和内存当中的值进行比较不相等的时候，表示内存中的值已经被别线程改动过，这时候失败返回，只有相等时，才会将内存中的值改为新的值，并返回成功。

上面已经提到在Java中sun.misc.Unsafe提供了compareAndSwap系列函数用于实现CAS操作，具体地，在JVM中的CAS操作就是基于处理器的CMPXCHG汇编指令实现的，因此，JVM中的CAS的原子性是处理器保障的。

这里我们可以看一下JAVA的原子类AtomicLong.getAndIncrement()的实现，来理解一下CAS这一乐观锁（JDK 1.8）

public final long getAndIncrement() {
   return unsafe.getAndAddLong(this, valueOffset, 1L);
}
public final long getAndAddLong(Object var1, long var2, long var4) {
   long var6;
   do {
       var6 = this.getLongVolatile(var1, var2);
   } while(!this.compareAndSwapLong(var1, var2, var6, var6 + var4));
   return var6;
}

可以看到AtomicLong.getAndIncrement()的实现就是通过CAS循环操作的实现，只有期望值与真实值相同情况下，CAS操作才会成功执行，退出循环，如果失败则继续自旋，直到成功。

ABA问题的解决思路是: 每次变量更新的时候把变量的版本号加1，那么A-B-A就会变成A1-B2-A3，只要变量被某一线程修改过，改变量对应的版本号就会发生递增变化，从而解决了ABA问题。在JDK的java.util.concurrent.atomic包中提供了AtomicStampedReference来解决ABA问题，该类的compareAndSet是该类的核心方法，实现如下：

public boolean compareAndSet(V expectedReference, V newReference, int expectedStamp, int newStamp) {
   Pair<V> current = pair;
   return expectedReference == current.reference && expectedStamp == current.stamp &&
       ((newReference == current.reference && newStamp == current.stamp) || 
        casPair(current, Pair.of(newReference, newStamp)));
}

可以发现，该类检查了当前引用与当前标志是否与预期相同，如果全部相等，才会以原子方式将该引用和该标志的值设为新的更新值，这样CAS操作中的比较就不依赖于变量的值了。

临风博客

Simply Understanding Compare-And-Swap

Simply Understanding Compare-And-Swap

0x00. TOC

0x01. 简介

0x02. 应用

0x03. ABA问题

0x04. 实现

0x05. Java中的CAS

0x06. 参考