分布式計算系統中死鎖的預防與檢測

賴河蒗

摘要：在分布式的網絡環(huán)境下，死鎖的避免、預防、檢測以及糾正都變得極為困難。針對這種情況，了解死鎖發(fā)生的原因以及掌握如何對死鎖進行預防以及檢測的方法就顯得具有非常重要的意義。為此，首先介紹了死鎖的定義以及死鎖發(fā)生的條件，接著分別介紹了死鎖的預防方法以及死鎖的檢測方法，最后得出結論在分布式環(huán)境下研究有效應對死鎖策略迫在眉睫。

關鍵詞：分布式；死鎖；預防；檢測；網絡環(huán)境

中圖分類號：TP393 文獻標識碼：A 文章編號：1009-3044（2014）26-6049-02

Abstract： In a distributed network environment， deadlock avoidance， prevention， detection， and correction have become extremely difficult. In view of this situation， it is a very important significance， which is to understand the reasons for the deadlock occurred and to learn the methods of how to prevent and detect deadlock. For this reason， firstly introduces the definition of deadlock and conditions of deadlock occurred， then introduces the prevention and detection methods of deadlock， finally has concluded in a distributed environment that it is very imminent to research strategies to effectively deal with the deadlock.

Key words： Distributed； deadlock； prevention； detection； network environment

1 分布式計算系統中的死鎖

分布式計算機系統是一種具有多處理器并且各個處理器之間通過互連網絡構建成一個具有整體功能的計算機系統。系統工作的原理是采用分布式計算結構，即將傳統計算機系統內中央處理器處理的任務分散給相應的各個處理器，實現不同功能的各個處理器可以相互協調合作，達到共享系統中外設與軟件的效果。系統具有的優(yōu)點是加快了處理的速度，簡化了主機的邏輯結構，特別適合于應用在工業(yè)生產線自動控制和企事業(yè)單位的管理，同時具有成本低和易于維護的特點，并且成為計算機應用領域發(fā)展中的一個重要方向。但是，在分布式環(huán)境下，由于通訊延遲的不確定性、地域的分布性以及資源和數據的高度共享性等影響因素的存在，使得死鎖預防和檢測變得極為困難。

1.1 死鎖的定義

在分布式計算系統中，有兩個以上的進程在并發(fā)執(zhí)行，每個進程都在等待被其它的進程所占用的系統資源（每個進程都在等待其它的進程釋放所持有的鎖）而不能繼續(xù)運行，即導致系統中任何一個進程都無法運行下去（死循環(huán)），這就產生了死鎖[1]。

1.2 死鎖發(fā)生的條件

Peterson[2]指出了發(fā)生死鎖的必要條件，確切地說，當且僅當以下四個條件同時成立時，死鎖才會發(fā)生。

1） 互斥。同一個資源在同一時刻最多只能被一個進程占用。

2） 占有并等待。必然有一個進程至少占用了系統中的一個資源，同時在等待獲取被其他進程占用的資源。

3） 不可剝奪。一個進程不能剝奪被其他進程占用的資源。

4） 循環(huán)等待。在等待圖中有一個循環(huán)。

其中條件4） 是關于一組進程的特定動態(tài)行為的陳述[3]。

2 分布式計算系統中死鎖的預防

2.1 一般方法

1） 靜態(tài)分配資源

這種方法是要求進程必須在開始執(zhí)行前就申請它所需要的全部資源，并且只有當系統能滿足進程的資源申請要求并把資源分配給進程之后，該進程才開始執(zhí)行。這種策略可以預防死鎖的發(fā)生是由于其破壞了“占有且等待資源”和“循環(huán)等待資源”的條件，從而系統中的所有進程必然不會發(fā)生死鎖。

2） 按序分配資源

這種方法是指在系統中的每一個資源都會給出一個編號。分配資源的時候作了以下規(guī)定：任何進程在申請兩個以上資源時，總是按照編號的大小順序申請。這種策略可以預防死鎖的發(fā)生是由于其破壞了“循環(huán)等待資源”的條件，從而系統中的所有進程必然不會發(fā)生死鎖。

3） 剝奪式分配資源

這種方法是指當一個進程申請資源得不到滿足時，可從另一個擁有這種資源的進程那里去搶奪，然后繼續(xù)運行。這種策略可以預防死鎖的發(fā)生是由于其破壞了“非搶奪式分配”的條件，從而系統中的所有進程必然不會發(fā)生死鎖。

以上的策略都是預防死鎖發(fā)生的有效方法，但是它們也有不足之處。例如，靜態(tài)分配策略和按序分配資源策略都有可能會出現進程在占有了資源后在相當一段時間里并不使用的情況，從而導致了系統資源利用率的下降；剝奪式分配資源策略在當前卻只適合于應用在對處理器和主存資源的分配，適用范圍較小。

2.2 基于時間戳的方法

這里主要介紹兩種基于時間戳的死鎖預防方法。

