從一把鎖，變成一個你能用來計數的計數器
在上一篇導覽裡，你在一個硬體原子指令之上打造出一把互斥鎖，也看見了「空轉燒 CPU 的自旋鎖」和「把等待者放去睡覺的阻塞鎖」之間的差別。一把鎖只回答一個問題：這一樣東西是空的還是被佔走了？這足以保護一段臨界區間，但很多真實的協調需要稍微豐富一點的答案。現在到底有幾台一模一樣的印表機是空的？生產者到底有沒有在緩衝區裡放進任何東西，好讓消費者去拿？由 Edsger Dijkstra 發明的號誌，正是同時回答這些問題的乾淨推廣——而它靠的只是一個整數。
想像一家忙碌餐廳櫃台上那一盤呼叫器。盤子上假設有三個呼叫器。一組客人到了就拿走一個然後走開去等；當一個都不剩時，下一組客人就只能在櫃台旁等，直到有呼叫器被還回來。還回來的客人把呼叫器放回盤子上，如果有人在等，帶位員就能直接把它遞過去。這個盤子從不告訴你誰拿了哪一個呼叫器——它在意的永遠只有「現在還有幾個呼叫器可用」這個數字。號誌正是那個盤子：一個永遠不會掉到零以下的整數，只透過兩個操作來觸碰。
這兩個操作就是 wait 與 signal（Dijkstra 把它們叫做 P 與 V，源自荷蘭文，你在書上仍會看到這兩個字母）。wait(S) 是來要一個呼叫器：它試著拿走一個，於是計數減一；如果計數已經是零，就沒有東西可拿，呼叫者只好等待。signal(S) 是還回一個呼叫器：它把一個還回去，計數加一，而如果有人在等，就喚醒其中一位。這裡有個關鍵的承諾，正是直接承襲自上一篇的硬體成果：這兩個操作各自都是原子地發生——不可分割，沒有別的執行緒能在中途插進來。若沒有這個承諾，計數本身就會遭遇本階梯一開頭講的那種競爭條件。
兩種口味：二元與計數
把號誌分成兩種的唯一差別，就只是計數一開始被允許從多高起算。二元號誌從 1 開始，所以永遠只停在 0 或 1——一個剛好只有一個呼叫器的盤子。這實際上就是一把互斥鎖：wait(S) 是上鎖、signal(S) 是解鎖，一次只有一條執行緒能待在臨界區間裡。計數號誌則從某個大於一的 N 開始——一個有 N 個呼叫器的盤子——並讓最多 N 條執行緒同時通過，直到第 N+1 條必須等待。機制完全一樣，改變的只有那個起始數字。
計數這種口味什麼時候才值回票價？只要你手上有一池好幾個一模一樣、可互換的資源就值得。假設一台列印伺服器擁有三台真正的印表機。把號誌初始化成 3，讓每個工作在列印前做 wait(S)、列印後做 signal(S)，計數就免費替你記帳：前三個工作各把計數往下拉（3、2、1）並平行列印，第四個發現它是 0 就等待，而只要任何一個工作完成並呼叫 signal(S)，計數就回升，等待中的工作便被釋放到剛空出來的那台印表機上。你完全沒寫任何關於「誰拿哪一台」的 if 判斷；計數器和它的兩個原子操作扛起了全部的邏輯。
wait(S): signal(S):
S.count = S.count - 1 S.count = S.count + 1
if S.count < 0: if S.count <= 0:
block this thread wake one blocked thread
(add to S's wait queue) (remove it from S's queue)
(each box runs atomically -- no other thread interleaves inside it)空轉還是睡覺？兩種誠實的實作
當計數歸零時，要讓一條執行緒「等待」有兩種辦法，而它們正是你已經見過的「自旋鎖對阻塞鎖」那個取捨，現在套用到號誌上。簡單的版本用忙碌等待：無法繼續的執行緒坐在一個緊湊的迴圈裡，一遍又一遍地檢查計數，就像一個人站在櫃台旁不停問「有呼叫器了嗎？有呼叫器了嗎？」這會浪費一個 CPU 核心去做沒用的事，只有在預期等待極短（幾個指令）時才勉強可接受——因為那時去睡覺一趟的成本，反而比等待本身還大。
成熟的版本是阻塞。無法繼續的執行緒不空轉，而是把自己整個從 CPU 上拿下來：它把自己的狀態改成等待、加入掛在號誌底下的一個佇列、然後請排程器去跑別的東西。這正是為什麼上面草圖裡的計數被允許變成負數——計數 -2 代表盤子空了，而且有兩條執行緒睡在它背後的佇列裡。稍後，signal(S) 做相反的事：它把計數加一，如果計數仍是零或更低，就從佇列挑一個沉睡者，把它移回就緒佇列，好讓排程器去跑它。等待時不燒任何 CPU；代價是那兩次上下文切換的小小開銷（睡下去、醒過來）。
用計數來發信號：生產者與消費者
到目前為止，號誌一直在守護存取。它另一個同樣重要的工作是發信號：一條執行緒告訴另一條「某個事件發生了」。這方面的經典舞台是生產者—消費者問題。一條或多條生產者執行緒把項目放進一個共享、固定大小的緩衝區；一條或多條消費者執行緒把項目取出。等待時有兩件事可能出錯：緩衝區滿了時生產者應該暫停（沒有空槽可填），緩衝區空了時消費者應該暫停（沒有項目可取）。注意這是兩個不同的計數，所以我們用兩個分開的計數號誌。
讓 empty 從 N 開始（緩衝區有 N 個槽，一開始全空），讓 full 從 0 開始（還沒有項目）。生產者做 wait(empty) 來搶一個空槽——這會把 empty 計數減一，若一個都沒有就阻塞——接著把項目放進去，然後做 signal(full) 宣告又多了一個項目就緒，這可能喚醒一條沉睡的消費者。消費者完全對稱地反過來：wait(full) 來搶一個項目（緩衝區空時阻塞），把它取出，然後 signal(empty) 宣告剛空出一個槽，這可能喚醒一條沉睡的生產者。兩個計數一呼一吸地相互應和，而一條原本會無謂空轉的執行緒，就只是被放去睡覺，直到那個相應的事件到來。
誠實的限制：一把不會自我檢查的利刃
號誌之所以強大，正因為它如此沒有結構——而這也正是它的危險。它只有在「每一條執行緒都同意：碰資料前一定呼叫 wait、碰完後一定呼叫 signal，每一次都不例外」時，才能保護共享資料。編譯器不會強制這件事；號誌根本不知道它該守護的是哪些變數。只要有一條執行緒沒呼叫 wait 就去讀共享資料，它就直接繞過了守衛，把競爭條件帶了回來，而這種臭蟲會時有時無、找起來令人抓狂。號誌是一個人人都必須遵守的約定，而不是一道能擋住擅闖者的牆。
這些錯誤既容易犯、也容易想像。忘了配對的 signal（或走了一條提早返回的路徑而跳過它），計數就再也回不來了——一個離開後再也沒被還回來的呼叫器——於是遲早所有等待的人都永遠卡住。不小心把兩個呼叫對調、先 signal 再 wait，你就可能讓兩條執行緒同時進入一個一次只准一人的臨界區間，悄悄地破壞了互斥，卻連一句錯誤訊息都沒有。兩條執行緒各握著一個號誌、又各自在等對方的那個，這又是教科書級的死結。這些都不會發出警報；程式就只是當住，或者把資料弄壞。
還有一個陷阱跟你程式碼裡的錯誤毫無關係。假設一條低優先權的執行緒握著一個高優先權執行緒此刻需要的號誌。高優先權執行緒阻塞了、客氣地等著——但源源不絕的中優先權執行緒不斷搶佔那個低優先權的持有者，使它始終拿不到 CPU 來完成並呼叫 signal。結果就是優先權反轉：一條高優先權執行緒實際上被一群較低優先權的卡住，有時還卡得久得危險。這可不是玩具般的顧慮。1997 年，一個著名案例差點葬送了 NASA 的火星拓荒者號任務，它不斷自我重置，直到工程師診斷出的正是這件事，並啟用了標準的修法——優先權繼承：暫時把等待者的高優先權借給持有者，好讓它快點完成並釋放號誌。
所以號誌是個優美而通用的原語：一個整數、兩個原子操作，從這兩者你就能搭出一把互斥鎖、一個資源計數器、一個事件信號。但正因為它如此通用，正確性是寄託在你的紀律裡，而不在工具裡。正是這份不安，促使語言設計者把這些想法包進更安全、更有結構的東西裡——條件變數與監督程式（monitor）——而那正是本階梯最後一篇導覽接下來要帶你去的地方。