死鎖

定義: 當兩個以上的運算單元,雙方都在等待對方停止運行,以獲取系統資源,但是沒有一方提前退出時,就稱為死鎖。

一組進程中,每個進程都無限等待被該組進程中另一進程所占有的資源,因而永遠無法得到的資源,這種現象稱為進程死鎖

資源

在進程對設備、文件等取得排他性訪問權時,有可能會出現死鎖。這類需要排它性使用的對象稱為資源 (resource)。資源分為以下兩類:

  • 可搶占資源: 可以擁有其他進程搶占而不會産生副作用 (如: 存儲器)。

  • 不可搶占資源: 不引起相關的計算失敗的情況下,無法把它從占有它的進程處搶占過來 (與死鎖有關)。

死鎖與不可搶占資源有關,有關可搶占資源的潛在死鎖通常可以通過在進程之間重新分配資源而化解。

資源死鎖

死鎖發生時,以下四個條件必須滿足:

  1. 互斥條件: 每個資源要麽已經分配給一個進程,要麽就是可用的。
  2. 占有和等待條件: 已經得到了某個資源的進程可以再請求新的資源。
  3. 不可搶占條件: 已經分配給一個進程的資源不能被強制性地搶占,它只能被占有它的進程顯示地釋放
  4. 環路等待條件: 死鎖發生時,系統中一定有由兩個或兩個以上的進程組成的環路,該環路中的每個進程都在等待著下一個進程所占有的資源

處裏死鎖的策略

死鎖檢測

檢測死鎖分為策略可分為兩種:

  • 每種類型一個資源的死鎖檢測: 可以使用一個簡單的算法,依次將每一個節點作為一棵樹的根結點,並進行深度優先搜索。如果碰到已經遇到過的節點,那麽就算是找到了一個環。如果從任何給定的節點出發的弧都被窮舉了,那麽就回溯到前面的節點。如果回溯到根並且不能再深入下去,那麽從當前節點出發的子圖就不包含任賀環。如果所有的節點都是如此,那麽整個圖就不存在環,也就是說系統不存在死鎖。
  • 每種類型多個資源 (多種相同的資源) 的死鎖檢測: 算法的第1步是尋找可以運行完畢的進程,該進程的特點是它有資源請求並且可被當前的可用資源滿足。這一選中的進程隨後就被運行完畢,再這段時間內它釋放自己持有的所有資源並將它們返回到可用資源庫中。然後這一資源被標記為完成。如果所有的進程最終都能運行完畢的話,就不存在死鎖的情況。如果其中某些進程一直不能運行,那麽它們就是死鎖進程。

死鎖恢複

假設已經檢測到死鎖,接下來就需要一些方法來使系統重回正軌。可以使用以下方法來對死鎖情況進行恢複:

  1. 利用搶占恢複: 再不通知原進程的情況下,將某一資源從一個進程強行取走給另一個進程使用,接著又送回,這種做法的可行性取決于該資源本身的特性。這種方法比較困難且不可能,若選擇挂起某個進程,則在很大程度上取決于哪個進程擁有比較容易回收回的資源。
  2. 利用回滾恢複: 周期性地對進程進行檢查點檢查 (checkpointed)。進程檢查點檢查就是將進程的狀態寫入一個文件以備以後重啓。為了使這一過程更有效,新的檢查點不應覆蓋原有的文件,而應該寫到新文件中。這樣,當進程執行時,將會有一系列的檢查點文件累積。一旦檢測到死鎖,就很容易發現需要哪些資源。為了進行恢複,要從一個較早的檢查點上開始,這樣擁有所需資源的進程會回滾到一個時間點,在此時間點之前該進程獲得了一些其他的資源。在該檢查點後所做的工作都丟失。簡單來說,就是將該進程複位到一個更早的狀態,那時它還沒有取的所需的資源,接著就把這個資源分配給一個死鎖進程。
  3. 通過殺死進程恢複: 殺死一個或若幹個進程。一種方法是殺掉環中的一個進程,如果走運的話,其他進程將可以繼續。如果行不通的話,就需要繼續殺死別的進程直到打破死循環。另一種方法是選一個環外的進程作為犧牲品以釋放該進程的資源。在使用這種方法時要特別小心,它可能正好持有環中某些進程所需的資源。最好是殺死可以從頭開始運行而且不會帶來副作用的進程。

死鎖避免

通過跟蹤哪一個狀態是安全狀態,那一個狀態是不安全狀態,可以避免資源死鎖。安全狀態就是: 存在一個事件序列,保證所有的進程都能完成。不安全狀態 (非等同于死鎖) 就沒有這樣的保證。

