本頁使用了標題或全文手工轉換

互斥鎖

維基百科,自由的百科全書
跳到: 導覽搜尋

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

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

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

需求[編輯]

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

實作[編輯]

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

硬件實作[編輯]

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

while (test_and_set(lock) == 1);

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

在檢查並置位機制中,一個核心在對旗標執行讀寫的過程當中不會釋放佔用的存取總線。該種方法又稱為自旋鎖

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

軟件實作[編輯]

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

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

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

高階的互斥鎖實作[編輯]

除了上述的基礎互斥鎖,還有一些更高階的實作方式,如:

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

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

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物件被放棄(abandoned). 等待該mutex物件的其他執行緒可獲得擁有權,但從等待函數得到的返回值為WAIT_ABANDONED。

Windows作業系統的臨界區(critical section)物件類似於mutex物件,但是臨界區物件只能用於一個行程內部。

延伸閱讀與參考書目[編輯]