發(fā)布時間：所屬分類：科技論文瀏覽：1次
摘 要： 摘要：當(dāng)一個進(jìn)程申請資源得不到滿足時，可從另一個擁有這種資源的進(jìn)程那里去搶奪，然后繼續(xù)運行。這種策略可以預(yù)防死鎖的發(fā)生是由于其破壞了非搶奪式分配的條件，從而系統(tǒng)中的所有進(jìn)程必然不會發(fā)生死鎖。 關(guān)鍵詞：計算機(jī)系統(tǒng),預(yù)防技術(shù),處理器, 計算機(jī)論文發(fā)
摘要：當(dāng)一個進(jìn)程申請資源得不到滿足時，可從另一個擁有這種資源的進(jìn)程那里去搶奪，然后繼續(xù)運行。這種策略可以預(yù)防死鎖的發(fā)生是由于其破壞了“非搶奪式分配”的條件，從而系統(tǒng)中的所有進(jìn)程必然不會發(fā)生死鎖。
關(guān)鍵詞：計算機(jī)系統(tǒng),預(yù)防技術(shù),處理器,計算機(jī)論文發(fā)表
預(yù)防死鎖發(fā)生的有效方法，但是它們也有不足之處。例如，靜態(tài)分配策略和按序分配資源策略都有可能會出現(xiàn)進(jìn)程在占有了資源后在相當(dāng)一段時間里并不使用的情況，從而導(dǎo)致了系統(tǒng)資源利用率的下降;剝奪式分配資源策略在當(dāng)前卻只適合于應(yīng)用在對處理器和主存資源的分配，適用范圍較小。
在死鎖預(yù)防的策略中，通常的做法是防止死鎖發(fā)生的四個條件中的任意一個發(fā)生。但是死鎖預(yù)防的缺點是降低了資源利用率和系統(tǒng)吞吐率。解決死鎖的另一個方法是死鎖避免，在死鎖避免中，需要知道如何請求資源，它動態(tài)檢查資源分布狀態(tài)，以保證沒有循環(huán)等待發(fā)生。實際上，死鎖避免算法的一個潛在問題是需要及時地收集到一致的全局狀態(tài)信息，一般來說，在分布系統(tǒng)中，很少使用死鎖避免，因為它對請求進(jìn)程和可用資源的數(shù)量這些信息的要求太嚴(yán)格了，而且對系統(tǒng)進(jìn)行安全性狀態(tài)的檢查也會涉及到大量的計算，這些都會引起巨大的開銷。當(dāng)死鎖不可避免地發(fā)生的時候，采取相應(yīng)的死鎖檢測算法進(jìn)行檢測與處理。
1 分布式計算系統(tǒng)中的死鎖
分布式計算機(jī)系統(tǒng)是一種具有多處理器并且各個處理器之間通過互連網(wǎng)絡(luò)構(gòu)建成一個具有整體功能的計算機(jī)系統(tǒng)。系統(tǒng)工作的原理是采用分布式計算結(jié)構(gòu)，即將傳統(tǒng)計算機(jī)系統(tǒng)內(nèi)中央處理器處理的任務(wù)分散給相應(yīng)的各個處理器，實現(xiàn)不同功能的各個處理器可以相互協(xié)調(diào)合作，達(dá)到共享系統(tǒng)中外設(shè)與軟件的效果。系統(tǒng)具有的優(yōu)點是加快了處理的速度，簡化了主機(jī)的邏輯結(jié)構(gòu)，特別適合于應(yīng)用在工業(yè)生產(chǎn)線自動控制和企事業(yè)單位的管理，同時具有成本低和易于維護(hù)的特點，并且成為計算機(jī)應(yīng)用領(lǐng)域發(fā)展中的一個重要方向。但是，在分布式環(huán)境下，由于通訊延遲的不確定性、地域的分布性以及資源和數(shù)據(jù)的高度共享性等影響因素的存在，使得死鎖預(yù)防和檢測變得極為困難。
1.1 死鎖的定義
在分布式計算系統(tǒng)中，有兩個以上的進(jìn)程在并發(fā)執(zhí)行，每個進(jìn)程都在等待被其它的進(jìn)程所占用的系統(tǒng)資源(每個進(jìn)程都在等待其它的進(jìn)程釋放所持有的鎖)而不能繼續(xù)運行，即導(dǎo)致系統(tǒng)中任何一個進(jìn)程都無法運行下去(死循環(huán))，這就產(chǎn)生了死鎖[1]。
1.2 死鎖發(fā)生的條件
Peterson[2]指出了發(fā)生死鎖的必要條件，確切地說，當(dāng)且僅當(dāng)以下四個條件同時成立時，死鎖才會發(fā)生。
1) 互斥。同一個資源在同一時刻最多只能被一個進(jìn)程占用。
2) 占有并等待。必然有一個進(jìn)程至少占用了系統(tǒng)中的一個資源，同時在等待獲取被其他進(jìn)程占用的資源。
3) 不可剝奪。一個進(jìn)程不能剝奪被其他進(jìn)程占用的資源。
4) 循環(huán)等待。在等待圖中有一個循環(huán)。
其中條件4) 是關(guān)于一組進(jìn)程的特定動態(tài)行為的陳述[3]。
2 分布式計算系統(tǒng)中死鎖的預(yù)防
2.1 一般方法
1) 靜態(tài)分配資源
這種方法是要求進(jìn)程必須在開始執(zhí)行前就申請它所需要的全部資源，并且只有當(dāng)系統(tǒng)能滿足進(jìn)程的資源申請要求并把資源分配給進(jìn)程之后，該進(jìn)程才開始執(zhí)行。這種策略可以預(yù)防死鎖的發(fā)生是由于其破壞了“占有且等待資源”和“循環(huán)等待資源”的條件，從而系統(tǒng)中的所有進(jìn)程必然不會發(fā)生死鎖。
2) 按序分配資源
這種方法是指在系統(tǒng)中的每一個資源都會給出一個編號。分配資源的時候作了以下規(guī)定：任何進(jìn)程在申請兩個以上資源時，總是按照編號的大小順序申請。這種策略可以預(yù)防死鎖的發(fā)生是由于其破壞了“循環(huán)等待資源”的條件，從而系統(tǒng)中的所有進(jìn)程必然不會發(fā)生死鎖。
2.2 基于時間戳的方法
這里主要介紹兩種基于時間戳的死鎖預(yù)防方法。
1) “傷害-等待”的方法
該方法基于剝奪方法。其主要思想是：當(dāng)進(jìn)程Pi請求的系統(tǒng)資源正被進(jìn)程Pj占有時，只有當(dāng)進(jìn)程Pi比Pj年輕(即它們的時間戳關(guān)系是Li>Lj)時，進(jìn)程Pi才能處于等待狀態(tài);否則進(jìn)程Pj會被取消(即Pj被Pi傷害)并帶有同一時間戳重新啟動，而Pi則可以獲得鎖后繼續(xù)執(zhí)行。該方法是以進(jìn)程啟動的時間戳來快速判斷進(jìn)程的優(yōu)先級，并以此決定進(jìn)程是應(yīng)該終止、繼續(xù)執(zhí)行還是等待。
2) “等待-死亡”的方法
該方法基于非剝奪方法。其主要思想是：當(dāng)進(jìn)程Pi請求的系統(tǒng)資源被進(jìn)程Pj占有時，只有當(dāng)進(jìn)程Pi比Pj老(即它們的時間戳關(guān)系是Li 3 分布式計算系統(tǒng)中死鎖的檢測
基于事先預(yù)防死鎖的方法基本上都會增加系統(tǒng)的開銷，降低資源的利用率，因此在實踐中并不太適用。在分布式系統(tǒng)中，為了降低系統(tǒng)開銷，在分配資源時會不加限制，只要系統(tǒng)中有剩余的資源，總是把資源分配給申請者。顯然，這樣的結(jié)果是可能會出現(xiàn)死鎖。那么，為了使系統(tǒng)能夠正常工作，在系統(tǒng)中會采用定時運行一個“死鎖檢測”程序的方法，當(dāng)檢測到死鎖時該程序再將會設(shè)法將其排除。在分布式系統(tǒng)中的死鎖檢測法不會造成很多不必要的進(jìn)程流產(chǎn)，但是也會增加了系統(tǒng)的額外開銷和復(fù)雜度。
在分布式的死鎖檢測算法[4]中，每個機(jī)器都保持它們的獨立性，一個局部的失效不會對算法產(chǎn)生致命的影響。通常可以將其劃分成兩種：第一種是每個機(jī)器都有一個全局等待圖的復(fù)制，即每個機(jī)器都有一個關(guān)于分布式系統(tǒng)的全局視圖;第二種是把系統(tǒng)的全局等待圖分解后分布在不同的機(jī)器上。
Knapp提出把分布式的死鎖檢測算法分成如下四類[5]。
1) 路徑推動算法。該算法的基本思想是：首先在每個機(jī)器上都構(gòu)建形式簡單的全局等待圖，當(dāng)進(jìn)行死鎖檢測時，各個機(jī)器就將全局等待圖的復(fù)制發(fā)送給一定數(shù)量的鄰近節(jié)點，若局部復(fù)制有更新則會被傳播下去。重復(fù)以上這一過程，直到某個節(jié)點獲得了足夠的信息并能夠構(gòu)造出一個全局等待圖并可以判斷出系統(tǒng)是否存在死鎖的結(jié)論。
2) 邊跟蹤算法。該算法的基本思想是：通過沿分布式網(wǎng)絡(luò)結(jié)構(gòu)圖的邊發(fā)送一種叫探測器的特殊信息來檢測是否存在回路。當(dāng)一個發(fā)起者得到一個與自己發(fā)送的探測器相匹配的探測器時，它就可以知道它是在該結(jié)構(gòu)圖中的一個回路里。
3) 擴(kuò)散計算。該算法的基本思想是：若懷疑系統(tǒng)發(fā)生死鎖的時候，進(jìn)程管理器將會通過向依賴于它的進(jìn)程發(fā)送查詢啟動一個擴(kuò)散進(jìn)程，使得系統(tǒng)不會生成全局等待圖。當(dāng)處于發(fā)送查詢信息時，擴(kuò)散計算就會增加;當(dāng)接收回答之后，擴(kuò)散計算就會減少。最后由所得信息，發(fā)起者會檢測到死鎖的發(fā)生。
4) 全局狀態(tài)檢測。該算法的基本思想是：通過建立一個統(tǒng)一的全局狀態(tài)但不需要暫停當(dāng)前的計算來獲得一個一致的全局等待圖。
