Mutex, Semaphore, the difference, and Linux kernel

名詞定義

  • Mutex: Linux kenrel 中的 mutex lock, <include/mutex.h>
  • Semaphore: Linux kernel 中的 semaphore, <include/semaphore.h>
  • mutual exclusion: 中翻互斥鎖,一個概念,為了防止 concurrency 狀況下出現 race condition.

 

Mutex 與 Semaphore 最大的差異是:

理論上,你應該要先跟面試官或是問你這個問題的人互動,詢問一下其所謂的差異是指哪個部份 (實作、用途、還是結構?),以及詢問這個問題時,想要將兩者應用在那邊,對於後續的回答會有所幫助。

  • 30秒:最大的差異在於 Mutex 只能由上鎖的 thread 解鎖,而 Semaphore 沒有這個限制,可以由原本的 thread 或是另外一個 thread 解開。另外,Mutex 只能讓一個 thread 進入 critical section,Semaphore 的話則可以設定要讓幾個 thread 進入。這讓實際上使用 Mutex 跟 Semaphore 場景有很大的差別。
    _
  • 60秒 (cont.):舉例而言,Mutex 的兩個特性:一個是只能有持鎖人解鎖、一個是在釋放鎖之前不能退出的特性,讓 Mutex 叫常使用在 critical section 只能有一個 thread 進入,而且要避免 priority inversion 的時候;Semaphore 也能透過 binary semaphore 做到類似的事情,卻沒有辦法避免 priority inversion 出現。
    _
  • 120秒 (cont.):而 Semaphore 更常是用在同步兩個 thread 或功能上面,因為 Semaphore 實際上使用的是 signal 的 up 與 down,讓 Semaphore 可以變成是一種 notification 的作用,例如 A thread 執行到某個地方時 B thread 才能繼續下去,就可以使用  Semaphore 來達成這樣的作用。

 

接下來可以在延伸談到一些 Fact checks、priority inversion 跟 Linux kernel 實作的部份:

在 Linux kernel 中,一開始是只有 semaphore 這個 structure,直到 2.6.16 版當中才把 mutex 從 semaphore 中分離出來 (這點可以從 LDD3e* 看出來)。雖然 Mutex 與 Semaphore 兩者都是休眠鎖,但是 Linux kernel 在實作 Mutex 的時候,有用到一些加速的技巧,將上鎖分為3個步驟:

  1. Fast path: 嘗試使用 atomic operation 直接減少 counter 數值來獲得鎖。
  2. Mid path: 第一步失敗的話,嘗試使用特化的 MCS spinlock 等待然後取鎖。
    當持鎖的 thread 還在運行,而且沒有存在更高 priority 的 task 時,我們可以大膽假設,持鎖 thread 很快就會把 thread 釋放出來 (看看 code 就知道了),因此會使用一個特化的 MCS spinlock 等待鎖被釋放。特化的 MCS spinlock 可以在被 reschedule 的時候退出 MCS spinlock queue。當走到這步時,就會到 Slow path。
  3. Slow path: 鎖沒有辦法取得,只好把自己休眠了。
    走到這一步,mutex 才會將自己加入 wait-queue 然後休眠,等待有人 unlock 後才會被喚醒。

 

當然這樣是會有代價的,Mutex 成為了 Linux kernel 中最大的一個鎖,在 x86-64 的環境下需要使用 40 bytes,相比於 semaphore 只需要使用 24 bytes,實在是大上許多。大的意思代表會佔用掉更多的 CPU cache (回頭看 phonebook) 跟 memory footprint。

而在 Linux kernel v4.6.0-rc2 中,使用 semaphore 的部份只有 75 處 (加上 drivers),mutex 則使用在 1463  個地方

  • semaphore in Linux kernel: 75 parts (#include <linux/semaphore.h>)
  • mutex in Linux kernel: 1463 parts (#include <linux/mutex.h>)

 

通常也不會把 Semaphore 當作是 Mutex 來使用,而是利用 signal 的特性,同步不同 thread 之間的工作。

Reference

 

補充 Jim Huang 所提不足之處:https://www.facebook.com/groups/system.software2016/permalink/1149793665100137

[#Week5] 課堂時段,我用「semaphore 和 mutex 的差異」來當模擬面試的問題,對 呂紹榕 (Louie Lu) 同學提問,儘管他當時表現不佳,事後他整理在網誌中,請見: https://blog.louie.lu/…/mutex-semaphore-the-difference-and…/

先不講內容,以面試技巧的觀點,他的回答方式有以下不足:

(a) 沒有提到實際應用案例,特別是自己的開發經驗中的差異;

(b) 設計 30 秒、60 秒,以及 120 秒回答問題的方式很好,但互動性不足,要考慮到部分面試主管缺乏耐心,可能會在中途打斷。既然一開始就提到「很大的差異」,後方就該要讓人體會到差異,特別是兩者不可 interchangeable 的特性;

(c) 既然會提到 Linux,在 30 秒回答的時候,可一併指出「我先探討定義,之後用 Linux 核心作為分析對象」

再來我們看呂同學的回覆,有什麼內容的問題呢?

(1) 先跟面試主管釐清「其所謂的差異是指哪個部份 (實作、用途、還是結構?)」之後,接續的答覆應該要能夠延續並且針對特定情境去探討,比方說 file system 使用 mutex 或 semaphore 的時機;

(2) semaphore 可用於非同步事件通知,而且 semaphore 包含狀態,我們可在 thread / process 中得知 blocking 的行為,這時可一併對照mutex + condition variable 的操作;

(3) POSIX semaphore 和 SysV semaphore 不同,很容易令人混淆,遇到面試主管有意或無意具體指出問題時,應該明確列舉出差異;




如果你覺得這篇文章不錯,歡迎打賞 IOTA:RFHEIVXVIZWJFXTZORZZRCMHZF9PSGFUFWAAKXTFNZE9JQUY9HFQREJYYSPSXDRLECKXCAQQDOMSMYJYDKPCKWXBKD

或是點選下方圖片贊助我一杯咖啡:

Leave a reply:

Your email address will not be published.

這個網站採用 Akismet 服務減少垃圾留言。進一步瞭解 Akismet 如何處理網站訪客的留言資料