概念性、宏觀視野的程序/執行緒同步機制總覽

大學時代， 作業系統這門課修得破破的。 後來當助教、 甚至現在自己教書再遇到作業系統， 也都不是那麼有信心。 特別是談論 processes 及 threads 的同步機制那一章： 各種硬體指令 (test-and-set、 compare-and-swap) 各種演算法 (Peterson's algorithm、 Bakery algorithm) 各種程式結構或資料結構 (spinlock、 mutex、 semaphore、 condition variable) 都很燒腦細胞。 更糟的是， 從來沒看過一篇宏觀的文章介紹這些機制彼此之間的關係， 就算看懂個別的演算法， 還是有見樹不見林的感覺。 還好現在有網路、 有 google。 爬了很多文之後， 整理這篇文章， 從宏觀角度著眼， 不鑽研程式碼 (但有很多超連結)， 自己思緒變得清晰很多， 也希望對未來的作業系統課程師生以及多執行緒程式設計師有幫助。 本文假設讀者對於 context switch、 critical section 等等名詞已有概念。 以下 processes 跟 threads 混著用不特別區分。

Peterson's algorithm 跟 Bakery algorithm ( 麵包店演算法) 都是窮人版的同步機制： 在沒有硬體支援的情況下， 可以用這兩個神妙演算法以純軟體的方式確保 critical section 底下的 「互斥/有進展/有限等待」 三要件。 Peterson's algorithm 適用於兩個 threads 的情況； Bakery algorithm 則可通用於任意個 threads。 兩個演算法其實長得很類似： 各自採用了兩個重要的資料結構， 一個用來表達 「進入的意圖」， 另一個用來表達 「優先順序」。 蕭宇程博士的 「意願 vs 權杖」 跟 GeeksforGeeks 的 "willingness vs turn 解釋得很清楚。 因為現代的硬體都有很簡單的指令可以達到相同的效果， 所以到了今天， 這兩個演算法的重點在於歷史/哲學/學術/考試意義； 它們已經沒有實用價值。

如上所述， 現代的硬體提供 Compare-and-Swap (CAS) 跟 Test and Set (TAS) 之類的 atomic instructions， 讓程式設計師可以很簡單地確保 critical section 的三要件。 不過除了作業系統核心當中極少數的開發者之外， 其他絕大多數的程式設計師沒有機會用組合語言的這些指令寫程式， 所以對作業系統的師生而言， 硬體所提供的這些 atomic instructions 也是考試價值遠大於實用價值。

對於寫 multi-threading 的一般程式設計師而言最有實用價值的知識， 是由作業系統或程式語言透過函式庫所提供給我們的同步機制， 例如 spinlock、 mutex 跟 semaphore。 如果你閒著無聊去查看作業系統實作這部分的原始碼， 會看到這些同步機制一定會用到一個或多個 atomic instructions。 更閒的話， 還可以試著用 bakery algorithm 來取代這些 atomic instructions， 再重新編譯核心， 理論上應該也還是能動， 只是系統效能會變很差。 不過我離題了， 應用程式設計師其實只要會用這些機制就可以了。

其中 spinlock 最簡單。 華盛頓大學講義 跟 維基百科 都提供了 CAS 實作 spinlock 的程式碼。 因為想要搶 lock 的那個 thread 會卡在一個不做事的迴圈裡面不停地原地打轉 -- 就像你在唯一的一間而且鎖住的廁所外面等不及， 卡在迴圈裡不停地去轉把手一樣 -- 所以叫做 spinlock。 這又叫做 busy waiting， 如果持續太久， 會很燒 CPU、 很浪費運算資源。 (不停轉把手的時間如果改拿來滑手機或閉目養神之類的， 不是比較有意義嗎?)

所以你可以理解為什麼一般來說 spinlock 是 「作業系統核心僅供自用的內部特權機制」； 它不會提供這個介面給程式設計師； 就算程式設計師自己試著寫 spinlock (像是 Peterson's 或 bakery 裡面的迴圈那樣) 也還是有可能因為被系統 context switch 出去而失去搶奪力。 一般的作業系統及程式語言會提供給程式設計師的同步機制是 mutex 跟 semaphore。

可以把 mutex 初步理解成一個未必 spin、 一般程式設計師被允許使用的 lock -- 如果你去碰這個 lock， 卻發現打不開， 就有可能立即被作業系統施展昏睡魔法， 把你 context switch 出去 -- 反正你現在也做不了任何事。 至於 「lock」 這個字， 有時被拿來當做 「確保互斥」 的概念/通稱， 包含 user mode 的 mutex 及 kernel mode 的 spinlock； 有時又是某個程式語言裡面的一個類別名稱， 基本上就是在做 mutex (mutual exclusive) 的事， 所以這個名詞很容易造成混淆。 也就是說， 這個最常用的、 保護 critical section 的機制， 在某些程式語言裡面被稱為 lock， 在另一些語言裡面則被稱為 mutex。 例如在 python 裡面， 既有 Lock 也有 Mutex， 但最終大家趨向使用同一種類別 (Lock)； 另一種 (Mutex) 則荒廢： 1、 2。 也就是說， 讀觀念性文章的時候， 可以把 lock 跟 mutex 當成相同的東西； 寫程式的時候， 要查看一下在這個語言裡大家習慣用哪一個類別的變數。

Semaphore 是由演算法大師 Dijkstra 所發明的， 所以很難懂 :-) 這個淺顯的比喻很讚： 「mutex 像是房間的鑰匙； semaphore 像是沒有鎖但容量有限的房間」。 通用的狀況叫做 counting semaphore； 最簡單的狀況 (容量一人的房間， 只有 0 跟 1 兩種狀態) 叫做 binary semaphore。 因為 mutex 比較好理解， 而 binary semaphore 又跟 mutex 長得很像， 所以經常被同時談起。 兩者有一個很大的差別： mutex 上鎖開鎖的必須是同一個 thread， 而 binary semaphore 則可由同一個或不同的 threads 上鎖開鎖。 暫時撇開造成 1997 年火星探測車不斷重開機、 難得遇到的 Priority Inversion 現象 不談， 如果你寫的程式可以容忍這類難以除錯的 「高優先權 process 餓死」 狀況， 那麼你可以用一個 「自鎖自開的 binary semaphore」 來模擬 mutex。 所以網路上有許多文章說這兩者大致相等。

但是最精確的說法， 應該看嵌入式作業系統專家 Michael Barr 的 這篇超讚文章 ( 中文摘要)。 我從這篇學到最多。 用自己的話再重新摘要一次：

1. 早先 Dijkstra 發明 semaphore 時， 確實被大家拿來分別應用於 critical section 跟 signaling 這兩類問題。
2. 但是當大家觀察到火星探測車重開機之類的 priority inversion 現象之後， 大家領悟到： 用 binary semaphore 來模擬 mutex 會有問題。 作業系統在實作 mutex 時還必須納入額外考量。
3. 對程式設計師而言， 最簡單最正確的想法應該是： 需要進入 critical section 時， 用 mutex -- 上鎖/解鎖永遠是同一個 thread； 需要處理 signaliing 時， 用 semaphore -- 等待/通知通常是不同的 threads。 換個方式說， 要搶資源時用 mutex； 要互相通知時用 semaphore。

所謂 signaling 就是 threads 之間要通知彼此 「某些條件已經改變」 的情境。 例如 producer-consumer 類型的問題可以用兩個 semaphore 來實作， 一個代表 「有資料可用」， 另一個代表 「有空間可放東西」。 單就某一種資源 (例如 「空間」) 來說， 有些 threads 專門負責執行 P (「我需要空間」)； 另一些 threads 專門負責執行 V (「有空間可用了哦」) 但一個 thread 通常不會對同一個 semaphore 既 P 又 V。 Q: 請用 「資料」 的觀點把上面這句話重說一遍， 但是請用 consumer 跟 producer 取代 「一些 threads」。

希望現在你再讀以下這些比較文章時， 會更容易理解 spinlock、 mutex、 semaphore 之間的關係： semaphore, mutex, spin lock (中文)、 Semaphore vs spinlock (中文)、 Mutex vs Semaphore (英文)。

單有 mutex 跟 semaphore 還是不太夠用。 有時一個 thread 搶到一個 lock 之後， 不一定能夠馬上開始工作。 再以 producer consumer 問題為例， 搶到 lock 的消費者面對空的 buffer， 什麼都不能做； 或是搶到 lock 的生產者面對滿的 buffer， 也是束手無策啊! 「搶到 lock 之後， 還需要檢查某些條件才能決定能否開工」 專為這種情況所設計的高階同步機制， 稱為 condition variable。 可以從這個 (不完全正確的) python 版範例 切入。 (註： 為什麼要按 ctrl-z 才有用? 之後還要記得 kill %1!) CV 的運作方式如下：

1. 每個 CV 都要依附著某個 mutex 而存在， 通常就是 用來保護條件運算式裡面的全域變數的那個 mutex。
2. 搶到 mutex 之後， 檢查條件， 如果不滿足， 就呼叫 CV 的 wait()。 此時系統會把你的 mutex 釋放出來， 並且把你推去睡覺， 一直到條件滿足時才會再把你 (也許還有其他人同時一起) 叫醒。 你不能確定自己是不是一起等待的所有 threads 當中第一個醒過來的， 但可以確定如果從 wait() 醒過來了， mutex 必然又回到手上。 (Mesa semantics)
3. 也就是說， 在比較簡單的情況下， 用 if (...) cv.wait() 也許 ok； 但最保險、 最萬無一失的寫法是 while (...) cv.wait()。
4. 處理完之後， 釋放 mutex。
5. 另一方面， 一定要有另外至少一個 thread 搶到 mutex 之後， 做了某些事， 讓原來不成立的條件變 ok 了， 它要負責呼叫 CV 的 signal() (在 python 裡面叫做 notivy())， 以便作業系統可以把等待的 thread 叫醒， 最後釋放 mutex。
6. 可能會有不只一個 CV 依附在同一個 mutex 上 -- 例如 producer consumer 的例子裡， 就應該要有兩個不同的條件： 「還有資料可吃」、 「還有空間可放資料」， 但他們都依附在 「保護 queue 的 mutex」 上面。

於是我參考 David Hovemeyer 教授的講義 及 Tcl 語言作者 John Ousterhout 教授的講義 去修改前面的 python 範例， 最終得到 多個 producers 多個 consumers 的 python 程式。 CV 解決了某一大類的同步問題； 如果沒有 CV 的話， 程式設計師會需要寫類似 spinlock 的 busy waiting 迴圈來等待條件成立， 這很浪費資源 (除非正好被作業系統 context switch 出去)。 大推深入淺出， 解說完整詳盡， 又有點搞笑， 讓我學到最多的 Arpaci Dusseau 教授的講義。 如果你在修改 python 範例程式的過程當中遇到奇怪的現象， 說不定可以在他的講義裡的錯誤示範找到答案。 看完 Dusseau 的講義之後， 你就可以試著理解， 甚至 debug 比較 CV 跟 semaphore 的文章。

CV 要如何實作呢? 可以用 semaphore 來實作， 不過一樣會遇到 類似 priority inversion 的問題 ( libc 就出過這個 bug) 所以 經驗豐富的微軟工程師建議： 最簡單的方式， 就是自己再補上一個 queue 來確保想要等這個 CV 的 threads 不會餓死。 如果上述都理解了 (我還沒)， 應該就可以看懂 分析 semaphore vs CV 效率的文章

最後， 請看著本文的插圖， 想想你自己的定位： 你是作業系統裡實作同步機制的程式設計師? 還是撰寫作業系統其他部分的程式設計師 (kernel mode programmer)? 還是一般使用 process/thread synchronization 的程式設計師 (user mode programmer)? 然後你就知道哪些地方對你比較重要了。 真的要寫程式時， 還是要以你的程式語言的手冊為準。 但至少現在手冊會比較容易讀了。