張君

摘要：在多道程序系統(tǒng)中，雖可借助于多個(gè)進(jìn)程的并發(fā)執(zhí)行，來改善系統(tǒng)的資源利用率，提高系統(tǒng)的吞吐量，但由于系統(tǒng)中資源分配不當(dāng)或進(jìn)程間推進(jìn)順序非法可能發(fā)生死鎖。死鎖是不能完全避免的，只能盡可能的去完善操作系統(tǒng)中的各項(xiàng)功能體系的設(shè)計(jì)，減少死鎖的發(fā)生概率。通過簡(jiǎn)單實(shí)例，從死鎖產(chǎn)生的原因和條件出發(fā)，討論了避免和解除死鎖的幾種方法。

關(guān)鍵詞：死鎖；銀行家算法；進(jìn)程；共享資源

中圖分類號(hào)：TP316文獻(xiàn)標(biāo)識(shí)碼：A文章編號(hào)：1009-3044(2012)01-0201-03

The Discussion of Process Deadlock in Operating System

ZHANG Jun

(hulunbuir College, Hulunbuir 021008, China)

Abstract: Although people can improve the using rate of resources and throughput of system by means of the concurrency of multiple processes in multiprogramming system, deadly lock can still occur due to improper resource allocation and illegal execution sequence. Deadly lock is unavoidable. People can only improve the design of the all kinds of functions architecture of OS to decrease the occurrence of deadly lock.The thesis discusses some means to avoid and release deadly lock from the reasons and conditions through some simple examples.

Key words: deadly lock; banker algorithm; process; sharing resourses

1死鎖的引入

在計(jì)算機(jī)的許多專業(yè)課（如操作系統(tǒng)、數(shù)據(jù)庫系統(tǒng)以及網(wǎng)絡(luò)通信）中，由于進(jìn)程的并發(fā)執(zhí)行和資源的共享，當(dāng)系統(tǒng)中資源分配順序或者進(jìn)程推進(jìn)順序不當(dāng)時(shí)就會(huì)造成系統(tǒng)死鎖。處于死鎖狀態(tài)的系統(tǒng)中，進(jìn)程之間互相等待資源而永遠(yuǎn)不能繼續(xù)向前推進(jìn)，嚴(yán)重地影響了系統(tǒng)的可靠性。

在日常生活中經(jīng)常會(huì)出現(xiàn)一種現(xiàn)象，圖1給出了某一個(gè)街區(qū)交通死鎖的情況，從圖中可以看到四個(gè)街區(qū)的路口都被連續(xù)的車輛堵塞，使得各車輛無法再前進(jìn)的狀態(tài)，這四個(gè)街口正是車流相互競(jìng)爭(zhēng)的共享資源，誰占據(jù)后都不愿意主動(dòng)放棄，最后造成誰也不會(huì)釋放自己占有的資源，誰也得不到所需資源，大家都處在相互等待中，形成所謂的死鎖。

在操作系統(tǒng)中也有類似的情況。在兩個(gè)或多個(gè)并發(fā)進(jìn)程中，如果每個(gè)進(jìn)程鎖定了其他進(jìn)程試圖鎖定的資源，此時(shí)會(huì)造成這些進(jìn)程都想得到資源而又都得不到資源，永久阻塞，從而出現(xiàn)死鎖。圖2是兩個(gè)進(jìn)程發(fā)生死鎖的例子（p1和p2是進(jìn)程，s1和s2是共享資源），p1占有s1，p2占有s2，p1申請(qǐng)s2卻申請(qǐng)不到，因?yàn)閜2沒執(zhí)行完不會(huì)放棄s2，只能等待，p2申請(qǐng)s1也申請(qǐng)不到，因?yàn)閜1沒執(zhí)行完不會(huì)放棄s1，只能等待，p1和p2互相等待永遠(yuǎn)不可能發(fā)生的事件，操作系統(tǒng)中這樣的現(xiàn)象就是死鎖。

2可以死鎖的資源

每個(gè)用戶進(jìn)程要想得到執(zhí)行可能獲取或等待獲取各種資源。以下類型的資源可能會(huì)造成阻塞，并最終導(dǎo)致死鎖。

