互斥與臨界區間問題

想像整間辦公室共用一間沒裝鎖的廁所。如果兩個人同時晃進去，就會發生尷尬的碰撞。有禮貌的解法是裝一把鎖：一次只能有一個人在裡面，其他人乖乖排隊等。互斥就是把這條規則套用到執行中的程式碼——在某一小段工作期間，一次只能有一個執行緒「在裡面」。

那段不能讓兩個執行緒同時進入的程式碼，稱為臨界區間。它通常只有寥寥幾行，碰觸到共享資料：讀一個計數器、加一、寫回去。如果兩個執行緒把這幾行交錯執行，它們可能都讀到舊值、又都寫回同一個新值，於是有一次的加一被默默吞掉了。臨界區間問題就是這個謎題：如何打造一個守門人，使任一瞬間至多只有一個執行緒在臨界區間裡（互斥），同時又確保執行緒不會永遠互相卡死（進展），且沒有執行緒會無限等下去（有限等待）。互斥是你想要的性質；互斥鎖、自旋鎖或號誌則是提供這個性質的工具。

這之所以重要，是因為只要兩個執行緒共用可變的記憶體，硬體並不會替你內建任何輪流機制——CPU 可以任意順序交錯它們的指令。互斥就是那套紀律，把「誰先到誰贏，偶爾還弄壞資料」轉變成「一次一個，正確無誤」。本領域幾乎每個原語的存在，都是為了提供互斥或圍繞著它做協調。要注意互斥只保護你實際包起來的程式碼區域——在所有臨界區間之外被碰觸的資料，仍然是不受保護的。