臨界區間問題（critical-section problem）

一旦你知道共用資料必須在受保護的臨界區間內才能碰，下一個顯而易見的問題就是：一個好的保護機制，究竟必須保證什麼？光是把人擋在外面還不夠——一個直接把廁所門永遠鎖死的機制，固然「防止了衝突」，卻也毫無用處。臨界區間問題，正是對「一個正確的進入／離開協定必須達成什麼」的精確陳述。它由戴克斯特拉提出，任何真正的解法——一把鎖、一個號誌、一段巧妙的軟體技巧——都必須同時滿足它的三項要求。

這三項要求是：互斥——若有一條執行緒正在它的臨界區間內執行，則其他執行緒同一時間都不得進入自己的臨界區間。進展（progress）——若沒有任何執行緒在臨界區間內，而有一條以上的執行緒想進入，那麼「下一個由誰進入」的決定不能被無限期拖延，而且只有真正在爭用的執行緒才能參與這個決定（一條閒置在剩餘區的執行緒不得阻擋他人）。有限等待（bounded waiting）——在某條執行緒提出進入請求之後、該請求被准許之前，其他執行緒進入自己臨界區間的次數要有上限，這樣就沒有執行緒會永遠等下去。互斥是安全性（壞事不會發生）；進展與有限等待是活性（好事終究會發生，而且公平）。

為什麼要分成三條規則？因為很容易滿足其中一條、卻悄悄違反另一條，而每少一條都是貨真價實的錯誤。一個有互斥但沒有進展的機制，可能死結，或在執行緒們不必要地空等時讓資源閒置。一個有互斥、有進展卻沒有有限等待的機制，可能讓某條倒楣的執行緒永遠飢餓，而別人不斷插隊。正確的解法還不能做不切實際的假設——例如，它不能依賴執行緒以某種特定的相對速度執行，因為排程器隨時都能暫停任一條執行緒。這三項要求合起來，就是每個同步原語都承諾要遵守的契約。