產(chǎn)生死鎖的原因和必要條件

1、1會(huì)計(jì)學(xué)產(chǎn)生死鎖的原因和必要條件產(chǎn)生死鎖的原因和必要條件一、競(jìng)爭(zhēng)資源引起死鎖一、競(jìng)爭(zhēng)資源引起死鎖1 1、可將系統(tǒng)中的資源分為兩類(lèi)：、可將系統(tǒng)中的資源分為兩類(lèi)：可剝奪性資可剝奪性資源和非剝奪性資源源和非剝奪性資源。 可剝奪性資源是指：某進(jìn)程在獲得這類(lèi)資可剝奪性資源是指：某進(jìn)程在獲得這類(lèi)資源后，該資源可被其他進(jìn)程搶占。源后，該資源可被其他進(jìn)程搶占。 如處理機(jī)、內(nèi)存。優(yōu)先權(quán)高的進(jìn)程可以剝?nèi)缣幚頇C(jī)、內(nèi)存。優(yōu)先權(quán)高的進(jìn)程可以剝奪優(yōu)先權(quán)低的進(jìn)程的處理機(jī)；內(nèi)存區(qū)可由內(nèi)存奪優(yōu)先權(quán)低的進(jìn)程的處理機(jī)；內(nèi)存區(qū)可由內(nèi)存管理程序把一個(gè)進(jìn)程從一個(gè)存儲(chǔ)區(qū)移到另一個(gè)管理程序把一個(gè)進(jìn)程從一個(gè)存儲(chǔ)區(qū)移到另一個(gè)存儲(chǔ)區(qū)，即剝奪了該進(jìn)

2、程原來(lái)占有的存儲(chǔ)區(qū)。存儲(chǔ)區(qū)，即剝奪了該進(jìn)程原來(lái)占有的存儲(chǔ)區(qū)。第2頁(yè)/共63頁(yè) 非剝奪性資源是指：進(jìn)程一旦占有該資源非剝奪性資源是指：進(jìn)程一旦占有該資源，就不可搶占，不管其它進(jìn)程的優(yōu)先權(quán)是否高，就不可搶占，不管其它進(jìn)程的優(yōu)先權(quán)是否高于當(dāng)前進(jìn)程，只能在該進(jìn)程用完后自行釋放。于當(dāng)前進(jìn)程，只能在該進(jìn)程用完后自行釋放。 如打印機(jī)、磁帶機(jī)等。如打印機(jī)、磁帶機(jī)等。 大多數(shù)情況下，我們所講引起的死鎖的資大多數(shù)情況下，我們所講引起的死鎖的資源競(jìng)爭(zhēng)，是指對(duì)于非剝奪性資源的競(jìng)爭(zhēng)。源競(jìng)爭(zhēng)，是指對(duì)于非剝奪性資源的競(jìng)爭(zhēng)。第3頁(yè)/共63頁(yè)2、競(jìng)爭(zhēng)非剝奪性資源、競(jìng)爭(zhēng)非剝奪性資源 若系統(tǒng)中只有一臺(tái)打印機(jī)若系統(tǒng)中只有一臺(tái)打印機(jī)R

3、1R1和一臺(tái)磁帶機(jī)和一臺(tái)磁帶機(jī)R2R2，可供進(jìn)程，可供進(jìn)程P1P1和和P2P2共享。假定共享。假定P1P1已占用了打已占用了打印機(jī)印機(jī)R1R1，P2P2占用了磁帶機(jī)占用了磁帶機(jī)R2R2。此時(shí)，若。此時(shí)，若P2P2繼續(xù)繼續(xù)要求打印機(jī)，要求打印機(jī)，P2P2將阻塞；將阻塞；P1P1若又要求磁帶機(jī)，若又要求磁帶機(jī)，P1P1也將阻塞。也將阻塞。 于是，于是，P1P1與與P2P2之間便形成了僵局，兩個(gè)進(jìn)之間便形成了僵局，兩個(gè)進(jìn)程都在等待對(duì)方釋放出自己所需的資源，但它程都在等待對(duì)方釋放出自己所需的資源，但它們又都因不能獲得所需的資源而不能繼續(xù)推進(jìn)，們又都因不能獲得所需的資源而不能繼續(xù)推進(jìn)，從而也不釋放自己已

4、占用的資源，就進(jìn)入了死從而也不釋放自己已占用的資源，就進(jìn)入了死鎖狀態(tài)。鎖狀態(tài)。第4頁(yè)/共63頁(yè)I/O設(shè)備共享時(shí)的死鎖情況設(shè)備共享時(shí)的死鎖情況P2P1R1R2 方塊代表資源方塊代表資源 圓圈代表進(jìn)程圓圈代表進(jìn)程 箭頭從進(jìn)程指向資箭頭從進(jìn)程指向資源，表示進(jìn)程請(qǐng)求該源，表示進(jìn)程請(qǐng)求該資源資源 箭頭從資源指向進(jìn)箭頭從資源指向進(jìn)程，表示該資源已分程，表示該資源已分配給進(jìn)程配給進(jìn)程第5頁(yè)/共63頁(yè)3、競(jìng)爭(zhēng)臨時(shí)性資源、競(jìng)爭(zhēng)臨時(shí)性資源 臨時(shí)性資源，也稱(chēng)為消耗性資源，是指由臨時(shí)性資源，也稱(chēng)為消耗性資源，是指由一個(gè)進(jìn)程產(chǎn)生，被另一進(jìn)程使用一短暫時(shí)間后一個(gè)進(jìn)程產(chǎn)生，被另一進(jìn)程使用一短暫時(shí)間后便無(wú)用的資源，如消息等。

5、便無(wú)用的資源，如消息等。 競(jìng)爭(zhēng)臨時(shí)性資源也可能引起死鎖。競(jìng)爭(zhēng)臨時(shí)性資源也可能引起死鎖。第6頁(yè)/共63頁(yè)例：例：S1、S2、S3是臨時(shí)性資源，進(jìn)程是臨時(shí)性資源，進(jìn)程P1產(chǎn)生消產(chǎn)生消息息S1，又要求接收，又要求接收S3；P3產(chǎn)生消息產(chǎn)生消息S3，又要求，又要求接收接收S2；P2產(chǎn)生消息產(chǎn)生消息S2，又要求接收，又要求接收S1。若消。若消息通信按以下順序進(jìn)行：息通信按以下順序進(jìn)行：P1:Release(S1);Request(S3);P2:Release(S2);Request(S1);P3:Release(S3);Request(S1);并不可能發(fā)生死鎖。并不可能發(fā)生死鎖。第7頁(yè)/共63頁(yè)若按以下

