# [Linux 核心設計](https://beta.hackfoldr.org/linux/): 淺談同步機制 Copyright (**慣C**) 2018 [宅色夫](http://wiki.csie.ncku.edu.tw/User/jserv) ==[直播錄影](https://youtu.be/lNt-ewfygy8)== ## 充斥歷史痕跡的同步機制 在 [UNIX 作業系統 fork/exec 系統呼叫的前世今生](https://hackmd.io/@sysprog/unix-fork-exec) 一文中,提及電腦科學家 Melvin Conway 在 1963 年發表論文〈[A Multiprocessor System Design](https://archive.org/details/AMultiprocessorSystemDesignConway1963/page/n7)〉,正式提出 fork 思想,大約在這個時間點,另一個電腦科學家 Edsger Dijkstra 則以數學定義提出 [Semaphore](https://en.wikipedia.org/wiki/Semaphore_(programming)) 概念,而早期分時多工作業系統 [Compatible Time-Sharing System](https://en.wikipedia.org/wiki/Compatible_Time-Sharing_System) (CTSS) 則在 1961 年首次進行示範運作,整個作業系統必要的特徵和思維都還在發展,其中包含同步機制。 同步問題陳述: critical section (以下簡稱 `CS`): 提供對共享變數之存取的互斥控制,從而確保資料正確。 ![](https://i.imgur.com/El3wtFd.png) CS 解法: 1. Mutual exclusion (互斥):任一時間點,只允許一個 process/thread 進入規範的 CS 內活動。 2. Progress (有進展): 需要同時滿足下面要件: * 不想進入 CS 的 process/thread 不得阻礙其它 process/thread 進入 CS,也就是說,不得參與進入 CS 的決策過程; * 必須在有限的時間從想進入 CS 的 process/thread 中,挑選其中一個 process/thread 進入 critical section,一有有空位就讓想進 CS 者即刻進入; 3. Bound waiting (有限的等待): 自 process/thread 提出進入 CS 的申請到獲准進入 CS 的等待時間是有限的。即若有 n 個 processes/thread 想進入,則任一 process/thread 至多等待 n - 1 次即可進入。 在缺乏專門硬體指令的狀況下,存在多種同步機制演算法: (但其實各自的假設) * [Dekker's algorithm](https://en.wikipedia.org/wiki/Dekker%27s_algorithm): 1960 年 * [Lamport's bakery algorithm](https://en.wikipedia.org/wiki/Lamport%27s_bakery_algorithm): 1973 年 * [Peterson's algorithm](https://en.wikipedia.org/wiki/Peterson%27s_algorithm): 1981 年 現代的電腦硬體都有簡單且明確的指令可達到相同的效果,不用再顧慮上述演算法的 [willingness vs. turn](https://www.geeksforgeeks.org/petersons-algorithm-for-mutual-exclusion-set-1/),換言之,這些軟體的同步演算法已無實用價值。 Edsger Dijkstra 提出 semaphore 概念時,被廣泛用於 CS 跟 signaling 這兩類問題。 * signaling 是 process/threads 之間要通知彼此 「某些條件已經改變」 的情境:例如 producer-consumer 類型的問題可用兩個 semaphore 來實作,一個代表 「有資料可用」,另一個代表 「有空間可放東西」。 隨著電腦硬體逐漸提供 atomic 指令後,[mutex](https://en.wikipedia.org/wiki/Lock_(computer_science)) 或稱為 lock 的機制被列入作業系統的實作考量: * 需要進入 CS 時, 用 mutex/lock —— 上鎖/解鎖永遠是同一個 thread/process; * 需要處理 signaliing 時,用 semaphore —— 等待/通知通常是不同的 threads/processes; 簡言之,要搶資源時用 mutex,要互相通知時用 semaphore。 ## 既生瑜,何生亮? 先來看 semaphore 與 mutex 的差異,參照 Michael Barr 的文章 [Mutexes and Semaphores Demystified](https://barrgroup.com/Embedded-Systems/How-To/RTOS-Mutex-Semaphore): mutex 與 Semaphore 都用於確保 critical section (以下簡稱 `CS`) 的正確,讓多個==執行單元==運作並存取資源時,執行結果不會因為執行單元的時間先後的影響而導致錯誤。 mutex 與 semaphore 的差別在於: * process 使用 mutex 時,process 的運作是持有 mutex,執行 CS 來存取資源,然後釋放 mutex * Mutex 就像是資源的一把鎖:解鈴還須繫鈴人 * process 使用 semaphore 時,process 總是發出信號 (signal),或者總是接收信號 (wait),同一個 process 不會先後進行 signal 與 wait * 換言之,[process 要不擔任 producer,要不充當 consumer 的角色](https://en.wikipedia.org/wiki/Semaphore_(programming)#Producer%E2%80%93consumer_problem),不能兩者都是。semaphore 是為了保護 process 的執行同步正確; mutex 與 semaphore 兩者設計來解決不同的問題。區分 mutex 與 binary semaphore: 1. mutex 確保數個 process 在一個時間點上,只能有一個 process 存取單項資源; 2. semaphore 讓數個 producer 與數個 consumer 在計數器的基礎上進行合作; 另一個 mutex 與 binary semaphore 的差異在於,==嚴格遵守== mutex 的情境中,要額外考慮 [priority inversion](https://barrgroup.com/Embedded-Systems/How-To/RTOS-Priority-Inversion)。因此,mutex 實作中多半採用一些機制來防止 Priority Inversion。Priority Inheritance 是基於 process 持有 mutex 的概念,使得數個不同 priority 的 process,在等待資源時透過 mutex 傳遞 priority,避免 priority inversion 發生。 注意,mutex 與 semaphore 在很多材料有著不同的解釋。Barr 的觀點是回歸 Dijkstra 所提出的數學模型,後者衍生出的 semaphore,則包含 counting semaphore 與 binary semaphore,也才能夠用於保護資源,或是處理 multiple identical resources 的問題。 對照 Taiwan Linux Kernel Hackers 的解說影片 [淺談 Semaphore 與 Mutex](https://www.youtube.com/watch?v=JEXwO_EoyZo) > 在科技公司的面試過程中,答覆 [Mutex, Semaphore, the difference, and Linux kernel](https://blog.louie.lu/2016/10/22/mutex-semaphore-the-difference-and-linux-kernel/) 在 Linux 核心中,起初僅有 semaphore 這個核心物件 (kernel object),直到 v2.6.16 核心才將 mutex 自 semaphore 實作中抽離。儘管 Mutex 與 Semaphore 兩者都是休眠鎖,但 Linux 核心實作 mutex 時,運用加速技巧,將上鎖區分以下三個步驟: 1. Fast path: 嘗試使用 atomic operation,減少 counter 數值來獲得鎖 2. Mid path: 上一步若失敗,嘗試使用特化的 MCS spinlock 等待,再取鎖。 * 當持鎖的 thread 還在執行,且系統不存在更高優先權的任務時,即可推定,持鎖的 thread 很快就會把所釋放出來,因此會使用一個特化的 MCS spinlock 等待鎖被釋放。特化的 MCS spinlock 可在被重新排程時,退出 MCS spinlock queue。當走到這步時,就會到 Slow path。 3. Slow path: 鎖沒有辦法取得,只好把自己休眠。 * 走到這一步,mutex 才會將自己加入 wait-queue 然後休眠,等待有人 unlock 後才會被喚醒。 這樣付出的代價是,mutex 成為 Linux 核心最複雜的 lock,在 x86-64 的環境下需要使用 40 bytes,相較之下,semaphore 只用 24 bytes,這意味著對 CPU cache 的效率和 cache coherence 的衝擊。 ## 回歸基本面 取自 Donald E. Porter 教授的 [CSE 506: Operating Systems](http://www.cs.unc.edu/~porter/courses/cse506/) 教材 - [ ] [Linux kernel synchronization](http://www.cs.unc.edu/~porter/courses/cse506/s16/slides/sync.pdf) ![](https://i.imgur.com/5YwiDCS.png) * [Big Kernel Lock](https://kernelnewbies.org/BigKernelLock): 鎖定整個 Linux 核心的機制,透過 `lock_kernel()` 與 `unlock_kernel()` 函式。這是為了支援多處理器,暫時引進的鎖定機制,已在 v2.6.39 徹底清除。 * [commit](https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git/commit/?id=4ba8216cd90560bc402f52076f64d8546e8aefcb) * [Killing the Big Kernel Lock](https://lwn.net/Articles/380174/) * BKL 用於保護整個核心,而 spinlock 用於保護非常特定的某一共享資源。行程 (process) 持有 BKL 時允許發生排程。實作機制:在執行`schedule` 時,`schedule` 將檢查行程是否擁有 BKL,若有,它將被釋放,以致於其它的行程能夠獲得該 lock,而當輪到該行程執行之際,再讓它重新獲得 BKL。注意:在持有 spinlock 期間不會發生排程。 * 整個核心僅有一個 BKL ![](https://i.imgur.com/hPewkvw.png) ![](https://i.imgur.com/YrnMY1b.png) ![](https://i.imgur.com/Aorbakl.png) * coarse-grained vs fine-grained: 粗粒度和細粒度。 * coarse-grained 對於 locking 來說,持有時間可以很長並不斷延長鎖的持有時間,好處在於對 lock 資源管理的責任較小,難點在於 lock 資源原有狀態的成本 * fine-grained 對於 locking 來說,持有時間一般是秒級或者毫秒級,好處在於 lock 資源後不必維持原有 lock 的狀態,但這種簡單的設計方法導致資源管理的責任變重 ![](https://i.imgur.com/F4k6URt.png) * Atomic increment/decrement (`x++` or `x--`) – Used for reference counting – Some variants also return the value x was set to by this instruction (useful if another CPU immediately changes the value) * Compare and swap (CAS) * 語意: `if (x == y) x = z;` ```C int compareAndSwap(int *loc, int expectedValue, int valueToStore) { ATOMIC { int val = *loc; if (val == expected) { *loc = valueToStore; } return val; } } ``` * 廣泛用於許多 [lock-free data structures](https://preshing.com/20120612/an-introduction-to-lock-free-programming/) - 延伸閱讀: [Atomic Instructions, Lock-Free Data Structures](http://faculty.ycp.edu/~dhovemey/spring2011/cs365/lecture/lecture20.html) * 一個 lock-free 的程式需要確保符合這個特徵:執行該程式的所有執行緒至少有一個能夠不被阻擋 (blocked) 而繼續執行 * lock-Free 中的 "Lock" 沒有直接涉及 mutex 和 semaphore 一類 mutual exclusion,而是描述了應用程式受限於特定原因被鎖定的可能,例如可能因為 dead lock, live lock,或者 thread scheduling 致使的 priority inversion 等等 * 下方的程式碼沒有任何 mutex,但卻不符合 lock-free 的屬性:若有兩個執行緒同時執行程式碼,考慮到特定的排程方式,非常可能兩個執行緒同時陷入無窮迴圈,也就是阻擋彼此 ```C while (x == 0) { x = 1 - x; } ``` * Lock-Free 程式設計的挑戰不僅來自於其任務本身的複雜性,還要始終著眼於對事物本質的洞察 * `0 -> 1; 1 - 1 -> 0 -> 1` ![](https://i.imgur.com/G6nHIqq.png) ![](https://i.imgur.com/MofqRaz.png) ![](https://i.imgur.com/arVGcp2.png) * 延伸閱讀: [Evaluating the Cost of Atomic Operations on Modern Architectures](https://spcl.inf.ethz.ch/Publications/.pdf/atomic-bench.pdf) ![](https://i.imgur.com/hlEkHSx.png) ![](https://i.imgur.com/A3fawqb.png) * Linux spinlock 的對等 C 語言實作 ```C while (0 != atomic_dec(&lock->counter)) { do { // Pause the CPU until some coherence // traffic : 考慮到 cache line 的效應!! } while (lock->counter <= 0); } ``` * 特定 CPU 的cache line 更新同步到不同 CPU 的 cache line 的時間不同,意味著等待 spinlock 的 CPU 中哪個 CPU 先得知 `lock->counter` 的變化,哪個 CPU 就能優先獲得 spinlock * [What is cache line bouncing? How may a spinlock trigger this frequently?](https://www.quora.com/What-is-cache-line-bouncing-How-may-a-spinlock-trigger-this-frequently) * 延伸閱讀: [從 CPU cache coherence 談 Linux spinlock 擴展議題](https://hackmd.io/s/BJ8djgdnm) ![](https://i.imgur.com/VSUphUl.png) * Test-and-Set Lock * 注意: Write Back + Evict (驅逐) Cache Line ![](https://i.imgur.com/l4u5ZZw.png) * Test-Test-and-Set Lock ![](https://i.imgur.com/z0znLgA.png) * 普通的 spinlock 對待 reader 和 writer 是一視同仁,RW spinlock 給 reader 賦予更高的優先權,有沒有讓 writer 優先的鎖呢?答案就是 seqlock * 延伸閱讀: [Linux內核同步機制之(六):Seqlock](http://www.wowotech.net/kernel_synchronization/seqlock.html) * [Chapter 5. Concurrency and Race Conditions](https://www.oreilly.com/library/view/linux-device-drivers/0596005903/ch05.html) * 相關學術研究: * [A Probabilistic Quantitative Analysis of Probabilistic-Write/Copy-Select](https://askra.de/papers/pwcs-nfm.pdf) * [Probabilistic Write Copy Select locks](https://www.osadl.org/?id=1113) * [pBseq: probabilistic buffer-swapping sequence locks](http://www.opentech.at/assets/slides/pBseq.pdf) - [ ] [Memory Consistency](http://www.cs.unc.edu/~porter/courses/cse506/s16/slides/consistency.pdf) ![](https://i.imgur.com/iMl6gcv.png) * 乍聽之下好似「電腦病毒會讓人類染病」一樣匪夷所思,但實際上,由於電腦由各種裝置組成,其結構強度落差極大,透過放射線影響 DRAM 一類的資料儲存裝置是可能的,而且 [Microsoft Windows 核心為此還要做出應對](https://news.ycombinator.com/item?id=18494690)。 * 在工業控制的領域,尤其是航空,就會面對 bit flips (位元反轉,原本該是 0 的資料,在某種時空狀況,會轉換為 1,反之亦然),這甚至是多項公共安全危機的原因。 * 學軟體可不是堆積程式碼和呼叫 API,而該從每個環節都充分掌握,畢竟我們需要對廣大的使用者負責 * [Cosmic Rays: what is the probability they will affect a program?](https://stackoverflow.com/questions/2580933/cosmic-rays-what-is-the-probability-they-will-affect-a-program) ## 羅習五副教授整理的教材 * [syncronization](https://www.dropbox.com/s/ioi4ujz0br7u5d9/ch05%EF%BC%8Csyncronization.pptx?dl=0) * [deadlock](https://www.dropbox.com/s/jx3wq5qcs5fec0x/ch06%EF%BC%8Cdeadlock.pptx?dl=0) :::success 編撰中,請支持優質繁體中文教材,如有建議和更正請回報於 [Taiwan Linux Kernel Hackers 討論區](https://www.facebook.com/groups/twlinuxkernelhackers/) ::: ## 接下來就是細節 討論脈絡會依循 [https://0xax.gitbooks.io/linux-insides/SyncPrim/](https://0xax.gitbooks.io/linux-insides/SyncPrim/)