OS2013_UNIT5 死鎖

1、Unit 5Unit 5操作系統(tǒng)原理操作系統(tǒng)原理馮耀霖馮耀霖進(jìn)程管理之四進(jìn)程管理之四內(nèi)容內(nèi)容 什么是死鎖什么是死鎖產(chǎn)生死鎖的條件產(chǎn)生死鎖的條件死鎖的應(yīng)對(duì)死鎖的應(yīng)對(duì)1 產(chǎn)生死鎖的原因產(chǎn)生死鎖的原因 死鎖定義死鎖定義圖圖5-1 生活現(xiàn)實(shí)中的交通死鎖生活現(xiàn)實(shí)中的交通死鎖造成這種死鎖的根本原因是什么？造成這種死鎖的根本原因是什么？競(jìng)爭(zhēng)資源！競(jìng)爭(zhēng)資源！在計(jì)算機(jī)系統(tǒng)中同樣會(huì)發(fā)生類(lèi)似交通死鎖的線程死鎖在計(jì)算機(jī)系統(tǒng)中同樣會(huì)發(fā)生類(lèi)似交通死鎖的線程死鎖現(xiàn)象?，F(xiàn)象。例如，設(shè)有兩個(gè)線程例如，設(shè)有兩個(gè)線程A和和B，它們都要使用資源，它們都要使用資源R1和和R2來(lái)完成各自的任務(wù)，且用以下方式使用這兩個(gè)資源：來(lái)完成各自的任

2、務(wù)，且用以下方式使用這兩個(gè)資源：線程線程A 線程線程B point1: 申請(qǐng)申請(qǐng) R1 申請(qǐng)申請(qǐng) R2 point2: 申請(qǐng)申請(qǐng) R2 申請(qǐng)申請(qǐng) R1 釋放釋放 R1 釋放釋放 R2 釋放釋放 R2 釋放釋放 R1 如果一個(gè)線程在另一個(gè)線程到達(dá)執(zhí)行點(diǎn)如果一個(gè)線程在另一個(gè)線程到達(dá)執(zhí)行點(diǎn)point1之前之前率先到達(dá)執(zhí)行點(diǎn)率先到達(dá)執(zhí)行點(diǎn)point2，那么它就能獲得它所需要的第，那么它就能獲得它所需要的第二個(gè)資源，從而可繼續(xù)運(yùn)行下去。但是，由于各線程都是二個(gè)資源，從而可繼續(xù)運(yùn)行下去。但是，由于各線程都是異步前進(jìn)的，如果沒(méi)有一個(gè)線程先于另一個(gè)線程到達(dá)異步前進(jìn)的，如果沒(méi)有一個(gè)線程先于另一個(gè)線程到達(dá)poin

3、t1之前到達(dá)之前到達(dá)point2，即它們都處于，即它們都處于point1和和point2之間，此時(shí)任一線程到達(dá)之間，此時(shí)任一線程到達(dá)point2都將相繼被阻塞，它們都將相繼被阻塞，它們都在等待獲取對(duì)方已經(jīng)占用了又無(wú)法釋放的資源，于是線都在等待獲取對(duì)方已經(jīng)占用了又無(wú)法釋放的資源，于是線程程A和和B陷入了死鎖。陷入了死鎖。再考慮下面的線程通信例子，每個(gè)線程都試圖接收另再考慮下面的線程通信例子，每個(gè)線程都試圖接收另一個(gè)線程發(fā)來(lái)的消息，然后再給對(duì)方發(fā)送一則消息：一個(gè)線程發(fā)來(lái)的消息，然后再給對(duì)方發(fā)送一則消息：線程線程A 線程線程B receive (B , mes); receive (A , mes)

4、; send (B , mes); send (A , mes); 這種設(shè)計(jì)錯(cuò)誤導(dǎo)致任一線程執(zhí)行這種設(shè)計(jì)錯(cuò)誤導(dǎo)致任一線程執(zhí)行receive操作時(shí)將被操作時(shí)將被阻塞而無(wú)法去執(zhí)行阻塞而無(wú)法去執(zhí)行send操作，從而發(fā)生死鎖。操作，從而發(fā)生死鎖。死鎖（死鎖（deadlock）定義：）定義：如果有一組線程，每個(gè)線程都在等待一個(gè)事如果有一組線程，每個(gè)線程都在等待一個(gè)事件的發(fā)生，而這個(gè)事件只能由該組線程里面的另件的發(fā)生，而這個(gè)事件只能由該組線程里面的另一個(gè)線程發(fā)出，則稱(chēng)這組線程發(fā)生了死鎖。一個(gè)線程發(fā)出，則稱(chēng)這組線程發(fā)生了死鎖。（這里的事件通常是指釋放資源）（這里的事件通常是指釋放資源）在死鎖狀態(tài)下，沒(méi)有線程