6、運(yùn)行順序：若按以下運(yùn)行順序：P1:Request(S3);Release(S1);P2:Request(S1);Release(S2);P3:Request(S2);Release(S3);則可能發(fā)生死鎖則可能發(fā)生死鎖P3P1S2S2P2S1進(jìn)程通信時(shí)的死鎖進(jìn)程通信時(shí)的死鎖第8頁(yè)/共63頁(yè)二、進(jìn)程推進(jìn)順序不當(dāng)引起死鎖二、進(jìn)程推進(jìn)順序不當(dāng)引起死鎖1、進(jìn)程推進(jìn)順序合法、進(jìn)程推進(jìn)順序合法例：在進(jìn)程例：在進(jìn)程P1和和P2并發(fā)執(zhí)行時(shí)，如果按以下順并發(fā)執(zhí)行時(shí)，如果按以下順序推進(jìn)：序推進(jìn)：P1 Request(R1); P1 Request(R2); P1 Release(R1); P1 Release(R

7、2);P2 Request(R2); P2 Request(R1); P2 Release(R2); P2 Release(R1); 則兩個(gè)進(jìn)程可順利完成。如下圖則兩個(gè)進(jìn)程可順利完成。如下圖4-16中的曲中的曲線(xiàn)線(xiàn)1 所示。所示。第9頁(yè)/共63頁(yè)第10頁(yè)/共63頁(yè)第11頁(yè)/共63頁(yè)第12頁(yè)/共63頁(yè)2、進(jìn)程推進(jìn)順序非法、進(jìn)程推進(jìn)順序非法 若并發(fā)進(jìn)程若并發(fā)進(jìn)程P1P1和和P2P2按曲線(xiàn)條所示的順序推按曲線(xiàn)條所示的順序推進(jìn)，進(jìn)，P1P1保持了資源保持了資源R1R1，P2P2保持了資源保持了資源R2R2，系統(tǒng)，系統(tǒng)處于不安全狀態(tài)。處于不安全狀態(tài)。 當(dāng)當(dāng)P1P1運(yùn)行到運(yùn)行到P1 Request(R2)

8、 P1 Request(R2) 時(shí)，將因時(shí)，將因R2R2已被已被P2P2占用而阻塞；當(dāng)占用而阻塞；當(dāng)P2P2運(yùn)行到運(yùn)行到P2 P2 Request(R1)Request(R1)時(shí)，又因時(shí)，又因R1R1已被已被P1P1占用而阻塞，占用而阻塞，于是發(fā)生了進(jìn)程死鎖。于是發(fā)生了進(jìn)程死鎖。第13頁(yè)/共63頁(yè)第14頁(yè)/共63頁(yè)系統(tǒng)中如果死鎖發(fā)生，則一定同時(shí)存在下列系統(tǒng)中如果死鎖發(fā)生，則一定同時(shí)存在下列四個(gè)條件，即死鎖的必要條件：四個(gè)條件，即死鎖的必要條件：（1 1）互斥條件）互斥條件（2 2）占有且申請(qǐng)條件）占有且申請(qǐng)條件（3 3）不可搶占條件）不可搶占條件（4 4）環(huán)路條件）環(huán)路條件第15頁(yè)/共63頁(yè)（

9、1 1）互斥條件）互斥條件 對(duì)于一個(gè)排它性資源，某一時(shí)刻最多只能對(duì)于一個(gè)排它性資源，某一時(shí)刻最多只能由一個(gè)進(jìn)程占有，不能同時(shí)分配給兩個(gè)以上的由一個(gè)進(jìn)程占有，不能同時(shí)分配給兩個(gè)以上的進(jìn)程。如果此時(shí)還有其它進(jìn)程要求該資源，要進(jìn)程。如果此時(shí)還有其它進(jìn)程要求該資源，要求者只能阻塞，直到占有該資源的進(jìn)程放棄該求者只能阻塞，直到占有該資源的進(jìn)程放棄該資源后，其它進(jìn)程才能占有該資源。資源后，其它進(jìn)程才能占有該資源。 如打印機(jī)是臨界資源，各進(jìn)程必須互斥地如打印機(jī)是臨界資源，各進(jìn)程必須互斥地使用。使用。第16頁(yè)/共63頁(yè)（2 2）請(qǐng)求和保持條件）請(qǐng)求和保持條件 進(jìn)程已經(jīng)保持了至少一個(gè)資源，但又申請(qǐng)進(jìn)程已經(jīng)保持了

10、至少一個(gè)資源，但又申請(qǐng)新的資源；而該資源已被另外進(jìn)程占有，此時(shí)新的資源；而該資源已被另外進(jìn)程占有，此時(shí)該進(jìn)程阻塞；但是，它在等待新資源時(shí)，仍不該進(jìn)程阻塞；但是，它在等待新資源時(shí)，仍不釋放已保持的資源。釋放已保持的資源。（3 3）不剝奪條件）不剝奪條件 進(jìn)程所獲得的資源，在未使用完畢之前，進(jìn)程所獲得的資源，在未使用完畢之前，不能被強(qiáng)行剝奪該資源；只能在該進(jìn)程釋放已不能被強(qiáng)行剝奪該資源；只能在該進(jìn)程釋放已獲得的資源后，其它進(jìn)程才可以使用。獲得的資源后，其它進(jìn)程才可以使用。第17頁(yè)/共63頁(yè)（4 4）環(huán)路等待條件）環(huán)路等待條件 如果死鎖產(chǎn)生，則一定存在一個(gè)如果死鎖產(chǎn)生，則一定存在一個(gè)“進(jìn)程進(jìn)程- -

11、資資源源”的環(huán)形鏈。即進(jìn)程集合的環(huán)形鏈。即進(jìn)程集合P0,P1,PnP0,P1,Pn，其，其中中P0P0等待等待P1 P1 所占有的資源，所占有的資源，P1P1等待等待P2P2所需的所需的資源，資源，Pn-1 Pn-1 等待等待Pn Pn 所占有的資源，所占有的資源，PnPn等等待待P0 P0 所占有的資源。所占有的資源。 以上四個(gè)條件是在死鎖發(fā)生時(shí)同時(shí)出現(xiàn)的以上四個(gè)條件是在死鎖發(fā)生時(shí)同時(shí)出現(xiàn)的，我們可以利用它的逆否命題，即：，我們可以利用它的逆否命題，即：四個(gè)條四個(gè)條件中只要有一個(gè)不滿(mǎn)足，則死鎖不會(huì)發(fā)生件中只要有一個(gè)不滿(mǎn)足，則死鎖不會(huì)發(fā)生。這正是我們預(yù)防死鎖所需考慮的方法。這正是我們預(yù)防死鎖所

