互斥鎖

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

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

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

需求

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

實現

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

硬件實現

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

while (test_and_set(lock) == 1);

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

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

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

軟件實現

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

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

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

進階的互斥鎖實現

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

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

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

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

Windows的Mutex對象

Windows作業系統提供了mutex同步對象。它有兩個狀態：

• signaled：如果它不被任何對象擁有；
• nonsignaled：如果它被一個（且至多一個）線程擁有。

Windows API函數CreateMutex或CreateMutexEx建立mutex對象。使用OpenMutex函數打開一個mutex對象。也可以使用DuplicateHandle函數或者父子handle繼承來使用一個無名mutex對象。

任何線程可以使用mutex的控制代碼（handle）於等待函數（wait functions）來獲得這個mutex對象的擁有權。如果該mutex對象正被其他線程擁有，則請求的線程在該等待函數上被阻塞直到擁有的線程呼叫ReleaseMutex函數釋放mutex並被該請求線程取得到擁有權。等待函數的返回值可以鑑別是否獲得了擁有權（該mutex被signaled）或者其他原因（如逾時返回）.

如果多個線程正在等待一個mutex對象，那麼該mutex被signaled時喚醒哪一個線程不能保證遵循先進先出(FIFO)順序。外部事件如非同步過程呼叫可改變等待順序。

如果一個線程擁有了一個mutex對象，該線程可以對該mutex對象執行多次等待函數呼叫而不會被阻塞。釋放mutex對象時，該線程必須呼叫ReleaseMutex函數的次數必須與呼叫等待函數的次數相同。 mutex對象內部有一個遞歸計數，表示獲得了該對象的線程佔用該對象的次數。

擁有mutex對象的線程沒有釋放擁有權就結束了，那麼該mutex對象被放棄（abandoned）. 等待該mutex對象的其他線程可獲得擁有權，但從等待函數得到的返回值為WAIT_ABANDONED。這表示一個錯誤已經發生了，任何被該互斥鎖保護的共用資源處於未定義的狀態。

Windows作業系統的臨界區（critical section）對象類似於mutex對象，但是臨界區對象只能用於一個行程內部。

延伸閱讀與參考書目

• 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

相關條目

• 線程安全