5、可以執(zhí)行或被喚醒，即該組在死鎖狀態(tài)下，沒(méi)有線程可以執(zhí)行或被喚醒，即該組線程陷入了相互永久阻塞的困局，其中的每個(gè)線程都必須線程陷入了相互永久阻塞的困局，其中的每個(gè)線程都必須在另一個(gè)線程向前推進(jìn)之后才能繼續(xù)推進(jìn)，但每個(gè)線程又在另一個(gè)線程向前推進(jìn)之后才能繼續(xù)推進(jìn)，但每個(gè)線程又都無(wú)法推進(jìn)，導(dǎo)致了系統(tǒng)的局部癱瘓，進(jìn)而可能導(dǎo)致整個(gè)都無(wú)法推進(jìn)，導(dǎo)致了系統(tǒng)的局部癱瘓，進(jìn)而可能導(dǎo)致整個(gè)系統(tǒng)的癱瘓。系統(tǒng)的癱瘓。2 必要條件必要條件 充分必要條件充分必要條件2.1 條件條件1：資源互斥資源互斥。即一組進(jìn)程使用了必須互斥的臨。即一組進(jìn)程使用了必須互斥的臨界資源。如果大家使用的是非臨界資源，就不會(huì)發(fā)生相互界資源。如果大

6、家使用的是非臨界資源，就不會(huì)發(fā)生相互等待現(xiàn)象，也就不會(huì)發(fā)生死鎖。等待現(xiàn)象，也就不會(huì)發(fā)生死鎖。條件條件2：請(qǐng)求和保持請(qǐng)求和保持。即進(jìn)程在請(qǐng)求使用新的資源的。即進(jìn)程在請(qǐng)求使用新的資源的同時(shí)，保持對(duì)已獲取資源的占有并不釋放。同時(shí)，保持對(duì)已獲取資源的占有并不釋放。條件條件3：不可剝奪不可剝奪。即一進(jìn)程所占有的資源是不可剝。即一進(jìn)程所占有的資源是不可剝奪資源。如果占有的是可剝奪資源則不會(huì)發(fā)生死鎖，例如，奪資源。如果占有的是可剝奪資源則不會(huì)發(fā)生死鎖，例如，不會(huì)因?yàn)閷?duì)不會(huì)因?yàn)閷?duì)CPU的爭(zhēng)奪而產(chǎn)生死鎖。的爭(zhēng)奪而產(chǎn)生死鎖。條件條件4：循環(huán)等待循環(huán)等待。即存在一個(gè)閉合的進(jìn)程資源環(huán)。即存在一個(gè)閉合的進(jìn)程資源環(huán)路，其

7、中的每個(gè)進(jìn)程已占有著某個(gè)（些）資源，同時(shí)又在路，其中的每個(gè)進(jìn)程已占有著某個(gè)（些）資源，同時(shí)又在等待獲取被環(huán)路中另一個(gè)進(jìn)程占有的資源。等待獲取被環(huán)路中另一個(gè)進(jìn)程占有的資源。2.2 充分必要條件充分必要條件假定在某個(gè)時(shí)刻一組線程使用一組資源的狀態(tài)為假定在某個(gè)時(shí)刻一組線程使用一組資源的狀態(tài)為S（S也稱(chēng)資源分配狀態(tài)），一個(gè)也稱(chēng)資源分配狀態(tài)），一個(gè)RAG (Resources Allocation Graph)是該是該S所對(duì)應(yīng)的有向圖，如果：所對(duì)應(yīng)的有向圖，如果：(1)該該RAG中未出現(xiàn)任何環(huán)路，則中未出現(xiàn)任何環(huán)路，則S為非死鎖狀態(tài)，為非死鎖狀態(tài)，也稱(chēng)安全狀態(tài)。也稱(chēng)安全狀態(tài)。(2)該該RAG中出現(xiàn)了環(huán)路

8、，但環(huán)路中的各資源不全為中出現(xiàn)了環(huán)路，但環(huán)路中的各資源不全為單單位資源，則單單位資源，則S不一定是死鎖狀態(tài)。換言之，由若干不不一定是死鎖狀態(tài)。換言之，由若干不全為單單位資源構(gòu)成的環(huán)路是全為單單位資源構(gòu)成的環(huán)路是S為死鎖狀態(tài)的必要條件但為死鎖狀態(tài)的必要條件但非充分條件。非充分條件。(3)該該RAG中出現(xiàn)了環(huán)路，且環(huán)路中的各資源均為單中出現(xiàn)了環(huán)路，且環(huán)路中的各資源均為單單位資源，則單位資源，則S為死鎖狀態(tài)。換言之，為死鎖狀態(tài)。換言之，由若干單單位資源由若干單單位資源構(gòu)成的環(huán)路是構(gòu)成的環(huán)路是S S為死鎖狀態(tài)的充要條件為死鎖狀態(tài)的充要條件。 圖圖5-2 死鎖定理死鎖定理(1)線程線程1線程線程2線程線

9、程3是可完全化簡(jiǎn)圖。是可完全化簡(jiǎn)圖。安全狀態(tài)！安全狀態(tài)！R1R2R3R4圖圖5-3 死鎖定理死鎖定理(2)線程線程1線程線程2線程線程3構(gòu)成不可化簡(jiǎn)圖。構(gòu)成不可化簡(jiǎn)圖。死鎖！死鎖！R1R2R3R4死鎖定理：死鎖定理：在某個(gè)時(shí)刻的進(jìn)程資源狀態(tài)在某個(gè)時(shí)刻的進(jìn)程資源狀態(tài)S為死鎖狀態(tài)的充為死鎖狀態(tài)的充分必要條件是當(dāng)且僅當(dāng)分必要條件是當(dāng)且僅當(dāng)S的資源分配圖（的資源分配圖（RAG）是不可完全化簡(jiǎn)的。是不可完全化簡(jiǎn)的。3 忽略死鎖策略忽略死鎖策略 檢測(cè)并解除策略檢測(cè)并解除策略 避免死鎖策略避免死鎖策略預(yù)防死鎖策略預(yù)防死鎖策略綜合治理綜合治理死鎖是操作系統(tǒng)必須應(yīng)對(duì)的問(wèn)題，是無(wú)法回避的。那死鎖是操作系統(tǒng)必須應(yīng)對(duì)

