比較並交換

比較並交換(compare and swap, CAS)，是原子操作的一種，可用於在多執行緒編程中實現不被打斷的數據交換操作，從而避免多執行緒同時改寫某一數據時由於執行順序不確定性以及中斷的不可預知性產生的數據不一致問題。 該操作通過將內存中的值與指定數據進行比較，當數值一樣時將內存中的數據替換為新的值。

概述

一個CAS操作等價於以下c代碼的原子實現:

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

在使用上，通常會記錄下某塊內存中的舊值，通過對舊值進行一系列的操作後得到新值，然後通過CAS操作將新值與舊值進行交換。如果這塊內存的值在這期間內沒被修改過，則舊值會與內存中的數據相同，這時CAS操作將會成功執行 使內存中的數據變為新值。如果內存中的值在這期間內被修改過，則一般來說舊值會與內存中的數據不同，這時CAS操作將會失敗，新值將不會被寫入內存。

應用

在應用中CAS可以用於實現無鎖資料結構，常見的有無鎖隊列（先入先出） 以及無鎖棧（先入後出）。對於可在任意位置插入數據的鍊表以及雙向鍊表，實現無鎖操作的難度較大。

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前綴來鎖定系統匯流排，使系統匯流排在彙編指令執行時無法訪問相應的內存地址。而各個編譯器根據這個特點實現了各自的原子操作函數。

• C語言，C11的頭文件<stdatomic.h>。由GNU提供了對應的__sync系列函數完成原子操作。
• C++11，STL提供了atomic系列函數。
• JAVA，sun.misc.Unsafe提供了compareAndSwap系列函數。
• C#，通過Interlocked方法實現。
• Go， 通過import "sync/atomic"包實現。
• Windows，通過Windows API實現了InterlockedCompareExchangeXYZ系列函數。