為什麼鎖有時反而是問題
在這一整階梯裡，你一直靠鎖與號誌來馴服共享資料：把臨界區間包起來、取得一把互斥鎖，一次只准一條執行緒碰那份資料。這管用，而且多數時候你就該這麼做。但鎖有一個安靜的代價，哲學家用餐問題其實已經暗示過了。當一條執行緒握著鎖時，其他每一條想要它的執行緒都只能等——而如果那位持有者夠倒楣，在更新到一半時被排程器暫停了（它的時間量子用完了，或者一次分頁錯誤把它送去讀磁碟），其他所有人就全卡在一條根本沒在跑的執行緒上。鎖把「一條執行緒的延遲」放大成了「所有執行緒的延遲」。
更糟的是，鎖會招來你已經見過的一整個臭蟲家族——當鎖以相衝突的順序取得時的死結、當低優先級持有者擋住高優先級等待者時的優先級反轉，以及當某條執行緒一再輸掉搶鎖之爭時的餓死。於是一個自然的問題浮現了：執行緒能不能在「完全不持有任何鎖」的情況下，仍正確地更新共享資料？令人意外的答案是：可以——但這需要硬體的幫忙，形式是一條把好幾件事「當成一個不可分割的步驟」來完成的指令。
讓這一切成為可能的那一條指令：比較並交換
回想同步那一階梯最深刻的教訓：競爭條件之所以發生，是因為看似無害的「把計數器加一」其實是三個步驟——讀出值、加一、寫回去——而另一條執行緒可以趁隙插進它們之間。鎖靠著「在這三步期間禁止任何人運行」來修補它。硬體則提供了另一種修法：一個原子操作，把那段危險的動作當成「單一、不可中斷」的一步來做，任何執行緒都絕不可能觀察到它做了一半的狀態。其中最重要的一個，就是比較並交換（CAS）。
CAS 接收三個引數，意思是：「看看這個記憶體位置。如果它還是我預期的那個值，就把它換成我的新值；否則就別動它。然後告訴我，發生的是哪一種。」整個「檢查並替換」是「單一」的原子步驟。為什麼這一招就夠了？因為它讓一條執行緒等於是在說：「只有在沒人趁我背後偷改資料的前提下，我才提交我的更新。」如果真有人改了，CAS 就回報失敗，於是這條執行緒就乾脆重新讀出新鮮的值、再試一次。這個「讀取—修改—CAS—重試」的模式，就是無鎖程式跳動的心臟。
// Atomically add 1 to a shared counter, no lock at all.
// CAS(address, expected, new) returns true on success.
retry:
old = counter // 1. read the current value
new = old + 1 // 2. compute the value we want
if CAS(&counter, old, new): // 3. commit ONLY if unchanged
done // success: nobody slipped in
else:
goto retry // someone changed it: re-read, redo用兩條執行緒搶著把一個值為 5 的計數器加一，來走一遍這個迴圈。兩者都讀到 old = 5、算出 new = 6。執行緒 A 的 CAS 先跑：那個位置還是 5，於是成功，計數器變成 6。執行緒 B 的 CAS 此刻去檢查那個位置——它預期 5，卻發現 6，於是 CAS 失敗，B 無傷地輸掉了這一輪。B 繞回去，讀到新鮮的 6、算出 7，它的 CAS 成功。從頭到尾沒取過任何鎖、沒有任何執行緒擋過另一條，而最終值是正確的 7。請留意這個誠實的隱憂：在激烈競爭下，一條執行緒可能連續輸好幾輪，所以它從不被「擋住」，但也不保證嘗試次數有上限。
無鎖、等待自由，以及它們各自的承諾
前面那個隱憂，正是精確詞彙派上用場的地方。無鎖資料結構保證的是「整個系統」永遠在前進：在每一個時刻，至少有一條執行緒會完成它的操作，即使其他人不斷在 CAS 上失敗、不斷重試。沒有任何單一、被暫停的執行緒能凍結所有人——而這正是鎖本來的那個問題。但它並不對任何「單一」執行緒承諾公平：一條倒楣的執行緒原則上可能連輸很久、重試很久。
等待自由（wait-free）資料結構給出更強的承諾：「每一條」執行緒都會在「它自己」有限的步數內完成操作，無論其他人做什麼。沒有任何執行緒會被餓死、或被迫無止境地重試。對於「必須趕上死線」的即時系統而言，這是個美妙的保證——但它設計起來困難得多，而且在常見情況下往往更慢，所以等待自由的結構較為罕見，僅保留給「那個保證真正要緊」之處。誠實的層級是：阻塞式（用鎖）最容易，無鎖更難也更強，等待自由最難也最強。
ABA 陷阱：當「沒變過」其實是個謊言
CAS 建立在一個其實微妙地不成立的假設上：「如果我讀到的值還在這裡，那就沒有任何重要的東西變過。」但一個值可以變過、又變回去。假設一條執行緒從一個無鎖堆疊的頂端讀到了指標 A，接著被暫停了，而在它沉睡時，另一條執行緒把 A 彈出、再把下一個節點彈出，然後推入一個剛好坐落在「同一個位址 A」的回收節點。我們這條執行緒醒來、跑它的 CAS、看到 A 還在——成功！——於是高高興興地換入了一個「對底下已被徹底重排過的堆疊」的陳舊視角。值是吻合了，但世界並沒有。這就是ABA 問題，得名於那個值經歷了 A、再 B、又變回 A。
- 一條執行緒讀取堆疊頂端、看到節點 A（位在節點 X、再下面是 Y 之上），接著在它的 CAS 之前就被排程器暫停了。
- 另一條執行緒彈出 A、再彈出 X，於是頂端現在是 Y——我們那位沉睡者記得的結構已被掏空。
- A 的記憶體被回收，一個位於「同一個位址 A」的節點又被推回頂端，於是頂端再次讀作 A。
- 沉睡者醒來，它的 CAS（頂端、預期 A、新值 X）成功了，因為 A 吻合——但 X 早已被釋放，於是它把堆疊接到了垃圾上。值吻合了，世界卻沒有。
標準的解法全都歸結為：讓「沒變過」真正意味著我們想要的那件事。一個「帶標籤的指標」（或版本計數器）把一個計數器黏在值上、每次變動就讓它加一，於是「A 配標籤 7」和「A 配標籤 9」不再相等——CAS 現在察覺得到那趟來回。或者，採用安全的記憶體回收機制，例如「危險指標（hazard pointers）」或「讀取—複製—更新」（RCU），它們乾脆保證：只要還有任何執行緒可能正在看著某個節點，它就絕不會被釋放並重用，於是那個位址不會在你腳下被回收掉。更深的教訓令人謙卑：無鎖程式唯有在你不只推理「值」、還推理它們的「整段歷史與記憶體生命週期」時，才會是正確的。
記憶體順序、交易，以及挑選你的工具
這裡還欠一層誠實。在現代的多核機器上，CPU 與編譯器會為了速度而重排記憶體操作，所以一條執行緒「寫入」的順序，未必就是另一條執行緒「看見」的順序——這由機器的記憶體一致性模型所主宰。基於鎖的程式對此是有遮蔽的，因為取得與釋放一把鎖會充當一道記憶體屏障，替你把順序釘牢。無鎖程式則沒有這把傘：你必須親手擺放正確的屏障（常稱作 acquire/release 柵欄），否則你的 CAS 迴圈可以完美地原子，卻仍然以一種錯亂、看似不可能的順序看到鄰居的寫入。這在很大程度上正是為什麼手寫的無鎖程式出了名地難寫對。
正因為「光是推理一次 CAS」就已經這麼精細，人們長久以來都盼望有某種「能組合」的東西——一種能把「一整塊」標記為「全有或全無」的辦法，就像資料庫的交易那樣。那個盼望就是交易式記憶體：你宣告某個區域是原子的，系統便推測性地執行它，如果沒有其他執行緒碰過同一份資料，它就一口氣提交；如果發生了衝突，它就中止並重試，恰如一個被放大到「同時多個位置」的 CAS 迴圈。這是個漂亮的構想，硬體支援也存在，但它帶著真實的侷限——交易可能因你無法掌控的原因而中止，過大的、或碰到 I/O 的交易也塞不進去——所以它是鎖與原子操作的「補充」，而非「取代」。
那麼這把你帶到了哪裡？誠實的預設仍然是鎖：簡單、可組合，而且幾乎在任何地方都夠快。當「無鎖式前進」對某個微小、滾燙的計數器或旗標真的划算時，再去動用裸的原子操作與 CAS 迴圈；而當你在激烈競爭下需要一個並行佇列或映射表時，去動用一個身經百戰的無鎖「函式庫」（而不是你從零自己刻的）。還有，如果一個問題感覺處處都在與「共享、可變的記憶體」搏鬥，那往往是個訊號，提示你或許該乾脆別再共享記憶體了——而那正是下一篇導覽要走的路：執行緒不靠鎖住共享資料來協調，而是靠在一條通道上彼此「傳訊息」。