10、的問(wèn)題，是無(wú)法回避的。那么如何應(yīng)對(duì)死鎖呢？么如何應(yīng)對(duì)死鎖呢？從高級(jí)境界來(lái)看，只有兩種對(duì)策：從高級(jí)境界來(lái)看，只有兩種對(duì)策：允許死鎖發(fā)生允許死鎖發(fā)生不允許死鎖發(fā)生不允許死鎖發(fā)生這兩種對(duì)策又各有兩個(gè)策略。這兩種對(duì)策又各有兩個(gè)策略。對(duì)于對(duì)策對(duì)于對(duì)策1，兩個(gè)策略是：，兩個(gè)策略是：(1)回避死鎖回避死鎖。即不予理睬，當(dāng)死鎖發(fā)生后就重啟唄。即不予理睬，當(dāng)死鎖發(fā)生后就重啟唄(2)檢測(cè)并解除檢測(cè)并解除。即一旦發(fā)生死鎖便能通過(guò)某種檢測(cè)。即一旦發(fā)生死鎖便能通過(guò)某種檢測(cè)機(jī)制立即檢測(cè)出來(lái)，并能精確地定位相關(guān)的進(jìn)程和資源，機(jī)制立即檢測(cè)出來(lái)，并能精確地定位相關(guān)的進(jìn)程和資源，然后采取適當(dāng)措施解除死鎖，使系統(tǒng)可繼續(xù)運(yùn)行。然后采

11、取適當(dāng)措施解除死鎖，使系統(tǒng)可繼續(xù)運(yùn)行。 對(duì)于對(duì)策對(duì)于對(duì)策2，兩個(gè)策略是：，兩個(gè)策略是：(1)預(yù)防死鎖預(yù)防死鎖。即通過(guò)設(shè)置某些嚴(yán)格的限制條件來(lái)。即通過(guò)設(shè)置某些嚴(yán)格的限制條件來(lái)消除產(chǎn)生死鎖的四個(gè)必要條件中的至少一個(gè)條件，從而杜消除產(chǎn)生死鎖的四個(gè)必要條件中的至少一個(gè)條件，從而杜絕死鎖的發(fā)生。絕死鎖的發(fā)生。(2)避免死鎖避免死鎖。與預(yù)防死鎖方法不同的是，它無(wú)需。與預(yù)防死鎖方法不同的是，它無(wú)需預(yù)先設(shè)置嚴(yán)格的限制條件，而是在資源的動(dòng)態(tài)分配過(guò)程中，預(yù)先設(shè)置嚴(yán)格的限制條件，而是在資源的動(dòng)態(tài)分配過(guò)程中，通過(guò)使用某種只需施加較弱限制條件的方法來(lái)防止相關(guān)線通過(guò)使用某種只需施加較弱限制條件的方法來(lái)防止相關(guān)線程進(jìn)入不安

12、全狀態(tài)，從而避免死鎖的發(fā)生。程進(jìn)入不安全狀態(tài)，從而避免死鎖的發(fā)生。3.1 回避死鎖策略回避死鎖策略這是人類(lèi)面對(duì)難題時(shí)經(jīng)常采取的辦法，或者是大部分這是人類(lèi)面對(duì)難題時(shí)經(jīng)常采取的辦法，或者是大部分人遇到困難時(shí)所采取的辦法，我們不想花力氣解決難題，人遇到困難時(shí)所采取的辦法，我們不想花力氣解決難題，或者沒(méi)有能力解決難題，或者認(rèn)為解決難題的代價(jià)超過(guò)難或者沒(méi)有能力解決難題，或者認(rèn)為解決難題的代價(jià)超過(guò)難題本身帶來(lái)的后果。為此，我們可能采取視而不見(jiàn)的辦法題本身帶來(lái)的后果。為此，我們可能采取視而不見(jiàn)的辦法來(lái)處理各種棘手問(wèn)題。來(lái)處理各種棘手問(wèn)題。此種策略就是操作系統(tǒng)不采取任何措施，任由死鎖的此種策略就是操作系統(tǒng)不采

13、取任何措施，任由死鎖的發(fā)生。這看上去是一種非常糟糕的策略，很多人可能認(rèn)為發(fā)生。這看上去是一種非常糟糕的策略，很多人可能認(rèn)為沒(méi)有什么操作系統(tǒng)會(huì)采取這種策略。但這種策略真的很糟沒(méi)有什么操作系統(tǒng)會(huì)采取這種策略。但這種策略真的很糟糕嗎？糕嗎？如果很糟糕，就不會(huì)有很多人在面對(duì)問(wèn)題時(shí)采取這種如果很糟糕，就不會(huì)有很多人在面對(duì)問(wèn)題時(shí)采取這種策略了。實(shí)際上，這種策略是大多數(shù)人在大多數(shù)情況下采策略了。實(shí)際上，這種策略是大多數(shù)人在大多數(shù)情況下采取的策略。老子說(shuō)過(guò)取的策略。老子說(shuō)過(guò)“無(wú)為而治無(wú)為而治”就是這個(gè)策略。你什么就是這個(gè)策略。你什么都都不用做（實(shí)際上并不是什么都不做，而是盡量少做），事不用做（實(shí)際上并不是什么