1）鎖。等待獲取資源（如對(duì)象、頁、行、元數(shù)據(jù)和應(yīng)用程序）的鎖可能導(dǎo)致死鎖。如圖2所示，進(jìn)程P1在S1上有共享鎖（S鎖）并等待獲取S2的排他鎖（X鎖）。進(jìn)程P2在S2上有共享鎖（S鎖）并等待獲取S1的排他鎖（X鎖）。這將導(dǎo)致一個(gè)鎖循環(huán)，其中，P1和P2都等待對(duì)方釋放已鎖定的資源。

2）工作線程。排隊(duì)等待可用工作線程的任務(wù)可能導(dǎo)致死鎖。如果排隊(duì)等待的任務(wù)擁有阻塞所有工作線程的資源，則將導(dǎo)致死鎖。例如，進(jìn)程P1獲取S1的共享鎖（S鎖）后，進(jìn)入睡眠狀態(tài)。在所有可用工作線程上運(yùn)行的進(jìn)程正嘗試獲取S1的排他鎖（X鎖）。因?yàn)檫M(jìn)程P1無法獲取其他工作線程，所以無法執(zhí)行完并釋放S1的鎖，這將導(dǎo)致死鎖。3）內(nèi)存。當(dāng)并發(fā)請(qǐng)求等待獲得內(nèi)存，而當(dāng)前的可用內(nèi)存無法滿足其需要時(shí)，可能發(fā)生死鎖。例如，兩個(gè)并發(fā)查詢（Q1和Q2）作為用戶定義函數(shù)執(zhí)行，分別獲取10MB和20MB的內(nèi)存。如果每個(gè)查詢需要30MB，而可用總內(nèi)存10MB，則Q1和Q2必須等待對(duì)方釋放內(nèi)存，然后申請(qǐng)執(zhí)行，這將導(dǎo)致死鎖。

4）用戶資源。線程等待可能被用戶應(yīng)用程序控制的資源時(shí)，該資源將被視為外部資源或用戶資源，并將按鎖進(jìn)行處理。

除了以上資源還有進(jìn)程互斥體，查詢語句等多種資源，這里不再列舉。

3死鎖產(chǎn)生的條件

3.1進(jìn)程數(shù)條件

1）參與死鎖的進(jìn)程最少是兩個(gè)；

2）參與死鎖的進(jìn)程至少有兩個(gè)已經(jīng)占有資源；3）參與死鎖的所有進(jìn)程都在等待資源；

4）參與死鎖的進(jìn)程是當(dāng)前系統(tǒng)中所有進(jìn)程的子集。

3.2必要條件

1）互斥條件：至少有一個(gè)資源必須處于非共享模式（即一次只有一個(gè)進(jìn)程使用）。如果另一個(gè)進(jìn)程申請(qǐng)?jiān)撡Y源，那么申請(qǐng)進(jìn)程必須延遲直到該資源釋放為止，涉及的資源是非共享的。

2）不剝奪條件：資源不能被搶占（即只在進(jìn)程完成其任務(wù)之后，才會(huì)釋放其資源）。不能強(qiáng)行剝奪進(jìn)程擁有的資源。

3）請(qǐng)求和保持條件：一個(gè)進(jìn)程必須占有至少一個(gè)資源，并等待另一資源，而該資源為其他進(jìn)程占有進(jìn)程在等待一新資源時(shí)繼續(xù)占有已分配的資源。

4）環(huán)路等待條件：有一組進(jìn)程{P0，P1，...，Pn}，P0等待的資源為P1所占有，P1等待的資源為P2所占有，Pn-1等待的資源為Pn所占有，Pn等待的資源為P0所占有，形成一個(gè)循環(huán)鏈。

四個(gè)條件必須同時(shí)滿足才會(huì)出現(xiàn)死鎖，或者說只要使上述四個(gè)必要條件中的某一個(gè)不滿足，則死鎖就可以解除。

4死鎖的檢測(cè)

這種方法并不需要事先采用任何限制性措施，也不用檢查系統(tǒng)是否已經(jīng)進(jìn)入不安全狀態(tài)，允許系統(tǒng)在運(yùn)行過程中發(fā)生死鎖。但可通過系統(tǒng)設(shè)置的檢測(cè)機(jī)構(gòu)---鎖監(jiān)視器線程，及時(shí)地檢測(cè)出死鎖的發(fā)生，并精確地確定與死鎖有關(guān)的進(jìn)程和資源，然后采取適當(dāng)措施，從系統(tǒng)中將已發(fā)生的死鎖清除。

