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