14、都不做，而是盡量少做），事情慢慢就朝著有利的方向發(fā)展。情慢慢就朝著有利的方向發(fā)展。 從哲學(xué)角度來(lái)說(shuō)，世界上本沒(méi)有問(wèn)題，是你認(rèn)為有問(wèn)從哲學(xué)角度來(lái)說(shuō)，世界上本沒(méi)有問(wèn)題，是你認(rèn)為有問(wèn)題，才有問(wèn)題。學(xué)生考試不及格，要補(bǔ)考，補(bǔ)考也不及格，題，才有問(wèn)題。學(xué)生考試不及格，要補(bǔ)考，補(bǔ)考也不及格，畢不了業(yè)。畢不了業(yè)是問(wèn)題嗎？不盡然。只有你認(rèn)為是問(wèn)畢不了業(yè)。畢不了業(yè)是問(wèn)題嗎？不盡然。只有你認(rèn)為是問(wèn)題時(shí)它才是問(wèn)題。比爾蓋茨大學(xué)沒(méi)畢業(yè)，并不妨礙他成為題時(shí)它才是問(wèn)題。比爾蓋茨大學(xué)沒(méi)畢業(yè)，并不妨礙他成為世界首富。喬布斯大學(xué)也沒(méi)畢業(yè)，世界首富。喬布斯大學(xué)也沒(méi)畢業(yè)，Larry Page則是研究則是研究生沒(méi)有畢業(yè)，前者創(chuàng)辦了生

15、沒(méi)有畢業(yè)，前者創(chuàng)辦了Apple，后者創(chuàng)辦了，后者創(chuàng)辦了Google。如。如果你畢業(yè)了，就不能成為比爾蓋茨或喬布斯或果你畢業(yè)了，就不能成為比爾蓋茨或喬布斯或Larry Page了，因?yàn)槟惝厴I(yè)了，已經(jīng)和他們不一樣了。了，因?yàn)槟惝厴I(yè)了，已經(jīng)和他們不一樣了。死鎖也一樣。只有你認(rèn)為它是問(wèn)題時(shí)它才是問(wèn)題。而死鎖也一樣。只有你認(rèn)為它是問(wèn)題時(shí)它才是問(wèn)題。而研究商業(yè)操作系統(tǒng)的人不認(rèn)為這是什么大問(wèn)題，因?yàn)榻?jīng)分研究商業(yè)操作系統(tǒng)的人不認(rèn)為這是什么大問(wèn)題，因?yàn)榻?jīng)分析發(fā)現(xiàn)，死鎖發(fā)生的頻率不太高（當(dāng)然這點(diǎn)有爭(zhēng)議），所析發(fā)現(xiàn)，死鎖發(fā)生的頻率不太高（當(dāng)然這點(diǎn)有爭(zhēng)議），所以不必管它。另外，死鎖防止的代價(jià)很高，防止死鎖比重以不必管

16、它。另外，死鎖防止的代價(jià)很高，防止死鎖比重啟系統(tǒng)啟系統(tǒng)100次的代價(jià)還高，因此不如直接重啟，即如果發(fā)次的代價(jià)還高，因此不如直接重啟，即如果發(fā)生死鎖的話，重啟即可。這就是生死鎖的話，重啟即可。這就是Windows等一些商業(yè)操等一些商業(yè)操作系統(tǒng)沒(méi)有采取死鎖防止措施的原因，這也是你的電腦經(jīng)作系統(tǒng)沒(méi)有采取死鎖防止措施的原因，這也是你的電腦經(jīng)常死機(jī)的原因，甚至連常死機(jī)的原因，甚至連Linux也沒(méi)有采取死鎖防止措施。也沒(méi)有采取死鎖防止措施。在操作系統(tǒng)設(shè)計(jì)時(shí)常常不得不進(jìn)行折中，是想盡量方在操作系統(tǒng)設(shè)計(jì)時(shí)常常不得不進(jìn)行折中，是想盡量方便，偶爾出點(diǎn)錯(cuò)誤呢？還是保證系統(tǒng)完全正確，但是費(fèi)了便，偶爾出點(diǎn)錯(cuò)誤呢？還是保