12、需考慮的方法。第18頁(yè)/共63頁(yè)為保證系統(tǒng)的正常運(yùn)行，應(yīng)事先采取措施，為保證系統(tǒng)的正常運(yùn)行，應(yīng)事先采取措施，預(yù)防或避免死鎖的發(fā)生。在系統(tǒng)已出現(xiàn)死鎖后，預(yù)防或避免死鎖的發(fā)生。在系統(tǒng)已出現(xiàn)死鎖后，要及時(shí)檢測(cè)到死鎖并解除死鎖。要及時(shí)檢測(cè)到死鎖并解除死鎖。目前用于處理死鎖問(wèn)題的方法有以下幾種：目前用于處理死鎖問(wèn)題的方法有以下幾種： 1 1死鎖的預(yù)防死鎖的預(yù)防 2 2死鎖的避免死鎖的避免 3 3死鎖的檢測(cè)死鎖的檢測(cè) 4 4死鎖的解除死鎖的解除第19頁(yè)/共63頁(yè)3.6 3.6 預(yù)防死鎖的方法預(yù)防死鎖的方法3.6.1 3.6.1 預(yù)防死鎖預(yù)防死鎖一、摒棄一、摒棄“請(qǐng)求和保持請(qǐng)求和保持”條件條件1 1、實(shí)現(xiàn)方

13、法、實(shí)現(xiàn)方法 要求進(jìn)程一次性申請(qǐng)整個(gè)運(yùn)行進(jìn)程中的全部要求進(jìn)程一次性申請(qǐng)整個(gè)運(yùn)行進(jìn)程中的全部資源，只有申請(qǐng)到全部資源后，方可投入運(yùn)行；資源，只有申請(qǐng)到全部資源后，方可投入運(yùn)行；這樣進(jìn)程運(yùn)行期間不會(huì)再提出資源要求。這樣進(jìn)程運(yùn)行期間不會(huì)再提出資源要求。 只要有一種資源要求不能滿(mǎn)足，則全部其它只要有一種資源要求不能滿(mǎn)足，則全部其它資源都不分配給進(jìn)程，而讓該進(jìn)程等待；這樣，資源都不分配給進(jìn)程，而讓該進(jìn)程等待；這樣，進(jìn)程等待期間未占有任何資源。進(jìn)程等待期間未占有任何資源。第20頁(yè)/共63頁(yè)一、摒棄一、摒棄“請(qǐng)求和保持請(qǐng)求和保持”條件條件優(yōu)點(diǎn)：優(yōu)點(diǎn)：簡(jiǎn)單，易于實(shí)現(xiàn)，安全。簡(jiǎn)單，易于實(shí)現(xiàn)，安全。缺點(diǎn)：缺點(diǎn)：資

14、源嚴(yán)重浪費(fèi)，進(jìn)程延遲運(yùn)行。資源嚴(yán)重浪費(fèi)，進(jìn)程延遲運(yùn)行。第21頁(yè)/共63頁(yè)二、摒棄二、摒棄“不剝奪不剝奪”條件條件1 1、實(shí)現(xiàn)方法：、實(shí)現(xiàn)方法： 一個(gè)已保持了某些資源的進(jìn)程，當(dāng)它在提出一個(gè)已保持了某些資源的進(jìn)程，當(dāng)它在提出新的資源要求而不能得到立即滿(mǎn)足時(shí)，必須釋新的資源要求而不能得到立即滿(mǎn)足時(shí)，必須釋放它已經(jīng)保持的所有資源，待以后需要時(shí)再重放它已經(jīng)保持的所有資源，待以后需要時(shí)再重新申請(qǐng)。新申請(qǐng)。2 2、缺點(diǎn)：、缺點(diǎn)：實(shí)現(xiàn)復(fù)雜、代價(jià)高。實(shí)現(xiàn)復(fù)雜、代價(jià)高。第22頁(yè)/共63頁(yè)三、摒棄三、摒棄“環(huán)路等待環(huán)路等待”條件條件1 1、實(shí)現(xiàn)方法：、實(shí)現(xiàn)方法： 將所有的資源按類(lèi)型進(jìn)行線(xiàn)性排隊(duì)，并賦將所有的資源按類(lèi)

15、型進(jìn)行線(xiàn)性排隊(duì)，并賦予不同的序號(hào)；并規(guī)定進(jìn)程的資源請(qǐng)求必須予不同的序號(hào)；并規(guī)定進(jìn)程的資源請(qǐng)求必須按資源序號(hào)遞增的次序提出。按資源序號(hào)遞增的次序提出。 這樣在所形成的資源分配圖中，不可能再這樣在所形成的資源分配圖中，不可能再出現(xiàn)環(huán)路；在采用這種策略時(shí)，總有一個(gè)進(jìn)出現(xiàn)環(huán)路；在采用這種策略時(shí)，總有一個(gè)進(jìn)程占據(jù)了較高序號(hào)的資源，它繼續(xù)請(qǐng)求的資程占據(jù)了較高序號(hào)的資源，它繼續(xù)請(qǐng)求的資源必然是空閑的，因而進(jìn)程可以一直向前推源必然是空閑的，因而進(jìn)程可以一直向前推進(jìn)。進(jìn)。第23頁(yè)/共63頁(yè)優(yōu)點(diǎn)：優(yōu)點(diǎn)：資源利用率和系統(tǒng)吞吐量得到了提高。資源利用率和系統(tǒng)吞吐量得到了提高。缺點(diǎn)：缺點(diǎn)：、限制了新設(shè)備的增加。、限制了新

16、設(shè)備的增加。、系統(tǒng)為資源分配的序號(hào)與進(jìn)程實(shí)際、系統(tǒng)為資源分配的序號(hào)與進(jìn)程實(shí)際使用資源的順序不同而造成資源浪費(fèi)。使用資源的順序不同而造成資源浪費(fèi)。 、給用戶(hù)編程帶來(lái)了麻煩。、給用戶(hù)編程帶來(lái)了麻煩。第24頁(yè)/共63頁(yè)3.6.2 3.6.2 系統(tǒng)的安全狀態(tài)系統(tǒng)的安全狀態(tài) 預(yù)防死鎖的方法都是施加了較強(qiáng)的限制條件預(yù)防死鎖的方法都是施加了較強(qiáng)的限制條件而使實(shí)現(xiàn)簡(jiǎn)單，但損害了系統(tǒng)的性能。在避免而使實(shí)現(xiàn)簡(jiǎn)單，但損害了系統(tǒng)的性能。在避免死鎖的方法中，所施加的限制條件較弱，有可死鎖的方法中，所施加的限制條件較弱，有可能獲得令人滿(mǎn)意的系統(tǒng)性能。能獲得令人滿(mǎn)意的系統(tǒng)性能。 在避免死鎖的方法中，把系統(tǒng)的狀態(tài)分為安在避免

