# [Linux 核心設計](http://hackfoldr.org/linux/): 多核處理器和 spinlock Copyright (**慣C**) 2018 [宅色夫](http://wiki.csie.ncku.edu.tw/User/jserv) ## 自我檢查清單 [點題](https://www.facebook.com/JservFans/photos/a.743333619126308/1817140628412263/) / [小處做起](https://twitter.com/jserv/status/552725130690826240) Linux 的 spinlock 出現在裝置驅動程式之際,有以下形式: (只列出常見者) * spin_lock() / spin_unlock(), * spin_lock_irq() / spin_unlock_irq(), * spin_lock_irqsave / spin_unlock_irqrestore() * spin_lock_bh() / spin_unlock_bh() * local_irq_disable / local_irq_enable * local_bh_disable / local_bh_enable 這一切很難「透明」地一眼望穿,遑論核心改版時,陸續添增新的 spinlock 機制,這該怎麼辦呢?不僅「Bug 出不去」,而且「程式碼進不來」。 本講座試著帶大家回頭研究 多核處理器的設計,重新學習 context switch 在 process 的意義,確認釐清多核之間的執行路徑,再來則是 IRQ 和核心間的關聯,最後才是思考 spinlock 存在和真正要解決的問題層面。過程中也會搭配 Linux 邁向即時處理機制 (不僅有工業控制,也有自動駕駛的控制需求,Google 公司也是推手之一) 所著重的 kernel preemption,我們會提及 PREEMPT_RT (開發十餘年的專案,預計在近期正式整合進核心) 對 spinlock 的影響,後者會轉換為 sleeping spinlocks,也就是支援 priority inheritance 的 RT-mutex (這到底是什麼鬼?!) 如果以上就讓你頭昏,多核處理器之間的 cache coherence 也是 spinlock 實作的關鍵考量,這十年來 Linux 核心針對 scalability 做了巨大的變革,許多廠商為了「發大財」,相繼投入可觀的工程資源,我們也會解析相關 議題,並且用機率統計 (不是只有人工智慧需要數學,你真要理解作業系統核心運作,也逃不掉的,孩子,誠實面對自己吧) 來解釋箇中運作機制。 在議程進行之前,請自行評估對以下提問的認知: 1. 知道 Linux 核心的 atomic context 出現於哪些場合嗎? 2. spinlock 作為 busy-waiting (教科書術語),到底在瞎忙什麼?對應於現代處理器做了哪些事? 3. spinlock 的實作可能涉及 disable interrupt,後者對作業系統和 latency 及 scalability 的影響為何? 4. 你應該知道 deadlock,但 spinlock 可能會導致 livelock,你知道為什麼嗎? 5. 中斷處理機制對許多程式開發者不陌生,特別是待過 IC 設計公司和系統廠的朋友,但為了提升 kernel preemption,核心開發者避免 disable interrupt 的發生,那該如何確保資料的正確呢? (提示: preempt_count) 6. 如果 spinlock 變成可以 sleeping (在 PREEMPT_RT),還有 critical section 可言嗎? 7. Threaded IRQ 是什麼?又如何對應到現代處理器的實作呢? 8. hard IRQ 和 soft IRQ (BH) 的關聯為何?你知道 ksoftirqd 的運作機制嗎? 若上述問題你沒辦法在三分鐘內回覆,那沒關係,就過來跟我們一起學習吧。 ## 既生瑜,何生亮? 相關講座: [Linux 核心設計: 淺談同步機制](https://hackmd.io/s/SJpp-bN0m) 先來看 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,執行 critical section 來存取資源,然後釋放 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 Inversion 是基於 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/) ## 重新思考 CS 和互斥 CS:APP [Concurrent Programming](http://www.cs.cmu.edu/~213/lectures/23-concprog.pdf), Page 40-56 ![](https://i.imgur.com/54C4mj9.png) CS:APP [Synchronization: Advanced](http://www.cs.cmu.edu/~213/lectures/25-sync-advanced.pdf), Page 40-49 ![](https://i.imgur.com/8Uhm2TA.png) 計數器的程式範例: ```clike // 全域變數 volatile long cnt = 0; // 計數器 void *thread(void *vargp) { long niters = *((long *)vargp); for (long i = 0; i < niters; i++) cnt++; return NULL; } int main(int argc, char **argv) { long niters; pthread_t tid1, tid2; niters = atoi(argv[1]); pthread_create(&tid1, NULL, thread, &niters); pthread_create(&tid2, NULL, thread, &niters); pthread_join(tid1, NULL); pthread_join(tid2, NULL); if (cnt != (2 * niters)) printf("Wrong! cnt=%ld\n", cnt); else printf("Correct! cnt=%ld\n", cnt); exit(0); } ``` 運行的結果每次不一樣: ``` $ ./badcnt 10000 OK cnt=20000 $ ./badcnt 10000 BOOM! cnt=10458 ``` 把 `cnt` 變數操作的部分抽出來看: 執行緒函式的迴圈程式碼: ```clike for (long i = 0; i < niters; i++) cnt++; ``` 對應的組合語言程式碼: ``` # 以下四句為 Head 部分,記為 H movq (%rdi), %rcx testq %rcx, %rcx jle .L2 movl $0, %eax .L3: movq cnt(%rip), %rdx # 讀取 cnt,記為 L addq $1, %rdx # 更新 cnt,記為 U movq %rdx, cnt(%rip) # 寫入 cnt,記為 S # 以下為 Tail 部分,記為 T addq $1, %rax cmpq %rcx, %rax jne .L3 .L2: ``` cnt 使用 `volatile` 關鍵字聲明,意思是避免編譯器產生的程式碼中,透過暫存器來保存數值,無論是讀取還是寫入,都在主記憶體操作。 細部的步驟分成 5 步:`H` -> `L` -> `U` -> `S` -> `T`,尤其要注意 LUS 這三個操作,這三個操作必須在一次執行中完成,一旦次序打亂,就會出現問題,不同線程拿到的值就不一定是最新的。 也就是說該函式的正確執行和指令的執行順序有關 ![](https://i.imgur.com/EU3fibV.png) 將 n 個 concurrent 執行緒的執行模型描述為 n 維空間中的軌跡線,每條軸 k 對應 k 的進度。下圖展示對於 H1, L1, U1, H2, L2, S1, T1, U2, S2, T2 的軌跡線的進度圖: ![](https://i.imgur.com/rADk08t.png) 對於執行緒編號 `i`,操作共享變數 `cnt` 內含值的指令 (,Li,Ui,Si) 構成了一個 CS,每個 CS 不應該和其他執行緒的 CS 交替執行。換言之,需要對共享變數進行互斥的存取: * 當執行緒繞過不安全區,叫做安全軌跡線; * 反之,為不安全軌跡線; ![](https://i.imgur.com/vx3U1qg.png) mutual exclusion ([互斥](http://terms.naer.edu.tw/detail/50571/)) 手段的選擇,不是根據 CS 的大小,而是根據 CS 的性質,以及有哪些部分的程式碼,也就是,仰賴於核心內部的執行路徑。 semaphore 和 spinlock 屬於不同層次的互斥手段,前者的實現仰賴於後者,可類比於 HTTP 和 TCP/IP 的關係,儘管都算是網路通訊協定,但層次截然不同: * [POSIX semaphore](http://www.csc.villanova.edu/~mdamian/threads/posixsem.html) 用於多個 process 之間對資源的互斥 * 雖然也是在核心中,但是該核心執行路徑是以 process 的身份,代表 process 來爭奪資源 * 如果 競爭不上,會有 context switch,process 可以去sleep,但 CPU 不會停下來,會接著運作其他的執行路徑 * 從概念上說,這和單核 CPU 或多核 CPU 沒有直接的關係,只是在 semaphore 本身的實做層面上,為了保證 semaphore 的 atomics,在多核 CPU 中需要 spinlock 來互斥 * 在多核 CPU 中, 加上了其他 CPU 的干擾,因此需要 spinlock 來幫助。一旦 CPU 進入 spinlock,就不會做別的事,直到鎖定成功為止。因此,這就決定了被 spinlock 鎖住的 CS 不能停 spinlock 的本意和目的就是保證資料修改的 atomics,因此也沒有理由在spinlock 鎖住的 CS 中停留。 [Synchronization primitives in the Linux kernel. Part 3](https://0xax.gitbooks.io/linux-insides/SyncPrim/linux-sync-3.html) 指出: 1. The main idea behind spinlock concept is a lock which will be acquired for a very short time. We can't sleep when a lock acquired by a process or thread, because other processes wait us. Context switch is not not allowed because preemption is disabled to avoid deadlocks. 2. semaphores is a good solution for locks which may be acquired for a long time. In other way this mechanism is not optimal for locks that acquired for a short time. CS:APP [Thread-Level Parallelism](http://www.cs.cmu.edu/~213/lectures/26-parallelism.pdf), Page 24-37 ## 核心同步機制從 spinlock 開始 General properties of spinlocks: 1. Loop until another processor releases the lock 2. Should only be used for short critical sections 3. Should always be released before the process/thread goes to sleep 3. Need to have interrupts disabled when locked by ordinary threads, if shared by an interrupt handler 4. Must be initialized explicitly, before use 取自 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/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) ![](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 Linux Spinlocks 1. Are currently based on the "ticket lock" mechanism 2. Also bundle in scheduler-level non-preemption 3. Optionally bundle in interrupt-masking (spin_lock_irqsave()). 搭配閱讀: * [Spin Locks & Other Forms of Mutual Exclusion](https://www.cs.fsu.edu/~baker/devices/notes/spinlock.html) * [從 CPU cache coherence 談 Linux spinlock 可擴展能力議題](https://hackmd.io/s/BJ8djgdnm) [Preemptable ticket spinlocks: improving consolidated performance in the cloud](https://www.slideshare.net/JiannanOuyang/preemptable-ticket-spinlocks-improving-consolidated-performance-in-the-cloud) ## Symmetric Multi-Processing (SMP) 的衝擊 ![](https://i.imgur.com/qrflKxV.png) 搭配閱讀 [Symmetric Multi-Processing](https://linux-kernel-labs.github.io/master/lectures/smp.html) 會造成 race condition 的程式碼: ```clike void release_resource() { counter--; if (!counter) free_resource(); } ``` ![](https://i.imgur.com/eQebIYD.png) 透過 atomics 改寫: ```clike void release_resource() { if (atomic_dec_and_test(&counter)) free_resource(); } ``` ![](https://i.imgur.com/T665HCE.png) Disabling preemption (interrupts) 在早期 i386 的實作 ```clike #define local_irq_disable() \ asm volatile ("cli" : : : „memory”) #define local_irq_enable() \ asm volatile ("sti" : : : „memory”) #define local_irq_save(flags) \ asm volatile ("pushf ; pop %0" :"=g" (flags) : /* no input */: "memory") #define local_irq_restore(flags) \ asm volatile ("push %0 ; popf" : /* no output */ : "g" (flags) :"memory", "cc"); ``` x86 中斷相關指令: [Basic x86 interrupts](https://alex.dzyoba.com/blog/os-interrupts/) * enabled interrupts (sti) * Disable interrupt (cli) queued spin lock ![](https://i.imgur.com/cMes7n0.png) 搭配閱讀: * [Synchronization primitives in the Linux kernel. Part 1](https://0xax.gitbooks.io/linux-insides/SyncPrim/linux-sync-1.html) * [Synchronization primitives in the Linux kernel. Part 2](https://0xax.gitbooks.io/linux-insides/SyncPrim/linux-sync-2.html) ## User vs. Kernel Locks [Linux Locking Mechanisms](https://www.slideshare.net/kerneltlv/linux-locking-mechanisms) livelock? 查閱 [Mutual exclusion, synchronization,communicationin shared memoryOperating systems](https://www.mit.bme.hu/eng/system/files/oktatas/targyak/8699/opre_slides12_mutex_en_1.pdf) 及 [Kernels and Locking](http://retis.sssup.it/~luca/AdvancedOS/kernel_locking.pdf) ![](https://i.imgur.com/MharkvD.png) ![](https://i.imgur.com/J5S6xbd.png) ELC 2017 [Effectively Measure and Reduce Kernel Latency for Real-time Constraints](https://elinux.org/images/a/a9/ELC2017-_Effectively_Measure_and_Reduce_Kernel_Latencies_for_Real-time_Constraints_%281%29.pdf)