17、證系統(tǒng)完全正確，但是費(fèi)了很大力氣？多數(shù)人選擇的是前者。當(dāng)然，如果涉及的是要很大力氣？多數(shù)人選擇的是前者。當(dāng)然，如果涉及的是要求高可靠性的高端系統(tǒng)或?qū)崟r(shí)控制系統(tǒng)，就另當(dāng)別論了，求高可靠性的高端系統(tǒng)或?qū)崟r(shí)控制系統(tǒng)，就另當(dāng)別論了，那絕對(duì)不允許死鎖。那絕對(duì)不允許死鎖。3.2 檢測(cè)并解除策略檢測(cè)并解除策略該策略也允許死鎖發(fā)生，但系統(tǒng)定時(shí)地或當(dāng)系統(tǒng)出現(xiàn)該策略也允許死鎖發(fā)生，但系統(tǒng)定時(shí)地或當(dāng)系統(tǒng)出現(xiàn)異常時(shí)執(zhí)行一個(gè)異常時(shí)執(zhí)行一個(gè)“死鎖檢測(cè)程序死鎖檢測(cè)程序”，用于判斷系統(tǒng)是否已，用于判斷系統(tǒng)是否已發(fā)生死鎖，如果檢測(cè)到已發(fā)生了死鎖，則設(shè)法加以解除。發(fā)生死鎖，如果檢測(cè)到已發(fā)生了死鎖，則設(shè)法加以解除。1. 檢測(cè)死鎖檢

18、測(cè)死鎖死鎖檢測(cè)算法的基本思路是：判斷死鎖定理是否成立。死鎖檢測(cè)算法的基本思路是：判斷死鎖定理是否成立。顯然，這可利用有向圖來(lái)實(shí)現(xiàn)，但算法的時(shí)間復(fù)雜度顯然，這可利用有向圖來(lái)實(shí)現(xiàn)，但算法的時(shí)間復(fù)雜度是是O(n3)，開(kāi)銷(xiāo)過(guò)大，通常不予采用。，開(kāi)銷(xiāo)過(guò)大，通常不予采用。下面是一種較實(shí)用的算法。下面是一種較實(shí)用的算法。設(shè)置設(shè)置2個(gè)矩陣。一個(gè)是資源占用矩陣個(gè)矩陣。一個(gè)是資源占用矩陣U，列出了各進(jìn)程，列出了各進(jìn)程占用資源的狀態(tài)，如圖占用資源的狀態(tài)，如圖5-4所示。一個(gè)是資源等待矩陣所示。一個(gè)是資源等待矩陣W，列出了各進(jìn)程還需要的資源，如圖列出了各進(jìn)程還需要的資源，如圖5-5所示。所示。R1R2R3R4R5Pr

19、o1_2132Pro27_325Pro346_32Pro4321_1Pro53543_圖圖5-4 資源占用矩陣資源占用矩陣R1R2R3R4R5Pro132210Pro206100Pro300311Pro411021Pro500002圖圖5-5 資源等待矩陣資源等待矩陣另設(shè)置另設(shè)置2個(gè)向量。一個(gè)是系統(tǒng)資源總數(shù)向量個(gè)向量。一個(gè)是系統(tǒng)資源總數(shù)向量T，如圖，如圖5-6所示。另一個(gè)是當(dāng)前可用資源向量所示。另一個(gè)是當(dāng)前可用資源向量C，如圖，如圖5-7所示。所示。R1R2R3R4R5系統(tǒng)總資源系統(tǒng)總資源2020101510R1R2R3R4R5可用資源數(shù)可用資源數(shù)35140圖圖5-6 系統(tǒng)資源總量系統(tǒng)資源總量

20、圖圖5-7 當(dāng)前可用資源當(dāng)前可用資源算法的運(yùn)算比較簡(jiǎn)單，把向量算法的運(yùn)算比較簡(jiǎn)單，把向量C依次與矩陣依次與矩陣W的每一的每一行進(jìn)行比較：行進(jìn)行比較：CjWij。如果每一行中都出現(xiàn)了負(fù)數(shù)，。如果每一行中都出現(xiàn)了負(fù)數(shù)，即每個(gè)進(jìn)程都有不能滿足的資源，那就是發(fā)生了死鎖。即每個(gè)進(jìn)程都有不能滿足的資源，那就是發(fā)生了死鎖。圖圖5-4到圖到圖5-7表示的系統(tǒng)將要發(fā)生死鎖。表示的系統(tǒng)將要發(fā)生死鎖。2. 解除死鎖解除死鎖通?？梢圆扇∠旅鎯煞N可行的方法。通?？梢圆扇∠旅鎯煞N可行的方法。(1) 資源剝奪法資源剝奪法 由于死鎖是因進(jìn)程競(jìng)爭(zhēng)資源而引起的，所以，從一由于死鎖是因進(jìn)程競(jìng)爭(zhēng)資源而引起的，所以，從一些進(jìn)程那里強(qiáng)行

21、剝奪足夠數(shù)量的資源再分配給死鎖進(jìn)程，些進(jìn)程那里強(qiáng)行剝奪足夠數(shù)量的資源再分配給死鎖進(jìn)程，就可以解除死鎖狀態(tài)。問(wèn)題是選擇哪個(gè)進(jìn)程作為犧牲品？就可以解除死鎖狀態(tài)。問(wèn)題是選擇哪個(gè)進(jìn)程作為犧牲品？而這往往不是容易作出的決策。一種選擇是剝奪而這往往不是容易作出的決策。一種選擇是剝奪占用資源最多的進(jìn)程，以期盡可能多地釋放資源，不過(guò)后占用資源最多的進(jìn)程，以期盡可能多地釋放資源，不過(guò)后果很難預(yù)料。果很難預(yù)料。每次剝奪后，需要再次調(diào)用死鎖檢測(cè)算法，若已成功每次剝奪后，需要再次調(diào)用死鎖檢測(cè)算法，若已成功解除死鎖，則不需再剝奪。解除死鎖，則不需再剝奪。(2) 撤消進(jìn)程法撤消進(jìn)程法該方法不光是剝奪某個(gè)進(jìn)程的資源，而是將