17、死鎖的方法中，把系統(tǒng)的狀態(tài)分為安全狀態(tài)和不安全狀態(tài)，只要能使系統(tǒng)始終處于全狀態(tài)和不安全狀態(tài)，只要能使系統(tǒng)始終處于安全狀態(tài)，就可避免發(fā)生死鎖。安全狀態(tài)，就可避免發(fā)生死鎖。第25頁(yè)/共63頁(yè)一、安全狀態(tài)一、安全狀態(tài) 在避免死鎖的方法中，允許進(jìn)程動(dòng)態(tài)地申請(qǐng)?jiān)诒苊馑梨i的方法中，允許進(jìn)程動(dòng)態(tài)地申請(qǐng)資源，系統(tǒng)在進(jìn)行資源分配之前，先計(jì)算資源資源，系統(tǒng)在進(jìn)行資源分配之前，先計(jì)算資源分配的安全性。若此次分配不會(huì)導(dǎo)致系統(tǒng)進(jìn)入分配的安全性。若此次分配不會(huì)導(dǎo)致系統(tǒng)進(jìn)入不安全狀態(tài)，便將資源分配給進(jìn)程；否則，進(jìn)不安全狀態(tài)，便將資源分配給進(jìn)程；否則，進(jìn)程等待。程等待。 所謂所謂“安全狀態(tài)安全狀態(tài)”，是指系統(tǒng)能按某種順序，是

18、指系統(tǒng)能按某種順序如如序列，來(lái)為每個(gè)進(jìn)程分配其序列，來(lái)為每個(gè)進(jìn)程分配其所需資源，直至最大需求，使每個(gè)進(jìn)程都可順?biāo)栀Y源，直至最大需求，使每個(gè)進(jìn)程都可順序完成。序完成。 若系統(tǒng)不存在這樣的安全序列，則稱(chēng)系統(tǒng)處若系統(tǒng)不存在這樣的安全序列，則稱(chēng)系統(tǒng)處于不安全狀態(tài)。于不安全狀態(tài)。第26頁(yè)/共63頁(yè) 雖然并非所有不安全狀態(tài)都是死鎖狀態(tài)，雖然并非所有不安全狀態(tài)都是死鎖狀態(tài)，但當(dāng)系統(tǒng)進(jìn)入不安全狀態(tài)時(shí)，便可能進(jìn)而進(jìn)但當(dāng)系統(tǒng)進(jìn)入不安全狀態(tài)時(shí)，便可能進(jìn)而進(jìn)入死鎖狀態(tài)；反之，只要系統(tǒng)處于安全狀態(tài)，入死鎖狀態(tài)；反之，只要系統(tǒng)處于安全狀態(tài)，系統(tǒng)便可避免進(jìn)入死鎖狀態(tài)。系統(tǒng)便可避免進(jìn)入死鎖狀態(tài)。 因此，避免死鎖的實(shí)質(zhì)在于：

19、因此，避免死鎖的實(shí)質(zhì)在于：如何使系統(tǒng)如何使系統(tǒng)不進(jìn)入不安全狀態(tài)不進(jìn)入不安全狀態(tài)。第27頁(yè)/共63頁(yè)二、安全狀態(tài)舉例二、安全狀態(tài)舉例 假定系統(tǒng)有三個(gè)進(jìn)程假定系統(tǒng)有三個(gè)進(jìn)程P1,P2,P3P1,P2,P3，共有，共有12 12 臺(tái)磁臺(tái)磁帶機(jī)。進(jìn)程帶機(jī)。進(jìn)程P1P1總共要求總共要求1010臺(tái)磁帶機(jī)，臺(tái)磁帶機(jī)，P2P2和和P3P3分別要分別要求求4 4臺(tái)和臺(tái)和9 9臺(tái)。設(shè)在臺(tái)。設(shè)在T T0 0時(shí)刻，進(jìn)程時(shí)刻，進(jìn)程P1P1、P2P2和和P3P3已分別已分別獲得獲得5 5臺(tái)、臺(tái)、2 2臺(tái)和臺(tái)和2 2臺(tái)，如下表所示：臺(tái)，如下表所示：進(jìn)程進(jìn)程最大需求最大需求已分配已分配可用可用P1P110105 53 3P2

20、P24 42 2P3P39 92 2第28頁(yè)/共63頁(yè) 經(jīng)分析可以發(fā)現(xiàn)，在經(jīng)分析可以發(fā)現(xiàn)，在T T0 0時(shí)刻，系統(tǒng)是安全時(shí)刻，系統(tǒng)是安全的。因?yàn)榈摹Ｒ驗(yàn)門(mén) T0 0時(shí)刻存在一個(gè)安全序列時(shí)刻存在一個(gè)安全序列 P2,P1,P3 P2,P1,P3 ，即只要系統(tǒng)按此序列分配，即只要系統(tǒng)按此序列分配資源，每個(gè)進(jìn)程都可以順利完成。資源，每個(gè)進(jìn)程都可以順利完成。第29頁(yè)/共63頁(yè)三、由安全狀態(tài)向不安全狀態(tài)的轉(zhuǎn)換三、由安全狀態(tài)向不安全狀態(tài)的轉(zhuǎn)換 當(dāng)系統(tǒng)不按照安全序列分配資源時(shí)，則系統(tǒng)可能當(dāng)系統(tǒng)不按照安全序列分配資源時(shí)，則系統(tǒng)可能由安全狀態(tài)進(jìn)入不安全狀態(tài)。由安全狀態(tài)進(jìn)入不安全狀態(tài)。進(jìn)程進(jìn)程最大需求最大需求 已分

21、配已分配可用可用P1P110105 53 3P2P24 42 2P3P39 92 2進(jìn)程進(jìn)程最大需求最大需求 已分配已分配 可用可用P1P110105 52 2P2P24 42 2P3P39 93 3T T0 0時(shí)刻安全狀態(tài)時(shí)刻安全狀態(tài)T T1 1時(shí)刻不安全狀態(tài)時(shí)刻不安全狀態(tài)第30頁(yè)/共63頁(yè)3.6.3 3.6.3 利用銀行家算法避免死鎖利用銀行家算法避免死鎖 最具有代表性的避免死鎖的算法，是最具有代表性的避免死鎖的算法，是DijkstraDijkstra的銀行家算法。這是由于該算法可的銀行家算法。這是由于該算法可能用于銀行現(xiàn)金貸款而得名的。一個(gè)銀行家能用于銀行現(xiàn)金貸款而得名的。一個(gè)銀行家把他

22、的固定資金貸給若干顧客。只要不出現(xiàn)把他的固定資金貸給若干顧客。只要不出現(xiàn)一個(gè)顧客借走所有資金后還不夠，銀行家的一個(gè)顧客借走所有資金后還不夠，銀行家的資金應(yīng)是安全的。銀行家需一個(gè)算法保證借資金應(yīng)是安全的。銀行家需一個(gè)算法保證借出去的資金在有限時(shí)間內(nèi)可收回。出去的資金在有限時(shí)間內(nèi)可收回。 第31頁(yè)/共63頁(yè)一、銀行家算法中的數(shù)據(jù)結(jié)構(gòu)一、銀行家算法中的數(shù)據(jù)結(jié)構(gòu)1 1可利用資源向量可利用資源向量AvailableAvailable 也稱(chēng)為空閑向量。這是一個(gè)含有也稱(chēng)為空閑向量。這是一個(gè)含有mm個(gè)元素的個(gè)元素的數(shù)組。其中的每一個(gè)元素，代表一類(lèi)可利用的數(shù)組。其中的每一個(gè)元素，代表一類(lèi)可利用的資源數(shù)目，其初始