可以使用銀行家算法 (banker’s algorithm)來避免死鎖的發生。該算法對每一個請求進行檢查,檢查如果滿足這一請求後是否會到達安全狀態 (即如果沒有死鎖發生,並且即使所有進程突然請求對資源的最大需求,也仍然存在某種調度次序能夠使得每個進程運行完畢)。如是,那麽就滿足該請求。否則,就推遲這一請求的滿足。為了檢查狀態是否安全,銀行家需要考慮它是否有足夠的資源滿足某一個客戶。如果可以,那麽這筆代就是能夠收回的,並且接著檢查最接近最大限額的一個客戶,以此類推。如果所有投資最終都能被收回,那麽該狀態是安全的,最初的請求可以被批準。本質上來說不可能實現,因為他需要獲知未來的請求,而這些請求是不可知的

死鎖預防

  • 破壞互斥條件: 一切都使用假脫機技術 (指傳輸數據的過程中,將數據存放在臨時工作區中,其它程序可以在之後的任意時間點對其訪問,其運許若幹個進程同時産生輸出)。有可能無法達到預期效果。但有一個思想是經常可適用的,那就是避免分配那些不是絕對必須的資源,做到盡可能少的進程可以真正請求資源。

  • 破壞占有並等待條件: 思想是只要禁止已持有資源的進程再等待其他資源便可以消除死鎖。一種方法是規定所有進程在開始執行前就請求所需的全部資源。如果資源都可用,就將他們分配給這個進程,于是該進程肯定能夠運行結束。如果有一個或多個資源正被使用,那麽就不進型分配,進程等待。這將會造成一個問題是很多進程直到運行時才知到它需要多少資源 (如果提前知道便可以使用銀行家算法)。另一個問題是這種方法的資源利用率不是最優的。也有另一種方案,即要求當一個進程請求資源時,先站時釋放其當前所占用的所有資源,然後再嘗試一次獲得所需的全部資源。

  • 破壞不可搶占條件: 搶占資源並通過虛擬化的方式來避免搶占可能發生的混亂。

  • 破壞環路等待條件: 消除該條件有幾種方法。一種是保證每個進程在任何時刻只能占用一個資源,如果要請求另外一個資源,他必須先釋放第一個資源。另一種是將所有資源統一編號。進程可以在任何時可提出資源請求,但是所有請求必須按照資源編號的順序提出

死鎖相關問題

兩階段加鎖 (two-phase locking)

在很多數據庫系統中,一個經常發生的操作是請求鎖住一些記錄,然後更新所有鎖住的記錄。當同時有多個進程運行時,就有出現死鎖的危險。避免此情況的常用方法是兩階段加鎖。在第一階段,進程試圖對所有所需的記錄進行加鎖,一次鎖一個記錄。如果第一階段加鎖成功,就開始第二階段,完成更新然後釋放鎖。在第一階段並沒有做實際的工作。某種意義上來說,這種方法類似于提前或者出現一些不可逆操作之前請求所有資源。

通信死鎖

該死鎖通常發生在通信系統(比如網絡)中。一種普遍的情形是,兩個或兩個以上進程利用發送信息來通信時,進程A向進程B發送請求消息,然後阻塞直至B回複。假設請求信息丟失,A將阻塞以等待回複,而B會阻塞等待一個向其發送命令的請求,因此發生死鎖。與資源死鎖不同的是,通信死鎖是協同同步的異常,處于這種死鎖中的進程如果是各自獨立執行的,則無法完成服務。而資源死鎖是競爭性同步的問題,進程在執行過程中如果與競爭的進程無交叉,便會順利執行。為避免通信死鎖,一般使用以下兩種技術:

  1. 超時策略: 設定時間以確認信息丟失。
  2. 協議: 避免超時策略設定時間太短引發重複發送信息。

活鎖

與死鎖有些相似,那就是它也可以停止所有的轉發進程。在某些情況下,進程意識到它不能獲取下一個鎖時,就會嘗試禮貌地釋放已經獲得的鎖,然後等待並再次嘗試。如果有另一進程同時做出這個動作,二者便會不斷地重複相同動作互相讓路,形成活鎖 (過程因為沒有進程阻塞,因此不構成死鎖)。由于活所包含了一些實際上並沒有鎖住的進程,因此可以通過先到先得的資源分配策略來避免饑餓

饑餓 (starvation): 在動態運行的系統中,在任何時刻都可能請求資源,這時就需要一些策略來決定誰獲取什麽資源,可能會導致一些進程永遠得不到服務 (非死鎖),從而饑餓至死 (無限制地推後,盡管他沒有被阻塞)。可以通過先到先得的資源分配策略來避免,等待最久的進程會是下一個被調度的進程,使最終都能夠獲得資源。