22、整個(gè)進(jìn)程該方法不光是剝奪某個(gè)進(jìn)程的資源，而是將整個(gè)進(jìn)程Kill。這其實(shí)并不會(huì)更加殘忍，因?yàn)閯儕Z一個(gè)進(jìn)程的資源。這其實(shí)并不會(huì)更加殘忍，因?yàn)閯儕Z一個(gè)進(jìn)程的資源有可能已經(jīng)造成該進(jìn)程無(wú)法在正確運(yùn)行了，所以干脆有可能已經(jīng)造成該進(jìn)程無(wú)法在正確運(yùn)行了，所以干脆Kill。其后果也難以預(yù)料。其后果也難以預(yù)料。實(shí)際上，死鎖的檢測(cè)與解除策略可能根本就行不通。實(shí)際上，死鎖的檢測(cè)與解除策略可能根本就行不通。首先，使用資源占用矩陣和資源等待矩陣來(lái)檢測(cè)死鎖首先，使用資源占用矩陣和資源等待矩陣來(lái)檢測(cè)死鎖并不可靠，因?yàn)樵撍惴ㄒ罁?jù)的只是死鎖的必要條件而非充并不可靠，因?yàn)樵撍惴ㄒ罁?jù)的只是死鎖的必要條件而非充要條件，即該算法的結(jié)果只

23、能說(shuō)明死鎖有可能發(fā)生，但并要條件，即該算法的結(jié)果只能說(shuō)明死鎖有可能發(fā)生，但并不能肯定死鎖必定發(fā)生。不能肯定死鎖必定發(fā)生。其次，在多用戶系統(tǒng)中這個(gè)矩陣可能是一個(gè)巨大的矩其次，在多用戶系統(tǒng)中這個(gè)矩陣可能是一個(gè)巨大的矩陣，并且，資源每發(fā)生一下變化，就要更新這個(gè)矩陣，陣，并且，資源每發(fā)生一下變化，就要更新這個(gè)矩陣，CPU開(kāi)銷(xiāo)也將很高。開(kāi)銷(xiāo)也將很高。3.3 避免死鎖策略避免死鎖策略死鎖的檢測(cè)與解除是種亡羊補(bǔ)牢的策略，即使是檢測(cè)死鎖的檢測(cè)與解除是種亡羊補(bǔ)牢的策略，即使是檢測(cè)出并解除了死鎖，也已經(jīng)浪費(fèi)了時(shí)間，降低了效率，甚至出并解除了死鎖，也已經(jīng)浪費(fèi)了時(shí)間，降低了效率，甚至造成了其他損失。而避免死鎖策略則更

24、加積極主動(dòng)，它是造成了其他損失。而避免死鎖策略則更加積極主動(dòng)，它是在資源的動(dòng)態(tài)分配過(guò)程中，通過(guò)使用某種方法來(lái)防止相關(guān)在資源的動(dòng)態(tài)分配過(guò)程中，通過(guò)使用某種方法來(lái)防止相關(guān)進(jìn)程進(jìn)入不安全狀態(tài)，從而避免死鎖的發(fā)生。進(jìn)程進(jìn)入不安全狀態(tài)，從而避免死鎖的發(fā)生。Dijkstra提出的提出的銀行家算法銀行家算法是最著名的避免死鎖算法。是最著名的避免死鎖算法。這一名稱(chēng)的來(lái)歷是基于該算法把操作系統(tǒng)比做一個(gè)銀這一名稱(chēng)的來(lái)歷是基于該算法把操作系統(tǒng)比做一個(gè)銀行家，操作系統(tǒng)管理的各種資源比做銀行的借貸資金，而行家，操作系統(tǒng)管理的各種資源比做銀行的借貸資金，而申請(qǐng)系統(tǒng)資源的進(jìn)程喻為借貸的客戶。如果每個(gè)客戶的借申請(qǐng)系統(tǒng)資源的進(jìn)

25、程喻為借貸的客戶。如果每個(gè)客戶的借貸總額不超過(guò)銀行的借貸資金總數(shù)，而且在有限的期限內(nèi)貸總額不超過(guò)銀行的借貸資金總數(shù)，而且在有限的期限內(nèi)可收回借出的全部貸款，那么銀行就可以滿足客戶的借貸可收回借出的全部貸款，那么銀行就可以滿足客戶的借貸要求，同客戶進(jìn)行借貸交易，否則銀行將拒絕借貸給客戶。要求，同客戶進(jìn)行借貸交易，否則銀行將拒絕借貸給客戶。 銀行家算法的基本思想是，在每次進(jìn)行資源分配時(shí)先銀行家算法的基本思想是，在每次進(jìn)行資源分配時(shí)先進(jìn)行安全性檢查：如果滿足此資源請(qǐng)求系統(tǒng)將進(jìn)入到不安進(jìn)行安全性檢查：如果滿足此資源請(qǐng)求系統(tǒng)將進(jìn)入到不安全狀態(tài)，則拒絕分配；只有確保系統(tǒng)處于安全狀態(tài)時(shí)才實(shí)全狀態(tài)，則拒絕分配