23、值是系統(tǒng)中所配置的該類(lèi)全資源數(shù)目，其初始值是系統(tǒng)中所配置的該類(lèi)全部可用資源的數(shù)目。其數(shù)值隨該類(lèi)資源的分配部可用資源的數(shù)目。其數(shù)值隨該類(lèi)資源的分配和回收而動(dòng)態(tài)地改變。和回收而動(dòng)態(tài)地改變。 如果如果Availablej=KAvailablej=K，則表示系統(tǒng)中現(xiàn)有，則表示系統(tǒng)中現(xiàn)有 Rj Rj 類(lèi)資源類(lèi)資源 K K 個(gè)。個(gè)。 第32頁(yè)/共63頁(yè)2 2最大需求矩陣最大需求矩陣MaxMax 這是一個(gè)這是一個(gè)n nmm的矩陣，它定義了系統(tǒng)中的矩陣，它定義了系統(tǒng)中n n個(gè)個(gè)進(jìn)程中的每一個(gè)進(jìn)程對(duì)進(jìn)程中的每一個(gè)進(jìn)程對(duì)mm類(lèi)資源的最大需求。類(lèi)資源的最大需求。 如果如果Maxi,j=KMaxi,j=K，則表示第，

24、則表示第i i個(gè)進(jìn)程需要個(gè)進(jìn)程需要RjRj類(lèi)類(lèi)資源的最大數(shù)目為資源的最大數(shù)目為K K。3 3分配矩陣分配矩陣AllocationAllocation 也叫做占有矩陣。這也是一個(gè)也叫做占有矩陣。這也是一個(gè)n nmm的矩陣，的矩陣，它定義了系統(tǒng)中每一進(jìn)程已占有的每一類(lèi)資源數(shù)它定義了系統(tǒng)中每一進(jìn)程已占有的每一類(lèi)資源數(shù)。 如果如果Allocationi,j=KAllocationi,j=K，則表示第，則表示第i i個(gè)進(jìn)程當(dāng)個(gè)進(jìn)程當(dāng)前已分得前已分得R Rj j類(lèi)資源的數(shù)目為類(lèi)資源的數(shù)目為K K。第33頁(yè)/共63頁(yè)4 4需求矩陣需求矩陣NeedNeed 也叫做申請(qǐng)矩陣。這也是一個(gè)也叫做申請(qǐng)矩陣。這也是一個(gè)

25、n nmm的矩陣的矩陣，用以表示每一個(gè)進(jìn)程尚需的各類(lèi)資源數(shù)。，用以表示每一個(gè)進(jìn)程尚需的各類(lèi)資源數(shù)。 如果如果Needi,j=Needi,j=K K，則表示第，則表示第i i個(gè)進(jìn)程還需要個(gè)進(jìn)程還需要RjRj類(lèi)資源類(lèi)資源K K個(gè)，才能完成其任務(wù)。個(gè)，才能完成其任務(wù)。顯然，以上三個(gè)矩陣之間存在如下關(guān)系：顯然，以上三個(gè)矩陣之間存在如下關(guān)系：Needi,j = Maxi,j - Allocationi,j Needi,j = Maxi,j - Allocationi,j 第34頁(yè)/共63頁(yè)二、銀行家算法二、銀行家算法 設(shè)設(shè)RequestiRequesti是進(jìn)程是進(jìn)程PiPi的請(qǐng)求向量，如果的請(qǐng)求向量，如

26、果Requestij=KRequestij=K，表示進(jìn)程，表示進(jìn)程PiPi需要需要RjRj類(lèi)型的資源的個(gè)類(lèi)型的資源的個(gè)數(shù)為數(shù)為K K。這里要提及的是，。這里要提及的是，RequestiRequesti與與NeediNeedi的關(guān)的關(guān)系可能為以下三種情況：系可能為以下三種情況：（1 1）RequestiNeediRequestiNeedi：表示該進(jìn)程的資源需求表示該進(jìn)程的資源需求已超過(guò)它所宣布的最大值，因此認(rèn)為出錯(cuò)。已超過(guò)它所宣布的最大值，因此認(rèn)為出錯(cuò)。（2 2）Requesti=NeediRequesti=Needi：表示該進(jìn)程現(xiàn)在對(duì)它所表示該進(jìn)程現(xiàn)在對(duì)它所還需的全部資源一次申請(qǐng)完成。還需的全

27、部資源一次申請(qǐng)完成。（3 3）RequestiNeediRequestiNeedi：表示該進(jìn)程現(xiàn)在對(duì)它所表示該進(jìn)程現(xiàn)在對(duì)它所需資源再進(jìn)行部分的申請(qǐng)，剩余的資源以后可再次需資源再進(jìn)行部分的申請(qǐng)，剩余的資源以后可再次申請(qǐng)。申請(qǐng)。第35頁(yè)/共63頁(yè) 當(dāng)進(jìn)程當(dāng)進(jìn)程PiPi發(fā)出資源請(qǐng)求后，系統(tǒng)按下述步驟發(fā)出資源請(qǐng)求后，系統(tǒng)按下述步驟進(jìn)行檢查：進(jìn)行檢查：（1 1）如果）如果RequestiNeediRequestiNeedi，轉(zhuǎn)向步驟，轉(zhuǎn)向步驟(2)(2)；否則認(rèn)為出錯(cuò)，因?yàn)樗枰馁Y源數(shù)已超過(guò)否則認(rèn)為出錯(cuò)，因?yàn)樗枰馁Y源數(shù)已超過(guò)它所事先要求的最大值。它所事先要求的最大值。（2 2）如果）如果Req

28、uestiAvailableRequestiAvailable，轉(zhuǎn)向步驟，轉(zhuǎn)向步驟3 3；否則，表示尚無(wú)足夠資源，；否則，表示尚無(wú)足夠資源，PiPi須等待。須等待。第36頁(yè)/共63頁(yè)（3 3）假設(shè)系統(tǒng)將資源分配給）假設(shè)系統(tǒng)將資源分配給PiPi，則需修改如下，則需修改如下數(shù)據(jù)結(jié)構(gòu)的值：數(shù)據(jù)結(jié)構(gòu)的值：Available:= Available -Requesti;Available:= Available -Requesti;Allocationi:=Allocationi+Requesti;Allocationi:=Allocationi+Requesti;Needi:=Needi-Reques