死鎖的檢測(cè)也可以用稱為系統(tǒng)資源分配圖的有向圖進(jìn)行更精確地檢測(cè)。這種圖有一個(gè)結(jié)點(diǎn)的集合V和一個(gè)邊的集合E組成。如果圖沒有環(huán)，那么系統(tǒng)就沒有進(jìn)程死鎖。如果圖有環(huán)，那么可能存在死鎖。死鎖狀態(tài)的充分條件是當(dāng)且僅當(dāng)該狀態(tài)的進(jìn)程資源分配圖是不可完全化簡(jiǎn)的。資源分配圖的化簡(jiǎn)過程如下：

1）找一個(gè)非孤立點(diǎn)進(jìn)程結(jié)點(diǎn)且只有分配邊，去掉分配邊，將其變?yōu)楣铝⒔Y(jié)點(diǎn)。

2）把相應(yīng)的資源分配給一個(gè)等待該資源的進(jìn)程，即將某進(jìn)程的申請(qǐng)邊變?yōu)榉峙溥叀?/p>

3）如果進(jìn)程資源分配圖中有環(huán)路，且涉及的資源類中有多個(gè)資源，則環(huán)路的存在只有產(chǎn)生死鎖的必要條件而不是充分條件。如果能在進(jìn)程資源分配圖中消去此進(jìn)程的所有請(qǐng)求邊和分配邊，成為孤立點(diǎn)。經(jīng)一系列化簡(jiǎn)，使所有進(jìn)程成為孤立結(jié)點(diǎn)。

5死鎖的預(yù)防

死鎖的預(yù)防是一種較簡(jiǎn)單和直觀的事先預(yù)防的方法。通過設(shè)置某些限制條件，以破壞產(chǎn)生死鎖的四個(gè)必要條件中的一個(gè)或幾個(gè)來防止死鎖的發(fā)生。

1）破壞第一個(gè)條件。使資源可同時(shí)訪問而不是互斥使用，這是個(gè)簡(jiǎn)單的方法，磁盤可用這種方法管理，但有許多資源往往是不能同時(shí)訪問，所以這種做法許多場(chǎng)合行不通。

2）破壞第二個(gè)條件。采用剝奪式調(diào)度方法可破壞第二個(gè)條件，但只適用于對(duì)存儲(chǔ)資源和處理器資源的分配。當(dāng)進(jìn)程已經(jīng)擁有一些資源，再去申請(qǐng)其他資源未獲得成功時(shí)，如果主動(dòng)釋放資源（一種剝奪式），然后采取等待，待所需資源都空閑時(shí)，再一起向系統(tǒng)提出申請(qǐng)，也能防止死鎖。此方法可以用AND型的信號(hào)量來實(shí)現(xiàn)。

3）破壞第三個(gè)條件或第四個(gè)條件。許多防止死鎖的辦法施加于資源的限制條件太嚴(yán)格，會(huì)造成資源利用率和吞吐率低。兩種比較實(shí)用的預(yù)防死鎖的方法，它們能破壞第三個(gè)條件或第四個(gè)條件：執(zhí)行前一次性申請(qǐng)全部資源，沒有占有資源時(shí)才能分配資源。確保占有并等待條件不會(huì)在系統(tǒng)內(nèi)出現(xiàn)，必須保證當(dāng)一個(gè)進(jìn)程申請(qǐng)一個(gè)資源時(shí)，它不能占有其他資源。一種可以使用的協(xié)議是每個(gè)進(jìn)程在執(zhí)行前申請(qǐng)并獲得所有資源。另外一種協(xié)議允許進(jìn)程在沒有資源時(shí)才可申請(qǐng)資源；確?！胺菗屨肌保瑸榱舜_保這一條件不成立，可使用如下協(xié)議：如果一個(gè)進(jìn)程占有資源并申請(qǐng)另一個(gè)不能立即分配的資源，那么其現(xiàn)已分配的資源都被搶占；確?！把h(huán)等待”，確保此條件不成立的方法是對(duì)所有資源類型進(jìn)行完全排序，且要求每個(gè)進(jìn)程按遞增順序來申請(qǐng)資源。

