2017年12月31日 星期日

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

同步機制總覽 大學時代, 作業系統這門課修得破破的。 後來當助教、 甚至現在自己教書再遇到作業系統, 也都不是那麼有信心。 特別是談論 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)? 然後你就知道哪些地方對你比較重要了。 真的要寫程式時, 還是要以你的程式語言的手冊為準。 但至少現在手冊會比較容易讀了。

1 則留言:

因為垃圾留言太多,現在改為審核後才發佈,請耐心等候一兩天。