互斥鎖

互斥鎖（英語：英語：Mutual exclusion，縮寫 Mutex）是一種用於多線程編程中，防止兩條線程同時對同一公共資源（比如全域變數）進行讀寫的機制。該目的通過將代碼切片成一個一個的臨界區域（critical section）達成。臨界區域指的是一塊對公共資源進行存取的代碼，並非一種機制或是演算法。一個程式、行程、線程可以擁有多個臨界區域，但是並不一定會應用互斥鎖。

需要此機制的資源的例子有：旗標、佇列、計數器、中斷處理程式等用於在多條並列執行的代碼間傳遞數據、同步狀態等的資源。維護這些資源的同步、一致和完整是很困難的，因為一條線程可能在任何一個時刻被暫停（休眠）或者恢復（喚醒）。

例如：一段代碼（甲）正在分步修改一塊數據。這時，另一條線程（乙）由於一些原因被喚醒。如果乙此時去讀取甲正在修改的數據，而甲碰巧還沒有完成整個修改過程，這個時候這塊數據的狀態就處在極大的不確定狀態中，讀取到的數據當然也是有問題的。更嚴重的情況是乙也往這塊地方寫數據，這樣的一來，後果將變得不可收拾。因此，多個線程間共用的數據必須被保護。達到這個目的的方法，就是確保同一時間只有一個臨界區域處於執行狀態，而其他的臨界區域，無論是讀是寫，都必須被掛起並且不能獲得執行機會。

需求

• 不准永遠耽擱一個要求進入臨界區域的線程，造成死結或是飢餓發生 。
• 若沒有任何線程處於臨界區域時，任何要求進入臨界區域的線程必須立刻得到允許。
• 不能對線程的相對速度與處理器的數目做任何假設。
• 線程只能在臨界區域內停留一有限的時間。
• 任何時間只允許一個線程在臨界區域執行。
• 在臨界區域停止執行的線程，不准影響其他線程執行。

實現

依實現方式可分為硬件實現和軟件實現兩種。

硬件實現

單核心系統上最常見的方式就是關閉儘可能多的可能對共用數據段進行讀寫的指令中斷。這樣一來就可以避免在臨界區域中暫停程式執行，或是來自硬件的要求修改目標共用數據段的中斷請求。多核心系統上則通過檢查並置位（取得原始值並指定新值）機制達成，當一個核心需要另一個核心佔用的資源的時候，該核心將不斷的查詢所有核心間共用的佔用旗標，直到另一個核心將佔用旗標復位為未使用為止。相關的為代碼如下所示：

while (test_and_set(lock) == 1);

lock的值為1則表示鎖被佔用，為0則是空閒。

在檢查並置位機制中，一個核心在對旗標執行讀寫的過程當中不會釋放佔用的訪問匯流排。該種方法又稱為自旋鎖。

類似的原子操作，如比較並交換機制，則更常用於對鏈結串列等數據結構進行不阻斷同步。

軟件實現

類似的方式也有通過軟件模擬達成的。但是該種模擬會對電腦造成極大的負荷，因為申請佔用自旋鎖的過程中會不間斷地對一個標誌位進行讀寫，並且該種模擬不允許亂序執行，因為這會破壞其機制。

更為常見的是使用作業系統提供的互鎖庫，這種庫通常設計為在有硬件支援時使用硬件機制，僅在找不到支援的硬件時才用軟件模擬，並且結合線程排程對鎖效能進行最佳化。比如一個線程要使用一個已經被佔用的鎖，這時候作業系統會把這個線程掛起，然後切換上下文到另外一個可以繼續執行的線程，若是沒有別的線程要繼續執行的話，系統就讓處理器進入低功耗狀態，而不是讓這個線程消耗大量處理能力進行自旋來等待鎖釋放。

現代的互斥鎖大多使用佇列和上下文交換以達到節約資源和降低延遲的目的。但是總有些情況下，掛起一個行程，然後過一陣子再恢復所用的時間會比讓行程在那裏自旋等待用的時間長。在這種情況下則更多會使用自旋鎖。

進階的互斥鎖實現

除了上述的基礎互斥鎖，還有一些更進階的實現方式，如：

• 訊號標
• 重入鎖
• 監視器
• 訊息佇列
• 元組空間

這些鎖各有各的副作用。例如一個常見的訊號標會允許死結的發生（兩條線程各自取得了一個訊號標，然後都在等待對方釋放另外一個）。其他可能會出現的現象有優先級倒置（高優先級的程式等待低優先級的程式完成）、資源饑荒（某個線程一直得不到足夠的鎖資源）等。

目前的研究多側重於消除這些副作用上，例如不阻斷同步，但是並沒有完美的解決方案。

延伸閱讀與參考書目

• Michel Raynal: Algorithms for Mutual Exclusion, MIT Press, ISBN 0-262-18119-3
• Sunil R. Das, Pradip K. Srimani: Distributed Mutual Exclusion Algorithms, IEEE Computer Society, ISBN 0-8186-3380-8
• Thomas W. Christopher, George K. Thiruvathukal: High-Performance Java Platform Computing, Prentice Hall, ISBN 0-13-016164-0
• Gadi Taubenfeld, Synchronization Algorithms and Concurrent Programming, Pearson/Prentice Hall, ISBN 0-13-197259-6
• Article "Common threads: POSIX threads explained - The little things called mutexes" by Daniel Robbins
• Mutual exclusion algorithm discovery
• Mutual Exclusion Petri Net
• Mutual Exclusion with Locks - an Introduction
• Mutual exclusion variants in OpenMP
• The Black-White Bakery Algorithm