讓無鎖成為可能的那一道指令
上一篇承諾了一種方法，能在從不持有鎖的情況下協調執行緒，並留下一個誠實的問題：如果沒有任何執行緒能讓其他執行緒停下來，那麼任何一個執行緒究竟要怎麼安全地改變共享狀態？答案是一道單一的硬體操作，叫做比較並交換，幾乎總是寫成 CAS。它是幾乎每一個無鎖演算法的心跳，因此值得精確地理解，而不是大概地理解。
CAS 接受三樣東西：一個位址、一個你預期在那裡找到的值，以及一個你想放進去的新值。它以一個不可分割的步驟檢查那塊記憶體是否仍持有預期值；若是，就寫入新值並回報成功；若否，就什麼也不改、回報失敗，並把它實際找到的值交還給你。整件事的重點就在那個有條件的寫入。你不是盲目地儲存，而是在說「把這個存進去，但前提是自我上次看過之後沒有人在我背後改動它」。因為這個檢查並寫入是一個沒有別的核心能拆開的讀-改-寫，所以兩個執行緒絕不可能同時相信自己贏了。
把它讀成一個不可中斷的步驟：`if (*addr == expected) { *addr = desired; return true; } else return false;`——但整個 if 與儲存被熔成一體，沒有別的核心能在測試與寫入之間穿插。可攜 C 的寫法是 atomic_compare_exchange_weak(&head, &expected, desired)：它回傳真或假，而失敗時它會用實際找到的值改寫你的 expected 變數，這正是下一節那個迴圈所需要的。
重試迴圈：你實際上如何使用 CAS
一次失敗的 CAS 並不是錯誤——它是正常、預期之中的，而且正是這套技巧能運作的根本原因。你幾乎從不只呼叫一次 CAS。你會把它包進一個CAS 重試迴圈：讀取目前的值、算出你想要的新值，然後 CAS。成功就完成；失敗就表示有人搶先了你一步，於是你拿著 CAS 剛交還的新鮮值，對著那個值重新計算，再試一次。這個迴圈是「等待鎖」的無鎖對應物——只是它不阻塞，而是向前自旋、重新嘗試。
具體來說，要原子地遞增一個共享計數器，你會寫：int old = atomic_load(&counter);，接著 while (!atomic_compare_exchange_weak(&counter, &old, old + 1)) ;，迴圈主體留空。每次 CAS 失敗時，那次呼叫都已經把 old 重新載入成目前的值，於是下一次嘗試是拿最新鮮的數字去算 old + 1——而當它終於成功時，計數器恰好移動了一，沒有任何遺失的更新。那個小小的迴圈就是整個模式；所有更花俏的版本，都是同一個形狀，只是中間「計算新值」那一步更有趣罷了。
仔細看為什麼這是無鎖，而不只是聰明。一次 CAS 只有在某個其他執行緒成功時才會失敗——值之所以改變，是因為某個競爭者取得了進展。所以整個系統作為一個整體永不停滯：每一次失敗的嘗試，都是別人勝利的影子。這正是第一篇那條無鎖保證。但要誠實面對它沒有買到的東西：你那個特定的執行緒可能一次又一次地輸掉競賽，而別人不斷地贏，於是一個倒楣的執行緒可能餓死。若在重度爭用下失敗不斷堆積、整個系統來回擺盪卻沒有人完成，你就遇上了活結（livelock）——系統有進展，卻有一個執行緒永遠在空轉。第五篇會回頭談馴服這件事為何真的很難。
CAS 有個手足：載入連結／條件儲存
x86 直接給你 CAS，就是 cmpxchg 指令。但 ARM、RISC-V 與 POWER 走另一條路抵達同一個目標，而當你在手機或伺服器晶片上讀反組譯時，馬上就會遇見它。它是一對指令，叫做載入連結／條件儲存，通常縮寫為 LL/SC。載入連結讀取一個位址，並悄悄告訴硬體開始盯著它。接著條件儲存試圖寫回——但只有在自配對的載入連結以來完全沒有東西碰過那個位址時，才會成功。只要有任何東西碰過，條件儲存就失敗，於是你就迴圈，正如同一次 CAS 重試。
這裡藏著一個深刻而美麗的差異，而它對本篇其餘部分至關重要。CAS 比較的是值：它問「這個數字還是 42 嗎？」LL/SC 盯著的是位置：它問「這個位址到底有沒有被寫過？」這兩個不是同一個問題。一個值可以離開 42 又回到 42，而 CAS 會樂意地認定它沒變。LL/SC 不會——對被盯著的位址的任何一次寫入，哪怕是把舊值還原回去的那一次，都會打斷連結、使條件儲存失敗。記住這個區別；它正是本篇以之命名的整個問題的種子。
ABA 問題：明明什麼都沒變，卻又一切都變了
現在輪到那個陷阱。因為 CAS 只比較值，它會被一個離開又回來的值騙倒。這就是ABA 問題，而這個名字就是整個故事：一個記憶體位置持有 A，你讀到 A，然後在你計算到一半時，另一個執行緒把它改成 B 再改回 A。當你的 CAS 終於執行，它看到 A、與你預期的 A 相符、於是回報成功——但這個世界已不是你當初讀到的那個世界。指標還是同一個數字；它指向的東西可能已經完全不同。CAS 分辨不出「從未改變」與「改了兩次又改回來」的差別。
這個問題經典的咬人之處，是一個無鎖堆疊——就是你會在第三篇建構的Treiber 堆疊。要彈出（pop），一個執行緒讀取頭指標（叫它節點 A）、讀取 A 的 next 欄位找出新的頭，然後把頭從 A 經 CAS 改成那個 next。想像這個執行緒讀到 head = A、打算把 head 設成 A 的 next，然後暫停了。另一個執行緒彈出 A、再彈出它後面那個節點、釋放（free）了 A，接著推入一個全新的節點，而配置器（allocator）恰好把它放在與 A 相同的位址。頭再一次是指標值 A——但 A 如今是一個帶著不同 next 的不同節點。暫停的執行緒醒來，把頭從 A 經 CAS 改成它那個過時、早已不存在的 next 指標，而且成功了。堆疊現在毀壞了，指向已釋放或錯誤的記憶體。
thread 1 (popping) thread 2
---------------------- --------------------------------
old = head; // = A
next = A->next; // = X
... paused ... pop A; pop X; free(A);
push(new); // malloc reuses A's address!
// head == A again, but A->next is now Y
CAS(&head, A, X) // SUCCEEDS — sees A, writes X
// head now points at X, which was freed. corruption.修補 ABA：標記、LL/SC，以及底下更深的問題
最直接的修法，是讓值自己攜帶它的歷史，使得「A 之後又是 A」不再看起來相同。你把指標與一個計數器——一個版本戳記——配成一對，並把這一對當成一個單位去做 CAS。每一次成功的修改都讓計數器加一，於是即使指標回到了 A，計數器也已經從比方說 7 走到了 9，而拿 (A, 7) 對著目前的 (A, 9) 做 CAS 會正確地失敗。這就是標記指標（tagged pointer）或版本指標的把戲。要一次 CAS 兩個字組，容易出現 ABA 的程式碼會動用雙倍寬度的 CAS，例如 x86 的 cmpxchg16b，把指標與計數器一起塞進 16 個位元組。
對計數器把戲有兩個誠實的但書。第一，計數器是有限的：到了 0x7fffffff 就回繞成 0，所以原則上，若恰好有那麼多次修改擠進你的讀取與你的 CAS 之間，ABA 仍可能重演。實務上 32 或 64 位元讓這變得天文數字般地不可能，但「天文數字般地不可能」並不等於「不可能」，誠實的工程師會把它歸檔在已知的限制之下。第二，回想那個手足指令：LL/SC 天生對 ABA 免疫，因為條件儲存對被盯著位址的任何寫入都會失敗，包括「A 又回到 A」在內。這份優雅是真的——但偽性失敗，加上「在載入連結與條件儲存之間你幾乎什麼都不能做」這條規則，讓 LL/SC 自成一種麻煩。
退一步，把整個形狀握在手裡。CAS 是一個有條件、不可分割的寫入——是無鎖演算法賴以組裝的原子。它唯一的盲點是它比較的是值、而非歷史，因此一個回到舊我的值會溜過檢查；那就是 ABA。你可以用版本計數器鈍化 ABA，或用 LL/SC 繞開它，但最深的成因幾乎總是被釋放記憶體的過早重用，而那其實是一個喬裝過的回收問題。把這三個念頭——有條件的寫入、對值的盲視、底下的回收——帶進接下來的篇章，在那裡你終於會建構出這些指令當初為之而生的堆疊與佇列。