比較並交換與取值並相加

兩個原子操作扛起了無鎖程式碼的大部分重活。第一個，取值並相加（fetch-and-add），是簡單的那個：原子地把一個值加到變數上，並回傳它原本的值，全在一個不可分割的步驟裡。它正是共享計數器所要的——每個執行緒的加一都落得到、一個也不丟，而且不用鎖。第二個，比較並交換（CAS），是聰明的那個，也是幾乎所有無鎖演算法的基石。

比較並交換接收三樣東西：一個記憶體位置、一個期望值、一個新值。它原子地檢查「這個位置是否仍存著期望值？若是，就把它換成新值並回報成功；若否，就什麼都不改、回報失敗（通常回傳它實際找到的值）」。威力就在「若它沒被改過」這部分：一個執行緒讀取目前的值、算出新值應該是多少，然後用 CAS——只有在此期間沒有別的執行緒改過這個位置時——才裝上新值。若另一個執行緒偷偷插隊，CAS 就失敗，於是你迴圈：重讀、重算、重試。這個「讀取-計算-CAS-重試」迴圈是樂觀並行的心跳——你假設沒有衝突，若你錯了，CAS 會逮到你。取值並相加可看成純加法情形下一個「特化、永遠成功」的手足。

這兩個原語正是無鎖程式設計得以可能的原因：與其拿鎖來安全地改動，執行緒準備好改動，只在世界沒在它腳下挪動過時，才用 CAS 原子地提交它。它們在現代硬體上是單一 CPU 指令（x86 的 cmpxchg、ARM 與其他平台的「載入連結／條件儲存」配對）。要誠實地點名一個微妙的隱患：ABA 問題——在你讀取與你 CAS 之間，值可能從 A 變成 B、又變回 A，於是 CAS 看到期望的 A 便成功，儘管世界底下其實確實變過了。真實的無鎖程式碼用版本標記或危險指標來防範 ABA；完整處理屬於第二卷的無鎖程式設計。