一間麵包店、一張架子，兩種速度
在上一個階梯，你學到了「共享」的危險（競爭條件），以及馴服它的那一族工具：互斥、鎖、號誌，還有監督程式。那些是並行的文法。現在我們要讀整句話了——也就是每位系統程式設計師都熟記於心的那些經典問題，它們展示出那些工具究竟是拿來做什麼用的。第一個、也是最重要的一個，就是生產者與消費者問題，而它的畫面是一間麵包店。後場裡，麵包師傅不斷把剛出爐的麵包從烤箱裡拿出來、擺到一張架子上。前台這頭，客人不斷把麵包從那張架子上取走。兩邊誰都不看著對方；中間這張架子讓他們不必協調每一個動作就能合作。
這種「解耦」正是全部的重點所在。師傅是生產者：它製造物品、把物品放到某處。客人是消費者：他們取走物品、加以使用。要把兩者分開的原因在於：他們以不同、且不斷變動的速度在運作。師傅可以一次端出一整盤十二個；下一位客人卻可能慢吞吞。如果他們必須一個一個直接交接，動作快的那一方就會不斷閒著、等動作慢的那一方。架子吸收了這種落差，於是每一邊都能時而衝在前頭、時而落在後面，而另一邊渾然不覺——前提是，那張架子本身被妥善管理。
架子是有大小的：有界緩衝區
中間那張架子就是有界緩衝區（bounded buffer），而「有界」這個詞正是關鍵所在。這張架子最多容納 N 個麵包——絕不會更多。你或許會問：那為什麼不乾脆用一個無止盡長大的堆（無界緩衝區）就好？這個「界限」是一項特性，不是該道歉的缺陷。如果生產者能永遠跑得比消費者快、而緩衝區又毫無上限地長大，你的程式終究會把記憶體全部吃光、被系統砍掉。固定大小保證這不會發生：當架子滿了，生產者就會被迫等待。這個界限施加了「反壓」，溫和地逼迫一個失控的生產者，把速度降到消費者能持續承受的水準。
在程式碼裡，有界緩衝區通常是一個環狀（ring）緩衝區：一個固定大小、有 N 個槽位的陣列，搭配兩個索引——一個是寫入下一個物品的 in 位置、一個是讀取下一個物品的 out 位置，兩者都會前進、並在走到陣列末端時繞回開頭。當 in 等於 out 時緩衝區是空的，而當 in 再前進一步就會撞上 out 時則是滿的。但這裡有個誠實的提醒：光是這樣，它只是一個陣列加兩個整數——它「並不是」執行緒安全的。唯有當我們替它套上同步機制，它才會成為一個正確的並行元件。資料結構是容易的部分；協調，才是整個問題的所在。
同步機制究竟必須保護什麼？用一個並行不變式（concurrency invariant）來思考——也就是一個關於資料、必須永遠為真的承諾。這裡的不變式很簡單：架子上物品的數量始終介於 0 與 N 之間，而且它等於實際存放的物品數。生產者在寫入某個槽位、並把計數加一的那一瞬間，會暫時打破這個承諾；消費者在讀取某個槽位、並把計數減一時也一樣。我們的全部工作，就是確保在那些瞬間裡，沒有任何別的執行緒能偷看，而且確保沒有人會試圖往一張滿了的架子上加東西、或從一張空的架子上拿東西。
一次加一個號誌，把解法搭起來
經典的正確解法用到三件同步工具，而美妙之處在於：每一件都回答了一個顯而易見的問題。第一個問題：生產者怎麼知道還有空位？我們用一個叫 empty 的計數號誌（counting semaphore），它從 N 開始，計算空閒的槽位數。回想上一個階梯：計數號誌不過是一個整數，配上兩個原子操作——wait(S) 把它減一，若會減到負數則讓呼叫者阻塞；signal(S) 把它加一，並喚醒一個等待者。於是生產者在插入之前先做 wait(empty)：如果架子滿了（empty 已歸零），生產者就直接阻塞——這正是我們想要的反壓。不必忙碌等待、不必空轉——它會睡著，直到有槽位空出來。
第二個問題：消費者怎麼知道有東西可拿？我們用一個叫 full 的第二個計數號誌如法炮製，它從 0 開始，計算已填滿的槽位數。消費者在移除之前先做 wait(full)：如果架子是空的（full 為 0），消費者就阻塞，直到某個生產者發出信號。而這兩個號誌會漂亮地彼此交棒。生產者插入之後，會做 signal(full)——告訴消費者「現在多了一個東西可以吃」。消費者移除之後，會做 signal(empty)——告訴生產者「現在多了一個空槽位」。這兩個計數器加起來永遠等於 N，而它們讓每一邊都恰好等待著正確的那個條件。
第三個問題——而這正是初學者會忘掉的那個：就算「確實」有空位、也「確實」有物品，兩個生產者仍可能同時試圖寫入同一個槽位，在 in 索引和計數上互相競爭。empty 與 full 號誌保證的是「可用性」，但它們「並不」保證同一時間只有一條執行緒碰觸緩衝區的內部。所以我們加上第三件工具：一個 mutex（一個初始值為 1 的二元號誌），把真正的插入或移除動作包起來，讓我們對架子的記帳取得互斥。三件工具、三項工作：empty 配給空間、full 配給可用物品，而 mutex 保護資料結構本身。
PRODUCER CONSUMER
-------- --------
wait(empty) // need a slot wait(full) // need an item
wait(mutex) // lock the shelf wait(mutex) // lock the shelf
... put item into buffer ... ... take item from buffer ...
signal(mutex) // unlock signal(mutex) // unlock
signal(full) // +1 item ready signal(empty) // +1 free slot
empty starts at N (free slots)
full starts at 0 (filled slots)
mutex starts at 1 (the shelf lock)兩個 wait 的順序不是小細節
請仔細盯著那張草圖裡的順序，因為對調兩行，就能把一個正確的程式變成一個會永遠凍結的程式。生產者先做 wait(empty)、「然後」才做 wait(mutex)。假設一個粗心的程式設計師把它們對調：先 wait(mutex)、再 wait(empty)。現在想像緩衝區是滿的。一個生產者搶到了 mutex（鎖住了架子），接著呼叫 wait(empty)——而這會阻塞，因為沒有空閒槽位。它現在「握著鎖睡著了」。這時一個消費者過來，想移除一個物品、空出一個槽位，但要這麼做，它必須先取得 mutex……而那把鎖正握在睡著的生產者手上，而且永遠不會被釋放。兩邊永遠互相等待。這就是教科書級的死結（deadlock）。
這個教訓遠遠超出這一個例子：當你必須同時持有不只一把鎖時，你取得它們的順序是承重的關鍵。這裡的安全紀律是「先計數、後上鎖」——在你搶下對共用結構的獨佔鎖「之前」，先確保自己有權繼續（有一個空槽位、或有一個可用的物品），而且絕不要握著 mutex 睡著。如果你只在「已經知道自己能跑完」之後才取 mutex，你持有它的時間就會盡可能地短，也絕不會在你自己卡著、等別的東西時，把另一條執行緒擋在門外。
同一個想法，更安全地表達
號誌解法很優雅，但它也很脆弱——我們應該對此誠實。一個號誌唯有在「每一個」生產者和「每一個」消費者，都以完全正確的順序執行完全正確的 wait 與 signal 時，才保護得了緩衝區。漏掉一次 signal(empty)，槽位就會一點一點地洩漏掉，直到一切卡死；對調兩個 wait，你就死結；對錯誤的號誌發信號，不變式就會悄悄腐爛。號誌是赤裸的；正確性完全活在程式設計師的紀律裡，散落在每一條執行緒之中。這就是為什麼較高階的語言與函式庫，通常會用一個更安全的外殼來提供同一個模式。
更高階的表達方式，是用一個監督程式搭配條件變數（condition variable）。mutex 變成了監督程式自動上的那把鎖——進入緩衝區的插入或移除方法時就取得它、離開時就釋放它，於是你「忘不了」。在原本生產者會卡在 wait(empty) 的地方，它改為在那個已上鎖的方法「裡面」，對一個叫 notFull 的條件變數做 wait；條件變數會「原子地」釋放鎖並睡著，然後在醒來時重新取回鎖。移除了一個物品的消費者，會對 notFull 做 signal，去喚醒一個等待中的生產者；插入了物品的生產者，則對 notEmpty 做 signal。這個結構與號誌解法如出一轍，但鎖是替你管理的，而等待則直接綁在那些有名字的條件上。
為什麼這一個模式無所不在
一旦你學會看出生產者與消費者的形狀，你就會發現它幾乎藏在每一個並行系統裡。一台網頁伺服器有一條接收執行緒（生產者），它收下進來的連線、丟進一個佇列，而一池工作執行緒（消費者）則把連線取出、加以處理。一套日誌系統把來自眾多執行緒（生產者）的訊息先緩衝起來，再由一條寫入執行緒（消費者）成批地把它們刷寫到磁碟。一個影片播放器會預先把畫格解碼進一個緩衝區，而顯示端則以正確的步調把它們讀出來。每一個都是同一間麵包店：一個快階段與一個慢階段，由一張有界的架子解耦開來。
最為人熟悉的例子，莫過於 Unix 管線。當你輸入像 ls | grep txt 這樣的指令時，shell 會透過一個核心緩衝區，把 ls（生產者，寫出檔名）連到 grep（消費者，讀取並過濾它們），而那個核心緩衝區，正正就是一個有界緩衝區。如果 grep 很慢，緩衝區就填滿，核心便會把 ls 擋住、直到有空間為止——反壓，自動且隱形。其實你每寫一條管線，就在使用一個正確同步好的生產者與消費者佇列，卻從來不必去想任何一個號誌。
這就是這篇導覽真正的教訓，也是通往本階梯其餘部分的橋樑。生產者與消費者問題不是一道謎題；它是一面鏡頭。它教你認出「任何兩方以不同速度合作」的情形，並伸手去拿一個有界緩衝區、加上正確的同步機制。接下來我們會遇見另外兩道經典謎題——讀者與寫者問題、以及哲學家用餐問題——它們把這同一批工具往新的方向拉伸，並揭露它們會出錯的新方式，包括你必須時時防範的飢餓與死結。