29、ti;Needi:=Needi-Requesti;（4 4）系統(tǒng)執(zhí)行安全性算法，檢查若此次資源分）系統(tǒng)執(zhí)行安全性算法，檢查若此次資源分配后，系統(tǒng)是否處于安全狀態(tài)。如果是安全的，配后，系統(tǒng)是否處于安全狀態(tài)。如果是安全的，則將資源真正地分配給進(jìn)程則將資源真正地分配給進(jìn)程PiPi，否則，將本進(jìn)程，否則，將本進(jìn)程的試探分配作廢，恢復(fù)原來(lái)的資源分配狀態(tài)，進(jìn)的試探分配作廢，恢復(fù)原來(lái)的資源分配狀態(tài)，進(jìn)程程PiPi等待。等待。第37頁(yè)/共63頁(yè)三、安全性算法三、安全性算法 系統(tǒng)所執(zhí)行的安全性算法可描述如下：系統(tǒng)所執(zhí)行的安全性算法可描述如下：（1 1）設(shè)置兩個(gè)向量：）設(shè)置兩個(gè)向量： 工作向量工作向量WorkWo

30、rk。 它表示在算法執(zhí)行過(guò)程它表示在算法執(zhí)行過(guò)程中，系統(tǒng)可提供給進(jìn)程繼續(xù)運(yùn)行所需的各類(lèi)中，系統(tǒng)可提供給進(jìn)程繼續(xù)運(yùn)行所需的各類(lèi)資源數(shù)目，它含有資源數(shù)目，它含有mm個(gè)元素，在執(zhí)行安全算個(gè)元素，在執(zhí)行安全算法開(kāi)始時(shí)，初始置法開(kāi)始時(shí)，初始置Work:=AvailableWork:=Available。 完成向量完成向量FinishFinish。 它表示系統(tǒng)能否運(yùn)行它表示系統(tǒng)能否運(yùn)行完成。它有完成。它有n n個(gè)分量，分別表示系統(tǒng)是否有個(gè)分量，分別表示系統(tǒng)是否有足夠的資源分配給進(jìn)程，使之運(yùn)行完畢。足夠的資源分配給進(jìn)程，使之運(yùn)行完畢。 開(kāi)始時(shí)，開(kāi)始時(shí)，F(xiàn)inishi:=falseFinishi:=false

31、；當(dāng)有足夠資源；當(dāng)有足夠資源分配給進(jìn)程時(shí)，令分配給進(jìn)程時(shí)，令Finishi:=trueFinishi:=true。第38頁(yè)/共63頁(yè)（2 2）從進(jìn)程集合中找到一個(gè)能滿(mǎn)足下述條件）從進(jìn)程集合中找到一個(gè)能滿(mǎn)足下述條件的進(jìn)程的進(jìn)程i i：Finishi=false; Finishi=false; NeediWork NeediWork； 若找到這樣的進(jìn)程，執(zhí)行步驟（若找到這樣的進(jìn)程，執(zhí)行步驟（3 3）；）； 若找不到這樣的進(jìn)程，則轉(zhuǎn)步驟（若找不到這樣的進(jìn)程，則轉(zhuǎn)步驟（4 4）。）。（3 3）當(dāng)進(jìn)程）當(dāng)進(jìn)程PiPi獲得資源后，可順序執(zhí)行，直獲得資源后，可順序執(zhí)行，直至完成，并釋放出分配給它的資源，即執(zhí)

32、行：至完成，并釋放出分配給它的資源，即執(zhí)行：Work:= Work+AllocationiWork:= Work+Allocationi；Finishi:= trueFinishi:= true；Go to Go to 步驟（步驟（2 2）；）； 第39頁(yè)/共63頁(yè)（4 4）若所有進(jìn)程的）若所有進(jìn)程的Finishi=trueFinishi=true，則表示，則表示系統(tǒng)處于安全狀態(tài)，正式將資源分配給進(jìn)程系統(tǒng)處于安全狀態(tài)，正式將資源分配給進(jìn)程PiPi；否則，系統(tǒng)處于不安全狀態(tài)，系統(tǒng)不能；否則，系統(tǒng)處于不安全狀態(tài)，系統(tǒng)不能進(jìn)行這次試探性分配，恢復(fù)原來(lái)的資源分配進(jìn)行這次試探性分配，恢復(fù)原來(lái)的資源分配狀

33、態(tài)，讓進(jìn)程狀態(tài)，讓進(jìn)程PiPi等待。等待。第40頁(yè)/共63頁(yè)四、銀行家算法舉例四、銀行家算法舉例 假定系統(tǒng)中有五個(gè)進(jìn)程假定系統(tǒng)中有五個(gè)進(jìn)程P0, P1, P2, P3, P4P0, P1, P2, P3, P4和三類(lèi)資源和三類(lèi)資源A, B, CA, B, C，各種資源的數(shù)量分別為，各種資源的數(shù)量分別為1010、5 5、7 7，在，在T T0 0時(shí)刻的資源分配情況如下圖所示。時(shí)刻的資源分配情況如下圖所示。第41頁(yè)/共63頁(yè)(1)(1)T T0 0時(shí)刻的安全性：時(shí)刻的安全性： 在在T T0 0時(shí)刻存在安全序列時(shí)刻存在安全序列P1P1，P3P3，P4P4，P2P2，P0 ,P0 ,因此系統(tǒng)是目前處于

34、安全狀態(tài)。因此系統(tǒng)是目前處于安全狀態(tài)。第42頁(yè)/共63頁(yè)第43頁(yè)/共63頁(yè)圖 3-18 P1申請(qǐng)資源時(shí)的安全性檢查 由所進(jìn)行的安全性檢查得知，可以找到一由所進(jìn)行的安全性檢查得知，可以找到一個(gè)安全序列個(gè)安全序列 P P ，P P ，P P ，P P ，P P 。因此，系統(tǒng)。因此，系統(tǒng)是安全的，可以立即將是安全的，可以立即將P1P1所申請(qǐng)的資源分配給所申請(qǐng)的資源分配給它。它。第44頁(yè)/共63頁(yè)第45頁(yè)/共63頁(yè)第46頁(yè)/共63頁(yè)圖圖 3-19 為為P0分配資源后的有關(guān)資源數(shù)據(jù)分配資源后的有關(guān)資源數(shù)據(jù) 第47頁(yè)/共63頁(yè)請(qǐng)思考：請(qǐng)思考： 在銀行家算法中，把在銀行家算法中，把P P0 0發(fā)出的請(qǐng)求向發(fā)

