semaphore, mutex, spin lock

深則厲, 淺則揭

這篇和 function reentrant, thread-safe, memory ordering (memory barrier) 一樣是個雜記, 一樣紀錄這三個惱人的東西還有一些自己的問題, 可對照著看。

spin lock, semaphore, mutex 這是在 os 課程中會提到的東西, 但是他們很難懂。其實要能體會他們的不同真的不容易, 如果只有照著教科書的內容解釋, 一定會覺得好像懂了, 又好像沒明白的那種感覺, 所以網路上才有這麼多討論他們的文章。我持續找了一堆相關資料, 總算有點頭緒。我們以 linux 來探討這 3 個惱人的東西。而我也花了很大的力氣才《實作 spinlock on raspberry pi 2》, 但實作出 spinlock 並沒有讓我徹底理解 spinlock, 使用它的情境實在太複雜。

在 linux 中, 寫 device driver 會用到, 也就是 kernel space 會用到; 而寫應用程式也會用到, 這表示在 kernel space, user space 都有這 3 個東西, 那在 kernel space 和 user space 他們有什麼不一樣嗎?

semaphore, mutex 會有睡覺的副作用, 什麼是「睡覺」, 就是原本在執行的這段程式碼, 在執行了 semaphore, mutex 的 function 之後, 有可能會自己把 cpu 讓出去 (有點像是 coroutine 的 yield), 要等一會兒才會再繼續執行; 那 spinlock 呢? 答案很有趣, 在 kernel space 不會, 甚是在 kernel space 的 spinlock 還需要關閉中斷, 很多情境都比 user mode 複雜; 在 user space 一樣會讓出 cpu, 不過是被迫讓出去 (os 排程的管理), 而不是自己讓出去, 我之前沒有意識到有 kernel/user mode 的 spinlock 用法, 把介紹 spinlock 文章寫的特性都搞在一起, 覺得哪裡怪怪的, 最後才裡出頭緒。

那為什麼 spinlock 在 kernel space 不會讓出 cpu 呢? 這是由於設計的關係, 當然也是可以設計讓出 cpu 的, 因為 spinlock 被用來設計在「中斷上下文 (interrupt context)」上使用, 所以才這樣設計, 什麼是「中斷上下文」, 就是中斷的程式碼, 而又因為中斷的程式碼被設計為不能去睡覺 (讓出 cpu), 為什麼呢? 參考以下連結。

中斷上下文 (interrupt context) 不能睡:

• 獲取自旋鎖和禁止中斷的時候為什麼不能睡眠?
• 为什么可能导致睡眠的函数都不能在中断上下文中使用呢？求解答

那可不可以把 mutex 也設計成不要去睡覺, 可以, 那個叫作 - spinlock。

但在 thread programming 中, 也會提到 semaphore, mutex, spinlock。

來談談 user mode 的 semaphore, mutex, spinlock:

mutex vs spinlock
Mutex 屬於 sleep-waiting 類型的鎖。
Spin lock 屬於 busy-waiting 類型的鎖。
只能用在 thread 程式, 如果是兩個 process, 你沒辦法用 mutex/spinlock 去保護共享資源, 共享資源並非只有共享記憶體/變數, file, 硬體資源都是。

mutex vs semaphore
mutex 除了擁有者外還有優先權的概念, 類似 thread 的優先權那樣。

semaphore 原理與操作說明 (節錄其中說明)

一、binary semaphore(二進位信號)

binary semaphore 值只能是 0 或 1, 在邏輯上相當於一個 mutex (互斥鎖)。mutex 使用上與 binary semaphore 具有相同功能, 但是, mutex 主要設計是防止兩個 process (descent: 這裡應該指 thread 吧?) 同時間執行相同的一段code或存取同一資料, 而 binary semaphore 設計上則是限制同時間存取同一資源; 很多應用上 mutex 具有 owner (擁有者) 的概念, 只有鎖住 mutex的 process, 才具有解鎖的權限; 相對的, semaphore 並無此限制。

semaphore 不只能用在 thread 程式, 兩個不同的 process 也可以用 semaphore 共享資源。

不過 3 者的共同點都需要 atomic 的操作。

ref:

• Pthreads 並行編程之 spin lock 與 mutex 性能對比分析
• http://www.makelinux.net/ldd3/chp-5-sect-5
• 《Linux内核同步机制之（一）：原子操作》這篇做了很好的解釋。
• Linux內核同步機制之（四）：spin lock
• Linux內核ARM構架中原子變量的底層實現研究
• Linux內核態搶占機制分析
• Linux 中断、抢占、锁之间的关系
• [轉]Spinlock 簡介
• semaphore的實現機制詳解
• 《程序员的自我修养》中关于加锁不能保证线程安全的一个错误
• spin lock, spin unlock, semaphore, mutex (mutually exclusive), test and set, atomic increase
• 精通 linux 核心開發 the 3rd chapter 10

cortex m3 ref:
http://www.arm.com/files/pdf/cortex-m3_programming_for_arm7_developers.pdf