賴河蒗

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

關(guān)鍵詞：分布式；死鎖；預(yù)防；檢測(cè)；網(wǎng)絡(luò)環(huán)境

中圖分類(lèi)號(hào)：TP393 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：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 分布式計(jì)算系統(tǒng)中的死鎖

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

1.1 死鎖的定義

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

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

Peterson[2]指出了發(fā)生死鎖的必要條件，確切地說(shuō)，當(dāng)且僅當(dāng)以下四個(gè)條件同時(shí)成立時(shí)，死鎖才會(huì)發(fā)生。

1） 互斥。同一個(gè)資源在同一時(shí)刻最多只能被一個(gè)進(jìn)程占用。

2） 占有并等待。必然有一個(gè)進(jìn)程至少占用了系統(tǒng)中的一個(gè)資源，同時(shí)在等待獲取被其他進(jìn)程占用的資源。

3） 不可剝奪。一個(gè)進(jìn)程不能剝奪被其他進(jìn)程占用的資源。

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

其中條件4） 是關(guān)于一組進(jìn)程的特定動(dòng)態(tài)行為的陳述[3]。

2 分布式計(jì)算系統(tǒng)中死鎖的預(yù)防

2.1 一般方法

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

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

2） 按序分配資源

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

3） 剝奪式分配資源

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

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

2.2 基于時(shí)間戳的方法

這里主要介紹兩種基于時(shí)間戳的死鎖預(yù)防方法。

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

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

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

該方法基于非剝奪方法。其主要思想是：當(dāng)進(jìn)程Pi請(qǐng)求的系統(tǒng)資源被進(jìn)程Pj占有時(shí)，只有當(dāng)進(jìn)程Pi比Pj老（即它們的時(shí)間戳關(guān)系是Li

3 分布式計(jì)算系統(tǒng)中死鎖的檢測(cè)

基于事先預(yù)防死鎖的方法基本上都會(huì)增加系統(tǒng)的開(kāi)銷(xiāo)，降低資源的利用率，因此在實(shí)踐中并不太適用。在分布式系統(tǒng)中，為了降低系統(tǒng)開(kāi)銷(xiāo)，在分配資源時(shí)會(huì)不加限制，只要系統(tǒng)中有剩余的資源，總是把資源分配給申請(qǐng)者。顯然，這樣的結(jié)果是可能會(huì)出現(xiàn)死鎖。那么，為了使系統(tǒng)能夠正常工作，在系統(tǒng)中會(huì)采用定時(shí)運(yùn)行一個(gè)“死鎖檢測(cè)”程序的方法，當(dāng)檢測(cè)到死鎖時(shí)該程序再將會(huì)設(shè)法將其排除。在分布式系統(tǒng)中的死鎖檢測(cè)法不會(huì)造成很多不必要的進(jìn)程流產(chǎn)，但是也會(huì)增加了系統(tǒng)的額外開(kāi)銷(xiāo)和復(fù)雜度。

在分布式的死鎖檢測(cè)算法[4]中，每個(gè)機(jī)器都保持它們的獨(dú)立性，一個(gè)局部的失效不會(huì)對(duì)算法產(chǎn)生致命的影響。通常可以將其劃分成兩種：第一種是每個(gè)機(jī)器都有一個(gè)全局等待圖的復(fù)制，即每個(gè)機(jī)器都有一個(gè)關(guān)于分布式系統(tǒng)的全局視圖；第二種是把系統(tǒng)的全局等待圖分解后分布在不同的機(jī)器上。

Knapp提出把分布式的死鎖檢測(cè)算法分成如下四類(lèi)[5]。

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

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

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

4） 全局狀態(tài)檢測(cè)。該算法的基本思想是：通過(guò)建立一個(gè)統(tǒng)一的全局狀態(tài)但不需要暫停當(dāng)前的計(jì)算來(lái)獲得一個(gè)一致的全局等待圖。

4 總結(jié)

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

參考文獻(xiàn)：

[1] 邵佩英.分布式數(shù)據(jù)庫(kù)系統(tǒng)及其應(yīng)用[M].2版.北京：科學(xué)出版社，2005.[2] Peterson J.L， Silberschatz A. Operating System Concepts， Second Edition. Addison-Wesley Publishing Company， 1985.

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

[4] 賈焰，王志英，韓偉紅，等.分布式數(shù)據(jù)庫(kù)技術(shù)[M].北京：國(guó)防大學(xué)出版社，2000.

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