上一篇導覽把我們困在哪裡
在第 2 篇導覽裡，你認識了臨界區間——那段會動到共享資料的短程式碼——以及任何解法都必須遵守的三條規則：互斥（同一時間至多一條執行緒在裡面）、進展（若沒人在裡面，想進去的人就進得去）、有限等待（沒有人會永遠等下去）。你也認識了 Peterson 解法，它只用對兩個共享變數的普通讀寫，就同時滿足了這三條。問題既然解決了——那為什麼還要整整一篇導覽來講硬體？
兩個誠實的理由。第一，Peterson 解法是為剛好兩條執行緒打造的；要推廣到 N 條執行緒既彆扭又通常不值得。第二，而且遠更令人不安的是，它在真實 CPU 上可能悄悄失效。Peterson 整套正確性論證都假設：當一條執行緒先寫下自己的旗標、再去讀另一條執行緒的旗標時，這些操作真的依那個順序發生，而且另一條執行緒看得到那次寫入。在現代處理器上，這兩個假設預設都不安全——而這道裂縫，正是這篇導覽的起點。
那道裂縫：CPU 會把你的記憶體存取重新排序
這是每個人都會被咬一次的驚奇。為了跑得快，一個 CPU 核心不一定會照你寫下的順序執行你的記憶體讀寫。一次寫入可能會先在每核心的緩衝區裡待上一陣子，才對其他核心變得可見；而編譯器與處理器在那些操作於單一執行緒看來無害時，可能把彼此獨立的讀寫重新排序。在單一執行緒上這是看不見的——核心會維持「一切都照順序執行」的錯覺。但跨越兩條共享記憶體的執行緒時，這個錯覺就碎了：執行緒 A 對自己旗標的寫入，可能在執行緒 B 去讀它的時候還躲在緩衝區裡，於是 B 看到舊值，兩條執行緒就一起翩然走進臨界區間。這一整套關於「一個核心能看到另一個核心多少寫入」的規則，就是機器的記憶體一致性模型。
解法是在恰恰好的位置告訴硬體：別跨越這裡重新排序。那條指令就是記憶體屏障（也叫圍籬）：它強迫在它之前發出的每一個記憶體操作都完成並變得可見之後，它之後的任何操作才能繼續進行。想像演唱會的一道旋轉閘門，它會把一個區段完全清空，才放下一批人進來——沒有東西能亂序溜過去。正確的無鎖程式碼裡灑滿了屏障，正確的 Peterson 解法也是，它需要在「寫下自己的旗標」與「讀取鄰居的旗標」之間放一道屏障。哪些重新排序被允許、哪些被禁止，這套通則就是記憶體排序，把它搞錯，得到的會是你一想細看就立刻消失的臭蟲。
一條一次做兩件事的指令
回想第 1 篇導覽裡 count++ 為何會競爭：它是三個分開的步驟（讀取、相加、寫回），另一條執行緒可以插進這幾步之間。根治之道，是讓「讀取與寫回」成為一個不可分割的步驟——一個原子操作，這裡的原子性意思是它要嘛完整發生、要嘛完全不發生，沒有任何其他核心能觀察到的中間狀態。你無法用普通指令拼出這種東西，所以每顆現代 CPU 都至少提供一條硬體本身保證會原子執行的特殊指令。其中兩條最有名。第一條是 測試並設定：在一個不可打斷的步驟裡，它讀出一個記憶體字、回傳它的舊值、再把 1 存進去。想像一間單人廁所，門上的牌子在你查看它是否空著的那一瞬間就翻成「使用中」——你在同一個動作裡既得知了舊狀態、又佔下了它，所以兩個人絕不可能同時都以為它是空的。
第二條，也是現代系統的主力，是 比較並交換（CAS）。它會原子地做這件事：看一個記憶體位置；如果它仍然存著我預期的值，就把它換成我的新值；無論如何，都告訴我那裡原本實際是什麼。那個帶條件的轉折正是它如此強大之處。你讀出一個值、算出一個新值，再請 CAS「只在這期間沒人改過這個值時」才裝上你的更新——若有人改了，CAS 就失敗，你重試一次即可。這個樂觀的迴圈，是無鎖資料結構的基礎，在那裡執行緒完全不用鎖就能往前推進。這兩者都是 原子操作的一種，而關鍵在於，每一條都附帶了普通讀寫所缺的記憶體排序保證，所以上一節那個屏障的煩惱，已經替你處理好了。
// build a lock from test-and-set (locked = 0 means free)
acquire(lock):
while test_and_set(lock) == 1: // was it already 1?
; do nothing, just loop // yes -> someone holds it, spin
// test_and_set returned 0 -> it WAS free, and we just set it to 1.
// we now hold the lock; fall through into the critical section.
release(lock):
lock = 0 // put the sign back to FREE從一條原始指令到你能用的互斥鎖
把一條原子指令包進上面那組 acquire/release，你就發明了互斥鎖——mutual exclusion（互斥）的縮寫。它的約定很簡單，也正是你真正會去用的日常工具：在臨界區間之前你呼叫 acquire（常叫做 lock），在它之後你呼叫 release（unlock）；這把鎖保證同一時間只有一條執行緒持有它。注意，這終於對任意數量的執行緒都乾淨地滿足了臨界區間的三條規則，而那些醜陋的記憶體排序細節，被封進鎖的實作裡，由一位專家一次處理掉了。這就是整個階梯的回報：你不再需要對旗標與屏障動腦筋，只要把臨界區間用 lock 和 unlock 框起來就好。
但一條發現鎖已被佔走的執行緒，究竟該怎麼等？有兩種策略，而兩者的差別關係重大。我們上面寫的那個版本就只是不斷迴圈、一遍遍重新檢查那把鎖——那是一把自旋鎖，那個迴圈就是忙碌等待。等待者全程都醒著，燒著一個 CPU 核心，卻只用來不停問「到了沒、到了沒」。這聽起來很浪費，而在單一核心上更是災難：自旋的人無法推進，還霸佔著持鎖者也許正需要拿來跑完並釋放的那個核心。自旋鎖只在「預期的等待時間比睡著再醒來的成本還短」時才划算——這正是多處理器上核心內部的情境，那裡持鎖者正跑在另一個核心上、會在幾奈秒內釋放。
另一種選擇是阻塞鎖。當一條執行緒拿不到鎖時，它不自旋，而是請作業系統讓它睡著——移出 CPU、移出執行佇列——排程器就改去跑些有用的東西。等鎖被釋放時，作業系統喚醒一個等待者、讓它重新變回就緒。當等待可能很長時，這是對的選擇，因為一條睡著的執行緒除了佔點記憶體之外什麼都不花。它的代價是睡著與喚醒所需的上下文切換——這筆開銷，你只在「不然等待會比那次切換還久」時才願意付。通用的互斥鎖常把兩者混用：先短暫自旋、盼能迅速得手，若等待拖久了再退回阻塞。
一個誠實的危險：優先權反轉
鎖解決了互斥，但它帶進一個微妙的陷阱，在你把它用在任何攸關時間的場合之前值得先知道：優先權反轉。當一條高優先權執行緒被迫去等一把由低優先權執行緒持有的鎖，而一條與這把鎖毫無關係的中優先權執行緒不斷搶佔那條低的、害它永遠跑不完也釋放不了時，就會發生這件事。結果整個顛倒了：那條重要的執行緒實際上被一條它本該能推開的執行緒擋住，只因為那條中優先權的執行緒卡在中間。這不是假想；它曾經讓 NASA 的火星拓荒者號探測車當機，直到工程師從數百萬公里之外為它打上修補程式。
標準的解法是優先權繼承：當一條低優先權執行緒持有著一條高優先權執行緒正在等的鎖時，持有者就暫時繼承那個高優先權，於是沒有中優先權執行緒能搶佔它——它衝過自己的臨界區間然後釋放。要往後帶著走的教訓比這個修法更廣：鎖不是一個免費、無副作用的黑盒子。它會與排程器互動，要把它用好，就得想想誰在等、等多久、以什麼優先權等。記下這個提醒之後，互斥鎖現在已是你可靠的建構積木——而在下一篇導覽裡，我們會把它推廣成號誌，一個不只能放進一條、而是放進固定數量執行緒的計數器，而且它既能守衛、也能發信號。