OS2013_UNIT5死鎖

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

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

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

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

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

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

7、中的每個進(jìn)程已占有著某個（些）資源，同時又在路，其中的每個進(jìn)程已占有著某個（些）資源，同時又在等待獲取被環(huán)路中另一個進(jìn)程占有的資源。等待獲取被環(huán)路中另一個進(jìn)程占有的資源。2.2 充分必要條件充分必要條件假定在某個時刻一組線程使用一組資源的狀態(tài)為假定在某個時刻一組線程使用一組資源的狀態(tài)為S（S也稱資源分配狀態(tài)），一個也稱資源分配狀態(tài)），一個RAG (Resources Allocation Graph)是該是該S所對應(yīng)的有向圖，如果：所對應(yīng)的有向圖，如果：(1)該該RAG中未出現(xiàn)任何環(huán)路，則中未出現(xiàn)任何環(huán)路，則S為非死鎖狀態(tài)，為非死鎖狀態(tài)，也稱安全狀態(tài)。也稱安全狀態(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是可完全化簡圖。是可完全化簡圖。安全狀態(tài)！安全狀態(tài)！R1R2R3R4圖圖5-3 死鎖定理死鎖定理(2)線程線程1線程線程2線程線程3構(gòu)成不可化簡圖。構(gòu)成不可化簡圖。死鎖！死鎖！R1R2R3R4死鎖定理：死鎖定理：在某個時刻的進(jìn)程資源狀態(tài)在某個時刻的進(jìn)程資源狀態(tài)S為死鎖狀態(tài)的充為死鎖狀態(tài)的充分必要條件是當(dāng)且僅當(dāng)分必要條件是當(dāng)且僅當(dāng)S的資源分配圖（的資源分配圖（RAG）是不可完全化簡的。是不可完全化簡的。3 忽略死鎖策略忽略死鎖策略 檢測并解除策略檢測并解除策略 避免死鎖策略避免死鎖策略預(yù)防死鎖策略預(yù)防死鎖策略綜合治理綜合治理死鎖是操作系統(tǒng)必須應(yīng)對的問題，是無法回避的。那死鎖是操作系統(tǒng)必須應(yīng)對

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

26、；只有確保系統(tǒng)處于安全狀態(tài)時才實施資源分配。施資源分配。所謂所謂安全狀態(tài)安全狀態(tài)是指，對于一組進(jìn)程系統(tǒng)能保證其中的是指，對于一組進(jìn)程系統(tǒng)能保證其中的每個進(jìn)程都能在有限時間內(nèi)獲得各自所需的全部資源。否每個進(jìn)程都能在有限時間內(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)（見書（見書Page110111）避免死鎖策略的優(yōu)點是，在死鎖有可能發(fā)生時采取先避免死鎖策略的優(yōu)點是，在死鎖有可能發(fā)生時

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

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

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

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

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

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

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