6死鎖的避免

該方法同樣是使用事先預(yù)防的策略，在資源的動(dòng)態(tài)分配過程中，用某種方法去防止系統(tǒng)進(jìn)入不安全狀態(tài)，從而避免死鎖的發(fā)生。這種方法只需事先加以較弱的限制條件，便可獲得較高的資源利用率及系統(tǒng)吞吐量，但在實(shí)現(xiàn)上有一定的難度。

最具有代表性的避免死鎖的算法是銀行家算法：銀行家擁有一筆周轉(zhuǎn)資金，客戶要求分期貸款，如果客戶能夠得到各期貸款，

就一定能夠歸還貸款，否則就一定不能歸還貸款，銀行家應(yīng)謹(jǐn)慎的貸款，防止出現(xiàn)壞賬。

銀行家算法的基本思想：系統(tǒng)中的所有進(jìn)程進(jìn)入進(jìn)程集合；在安全狀態(tài)下系統(tǒng)收到進(jìn)程的資源請(qǐng)求后，先把資源試探性分配給它；系統(tǒng)用剩下的可用資源和進(jìn)程集合中其他進(jìn)程還需要的資源作比較，在進(jìn)程集合中找到剩余資源能滿足最大需求量的進(jìn)程，從而保證這個(gè)進(jìn)程運(yùn)行完畢并歸還全部資源；把這個(gè)進(jìn)程從集合中去掉，系統(tǒng)的剩余資源更多了，反復(fù)執(zhí)行上述步驟；最后，檢查進(jìn)程集合，若為空表明本次申請(qǐng)可行，系統(tǒng)處于安全狀態(tài)，可實(shí)施本次分配；否則有進(jìn)程執(zhí)行不完，系統(tǒng)處于不安全狀態(tài)，本次資源分配暫不實(shí)施，讓申請(qǐng)進(jìn)程等待。如圖3所示。

圖3

所以在進(jìn)程執(zhí)行過程中求得一個(gè)安全序列就可以避免死鎖。

7死鎖的解除

如果死鎖發(fā)生會(huì)浪費(fèi)大量系統(tǒng)資源，甚至導(dǎo)致系統(tǒng)崩潰。所以發(fā)生率死鎖必須給予解除?？刹捎靡韵聨追N簡(jiǎn)單方法。

1）立即結(jié)束所有進(jìn)程的執(zhí)行，并重新啟動(dòng)操作系統(tǒng)。方法簡(jiǎn)單，但以前工作全部作廢，損失可能很大。

2）撤銷陷于死鎖的所有進(jìn)程，解除死鎖繼續(xù)執(zhí)行。

3）逐個(gè)陷于死鎖的進(jìn)程，回收其資源，直至死鎖解除。

4）剝奪陷于死鎖的進(jìn)程占有的資源，但并不撤銷它，直至死鎖解除。

5）根據(jù)系統(tǒng)保存的checkpoint，讓所有進(jìn)程回退，直至足以解除死鎖。

6）當(dāng)檢測(cè)到死鎖時(shí)，如果存在某些未卷入死鎖的進(jìn)程，而這些進(jìn)程隨著建立一些新的抑制進(jìn)程能執(zhí)行到結(jié)束，則它們可能釋放足夠的資源來解除死鎖。

參考文獻(xiàn)：

[1] MSDN[EB/OL].http://msdn.microsoft.com.

[2]趙寧.操作系統(tǒng)中多進(jìn)程并行時(shí)的死鎖問題[J].鐵路計(jì)算機(jī)應(yīng)用雜志,2007(12).

[3]王繼奎.基于銀行家算法的進(jìn)程安全序列全搜索算法[J].甘肅科學(xué)學(xué)報(bào),2009(2).

[4]汪江樺.關(guān)于操作系統(tǒng)中死鎖問題的探討[J].科技信息,2009(17).

[5]湯子瀛.計(jì)算機(jī)操作系統(tǒng)[M].西安:西安電子科技大學(xué)出版社,2000.

[6]徐小青.操作系統(tǒng)[M].北京:中國物資出版社,1998.

[7]史美林.計(jì)算機(jī)操作系統(tǒng)教程[M].北京:清華大學(xué)出版社,2006.