DISTRIBUTED SYSTEMS中死鎖問題解決方法研究

韋侃

[摘要]本文介紹了分布式系統下出現死鎖的原因，類型。分布式系統死鎖的檢測，在檢測中出現的問題。以及預防分布式系統死鎖和解決分布式系統死鎖的方法。

[關鍵詞]分布式系統，死鎖，進程，資源

[中圖分類號][C94] [文獻標識碼]A [文章編號]1672-5158（2013）06-0392-02

一、引言

分布式系統就是把多個處理機通過線路互連而構成系統，它的處理和控制功能分布在各處理機上。在系統中的一組進程，由于競爭系統資源或由于彼此通信而永遠阻塞，我們稱這些進程處于死鎖狀態。產生死鎖的原因，可歸結為兩點：（1）競爭資源，（2）進程推進順序非法。

二、死鎖類型

總的來說，系統中的資源可分為兩種類型：可剝奪性資源，如處理機，存儲器等；非剝奪性資源，如打印機，磁帶機等；在網絡和分布式系統中上述兩種資源都可能引起以下兩種類型的死鎖：

2.1 資源型死鎖（resource deadlock）

當有一組進程競爭非剝奪性資源時，如果出現因進程的推進順序不正確，進入了不安全區，導致發生進程死鎖。

2.2 消息型死鎖（message deadlock）

在不同結點中的進程，為發送和接收分組而競爭緩沖區，以致發生了既不能發送消息，也不能接收消息的僵持狀態。典型的消息型死鎖有三種類型：重新組裝型死鎖（reassembly deadlock）、直接存儲-轉發型死鎖（direct store-and-forward deadlock）、間接存儲-轉發型死鎖。

三、死鎖檢測中出現的問題

分布式系統下產生的死鎖與單機系統下產生死鎖有很多相似，其產生原因和必要條件，基本相同。但也有著自己的一系列特殊性。

3.1 進程與資源的分布性

在單機環境下，非剝奪性資源和一組競爭該資源的進程都處于同一系統中。相應地，在系統中設置一個死鎖檢測機構，由它統一監視和計算機使用共享資源時，是否會出現環路條件。

在分布式環境下，可供全網共享的資源是分布在各個結點中，而競爭資源的進程又是來自于不同的結點。然而，擁有共享資源的每個結點，通常都只知道本結點中資源的使用情況。因此，要檢測來自不同結點的進程在競爭共享資源時是否會引起死鎖，無疑是十分困難的。

3.2 死鎖的虛假性

在單機環境下，當一組進程競爭非剝奪性資源時，如果在資源分配圖中已經檢測到出現了環行鏈，說明這組進程中的每個進程，至少都保持了一個其后繼進程所需的資源。則可認為此時發生了進程死鎖。

然而，分布系統環境下，如果檢測出資源分配圖中出現了環行鏈，卻不能認為是發生了真正的死鎖，此時的死鎖可能是真正的死鎖。也可能是虛假的死鎖。因為在分布式系統環境下存在著進程發出的請求資源和釋放資源的時序性。

在圖1（a）所示的資源分配圖中，有一組進程p1，p2，p3。其中，p1保持資源R1又請求資源R2；p2保持R2又請求R3；p3保持R3。假設此時p3又先發出釋放R3的命令，然后再發出請求R1的命令。如果釋放R3的命令先到達，環路檢測進程，而p3請求R1的命令后到達，則此時會出現圖1（b）所示的資源分配圖，從圖可知，這組進程未進入死鎖狀態。但如果p3請求R1的命令比它釋放R3的命令先到達檢測進程，此時的資源分配圖，將如圖（c）所示出現了環路，因而檢測進程認為發生了死鎖。然而，此時的死鎖是虛假的。因為當釋放R3的命令到達后，在圖中的R3到p3的分配邊將被消去，環路條件不成立。

四、死鎖的解除與恢復

