英語

通用互斥鎖子系統

由 Ingo Molnar <mingo@redhat.com> 發起

由 Davidlohr Bueso <davidlohr@hp.com> 更新

什麼是互斥鎖？

在 Linux 核心中，互斥鎖指的是一種特定的鎖定原語，它在共享記憶體系統上強制執行序列化，而不僅僅是指學術界或類似理論教科書中發現的指代“互斥”的一般術語。 互斥鎖是睡眠鎖，其行為類似於二進位制訊號量，於 2006 年 [1] 作為這些訊號量的替代品引入。 這種新的資料結構提供了許多優點，包括更簡單的介面，以及當時更小的程式碼（參見缺點）。

[1] https://lwn.net/Articles/164802/

實現

互斥鎖由“struct mutex”表示，定義在 include/linux/mutex.h 中，並在 kernel/locking/mutex.c 中實現。 這些鎖使用原子變數 (->owner) 來跟蹤其生命週期內的鎖狀態。 欄位 owner 實際上包含指向當前鎖所有者的 struct task_struct *，因此如果當前未被擁有，則為 NULL。 由於 task_struct 指標至少對齊到 L1_CACHE_BYTES，因此低位 (3) 用於儲存額外狀態（例如，等待者列表是否非空）。 在其最基本的形式中，它還包括一個等待佇列和一個序列化對其訪問的自旋鎖。 此外，CONFIG_MUTEX_SPIN_ON_OWNER=y 系統使用一個旋轉 MCS 鎖 (->osq)，如下面 (ii) 中所述。

當獲取互斥鎖時，根據鎖的狀態，可以採用三種可能的路徑

  1. fastpath：嘗試透過 cmpxchg() 將所有者與當前任務進行原子交換來獲取鎖。 這僅適用於無競爭的情況（cmpxchg() 針對 0UL 進行檢查，因此上面的所有 3 個狀態位都必須為 0）。 如果鎖存在競爭，則會轉到下一個可能的路徑。

  2. midpath：又名樂觀旋轉，嘗試在鎖所有者正在執行且沒有其他準備執行且優先順序更高的任務時旋轉以進行獲取（need_resched）。 理由是，如果鎖所有者正在執行，則很可能會很快釋放鎖。 互斥鎖旋轉器使用 MCS 鎖排隊，以便只有一個旋轉器可以競爭互斥鎖。

    MCS 鎖（由 Mellor-Crummey 和 Scott 提出）是一個簡單的自旋鎖，具有公平的理想屬性，並且每個 CPU 嘗試獲取鎖時都在本地變數上旋轉。 它可以避免常見的測試和設定自旋鎖實現所產生的昂貴的快取行反彈。 類似於 MCS 的鎖是專門為睡眠鎖實現的樂觀旋轉而定製的。 定製 MCS 鎖的一個重要特性是，當旋轉器需要重新排程時，它們能夠退出 MCS 自旋鎖佇列。 這進一步有助於避免需要重新排程的 MCS 旋轉器繼續等待旋轉互斥鎖所有者，而只是在獲得 MCS 鎖後直接進入慢速路徑的情況。

  3. slowpath：最後的手段，如果仍然無法獲取鎖，則將任務新增到等待佇列並休眠，直到被解鎖路徑喚醒。 在正常情況下，它會以 TASK_UNINTERRUPTIBLE 狀態阻塞。

雖然形式上核心互斥鎖是可睡眠鎖，但正是路徑 (ii) 使它們在實踐中更像是一種混合型別。 透過簡單地不中斷任務，並忙等待幾個週期而不是立即休眠，已經看到這種鎖的效能顯著提高了許多工作負載。 請注意，該技術也用於讀寫訊號量。

語義

互斥鎖子系統檢查並強制執行以下規則

  • 一次只能有一個任務持有互斥鎖。

  • 只有所有者才能解鎖互斥鎖。

  • 不允許多次解鎖。

  • 不允許遞迴鎖定/解鎖。

  • 互斥鎖必須僅透過 API 初始化（見下文）。

  • 任務不得在持有互斥鎖的情況下退出。

  • 不得釋放持有鎖所在的記憶體區域。

  • 不得重新初始化持有的互斥鎖。

  • 互斥鎖不得用於硬體或軟體中斷上下文，例如 tasklet 和定時器。

當啟用 CONFIG_DEBUG_MUTEXES 時，將完全強制執行這些語義。 此外，互斥鎖除錯程式碼還實現了許多其他功能，使鎖除錯更容易和更快

  • 只要在除錯輸出中列印互斥鎖，就使用互斥鎖的符號名稱。

  • 獲取點跟蹤、函式名稱的符號查詢、系統中持有的所有鎖的列表、它們的列印輸出。

  • 所有者跟蹤。

  • 檢測自遞迴鎖並打印出所有相關資訊。

  • 檢測多工迴圈死鎖並打印出所有受影響的鎖和任務（以及僅那些任務）。

互斥鎖 - 以及大多數其他睡眠鎖（如 rwsems）- 不會為其佔用的記憶體提供隱式引用，該引用會透過 mutex_unlock() 釋放。

[ 這與 spin_unlock() [或 completion_done()] 形成對比，後者

API 可用於保證在 spin_unlock()/completion_done() 釋放鎖後，鎖實現不會觸及該記憶體。 ]

mutex_unlock() 甚至可能在內部已經釋放鎖後訪問互斥鎖結構 - 因此對於另一個上下文來說，獲取互斥鎖並假設 mutex_unlock() 上下文不再使用該結構是不安全的。

互斥鎖使用者必須確保在釋放操作仍在進行時不會銷燬互斥鎖 - 換句話說，mutex_unlock() 的呼叫者必須確保互斥鎖在 mutex_unlock() 返回之前保持活動狀態。

介面

靜態定義互斥鎖

DEFINE_MUTEX(name);

動態初始化互斥鎖

mutex_init(mutex);

獲取互斥鎖，不可中斷

void mutex_lock(struct mutex *lock);
void mutex_lock_nested(struct mutex *lock, unsigned int subclass);
int  mutex_trylock(struct mutex *lock);

獲取互斥鎖，可中斷

int mutex_lock_interruptible_nested(struct mutex *lock,
                                    unsigned int subclass);
int mutex_lock_interruptible(struct mutex *lock);

獲取互斥鎖，可中斷，如果 dec 為 0

int atomic_dec_and_mutex_lock(atomic_t *cnt, struct mutex *lock);

解鎖互斥鎖

void mutex_unlock(struct mutex *lock);

測試互斥鎖是否被佔用

int mutex_is_locked(struct mutex *lock);

缺點

與其最初的設計和目的不同，“struct mutex”是核心中最大的鎖之一。 例如：在 x86-64 上它是 32 位元組，而“struct semaphore”是 24 位元組，rw_semaphore 是 40 位元組。 較大的結構大小意味著更多的 CPU 快取和記憶體佔用。

何時使用互斥鎖

除非互斥鎖的嚴格語義不合適，並且/或者臨界區阻止鎖被共享，否則始終優先於任何其他鎖定原語。