當「共享」不對稱時
上一篇導覽裡的生產者與消費者問題，把每個人都一視同仁：每一條執行緒都會碰觸架子，所以在每一次存取外面套上單一一把 互斥鎖，是正確的想法。但很多真實資料被「讀」的次數，遠遠多於被「改」的次數。想像一座車站裡牆上掛的列車時刻表。一百個旅客可以同時站在它前面讀，毫無問題——他們彼此並不干擾，因為「讀」並不改變任何東西。唯一危險的時刻，是有一位工人爬上去重漆某個出發時間的時候。當那位工人正塗到一半時，誰都不該在讀（他們可能看到一半舊時間、一半新時間），也不該有第二位工人在漆同一塊板子。
這就是讀者-寫者問題（readers-writers problem），而整件事的重點在於：這兩種存取並不對稱。讀者與其他讀者並不衝突，所以像一把普通互斥鎖那樣，逼他們一次只能一個、輪流進場，會很浪費。寫者卻與所有人都衝突——與其他寫者、也與讀者都衝突。所以我們真正要的規則是：可以同時有「任意多個」讀者在裡面，「或者」恰好有「一個」寫者單獨在裡面，但絕不會兩者同時。讓眾多讀者同時共享，是「加速」；保證寫者「完全獨佔」，則是「安全」。
第一種解法——以及那個餓死的寫者
教科書上的「讀者優先」解法很巧妙，值得追蹤一遍。我們維護一個計數器 readcount，記錄目前有幾個讀者在裡面，由它自己的一把小互斥鎖看守。關鍵在於：只有「第一個」到的讀者，才會對第二個叫 rw 的號誌（寫者也必須持有的那一個）做 wait；也只有「最後一個」離開的讀者，才會對它做 signal。於是一整群讀者之間，總共只取得那把擋住寫者的鎖「一次」，而任何在別人已經在裡面時才到的讀者，只要把計數器加一、就直接走進去。相對地，每一個寫者都必須單獨搶下 rw，而在場的一群讀者正把它鎖死。
READER WRITER
------ ------
wait(mutex) wait(rw) // exclusive
readcount += 1 ... write the data ...
if readcount == 1: wait(rw) signal(rw)
signal(mutex)
... read the data ... mutex starts at 1
wait(mutex) rw starts at 1
readcount -= 1 readcount starts at 0
if readcount == 0: signal(rw)
signal(mutex)現在請再讀一次最後那句話，因為它藏著一個嚴重的瑕疵。只要永遠至少有一個讀者在裡面，readcount 就永遠不會降回零，rw 就永遠不會被釋放，於是一個等待中的寫者就永遠等下去。在一個讀多的系統裡，這並非空談——在前一群讀者還沒完全清空之前，就有一個新讀者到了，於是寫者被無限期地擋在門外。這就是寫者飢餓（writer starvation）：一條已經就緒、也有能力執行的執行緒，卻不斷被其他執行緒超車。回想排程階梯裡的飢餓——這裡是同一種病，起因於我們的政策，而不是任何死結。整個系統「有」在前進；只是某一條倒楣的執行緒，永遠輪不到。
用「公平」來治飢餓
解法是：不要再讓讀者自動享有優先權。一種「寫者優先」的變體，把偏向反過來：一旦有寫者在等，新到的讀者就被排到它後面，於是當目前的讀者清空時，寫者立刻就能進去。但這只是把飢餓搬到讀者身上、發生在寫多的爆量時段。真正公平的修法是一道「閘門」：在整個入口前面放一個額外的號誌，每一個新來者——不論讀者或寫者——都必須一次一個地通過它。因為它保住了「到達順序」，一個到了的寫者就絕不會被晚於它才來的讀者插隊，而早已通過閘門的一串讀者，仍然能在裡面開心地共享。
請留意這個更深的想法，因為它在作業系統裡反覆出現：飢餓幾乎總是靠「引入公平」來治，而公平通常意味著尊重到達順序，或更廣義地說，有界等待（bounded waiting）——一個保證：一旦你提出請求，在輪到你之前，最多只有有限個其他人能先過。這跟 CPU 排程裡的老化（aging）是完全一樣的招數：一份工作等得越久，它的有效優先權就慢慢升高，於是它不會被永遠忽略。每當一個設計讓某一類請求得以無限期超車另一類時，就去找一個替「任何人被跳過多久」設下上限的公平機制。
五位哲學家、五支叉子、一場災難
第二道大謎題是哲學家用餐問題（dining philosophers），它是死結的經典畫面。五位哲學家圍坐在一張圓桌旁。每一對相鄰的人之間，擺著一支叉子——五個人共五支叉子。一位哲學家永遠只做兩件事：思考，與用餐。要吃那（滑溜溜的）義大利麵，一位哲學家需要「同時」拿到左手邊和右手邊「兩支」叉子。最自然、最顯而易見的程式碼是：拿起左叉，再拿起右叉，吃，然後把兩支都放下。每一支叉子都是一項共用資源——把它建模成一把互斥鎖、或一個二元號誌，每支叉子一個。
災難就在這裡。假設五位哲學家在同一瞬間都餓了，於是每個人都拿起自己左手邊的叉子。現在桌上每一支叉子都被握著，而每一位哲學家都坐在那裡握著一支叉子，等著他右手邊的那支——而那支正是他鄰居「左手邊」的叉子，那位鄰居同樣在等、而且永遠不會放手。沒有人能吃、沒有人會放下叉子，整張桌子就永遠凍結。這是一個你親眼就能看見的死結：一個完美的「等待之環」。
打破那個環：解法們
這裡正是死結階梯那套抽象理論派上用場的地方。回想：一個死結需要四個必要條件「全部」同時成立：互斥、持有並等待、不可搶佔、以及循環等待。它們是「一起」才必要的，這是天大的好消息——你不必把四個全修好。只要打破「任何一個」，死結就變得不可能。哲學家用餐問題正是檢驗這件事的完美實驗室，因為每一種經典解法，都對應著攻擊其中一個特定的條件。
- 限制用餐人數：一次最多只允許四位哲學家上桌（用一個從 4 開始的計數號誌）。只要有一個空位，就一定至少有一位哲學家能拿到兩支叉子。這招攻擊的是「持有並等待」，做法是確保所有資源永遠不會被同時佔滿。
- 要嘛兩支都拿、要嘛一支都不拿：一位哲學家在單一一個臨界區間內「原子地」取得這一對叉子，唯有兩支都空著時才兩支一起拿、否則一支都不拿。這直接禁止了「持有並等待」——你絕不會握著一支、卻在等另一支。
- 用一個全域的叉子順序來打破對稱：把叉子編號，並要求每一位哲學家都「先」拿編號較小的那支。如此一來，某位哲學家「第一」就去搶的那支叉子，正是他鄰居「第二」才會去搶的，於是那個循環等待就無法閉合。這正正就是鎖定順序（lock ordering）。
鎖定順序這個解法是最該內化的一個，因為它能推廣到你日後寫的「每一個」多鎖程式。這個死結源自一個循環等待（circular wait）：一個環，環上每一條執行緒都握著下一條所需要的資源。如果每一條執行緒都「永遠」以相同的全域順序去取得鎖，你就「根本」無法形成一個環——形成環需要某條執行緒在取得編號較小的鎖之前先取得編號較大的，而這正是規則所禁止的。整個對稱的環之所以被打破，是因為在一致的順序下，至少有一位哲學家（左叉編號較大的那一位）拿叉子的次序，跟其他所有人相反。
這些謎題真正在教的事
退一步，看看這些玩具故事究竟把什麼鑽進了你腦袋。讀者-寫者問題教你：並非所有共享存取都一樣，而且一個「正確」的解法，若餓死了一整類執行緒，仍然可能是個「壞」解法——正確性與公平性，是你必須各自獨立檢查的兩個不同目標。哲學家用餐問題教你：死結並不神祕，它就是那四個條件，而你靠「精準地打破其中一個」來擊敗它，通常是用一致的鎖定順序。它有個近親，理髮師睡覺問題（sleeping barber），把同一套機制換到另一個場景——一位沒客人時就睡著的理髮師、以及在所有候位椅都坐滿時就離開的客人——來反覆操練「喚醒某人」這個交棒動作，且不弄丟任何一次通知。
不過，對於真實世界如何處理死結，得誠實一點。哲學家用餐問題的解法顯示「預防」是辦得到的，但那些笨重的執行期替代方案——在等待圖裡偵測環、並中止犧牲者，或執行銀行家演算法以避開不安全狀態——既昂貴、又需要事先知道資源的需求量。所以大多數通用作業系統，悄悄採用的是鴕鳥演算法（ostrich algorithm）：它們乾脆完全忽略死結，賭它罕見到「重開機」比「預防它所需的機制」還便宜。那不是偷懶；那是一個真實的工程取捨，被誠實地命名了。你靠鎖定順序之類的紀律，在自己的程式碼裡預防死結，並接受一件事：底下的作業系統，多半不會來救你。
到目前為止，本階梯裡的每一件工具——號誌、互斥鎖、條件變數——都是一把「鎖」：一種讓執行緒輪流的方式。它們很強大，卻很脆弱，正如寫者飢餓和哲學家之環都展示過的。下一篇導覽，我們會徹底走到鎖的「外面」，去看原子操作與比較並交換（compare-and-swap）迴圈，以及那些讓執行緒在「沒有任何人持有任何鎖」的情況下仍能前進的無鎖資料結構——一種馴服同一批共用資料的、不同而令人驚訝的方式。