35、出的請(qǐng)求向量改為量改為RequstRequst0 0(0(0，1 1，0)0)，系統(tǒng)是否能，系統(tǒng)是否能將資源分配給它？將資源分配給它？第48頁(yè)/共63頁(yè)3.7 3.7 死鎖的檢測(cè)與解除死鎖的檢測(cè)與解除 3.7.1 3.7.1 死鎖的檢測(cè)死鎖的檢測(cè) 1.1.資源分配圖資源分配圖(Resource Allocation Graph) (Resource Allocation Graph) 系統(tǒng)死鎖可利用資源分配圖來(lái)描述。系統(tǒng)死鎖可利用資源分配圖來(lái)描述。 該圖由一組結(jié)點(diǎn)該圖由一組結(jié)點(diǎn)N N和一組邊和一組邊E E所組成的一對(duì)所組成的一對(duì)偶偶G=G=（N N，E E）。）。 第49頁(yè)/共63頁(yè)（1 1）

36、N N是頂點(diǎn)的集合，它被分為兩個(gè)互斥的子集：是頂點(diǎn)的集合，它被分為兩個(gè)互斥的子集：進(jìn)程結(jié)點(diǎn)進(jìn)程結(jié)點(diǎn)P=P1P=P1，P2P2，PnPn；資源結(jié)點(diǎn)；資源結(jié)點(diǎn)R=r1R=r1，r2r2，rn rn 。(2) E(2) E是有向邊的集合。凡屬于是有向邊的集合。凡屬于E E中的一個(gè)邊中的一個(gè)邊eEeE，都連接著都連接著P P中的一個(gè)結(jié)點(diǎn)和中的一個(gè)結(jié)點(diǎn)和R R中的一個(gè)結(jié)點(diǎn)。中的一個(gè)結(jié)點(diǎn)。 e=pi, rje=pi, rj是資源請(qǐng)求邊，由進(jìn)程是資源請(qǐng)求邊，由進(jìn)程pipi指向資源指向資源rj rj， 表示進(jìn)程表示進(jìn)程pipi請(qǐng)求一個(gè)單位的請(qǐng)求一個(gè)單位的rj rj資源。資源。 e=rj, pie=rj, pi

37、是資源分配邊，由資源是資源分配邊，由資源rj rj指向進(jìn)程指向進(jìn)程pi, pi, 它表示把一個(gè)單位的資源它表示把一個(gè)單位的資源rj rj分配給進(jìn)程分配給進(jìn)程pipi。 第50頁(yè)/共63頁(yè)圖圖3-20 3-20 每類(lèi)資源有多個(gè)時(shí)的情況每類(lèi)資源有多個(gè)時(shí)的情況 P1P2r1r2P= P1,P2P= P1,P2R= r1,r2R= r1,r2N= P1,P2U r1,r2N= P1,P2U r1,r2E= (p1,r2),(p2,r1)E= (p1,r2),(p2,r1)， (r1,p1),(r1,p2)(r1,p1),(r1,p2)， (r2,p2)(r2,p2) 第51頁(yè)/共63頁(yè)資源分配圖的化簡(jiǎn)

38、方法：資源分配圖的化簡(jiǎn)方法：假設(shè)某個(gè)資源分配圖中存在一個(gè)進(jìn)程假設(shè)某個(gè)資源分配圖中存在一個(gè)進(jìn)程PiPi，此刻此刻PiPi是非封鎖進(jìn)程，對(duì)非封鎖進(jìn)程是非封鎖進(jìn)程，對(duì)非封鎖進(jìn)程PiPi的化簡(jiǎn)的化簡(jiǎn)即刪除資源分配圖中與即刪除資源分配圖中與PiPi連結(jié)的所有有向邊，連結(jié)的所有有向邊，使使PiPi變成孤立結(jié)點(diǎn)，重復(fù)上述過(guò)程直到不能化變成孤立結(jié)點(diǎn)，重復(fù)上述過(guò)程直到不能化簡(jiǎn)為止。簡(jiǎn)為止。二、二、 死鎖定理死鎖定理 第52頁(yè)/共63頁(yè) 首先，在圖首先，在圖3-21(a)3-21(a)中找到一個(gè)非封鎖進(jìn)中找到一個(gè)非封鎖進(jìn)程程P1P1，刪去其所有的有向邊，使之成為孤立結(jié)，刪去其所有的有向邊，使之成為孤立結(jié)點(diǎn)。點(diǎn)。

39、即讓即讓P1P1獲得所需的資源而繼續(xù)執(zhí)行，直到獲得所需的資源而繼續(xù)執(zhí)行，直到運(yùn)行完畢，再釋放期所占有的全部資源；得到運(yùn)行完畢，再釋放期所占有的全部資源；得到如圖如圖3-21(b)3-21(b)所示。所示。(b)P1P2(a)P1P2第53頁(yè)/共63頁(yè)(c)P1P2(b)P1P2 由于由于P1P1進(jìn)程釋放了進(jìn)程釋放了R1R1資源從而喚醒資源從而喚醒P2P2進(jìn)進(jìn)程，使程，使P2P2也變成了非封鎖進(jìn)程，然后我們繼也變成了非封鎖進(jìn)程，然后我們繼續(xù)化簡(jiǎn)續(xù)化簡(jiǎn)P2P2，刪去，刪去P2P2的所有有向邊，使的所有有向邊，使P2P2也成也成了孤立結(jié)點(diǎn)，如圖了孤立結(jié)點(diǎn)，如圖3-21(c)3-21(c)所示。所示。

40、 第54頁(yè)/共63頁(yè) 在進(jìn)行一系統(tǒng)的簡(jiǎn)化后，若能消去圖中所在進(jìn)行一系統(tǒng)的簡(jiǎn)化后，若能消去圖中所有的邊，使所有進(jìn)程都成為孤立結(jié)點(diǎn)，則稱(chēng)該有的邊，使所有進(jìn)程都成為孤立結(jié)點(diǎn)，則稱(chēng)該圖是可完全簡(jiǎn)化的；若不能通過(guò)任何過(guò)程使該圖是可完全簡(jiǎn)化的；若不能通過(guò)任何過(guò)程使該圖完全簡(jiǎn)化，則稱(chēng)該圖是不可完全簡(jiǎn)化的。圖完全簡(jiǎn)化，則稱(chēng)該圖是不可完全簡(jiǎn)化的。不可簡(jiǎn)化的資源分配圖不可簡(jiǎn)化的資源分配圖第55頁(yè)/共63頁(yè)通過(guò)資源分配圖，我們就可以很直觀地看通過(guò)資源分配圖，我們就可以很直觀地看出系統(tǒng)中的進(jìn)程使用資源的情況。很顯然，如出系統(tǒng)中的進(jìn)程使用資源的情況。很顯然，如果圖中不出現(xiàn)封閉的環(huán)路，則系統(tǒng)中不會(huì)存在果圖中不出現(xiàn)封閉的環(huán)