1） “傷害-等待”的方法

該方法基于剝奪方法。其主要思想是：當進程Pi請求的系統資源正被進程Pj占有時，只有當進程Pi比Pj年輕（即它們的時間戳關系是Li>Lj）時，進程Pi才能處于等待狀態(tài)；否則進程Pj會被取消（即Pj被Pi傷害）并帶有同一時間戳重新啟動，而Pi則可以獲得鎖后繼續(xù)執(zhí)行。該方法是以進程啟動的時間戳來快速判斷進程的優(yōu)先級，并以此決定進程是應該終止、繼續(xù)執(zhí)行還是等待。

2） “等待-死亡”的方法

該方法基于非剝奪方法。其主要思想是：當進程Pi請求的系統資源被進程Pj占有時，只有當進程Pi比Pj老（即它們的時間戳關系是Li

3 分布式計算系統中死鎖的檢測

基于事先預防死鎖的方法基本上都會增加系統的開銷，降低資源的利用率，因此在實踐中并不太適用。在分布式系統中，為了降低系統開銷，在分配資源時會不加限制，只要系統中有剩余的資源，總是把資源分配給申請者。顯然，這樣的結果是可能會出現死鎖。那么，為了使系統能夠正常工作，在系統中會采用定時運行一個“死鎖檢測”程序的方法，當檢測到死鎖時該程序再將會設法將其排除。在分布式系統中的死鎖檢測法不會造成很多不必要的進程流產，但是也會增加了系統的額外開銷和復雜度。

在分布式的死鎖檢測算法[4]中，每個機器都保持它們的獨立性，一個局部的失效不會對算法產生致命的影響。通?？梢詫⑵鋭澐殖蓛煞N：第一種是每個機器都有一個全局等待圖的復制，即每個機器都有一個關于分布式系統的全局視圖；第二種是把系統的全局等待圖分解后分布在不同的機器上。

Knapp提出把分布式的死鎖檢測算法分成如下四類[5]。

1） 路徑推動算法。該算法的基本思想是：首先在每個機器上都構建形式簡單的全局等待圖，當進行死鎖檢測時，各個機器就將全局等待圖的復制發(fā)送給一定數量的鄰近節(jié)點，若局部復制有更新則會被傳播下去。重復以上這一過程，直到某個節(jié)點獲得了足夠的信息并能夠構造出一個全局等待圖并可以判斷出系統是否存在死鎖的結論。

2） 邊跟蹤算法。該算法的基本思想是：通過沿分布式網絡結構圖的邊發(fā)送一種叫探測器的特殊信息來檢測是否存在回路。當一個發(fā)起者得到一個與自己發(fā)送的探測器相匹配的探測器時，它就可以知道它是在該結構圖中的一個回路里。

3） 擴散計算。該算法的基本思想是：若懷疑系統發(fā)生死鎖的時候，進程管理器將會通過向依賴于它的進程發(fā)送查詢啟動一個擴散進程，使得系統不會生成全局等待圖。當處于發(fā)送查詢信息時，擴散計算就會增加；當接收回答之后，擴散計算就會減少。最后由所得信息，發(fā)起者會檢測到死鎖的發(fā)生。

4） 全局狀態(tài)檢測。該算法的基本思想是：通過建立一個統一的全局狀態(tài)但不需要暫停當前的計算來獲得一個一致的全局等待圖。

4 總結

在死鎖預防的策略中，通常的做法是防止死鎖發(fā)生的四個條件中的任意一個發(fā)生。但是死鎖預防的缺點是降低了資源利用率和系統吞吐率。解決死鎖的另一個方法是死鎖避免，在死鎖避免中，需要知道如何請求資源，它動態(tài)檢查資源分布狀態(tài)，以保證沒有循環(huán)等待發(fā)生。實際上，死鎖避免算法的一個潛在問題是需要及時地收集到一致的全局狀態(tài)信息，一般來說，在分布系統中，很少使用死鎖避免，因為它對請求進程和可用資源的數量這些信息的要求太嚴格了，而且對系統進行安全性狀態(tài)的檢查也會涉及到大量的計算，這些都會引起巨大的開銷。當死鎖不可避免地發(fā)生的時候，采取相應的死鎖檢測算法進行檢測與處理。

參考文獻：

[1] 邵佩英.分布式數據庫系統及其應用[M].2版.北京：科學出版社，2005.[2] Peterson J.L， Silberschatz A. Operating System Concepts， Second Edition. Addison-Wesley Publishing Company， 1985.

[3] Jean B， Tim H. 操作系統-并發(fā)與分布式軟件設計[M].陳向群，譯.北京：電子工業(yè)出版社，2005.

[4] 賈焰，王志英，韓偉紅，等.分布式數據庫技術[M].北京：國防大學出版社，2000.

[5] Edgar Knapp. Deadlock Detection in Distributed Databases. ACM Computing Surveys， 1987， 19：303-328.