比较并交换

一个CAS操作的过程可以用以下c代码表示: ^[1]

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

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

应用

在应用中CAS可以用于实现无锁数据结构，常见的有无锁队列（先入先出）^[3] 以及无锁栈（先入后出）。对于可在任意位置插入数据的链表以及双向链表，实现无锁操作的难度较大。^[4]

ABA问题

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

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

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

   top
    |
    V   
  0x0014
| Node A | --> |  Node X | --> ……

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

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

而进程P2在执行CAS操作之前打断了P1，并对栈进行了一系列的pop和push操作，使栈变为如下结构：

   top
    |
    V  
  0x0014
| Node C | --> | Node B | --> |  Node X | --> ……

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

这时P1又开始继续运行，在执行CAS操作时，由于top依旧指向的是NodeA的地址(实际上已经变为NodeC)，因此将top的值修改为了NodeX，这时栈结构如下：

                                   top
                                    |
   0x0014                           V
 | Node C | --> | Node B | --> |  Node X | --> ……

经过CAS操作后，top指针错误地指向了NodeX而不是NodeB。

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

• C语言，C11的头文件<stdatomic.h>。由GNU提供了对应的__sync系列函数完成原子操作。 ^[6][7]
• C++11，STL提供了atomic系列函数。^[8][7]
• JAVA，sun.misc.Unsafe提供了compareAndSwap系列函数。^[9]
• C#，通过Interlocked方法实现。^[10]
• Go， 通过import "sync/atomic"包实现。^[11]
• Windows，通过Windows API实现了InterlockedCompareExchangeXYZ系列函数。^[12][7]