41、路，則系統(tǒng)中不會(huì)存在死鎖。死鎖。 但如果系統(tǒng)出現(xiàn)由各有向邊組成的環(huán)路，但如果系統(tǒng)出現(xiàn)由各有向邊組成的環(huán)路，則是否產(chǎn)生死鎖，還需進(jìn)一步分析：如果環(huán)路則是否產(chǎn)生死鎖，還需進(jìn)一步分析：如果環(huán)路可以通過(guò)化簡(jiǎn)的方式取消，則系統(tǒng)一定不產(chǎn)生可以通過(guò)化簡(jiǎn)的方式取消，則系統(tǒng)一定不產(chǎn)生死鎖；如果環(huán)路通過(guò)化簡(jiǎn)的方式仍不能取消，死鎖；如果環(huán)路通過(guò)化簡(jiǎn)的方式仍不能取消，即不能再進(jìn)行簡(jiǎn)化，則系統(tǒng)一定會(huì)產(chǎn)生死鎖。即不能再進(jìn)行簡(jiǎn)化，則系統(tǒng)一定會(huì)產(chǎn)生死鎖。這就是著名的死鎖定理。這就是著名的死鎖定理。第56頁(yè)/共63頁(yè)三、三、 死鎖檢測(cè)中的數(shù)據(jù)結(jié)構(gòu)死鎖檢測(cè)中的數(shù)據(jù)結(jié)構(gòu) (1) (1) 可利用資源向量可利用資源向量Availabl

42、eAvailable，它表示了，它表示了mm類(lèi)資類(lèi)資源中每一類(lèi)資源的可用數(shù)目。源中每一類(lèi)資源的可用數(shù)目。(2) (2) 把不占用資源的進(jìn)程把不占用資源的進(jìn)程( (向量向量Allocation=0)Allocation=0)記入記入L L表中，表中， 即即L Li iLL。(3) (3) 從進(jìn)程集合中找到一個(gè)從進(jìn)程集合中找到一個(gè)RequestRequesti iWorkWork的的進(jìn)程，做如下處理：進(jìn)程，做如下處理： 將其資源分配圖簡(jiǎn)化，釋放出資源，增加工將其資源分配圖簡(jiǎn)化，釋放出資源，增加工作向量作向量Work=Work+AllocationWork=Work+Allocationi i。 將

43、它記入將它記入L L表中。表中。 第57頁(yè)/共63頁(yè)(4) (4) 若不能把所有進(jìn)程都記入若不能把所有進(jìn)程都記入L L表中，表中， 便表明系便表明系統(tǒng)狀態(tài)統(tǒng)狀態(tài)S S的資源分配圖是不可完全簡(jiǎn)化的。的資源分配圖是不可完全簡(jiǎn)化的。 因因此，該系統(tǒng)狀態(tài)將發(fā)生死鎖。此，該系統(tǒng)狀態(tài)將發(fā)生死鎖。 第58頁(yè)/共63頁(yè)Work =Available; L =Li|Allocationi=0Requesti=0 for all Li L do begin for all RequestiWork do begin Work =Work+Allocationi; LiL; end end deadlock = (

44、L=p1, p2, , pn); 第59頁(yè)/共63頁(yè)3.7.2 3.7.2 死鎖的解除死鎖的解除 當(dāng)發(fā)現(xiàn)有進(jìn)程死鎖時(shí)，便應(yīng)立即把它們從死當(dāng)發(fā)現(xiàn)有進(jìn)程死鎖時(shí)，便應(yīng)立即把它們從死鎖狀態(tài)中解脫出來(lái)，常用的兩種方法是：鎖狀態(tài)中解脫出來(lái)，常用的兩種方法是：（1 1）剝奪資源。）剝奪資源。 從其它進(jìn)程剝奪足夠數(shù)量的資源給死鎖進(jìn)程，從其它進(jìn)程剝奪足夠數(shù)量的資源給死鎖進(jìn)程，以解除死鎖狀態(tài)。以解除死鎖狀態(tài)。（2 2）撤消進(jìn)程。）撤消進(jìn)程。 最簡(jiǎn)單的方法是：使全部死鎖進(jìn)程都夭折；最簡(jiǎn)單的方法是：使全部死鎖進(jìn)程都夭折； 另一種方法是：按照某種順序逐個(gè)地撤消進(jìn)程，另一種方法是：按照某種順序逐個(gè)地撤消進(jìn)程，直到有足夠的

45、資源可用，死鎖狀態(tài)消除為止。直到有足夠的資源可用，死鎖狀態(tài)消除為止。第60頁(yè)/共63頁(yè) 在出現(xiàn)死鎖時(shí)，可采用各種策略來(lái)撤消進(jìn)在出現(xiàn)死鎖時(shí)，可采用各種策略來(lái)撤消進(jìn)程。如撤消進(jìn)程所付出的代價(jià)最小。為把系統(tǒng)程。如撤消進(jìn)程所付出的代價(jià)最小。為把系統(tǒng)從死鎖狀態(tài)中解脫出來(lái)，所花費(fèi)的代價(jià)可表示從死鎖狀態(tài)中解脫出來(lái)，所花費(fèi)的代價(jià)可表示為：為： R(S)R(S)minmin=minC=minCuiui+minC+minCujuj+minC+minCukuk+ + 一個(gè)付出最小代價(jià)的方法如圖一個(gè)付出最小代價(jià)的方法如圖4-234-23所示。所示。第61頁(yè)/共63頁(yè)圖圖3-22 付出代價(jià)最小的死鎖解除方法付出代價(jià)最小

46、的死鎖解除方法 U1V12V13V1kW132W134W13kP2P3P2P4PkPkU2V21V22V2kW231W234W23kP1P4PkUkVk1Vk2VkkWk21Wk22Wk2kPkSP1(cu1)P1(cuk)P1(cud)第62頁(yè)/共63頁(yè)第63頁(yè)/共63頁(yè)第10頁(yè)/共63頁(yè)3.6 3.6 預(yù)防死鎖的方法預(yù)防死鎖的方法3.6.1 3.6.1 預(yù)防死鎖預(yù)防死鎖一、摒棄一、摒棄“請(qǐng)求和保持請(qǐng)求和保持”條件條件1 1、實(shí)現(xiàn)方法、實(shí)現(xiàn)方法 要求進(jìn)程一次性申請(qǐng)整個(gè)運(yùn)行進(jìn)程中的全部要求進(jìn)程一次性申請(qǐng)整個(gè)運(yùn)行進(jìn)程中的全部資源，只有申請(qǐng)到全部資源后，方可投入運(yùn)行；資源，只有申請(qǐng)到全部資源后，方可投入運(yùn)行；這樣進(jìn)程運(yùn)行期間不會(huì)再提出資源要求。這樣進(jìn)程運(yùn)行期間不會(huì)再提出資源要求。 只要有一種資源要求不能滿(mǎn)足，則全部其它只要