在網絡和分布式系統環境下，資源型死鎖的解除方法與單機系統時類似，當然要復雜得多。對于消息型死鎖，由于消息是一種特殊形式的資源，它很容易產生、控制和復制，致使其解除死鎖的方法，比資源型死鎖的解除方法更多且更方便。例如，當發現分組在網絡中傳輸過多時，就會很容易因緩沖區的不足而產生死鎖，這時就可采取禁止主機產生新的消息并送入網絡的方法來避免死鎖。又如，當某個結點沒有足夠的緩沖區來接收新的分組的時候，可以利用流量控制機構，來禁止源結點繼續向本結點發送分組，或者可以將到達的分組丟棄，以避免死鎖的發生。在發生死鎖時，可通過撤銷一部分網絡中正在傳輸分組的方法來解決死鎖。

當檢測到一組進程處于死鎖中，應立即采用事先商定好的死鎖恢復算法將死鎖解除，以使系統恢復正常工作。死鎖恢復方法有：

（1）殺死處于死鎖狀態中的一個或若干個進程。或干脆殺掉所有的死鎖過程，然后回收它們占有的資源，以解除死鎖。這是比較簡單的方法，也是分布式操作系統常用死鎖恢復方法。

（2）系統周期性地對進程進行檢查，在每個檢查點都將進程的狀態寫入文件以便需要時備用。這樣做也為進程從死鎖中恢復提供了幫助。當死鎖發生時，將死鎖的進程回退到前面備份的檢查點，然后再重新啟動所有的進程。則該檢查點以后的工作將被丟棄。這種方法實現起來要比第（1）種方法復雜得多，開銷也大，而且可能會導致再次死鎖的分險。但在并發系統中這種可能性幾乎為零。

五、死鎖預防

為了防止在網絡中出現死鎖，可以采取摒棄產生死鎖的四個必要條件之一的方法來實現。

5.1 摒棄“請求和保持”條件

（1）資源型死鎖的預防

像單機系統一樣，為防止進程爭奪網絡資源而發生死鎖，可讓所有的進程在運行之前，一次性地申請其所需的全部網絡資源。這樣，進程在運行中便不會再提出資源請求，從而摒棄了請求條件。如果網絡無法滿足進程的所有資源要求，便不把任何資源分配給該進程，這樣也就摒棄了保持條件。

（2）重新組裝型死鎖的預防

為了避免發生重裝型死鎖，源結點中的發送進程在發送一分報文中的各個分組之前，應一次性地向目標結點申請一份報文所需的全部緩沖區。如果目標結點有足夠的緩沖區，便為發送進程如數地分配其所需的全部緩沖區。這樣，發送進程在傳送這些分組時，便不會再提出緩沖區請求，因而摒棄了請求條件，目標結點若無足夠的緩沖區，便一個也不分配給發送進程，于是也就摒棄了保持條件。

5.2 摒棄“環路等待”條件

（1）線形排序法、

將網絡中所有可供共享的網絡資源，進行線形排序。同時，要求所有進程對網絡資源的請求，嚴格按資源號遞增的次序提出申請。這樣便可防止在資源分配圖中出現“環路等待”條件。

（2）等待死亡（waiFdie）算法

該算法用于分布式數據庫系統的并發控制。這里把能并發執行的基本單位稱為事物。在創建一個事物T時，便為它打上一個時間郵戳（timestamp）e（T），并建立一個嚴格的按時間排序的事物序列。如果某一資源R1已被事物T1占有而又被事物T2請求時，檢測機構比較兩個事物的時間郵戳，如e（T2）

綜上所述我們可以知道，對于分布式環境下的死鎖檢測，所付出的通信開銷是非常大的，而且還可能出現虛假死鎖。所以我們在實際應用中，主要還是采用預防死鎖的方法。

參考文獻

[1]屠祁，屠立德等著，《操作系統基礎》，北京：清華大學出版社，2000年9月，第120～160頁

[2]何炎祥，宋文欣，彭鋒編著，《高級操作系統》，北京：科學出版社，1999年4月，第178～281頁