操作系統(tǒng)中的死鎖問題

秦桂云

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

關(guān)鍵詞：死鎖;產(chǎn)生原因;必要條件;處理方法

中圖分類號：TP311? ? ? ? ? ? ? ? 文獻(xiàn)標(biāo)志碼：A

0 引言

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

1 死鎖的概念

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

2 產(chǎn)生死鎖的原因

2.1 資源有限，引發(fā)資源競爭

系統(tǒng)資源有限，而進(jìn)程運(yùn)行又要求占用足夠多的資源。當(dāng)進(jìn)程所需資源被另一進(jìn)程所占，另一進(jìn)程所需資源被其他進(jìn)程所占，循環(huán)往復(fù)，這就導(dǎo)致了所有進(jìn)程都處于一個(gè)不能繼續(xù)執(zhí)行的狀態(tài)，此時(shí)系統(tǒng)處于死鎖狀態(tài)。

2.2 并發(fā)進(jìn)程的執(zhí)行次序非法

借助例子闡明，山谷內(nèi)有僅容一人通過的洞口，大家順序通過，則可保持通暢，當(dāng)發(fā)生混亂，一群人涌向洞口，則此時(shí)就會造成洞口堵塞，導(dǎo)致誰也不能通過，進(jìn)程也是如此，當(dāng)其執(zhí)行順序不合理時(shí)，進(jìn)程進(jìn)入死鎖區(qū)，在死鎖點(diǎn)產(chǎn)生死鎖。

3 死鎖的必要條件

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

4 處理死鎖的辦法

死鎖會影響計(jì)算機(jī)的使用效果，必須對其加以解決，來使系統(tǒng)進(jìn)程可以正常運(yùn)行。死鎖有以下幾種處理方法。

4.1 死鎖的預(yù)防

想要預(yù)先防止死鎖發(fā)生，可以從產(chǎn)生死鎖的必要條件入手。

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

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

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

（4）預(yù)防形成環(huán)路?？梢圆捎冒葱?qū)Y源進(jìn)行分配，給資源分級編號。這就要求所有進(jìn)程在申請資源時(shí)，必須按遞增順序來申請，并且相同級別資源要一次申請完，這就阻止了環(huán)路的產(chǎn)生，從而避免了死鎖的產(chǎn)生。這種預(yù)防方法是低效的，因?yàn)樗鼤惯M(jìn)程的執(zhí)行速度變慢，增加了進(jìn)程占用資源的時(shí)間，并且給系統(tǒng)資源進(jìn)行分級編號也是很困難的。

4.2 死鎖避免

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

4.3 死鎖檢測

預(yù)防和避免死鎖要求代價(jià)太高，為提高資源的利用率，我們一般不阻止死鎖的產(chǎn)生。而是采用系統(tǒng)定時(shí)檢測的方式，當(dāng)檢測到發(fā)生死鎖時(shí)，再采取某種措施來解除死鎖

（1）檢測死鎖的時(shí)機(jī)：進(jìn)程發(fā)生等待時(shí)檢測、定時(shí)進(jìn)行檢測、系統(tǒng)資源利用率下降時(shí)檢測。

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

（3）死鎖定理：當(dāng)某個(gè)狀態(tài)的資源分配圖不能再繼續(xù)化簡時(shí)，該狀態(tài)為死鎖。資源分配圖簡化原則是進(jìn)程申請的資源如果空閑，則可將請求邊改為分配邊，并將資源分配給該進(jìn)程。當(dāng)進(jìn)程僅有分配邊沒有申請邊時(shí)，可看作該進(jìn)程在規(guī)定時(shí)間內(nèi)完成并釋放所占用的資源，可將指向該進(jìn)程結(jié)點(diǎn)的邊抹去，從而簡化過程。

4.4 死鎖復(fù)原

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

5 結(jié)語

死鎖問題是任何操作系統(tǒng)中都存在的潛在問題，資源死鎖也并不是唯一的死鎖?？紤]到系統(tǒng)復(fù)雜多樣和效率代價(jià)問題，很難只靠死鎖的預(yù)防和避免去解決它，大多還是要依靠死鎖的恢復(fù)和檢測，不過，這些都要靠增加計(jì)算機(jī)工作效率來實(shí)現(xiàn)。因此，在未來還需要我們繼續(xù)對死鎖問題進(jìn)行深入研究，爭取早日攻克這一大難題。

參考文獻(xiàn)

[1]湯子贏.計(jì)算機(jī)操作系統(tǒng)[M].西安：西安電子科技大學(xué)出版社，1999.

[2]張堯?qū)W，史美林.計(jì)算機(jī)操作系統(tǒng)教程[M].北京：清華大學(xué)出版社，2000.

[3]張堯?qū)W，宋虹，張高.計(jì)算機(jī)操作系統(tǒng)教程[M].北京：清華大學(xué)出版社，2013.

[4]申雪琴.計(jì)算機(jī)操作系統(tǒng)中死鎖問題的研究[J].計(jì)算機(jī)與數(shù)字工程，2008（7）：203-206.

[5]Andrew.S.Tanenbaum著，陳向群，馬洪兵等譯.現(xiàn)代操作系統(tǒng)[M].北京：機(jī)械工業(yè)出版社.

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