26、；只有確保系統(tǒng)處于安全狀態(tài)時(shí)才實(shí)施資源分配。施資源分配。所謂所謂安全狀態(tài)安全狀態(tài)是指，對(duì)于一組進(jìn)程系統(tǒng)能保證其中的是指，對(duì)于一組進(jìn)程系統(tǒng)能保證其中的每個(gè)進(jìn)程都能在有限時(shí)間內(nèi)獲得各自所需的全部資源。否每個(gè)進(jìn)程都能在有限時(shí)間內(nèi)獲得各自所需的全部資源。否則，就是不安全狀態(tài)。則，就是不安全狀態(tài)。不安全狀態(tài)并不是死鎖狀態(tài)，而是潛在的死鎖狀態(tài)，不安全狀態(tài)并不是死鎖狀態(tài)，而是潛在的死鎖狀態(tài)，極有可能轉(zhuǎn)化為死鎖狀態(tài)。極有可能轉(zhuǎn)化為死鎖狀態(tài)。例：安全狀態(tài)例：安全狀態(tài)例：不安全狀態(tài)例：不安全狀態(tài)（見(jiàn)書(shū)（見(jiàn)書(shū)Page110111）避免死鎖策略的優(yōu)點(diǎn)是，在死鎖有可能發(fā)生時(shí)采取先避免死鎖策略的優(yōu)點(diǎn)是，在死鎖有可能發(fā)生時(shí)

27、采取先發(fā)制人的措施，斷然拒絕可能引導(dǎo)系統(tǒng)進(jìn)入潛在死鎖的資發(fā)制人的措施，斷然拒絕可能引導(dǎo)系統(tǒng)進(jìn)入潛在死鎖的資源請(qǐng)求。由于系統(tǒng)從來(lái)不會(huì)進(jìn)入到死鎖狀態(tài)，死鎖帶來(lái)的源請(qǐng)求。由于系統(tǒng)從來(lái)不會(huì)進(jìn)入到死鎖狀態(tài)，死鎖帶來(lái)的各種問(wèn)題自然不復(fù)存在。各種問(wèn)題自然不復(fù)存在。但該策略的缺點(diǎn)也是十分明顯的。首先，計(jì)算一個(gè)狀但該策略的缺點(diǎn)也是十分明顯的。首先，計(jì)算一個(gè)狀態(tài)是否安全不是一件容易的事。從上面的例子也許覺(jué)得這態(tài)是否安全不是一件容易的事。從上面的例子也許覺(jué)得這種計(jì)算不是十分困難，問(wèn)題是，這只是對(duì)一種資源及種計(jì)算不是十分困難，問(wèn)題是，這只是對(duì)一種資源及3個(gè)個(gè)進(jìn)程的超簡(jiǎn)單系統(tǒng)進(jìn)行的計(jì)算，如果系統(tǒng)資源種類(lèi)繁多，進(jìn)程的超簡(jiǎn)

28、單系統(tǒng)進(jìn)行的計(jì)算，如果系統(tǒng)資源種類(lèi)繁多，進(jìn)程個(gè)數(shù)龐大，則這種計(jì)算將變得十分復(fù)雜和費(fèi)時(shí)。其次，進(jìn)程個(gè)數(shù)龐大，則這種計(jì)算將變得十分復(fù)雜和費(fèi)時(shí)。其次，該策略要求事先知道每個(gè)進(jìn)程的最大資源需求，這不是需該策略要求事先知道每個(gè)進(jìn)程的最大資源需求，這不是需要預(yù)測(cè)將來(lái)嗎？這是非常困難的。只能采用粗略估算，但要預(yù)測(cè)將來(lái)嗎？這是非常困難的。只能采用粗略估算，但粗略估算往往是不可靠的。例如，粗略估算往往是不可靠的。例如，20072008年年度的美國(guó)次級(jí)貸就是這種錯(cuò)誤估算的一個(gè)實(shí)例，因?yàn)樗麄兌鹊拿绹?guó)次級(jí)貸就是這種錯(cuò)誤估算的一個(gè)實(shí)例，因?yàn)樗麄兯沐e(cuò)了客戶的信用額度，使得很多人還不起貸款，從而導(dǎo)算錯(cuò)了客戶的信用額度，使得

29、很多人還不起貸款，從而導(dǎo)致美國(guó)的金融危機(jī)。致美國(guó)的金融危機(jī)。3.4 預(yù)防死鎖策略預(yù)防死鎖策略該策略的中心思想是清除死鎖發(fā)生的土壤，而死鎖發(fā)該策略的中心思想是清除死鎖發(fā)生的土壤，而死鎖發(fā)生的土壤就是死鎖的生的土壤就是死鎖的4個(gè)必要條件，如果消除這個(gè)必要條件，如果消除這4個(gè)必要個(gè)必要條件中的任何一個(gè)，則死鎖就不可能發(fā)生。條件中的任何一個(gè)，則死鎖就不可能發(fā)生。1. 消除資源互斥條件消除資源互斥條件對(duì)有些臨界資源可以將它們改造成邏輯上的非臨界資對(duì)有些臨界資源可以將它們改造成邏輯上的非臨界資源，例如，利用源，例如，利用“假脫機(jī)假脫機(jī)”技術(shù)可將打印機(jī)改造成非臨界技術(shù)可將打印機(jī)改造成非臨界資源。不過(guò)資源。不

