操作系統中的死鎖問題

秦桂云

摘? 要：操作系統的核心是進程管理，在管理進程的時候，如果設計不當就會出現進程堵塞的現象——死鎖。進程中的死鎖問題是如今計算機發展過程中仍需解決的重要問題，許多研究者都在致力于解決該問題。但迄今為止仍舊沒有一個通行的解決方法。該文針對死鎖問題進行了探討，論述了死鎖概念、產生原因、必要條件以及處理辦法。

關鍵詞：死鎖;產生原因;必要條件;處理方法

中圖分類號：TP311? ? ? ? ? ? ? ? 文獻標志碼：A

0 引言

隨著科學技術的不斷發展，計算機類型復雜多樣，進程、資源種類也各不相同。在操作系統中存在很多在任意時刻都只能被一個進程占用的資源。該類資源屬于獨占性資源，不能同時被2個或2個以上的進程使用，否則會導致進程堵塞，從而使計算機系統崩潰。另外，一個進程常常需要訪問各種排他性的資源（磁帶機、打印機等），因此死鎖在系統中出現的次數更會大大增加。死鎖現象的出現給人們工作生活帶來了很大困擾。

1 死鎖的概念

死鎖，顧名思義是一把沒有鑰匙的鎖，指計算機系統、進程陷入一種死循環的狀態，常常定義為在系統進程集合中的每個進程都在請求并等待其他進程所占有的資源，導致所有進程都處于等待狀態不能運行，形成死循環。在該狀態中，沒有終止條件能使陷入死循環的進程得以解脫，從而也不能解開環路使其他進程得以釋放。由此引發了所有進程都陷入想得到資源卻又都得不到資源的局面。如果長期無法改變這種等待狀態，那么這種現象被稱為“饑餓”。

2 產生死鎖的原因

2.1 資源有限，引發資源競爭

系統資源有限，而進程運行又要求占用足夠多的資源。當進程所需資源被另一進程所占，另一進程所需資源被其他進程所占，循環往復，這就導致了所有進程都處于一個不能繼續執行的狀態，此時系統處于死鎖狀態。

2.2 并發進程的執行次序非法

借助例子闡明，山谷內有僅容一人通過的洞口，大家順序通過，則可保持通暢，當發生混亂，一群人涌向洞口，則此時就會造成洞口堵塞，導致誰也不能通過，進程也是如此，當其執行順序不合理時，進程進入死鎖區，在死鎖點產生死鎖。

3 死鎖的必要條件

對于可再使用的永久資源來說：1）互斥條件，又稱獨占條件。有些資源只能同時被一個進程所占用，而其他進程不能訪問這些已被占用了的資源。2）請求并保持，也稱部分分配條件。當進程等待其他資源時，仍然繼續占有已經得到的資源。3）非搶占條件。進程獲得的資源未使用完之前，其他進程不能強占，資源只能被占有它的進程自主釋放。4）循環環路等待。死鎖發生時，系統中存在著一條由至少2個進程組成的環路，在這條環路中的每一個進程都在等待后一個進程所占資源的釋放，因此導致環路堵塞，使進程不能再繼續運行。

4 處理死鎖的辦法

死鎖會影響計算機的使用效果，必須對其加以解決，來使系統進程可以正常運行。死鎖有以下幾種處理方法。

4.1 死鎖的預防

想要預先防止死鎖發生，可以從產生死鎖的必要條件入手。

（1）摒棄互斥條件。首先使用虛擬設備技術，破壞了死鎖形成的必要條件中的互斥條件。該技術可將一臺獨占設備虛擬成多臺邏輯設備，能夠提供給多個進程來使用，提高了系統資源利用效率。虛擬設備技術就用共享設備的空間模擬了獨占設備的功能，將獨占改為共享。

（2）預分配所有共享資源。進程運行時所需的所有資源一次性申請，并且在所需資源未得到滿足之前，不運行該進程，一直等到所需資源均空閑時，再運行該進程。其存在以下不足：進程可能會等待很長的時間，才能滿足所請求的資源，但實際上，有的進程僅需要部分資源就可以繼續執行下去。其次，被分配的資源可能等候較長時間都不會被進程使用，也不能為其他進程所運行使用，因此就造成了資源浪費。

（3）預防占有保持。針對資源不能被其他進程搶占的條件，可從以下方面解決。等待時釋放，當已經占有部分資源的進程再次申請資源時，如果被拒絕則要求其必須釋放原先占有的資源。強制剝奪，當進程請求當前正被其他進程占有的資源時，系統可以主動搶占另一個進程的資源幫助該進程運行下去，因此進程在運行過程中，所占有的資源是能夠被系統所剝奪的。不過第2種方法只有在2個進程優先級不同時才有效。此外，被剝奪了資源的進程在此之前所完成的工作全部失效，同時，進行的這一系列操作也加大了系統開銷，造成了不必要的浪費

