互斥鎖

互斥鎖（英語：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

相關條目

• 執行緒安全