30、過(guò)“假脫機(jī)假脫機(jī)”技術(shù)并不適應(yīng)所有的臨界資源，如技術(shù)并不適應(yīng)所有的臨界資源，如鍵盤(pán)。鍵盤(pán)。2. 消除保持和請(qǐng)求條件消除保持和請(qǐng)求條件消除這個(gè)條件很簡(jiǎn)單，只要進(jìn)程一次性請(qǐng)求它所需要消除這個(gè)條件很簡(jiǎn)單，只要進(jìn)程一次性請(qǐng)求它所需要的所有資源，由于一個(gè)進(jìn)程一次就獲得了其所需的所有資的所有資源，由于一個(gè)進(jìn)程一次就獲得了其所需的所有資源，該進(jìn)程自然就可以順利運(yùn)行，從而不會(huì)發(fā)生死鎖。當(dāng)然，源，該進(jìn)程自然就可以順利運(yùn)行，從而不會(huì)發(fā)生死鎖。當(dāng)然，如果系統(tǒng)不能一次性地滿足一進(jìn)程的所有資源，則阻塞該進(jìn)如果系統(tǒng)不能一次性地滿足一進(jìn)程的所有資源，則阻塞該進(jìn)程。程。這種策略的缺點(diǎn)是：一次性分配所有資源太過(guò)浪費(fèi)，因這種策略

31、的缺點(diǎn)是：一次性分配所有資源太過(guò)浪費(fèi)，因?yàn)橛械馁Y源可能要到最后才使用，但卻長(zhǎng)時(shí)間閑置著又不能為有的資源可能要到最后才使用，但卻長(zhǎng)時(shí)間閑置著又不能給其他進(jìn)程使用；其次，一開(kāi)始就需要知道一個(gè)進(jìn)程所需要給其他進(jìn)程使用；其次，一開(kāi)始就需要知道一個(gè)進(jìn)程所需要的所有資源，這個(gè)問(wèn)題仍然無(wú)解。的所有資源，這個(gè)問(wèn)題仍然無(wú)解。3. 消除不可剝奪條件消除不可剝奪條件該策略可適用于某些資源，如剝奪一進(jìn)程的該策略可適用于某些資源，如剝奪一進(jìn)程的CPU和內(nèi)存和內(nèi)存空間。另外，可借助空間。另外，可借助SPOOLing技術(shù)將某些獨(dú)享設(shè)備改造成技術(shù)將某些獨(dú)享設(shè)備改造成虛擬的共享設(shè)備。虛擬的共享設(shè)備。不過(guò)，不是所有的資源都可以被

32、剝奪而不產(chǎn)生不良后不過(guò)，不是所有的資源都可以被剝奪而不產(chǎn)生不良后果。例如，鎖就不能被剝奪，如果強(qiáng)行剝奪了一進(jìn)程的鎖，果。例如，鎖就不能被剝奪，如果強(qiáng)行剝奪了一進(jìn)程的鎖，后果有可能不堪設(shè)想。后果有可能不堪設(shè)想。4. 消除循環(huán)等待條件消除循環(huán)等待條件循環(huán)等待的原因是因?yàn)檫M(jìn)程請(qǐng)求資源的順序是隨機(jī)的，循環(huán)等待的原因是因?yàn)檫M(jìn)程請(qǐng)求資源的順序是隨機(jī)的，即一個(gè)進(jìn)程可以先請(qǐng)求資源即一個(gè)進(jìn)程可以先請(qǐng)求資源A在請(qǐng)求資源在請(qǐng)求資源B，也可以先請(qǐng)，也可以先請(qǐng)求求B再請(qǐng)求再請(qǐng)求A。這樣，如果兩個(gè)進(jìn)程按照不同的順序請(qǐng)求。這樣，如果兩個(gè)進(jìn)程按照不同的順序請(qǐng)求A、B兩個(gè)資源，死鎖就有可能發(fā)生。但如果我們規(guī)定對(duì)兩個(gè)資源，死鎖就

33、有可能發(fā)生。但如果我們規(guī)定對(duì)A、B兩個(gè)資源的使用必須按照先兩個(gè)資源的使用必須按照先A后后B的順序請(qǐng)求，則死鎖就的順序請(qǐng)求，則死鎖就不會(huì)發(fā)生。不會(huì)發(fā)生。假定一個(gè)系統(tǒng)有假定一個(gè)系統(tǒng)有A、B、C三種資源，且規(guī)定請(qǐng)求資源三種資源，且規(guī)定請(qǐng)求資源的順序必須是的順序必須是A-B-C。如果一進(jìn)程只使用一種資源，。如果一進(jìn)程只使用一種資源，則直接請(qǐng)求該資源即可；如果一進(jìn)程需要請(qǐng)求兩個(gè)或以上則直接請(qǐng)求該資源即可；如果一進(jìn)程需要請(qǐng)求兩個(gè)或以上的資源，必須按規(guī)定順序請(qǐng)求資源。例如，如果某進(jìn)程需的資源，必須按規(guī)定順序請(qǐng)求資源。例如，如果某進(jìn)程需要使用要使用A、C兩個(gè)資源，則必須先請(qǐng)求兩個(gè)資源，則必須先請(qǐng)求A，再請(qǐng)求，再請(qǐng)求C，即使，即使該進(jìn)程實(shí)際