（4）預防形成環路。可以采用按序對資源進行分配，給資源分級編號。這就要求所有進程在申請資源時，必須按遞增順序來申請，并且相同級別資源要一次申請完，這就阻止了環路的產生，從而避免了死鎖的產生。這種預防方法是低效的，因為它會使進程的執行速度變慢，增加了進程占用資源的時間，并且給系統資源進行分級編號也是很困難的。

4.2 死鎖避免

死鎖避免也稱動態監測。該方法與死鎖預防差別較小，死鎖預防約束申請資源請求，從而破壞4個必要條件中的一個，但這同時使資源利用率和進程執行率大大降低。而死鎖避免則相反，在分配資源的過程中，系統對于申請資源的命令提前進行檢測，依據所進行的檢查結果選擇是否分配其資源。它允許互斥、請求和保持，不可剝奪3個條件，但卻保證永遠不會到達死鎖點，能夠執行多個并發程序。

4.3 死鎖檢測

預防和避免死鎖要求代價太高，為提高資源的利用率，我們一般不阻止死鎖的產生。而是采用系統定時檢測的方式，當檢測到發生死鎖時，再采取某種措施來解除死鎖

（1）檢測死鎖的時機：進程發生等待時檢測、定時進行檢測、系統資源利用率下降時檢測。

（2）利用資源分配圖檢測：借助資源分配圖，如果發現其中不存在環路，則未出現死鎖，如果存在環路，則有可能出現死鎖（存在不確定性）

（3）死鎖定理：當某個狀態的資源分配圖不能再繼續化簡時，該狀態為死鎖。資源分配圖簡化原則是進程申請的資源如果空閑，則可將請求邊改為分配邊，并將資源分配給該進程。當進程僅有分配邊沒有申請邊時，可看作該進程在規定時間內完成并釋放所占用的資源，可將指向該進程結點的邊抹去，從而簡化過程。

4.4 死鎖復原

一旦檢測出死鎖就要采取一些措施來使系統重新恢復運行。1）強制搶占，臨時將資源從它當前所有者中人工干預轉移到需要該資源的另一進程，使另一進程可以運行。當另一進程完成時，原進程可再申請可用資源繼續完成工作，由此解決死鎖問題。該方法的可行度不強，實行起來較為困難，選擇搶奪某個進程的資源時，很大程度上要考慮該進程所擁有的資源是否容易回收。2）死鎖進程回退，使其回到還未產生死鎖的時候。借助檢查點，當系統死鎖時，檢測所需資源，從較早的檢查點開始，使其回到還未產生死鎖的狀態，并使該進程獲得所需資源。其中檢查點包括資源狀態和存儲映像，即那些資源分配給了那個進程，不過該方法可能使系統再次進入死鎖。3）終止所有進程。可以先終止死鎖環路中的一個進程，如果死鎖還未解除，繼續撤銷其他的進程，直至進程全部撤銷或者死鎖恢復至系統正常運行。也可選擇對環路外的進程進行撤銷，使其釋放所占有的資源。不過該方法要求所撤銷的進程中正好擁有環路中堵塞進程所需要的資源，且最好撤銷的是不會有其他影響的進程。

5 結語

死鎖問題是任何操作系統中都存在的潛在問題，資源死鎖也并不是唯一的死鎖。考慮到系統復雜多樣和效率代價問題，很難只靠死鎖的預防和避免去解決它，大多還是要依靠死鎖的恢復和檢測，不過，這些都要靠增加計算機工作效率來實現。因此，在未來還需要我們繼續對死鎖問題進行深入研究，爭取早日攻克這一大難題。

參考文獻

[1]湯子贏.計算機操作系統[M].西安：西安電子科技大學出版社，1999.

[2]張堯學，史美林.計算機操作系統教程[M].北京：清華大學出版社，2000.

[3]張堯學，宋虹，張高.計算機操作系統教程[M].北京：清華大學出版社，2013.

[4]申雪琴.計算機操作系統中死鎖問題的研究[J].計算機與數字工程，2008（7）：203-206.

[5]Andrew.S.Tanenbaum著，陳向群，馬洪兵等譯.現代操作系統[M].北京：機械工業出版社.

[6]孔憲君，王亞東.操作系統的原理與應用[M].北京：高等教育出版社，2008.