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

韋侃

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

[關鍵詞]分布式系統(tǒng)，死鎖，進程，資源

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

一、引言

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

二、死鎖類型

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

2.1 資源型死鎖（resource deadlock）

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

2.2 消息型死鎖（message deadlock）

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

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

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

3.1 進程與資源的分布性

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

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

3.2 死鎖的虛假性

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

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

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

四、死鎖的解除與恢復

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

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

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

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

五、死鎖預防

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

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

（1）資源型死鎖的預防

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

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

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

5.2 摒棄“環(huán)路等待”條件

（1）線形排序法、

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

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

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

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

參考文獻

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

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