比較並交換

維基百科,自由的百科全書
跳至導覽 跳至搜尋

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

概述[編輯]

一個CAS操作的過程可以用以下c代碼表示: [1]

1 int cas(long *addr, long old, long new)
2 {
3     /* Executes atomically. */
4     if(*addr != old)
5         return 0;
6     *addr = new;
7     return 1;
8 }

在使用上,通常會記錄下某塊內存中的舊值,通過對舊值進行一系列的操作後得到新值,然後通過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_prt = 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]

參考資料[編輯]

外部連結[編輯]