操作系統(tǒng)8--死鎖

1、8.8.8.1 1 1/38/38/38 202220222022年年年3 3 3月月月操作系統(tǒng)操作系統(tǒng)操作系統(tǒng)3.4 3.4 死鎖問(wèn)題死鎖問(wèn)題( (DEADLOCK) DEADLOCK) P103P103 3.4.1 3.4.1 概述概述3.4.2 3.4.2 死鎖的預(yù)防死鎖的預(yù)防3.4.3 3.4.3 死鎖的避免死鎖的避免3.4.4 3.4.4 死鎖的檢測(cè)死鎖的檢測(cè)3.4.5 3.4.5 死鎖的解除死鎖的解除8.8.8.2 2 2/38/38/38 202220222022年年年3 3 3月月月操作系統(tǒng)操作系統(tǒng)操作系統(tǒng)3.4.1 3.4.1 概述概述死鎖指多個(gè)進(jìn)程因競(jìng)爭(zhēng)資源而造成的一種僵局

2、，若無(wú)外力作死鎖指多個(gè)進(jìn)程因競(jìng)爭(zhēng)資源而造成的一種僵局，若無(wú)外力作用，這些進(jìn)程都將永遠(yuǎn)不能再向前推進(jìn)。用，這些進(jìn)程都將永遠(yuǎn)不能再向前推進(jìn)。1. 1. 死鎖發(fā)生原因死鎖發(fā)生原因（1 1）競(jìng)爭(zhēng)資源）競(jìng)爭(zhēng)資源（2 2）進(jìn)程推進(jìn)順序非法）進(jìn)程推進(jìn)順序非法8.8.8.3 3 3/38/38/38 202220222022年年年3 3 3月月月操作系統(tǒng)操作系統(tǒng)操作系統(tǒng)資源分類：資源分類：可剝奪資源可剝奪資源CPU、主存主存非剝奪資源非剝奪資源磁帶機(jī)、打印機(jī)磁帶機(jī)、打印機(jī)永久性資源永久性資源可順序重復(fù)使用的資源可順序重復(fù)使用的資源 如：打印機(jī)等如：打印機(jī)等臨時(shí)性資源臨時(shí)性資源可以動(dòng)態(tài)生成和消耗?？梢詣?dòng)態(tài)生成和

3、消耗。 如：硬件中斷、消息等如：硬件中斷、消息等(1) (1) 競(jìng)爭(zhēng)資源引起死鎖競(jìng)爭(zhēng)資源引起死鎖8.8.8.4 4 4/38/38/38 202220222022年年年3 3 3月月月操作系統(tǒng)操作系統(tǒng)操作系統(tǒng). Request(B); Request(A); Release(A); Release(B);P2P2. Request(A); Request(B); Release(B); Release(A);P1P1死鎖發(fā)生：雙方都擁有部分資源，同時(shí)在請(qǐng)求對(duì)方已死鎖發(fā)生：雙方都擁有部分資源，同時(shí)在請(qǐng)求對(duì)方已占有的資源。如次序：占有的資源。如次序：P1 P2 P1 P2P1 P2 P1 P2A.

4、A.競(jìng)爭(zhēng)非剝奪資源引起死鎖競(jìng)爭(zhēng)非剝奪資源引起死鎖8.8.8.5 5 5/38/38/38 202220222022年年年3 3 3月月月操作系統(tǒng)操作系統(tǒng)操作系統(tǒng). Receive(P1,Q); Send(P1,R);P2P2. Receive(P2,M); Send(P2,N);P1P1死鎖發(fā)生：雙方都等待對(duì)方去生成資源，死鎖發(fā)生：雙方都等待對(duì)方去生成資源，如次序：如次序：P1 P2P1 P2B.B.競(jìng)爭(zhēng)臨時(shí)性資源引起死鎖競(jìng)爭(zhēng)臨時(shí)性資源引起死鎖8.8.8.6 6 6/38/38/38 202220222022年年年3 3 3月月月操作系統(tǒng)操作系統(tǒng)操作系統(tǒng)詳見書詳見書 P104 P104 圖圖3

5、-13,3-13,圖圖3-3-1414P1R2P2R1P1PP2s2s3s1從資源出發(fā)的箭頭表示該資源已分配,如R1已分配給P1從進(jìn)程出發(fā)的箭頭表示進(jìn)程正在申請(qǐng)資源,如P1正申請(qǐng)R2S1P1:表示由P1產(chǎn)生的消息S1,即:S1隸屬于P1P1S2 表示由P1要求接收消息S2,S2是另一個(gè)進(jìn)程產(chǎn)生的。8.8.8.7 7 7/38/38/38 202220222022年年年3 3 3月月月操作系統(tǒng)操作系統(tǒng)操作系統(tǒng)(2)(2)進(jìn)程推進(jìn)順序不當(dāng)引起死鎖進(jìn)程推進(jìn)順序不當(dāng)引起死鎖ProcessQReleaseAReleaseBGet AGet BGet A Get BRelease ARelease BPr

6、ocess Pdeadlockinevitable123456P105 圖圖3-158.8.8.8 8 8/38/38/38 202220222022年年年3 3 3月月月操作系統(tǒng)操作系統(tǒng)操作系統(tǒng)2. 2. 死鎖發(fā)生條件死鎖發(fā)生條件死鎖的發(fā)生必須具備下列死鎖的發(fā)生必須具備下列4 4個(gè)必要條件：個(gè)必要條件：互斥：互斥：任一時(shí)刻只允許一個(gè)進(jìn)程使用資源任一時(shí)刻只允許一個(gè)進(jìn)程使用資源請(qǐng)求和保持：請(qǐng)求和保持：進(jìn)程在請(qǐng)求其余資源時(shí)，不主進(jìn)程在請(qǐng)求其余資源時(shí)，不主動(dòng)釋放已經(jīng)占用的資源動(dòng)釋放已經(jīng)占用的資源非剝奪：非剝奪：進(jìn)程已經(jīng)占用的資源，不會(huì)被強(qiáng)制進(jìn)程已經(jīng)占用的資源，不會(huì)被強(qiáng)制剝奪剝奪環(huán)路等待：環(huán)路等待：環(huán)

7、路中的每一條邊是進(jìn)程在請(qǐng)求環(huán)路中的每一條邊是進(jìn)程在請(qǐng)求另一進(jìn)程已經(jīng)占有的資源。另一進(jìn)程已經(jīng)占有的資源。8.8.8.9 9 9/38/38/38 202220222022年年年3 3 3月月月操作系統(tǒng)操作系統(tǒng)操作系統(tǒng)3. 3. 處理死鎖的基本方法處理死鎖的基本方法1.1. 預(yù)防死鎖預(yù)防死鎖：破壞四個(gè)必要條件中的一個(gè)或幾個(gè)條件；：破壞四個(gè)必要條件中的一個(gè)或幾個(gè)條件； 易于實(shí)現(xiàn)，但會(huì)導(dǎo)致資源利用率和系統(tǒng)吞吐量降低易于實(shí)現(xiàn)，但會(huì)導(dǎo)致資源利用率和系統(tǒng)吞吐量降低2.2. 避免死鎖避免死鎖：用某種方法在資源動(dòng)態(tài)分配過(guò)程中，防止：用某種方法在資源動(dòng)態(tài)分配過(guò)程中，防止系統(tǒng)進(jìn)入不安全狀態(tài)。系統(tǒng)進(jìn)入不安全狀態(tài)。 實(shí)

8、現(xiàn)有難度，但可獲得較高實(shí)現(xiàn)有難度，但可獲得較高的資源利用率和系統(tǒng)吞吐量。的資源利用率和系統(tǒng)吞吐量。3.3. 檢測(cè)死鎖檢測(cè)死鎖：允許死鎖發(fā)生。通過(guò)檢測(cè)機(jī)構(gòu)檢測(cè)，然后：允許死鎖發(fā)生。通過(guò)檢測(cè)機(jī)構(gòu)檢測(cè)，然后采取措施，清除死鎖。采取措施，清除死鎖。4.4. 解除死鎖解除死鎖：與檢測(cè)配套完成。常通過(guò)撤銷或掛起一些：與檢測(cè)配套完成。常通過(guò)撤銷或掛起一些進(jìn)程實(shí)現(xiàn)。進(jìn)程實(shí)現(xiàn)。8.8.8.101010/38/38/38 202220222022年年年3 3 3月月月操作系統(tǒng)操作系統(tǒng)操作系統(tǒng)3.4.2 3.4.2 死鎖的預(yù)防死鎖的預(yù)防預(yù)防是采用某種策略，預(yù)防是采用某種策略，限制限制并發(fā)進(jìn)程對(duì)資源的請(qǐng)求，使系并發(fā)進(jìn)

9、程對(duì)資源的請(qǐng)求，使系統(tǒng)在任何時(shí)刻都統(tǒng)在任何時(shí)刻都不滿足死鎖的必要條件不滿足死鎖的必要條件。預(yù)防死鎖的預(yù)防死鎖的3 3種策略：種策略：摒棄摒棄“請(qǐng)求和保持請(qǐng)求和保持”條件條件：要求所有進(jìn)程一：要求所有進(jìn)程一次性申請(qǐng)所需全部資源，保證不等待資源；次性申請(qǐng)所需全部資源，保證不等待資源；簡(jiǎn)單、易于實(shí)現(xiàn)，但：簡(jiǎn)單、易于實(shí)現(xiàn)，但：降低了對(duì)資源的利用率，降低進(jìn)程的并發(fā)降低了對(duì)資源的利用率，降低進(jìn)程的并發(fā)程度；程度；進(jìn)程延遲運(yùn)行；進(jìn)程延遲運(yùn)行；有可能無(wú)法預(yù)先知道所需資源；有可能無(wú)法預(yù)先知道所需資源；8.8.8.111111/38/38/38 202220222022年年年3 3 3月月月操作系統(tǒng)操作系統(tǒng)操作系

10、統(tǒng)對(duì)于已經(jīng)保持了某些資源的進(jìn)程，當(dāng)他再提出對(duì)于已經(jīng)保持了某些資源的進(jìn)程，當(dāng)他再提出新的資源要求而不能立即滿足時(shí)，必須釋放已保新的資源要求而不能立即滿足時(shí)，必須釋放已保持的所有資源，待以后需要時(shí)重新申請(qǐng)。持的所有資源，待以后需要時(shí)重新申請(qǐng)。摒棄摒棄“環(huán)路等待環(huán)路等待”條件條件：把資源分類按順序排列，所有進(jìn)程對(duì)資源的請(qǐng)把資源分類按順序排列，所有進(jìn)程對(duì)資源的請(qǐng)求必須嚴(yán)格按照資源序號(hào)遞增的次序提出，保證求必須嚴(yán)格按照資源序號(hào)遞增的次序提出，保證不形成環(huán)路；不形成環(huán)路；改善了資源利用率和系統(tǒng)吞吐量，但：改善了資源利用率和系統(tǒng)吞吐量，但： 1. 1. 限制了新設(shè)備類型的增加限制了新設(shè)備類型的增加 2. 2

11、. 進(jìn)程申請(qǐng)資源的順序很難與系統(tǒng)為資進(jìn)程申請(qǐng)資源的順序很難與系統(tǒng)為資源分配的序號(hào)總保持一致。源分配的序號(hào)總保持一致。 3. 3. 限制了用戶簡(jiǎn)單、自主的編程限制了用戶簡(jiǎn)單、自主的編程- -摒棄摒棄“不剝奪不剝奪”條件條件：8.8.8.121212/38/38/38 202220222022年年年3 3 3月月月操作系統(tǒng)操作系統(tǒng)操作系統(tǒng)3.4.3 3.4.3 死鎖的避免死鎖的避免用用預(yù)防死鎖預(yù)防死鎖的方法解決死鎖問(wèn)題，是通過(guò)增加了較強(qiáng)的方法解決死鎖問(wèn)題，是通過(guò)增加了較強(qiáng)的限制條件來(lái)完成的，實(shí)現(xiàn)簡(jiǎn)單，但嚴(yán)重?fù)p害了系統(tǒng)的限制條件來(lái)完成的，實(shí)現(xiàn)簡(jiǎn)單，但嚴(yán)重?fù)p害了系統(tǒng)的性能。的性能。避免死鎖避免死鎖來(lái)解

12、決死鎖問(wèn)題，可施加較弱的條件，獲得來(lái)解決死鎖問(wèn)題，可施加較弱的條件，獲得令人滿意的系統(tǒng)性能。令人滿意的系統(tǒng)性能。避免死鎖避免死鎖在系統(tǒng)運(yùn)行過(guò)程中，對(duì)進(jìn)程發(fā)出的每一個(gè)系在系統(tǒng)運(yùn)行過(guò)程中，對(duì)進(jìn)程發(fā)出的每一個(gè)系統(tǒng)能夠滿足的資源申請(qǐng)進(jìn)行動(dòng)態(tài)檢查，并根據(jù)檢查結(jié)統(tǒng)能夠滿足的資源申請(qǐng)進(jìn)行動(dòng)態(tài)檢查，并根據(jù)檢查結(jié)果決定是否分配資源，若分配后系統(tǒng)可能發(fā)生死鎖，果決定是否分配資源，若分配后系統(tǒng)可能發(fā)生死鎖，則不予分配，否則予以分配。則不予分配，否則予以分配。8.8.8.131313/38/38/38 202220222022年年年3 3 3月月月操作系統(tǒng)操作系統(tǒng)操作系統(tǒng)1.1.系統(tǒng)的安全狀態(tài)系統(tǒng)的安全狀態(tài)（見書（見

13、書107107） 如果系統(tǒng)能夠按照某種順序?yàn)槊總€(gè)進(jìn)程分配其所需資源，如果系統(tǒng)能夠按照某種順序?yàn)槊總€(gè)進(jìn)程分配其所需資源，直至最大需求，則當(dāng)前狀態(tài)為直至最大需求，則當(dāng)前狀態(tài)為安全狀態(tài)安全狀態(tài)。否則。否則 進(jìn)程推進(jìn)的順序稱為進(jìn)程推進(jìn)的順序稱為安全序列安全序列.可為資源分配提供借鑒：可為資源分配提供借鑒： 當(dāng)有進(jìn)程提出資源請(qǐng)求時(shí)，若分配后能夠安全，則執(zhí)當(dāng)有進(jìn)程提出資源請(qǐng)求時(shí)，若分配后能夠安全，則執(zhí)行資源分配。否則不予分配，將進(jìn)程阻塞行資源分配。否則不予分配，將進(jìn)程阻塞8.8.8.141414/38/38/38 202220222022年年年3 3 3月月月操作系統(tǒng)操作系統(tǒng)操作系統(tǒng)安全狀態(tài)舉例安全狀態(tài)舉

14、例進(jìn)程進(jìn)程最大需求最大需求 To時(shí)刻獲得資源狀態(tài)時(shí)刻獲得資源狀態(tài)(已分配已分配)可用可用P11053P242P392假定系統(tǒng)有三個(gè)進(jìn)程假定系統(tǒng)有三個(gè)進(jìn)程P1,P2,P3, 12臺(tái)磁帶機(jī)。臺(tái)磁帶機(jī)。1、當(dāng)前是否為安全狀態(tài)、當(dāng)前是否為安全狀態(tài)?2、若進(jìn)程、若進(jìn)程2提出提出2個(gè)資源需求是否可以分配？個(gè)資源需求是否可以分配？3、若進(jìn)程、若進(jìn)程3提出提出1個(gè)資源需求是否可以分配？個(gè)資源需求是否可以分配？是，是， P2，P1，P38.8.8.151515/38/38/38 202220222022年年年3 3 3月月月操作系統(tǒng)操作系統(tǒng)操作系統(tǒng)2.2.利用銀行家算法避免死鎖利用銀行家算法避免死鎖銀行家算法（

15、銀行家算法（Dijkstra, 1965）問(wèn)題問(wèn)題一個(gè)銀行家把他的固定資金（一個(gè)銀行家把他的固定資金（capitalcapital）貸給若干顧客。貸給若干顧客。只要不出現(xiàn)一個(gè)顧客借走所有資金后只要不出現(xiàn)一個(gè)顧客借走所有資金后還不夠還不夠，銀行，銀行家的資金應(yīng)是家的資金應(yīng)是安全安全的。銀行家需一個(gè)算法保證借出的。銀行家需一個(gè)算法保證借出去的資金在有限時(shí)間內(nèi)可收回。去的資金在有限時(shí)間內(nèi)可收回。具體步驟如下：v假定顧客分成若干次進(jìn)行；并在第一次借款時(shí)，能說(shuō)明他的最大借款額。v顧客的借款操作依次順序進(jìn)行，直到全部操作完成；v銀行家對(duì)當(dāng)前顧客的借款操作進(jìn)行判斷，以確定其安全性（能否支持顧客借款，直到全部

16、歸還）；v安全時(shí)，貸款；否則，暫不貸款。8.8.8.161616/38/38/38 202220222022年年年3 3 3月月月操作系統(tǒng)操作系統(tǒng)操作系統(tǒng)銀行家算法的實(shí)現(xiàn)：銀行家算法的實(shí)現(xiàn)：可利用資源向量可利用資源向量Available: m個(gè)元素的數(shù)組；個(gè)元素的數(shù)組；最大需求矩陣最大需求矩陣Max：n m矩陣；矩陣；分配矩陣分配矩陣Allocation: n m矩陣；矩陣；需求矩陣需求矩陣Need:n m矩陣；矩陣；設(shè)系統(tǒng)中有設(shè)系統(tǒng)中有n n個(gè)進(jìn)程，個(gè)進(jìn)程， m m種資源：種資源：三個(gè)矩陣間的關(guān)系：三個(gè)矩陣間的關(guān)系：Needi,j=Maxi,j-Allocationi,j算法中用到的數(shù)據(jù)結(jié)構(gòu)

17、：算法中用到的數(shù)據(jù)結(jié)構(gòu)：8.8.8.171717/38/38/38 202220222022年年年3 3 3月月月操作系統(tǒng)操作系統(tǒng)操作系統(tǒng)銀行家算法銀行家算法 P109P109 假設(shè)用假設(shè)用RequestRequesti ijj=k=k表示并發(fā)執(zhí)行時(shí)進(jìn)程表示并發(fā)執(zhí)行時(shí)進(jìn)程i i提出請(qǐng)求提出請(qǐng)求j j類類資源資源k k個(gè)個(gè)。系統(tǒng)按下述步驟進(jìn)行檢查：系統(tǒng)按下述步驟進(jìn)行檢查： (1) (1)如果如果RequestRequesti iNeedNeedi i則繼續(xù)以下檢查，否則顯示需求申請(qǐng)則繼續(xù)以下檢查，否則顯示需求申請(qǐng)超出最大需求值的錯(cuò)誤。超出最大需求值的錯(cuò)誤。 (2) (2)如果如果RequestR

18、equesti iAvailableAvailable則繼續(xù)以下檢查，否則顯示系則繼續(xù)以下檢查，否則顯示系統(tǒng)無(wú)足夠資源，統(tǒng)無(wú)足夠資源，P Pi i阻塞等待。阻塞等待。 (3) (3)系統(tǒng)試探把要求的資源分配給進(jìn)程系統(tǒng)試探把要求的資源分配給進(jìn)程i i并修改有關(guān)數(shù)據(jù)結(jié)構(gòu)并修改有關(guān)數(shù)據(jù)結(jié)構(gòu)的值：的值： Available=Available-Available=Available-RequestRequesti i； AllocationAllocationi i= =AllocationAllocationi i+Request+Requesti i； NeedNeedi i= =NeedNeed

19、i i-Request-Requesti i；(4)(4)系統(tǒng)執(zhí)行系統(tǒng)執(zhí)行安全性算法安全性算法，檢查此次資源分配后，系統(tǒng)是否處，檢查此次資源分配后，系統(tǒng)是否處于安全狀態(tài)，若安全，才正式將資源分配給進(jìn)程于安全狀態(tài)，若安全，才正式將資源分配給進(jìn)程i i，以完成本以完成本次分配；否則將試探分配作廢，恢復(fù)原來(lái)的資源分配狀態(tài)，讓次分配；否則將試探分配作廢，恢復(fù)原來(lái)的資源分配狀態(tài)，讓進(jìn)程進(jìn)程P Pi i等待。等待。8.8.8.181818/38/38/38 202220222022年年年3 3 3月月月操作系統(tǒng)操作系統(tǒng)操作系統(tǒng)安全性算法安全性算法: :安全性算法執(zhí)行步驟如下：安全性算法執(zhí)行步驟如下： A.

20、A.初始化設(shè)置工作向量初始化設(shè)置工作向量WorkmWorkm表示系統(tǒng)可提供的各類資源數(shù)目，表示系統(tǒng)可提供的各類資源數(shù)目，用以保護(hù)原數(shù)據(jù)結(jié)構(gòu)有關(guān)值。用以保護(hù)原數(shù)據(jù)結(jié)構(gòu)有關(guān)值。Work = AvailableWork = Available；設(shè)置完成標(biāo)志向量設(shè)置完成標(biāo)志向量 FinishnFinishn。Finishi = false Finishi = false 表示進(jìn)程表示進(jìn)程i i尚尚末完成，如值為末完成，如值為truetrue則表示進(jìn)程則表示進(jìn)程i i已完成已完成( (可以順利推進(jìn)可以順利推進(jìn)) )。 B. B.從進(jìn)程集合從進(jìn)程集合n n中找到一個(gè)能滿足下述二個(gè)條件中找到一個(gè)能滿足下述二

21、個(gè)條件: : Finishi = falseFinishi = false和和NecdNecdi iWorkWork，如找到則執(zhí)行步驟如找到則執(zhí)行步驟C C，如找不如找不到同時(shí)滿足以上二條件的進(jìn)程則執(zhí)行步驟到同時(shí)滿足以上二條件的進(jìn)程則執(zhí)行步驟D D。 C. C.當(dāng)進(jìn)程當(dāng)進(jìn)程i i獲得資源后可順利執(zhí)行直到完成，并釋放出分配給它獲得資源后可順利執(zhí)行直到完成，并釋放出分配給它的資源，表示如下：的資源，表示如下： work = work = work+Allocationwork+Allocationi i ； Finishi=true Finishi=true ；轉(zhuǎn)執(zhí)行步驟轉(zhuǎn)執(zhí)行步驟B B。 D.

22、D.如果所有的如果所有的FinishiFinishitruetrue，則表示系統(tǒng)處于安全狀態(tài)，否，則表示系統(tǒng)處于安全狀態(tài)，否則系統(tǒng)處于不安全狀態(tài)。則系統(tǒng)處于不安全狀態(tài)。8.8.8.191919/38/38/38 202220222022年年年3 3 3月月月操作系統(tǒng)操作系統(tǒng)操作系統(tǒng)銀行家算法例：銀行家算法例：P110P110 假定系統(tǒng)中有五個(gè)進(jìn)程假定系統(tǒng)中有五個(gè)進(jìn)程 P P0 0、P P1 1、P P2 2、P P3 3、P P4 4 和三種類型資源和三種類型資源 A A、B B、CC，每一種資源的數(shù)量分別為每一種資源的數(shù)量分別為1010、5 5、7 7。各進(jìn)程的最大需。各進(jìn)程的最大需求、求、

23、T T0 0時(shí)刻資源分配情況如下所示。時(shí)刻資源分配情況如下所示。試問(wèn)：試問(wèn)： 1. 1.T T0 0時(shí)刻是否安全？時(shí)刻是否安全？ 2. 2.P P1 1請(qǐng)求資源請(qǐng)求資源RequestRequest1 1(1,0,2)(1,0,2)是否允許？是否允許？ 3. 3.P P4 4請(qǐng)求資源請(qǐng)求資源RequestRequest4 4(3,3,0)(3,3,0)是否允許？是否允許？ 4. 4.P P0 0請(qǐng)求資源請(qǐng)求資源Request(0,2,0)Request(0,2,0)是否允許？是否允許？MaxMax A B CAllocation A B CNeed A B CAvailableA B CP0 P

24、1 P2 P3 P47 5 3 3 2 29 0 2 2 2 2 4 3 30 1 02 0 0 3 0 2 2 1 1 0 0 2 7 4 31 2 26 0 0 0 1 1 4 3 13 3 28.8.8.202020/38/38/38 202220222022年年年3 3 3月月月操作系統(tǒng)操作系統(tǒng)操作系統(tǒng)3 3 27 4 3 1 2 26 0 00 1 14 3 10 1 02 0 03 0 22 1 10 0 27 5 33 2 29 0 2 2 2 24 3 3 P0 P1 P2 P3 P4AvailableA B CNeedA B C AllocationA B C Max A B

25、 C 資源情況進(jìn)程T0時(shí)刻的資源分配表 falsefalsefalsefalsefalse0 1 02 0 03 0 22 1 10 0 27 4 31 2 26 0 00 1 14 3 1P0P1P2P3P4FinishWork+AllocationA B CAllocation A B CNeed A B CWork A B C 資源情況進(jìn)程T0時(shí)刻的安全序列1、T0時(shí)刻的安全性時(shí)刻的安全性13 3 25 3 225 3 27 4 337 4 37 5 3truetruetrue47 5 310 5 5true510 5 510 5 7trueP1 P3 P0 P2 P48.8.8.212

26、121/38/38/38 202220222022年年年3 3 3月月月操作系統(tǒng)操作系統(tǒng)操作系統(tǒng)3 3 27 4 3 1 2 26 0 00 1 14 3 10 1 02 0 03 0 22 1 10 0 27 5 33 2 29 0 2 2 2 24 3 3 P0 P1 P2 P3 P4AvailableA B CNeedA B C AllocationA B C Max A B C 資源情況進(jìn)程T0時(shí)刻的資源分配表 True True True True True 5 3 2 7 4 3 7 4 5 10 4 7 10 5 7 2 0 0 2 1 1 0 0 2 3 0 2 0 1 0 1

27、 2 2 0 1 1 4 3 1 6 0 0 7 4 3 3 3 2 5 3 2 7 4 3 7 4 5 10 4 7P1P3P4P2P0FinishWork+Allocation A B CAllocation A B CNeed A B CWork A B C 資源情況進(jìn)程T0時(shí)刻的另時(shí)刻的另一個(gè)安全序一個(gè)安全序列列1、T0時(shí)刻的安全性（時(shí)刻的安全性（2）8.8.8.222222/38/38/38 202220222022年年年3 3 3月月月操作系統(tǒng)操作系統(tǒng)操作系統(tǒng)P1P1發(fā)出請(qǐng)求向量發(fā)出請(qǐng)求向量Request(1,0,2),Request(1,0,2),系統(tǒng)按銀行家算法進(jìn)行檢查：系統(tǒng)按

28、銀行家算法進(jìn)行檢查：2、 P1請(qǐng)求資源請(qǐng)求資源發(fā)現(xiàn)可以發(fā)現(xiàn)可以找到找到一個(gè)安全序列一個(gè)安全序列 P1P1，P3P3，P4P4，P0P0，P2P2，因此系統(tǒng)因此系統(tǒng)是安全的，可以立即將是安全的，可以立即將P1P1所申請(qǐng)的資源分配給它。所申請(qǐng)的資源分配給它。 （1 1）Request1(1,0,2)Request1(1,0,2)Need(1,2,2)Need(1,2,2) （2 2）Request1(1,0,2) AvailableRequest1(1,0,2) Available(3,3,2)(3,3,2) （3 3）系統(tǒng)假定可為）系統(tǒng)假定可為P1P1分配資源，并修改分配資源，并修改Availa

29、ble,Allocation1Available,Allocation1和和NeedNeed向量。向量。 （4 4）檢查檢查此時(shí)系統(tǒng)是否安全。此時(shí)系統(tǒng)是否安全。8.8.8.232323/38/38/38 202220222022年年年3 3 3月月月操作系統(tǒng)操作系統(tǒng)操作系統(tǒng)P4P4發(fā)出請(qǐng)求向量發(fā)出請(qǐng)求向量Request4(3,3,0),Request4(3,3,0),系統(tǒng)按銀行系統(tǒng)按銀行家算法進(jìn)行檢查：家算法進(jìn)行檢查：（1 1）Request4(3,3,0)Request4(3,3,0)Need4(4,3,1)Need4(4,3,1)（2 2）Request4(3,3,0)Available(

30、2,3,0),Request4(3,3,0)Available(2,3,0),讓讓P4P4等待。等待。3、P4請(qǐng)求資源請(qǐng)求資源8.8.8.242424/38/38/38 202220222022年年年3 3 3月月月操作系統(tǒng)操作系統(tǒng)操作系統(tǒng)P0P0發(fā)出請(qǐng)求向量發(fā)出請(qǐng)求向量Request0(0,2,0),Request0(0,2,0),系統(tǒng)按銀行家算法進(jìn)行檢查：系統(tǒng)按銀行家算法進(jìn)行檢查：2 1 02 1 07 2 37 2 30 2 00 2 06 0 0 6 0 0 0 1 10 1 14 3 14 3 10 3 00 3 03 0 23 0 23 0 23 0 22 1 12 1 10 0

31、20 0 2 P0P0 P1 P1 P2 P2 P3 P3 P4 P4AvaiableAvaiableA B CA B C NeedNeedA B CA B CAllocationAllocationA B CA B C 資源情況資源情況進(jìn)程進(jìn)程為為P0P0分配資源后的有關(guān)分配資源后的有關(guān)資源數(shù)據(jù)資源數(shù)據(jù)4 4、P0P0請(qǐng)求資源請(qǐng)求資源（1 1）Request0(0,2,0)Request0(0,2,0)Need0(7,4,3)Need0(7,4,3)（2 2）Request0(0,2,0) Available(2,3,0)Request0(0,2,0) Available(2,3,0)（3

32、3）系統(tǒng)暫時(shí)假定可為系統(tǒng)暫時(shí)假定可為P0P0分配資源，并修改有關(guān)數(shù)據(jù)，下表所示。分配資源，并修改有關(guān)數(shù)據(jù)，下表所示。（4 4）進(jìn)行安全性檢查，發(fā)現(xiàn)可用資源）進(jìn)行安全性檢查，發(fā)現(xiàn)可用資源AvailableAvailable(2,1,0)(2,1,0)已不能滿足任何進(jìn)已不能滿足任何進(jìn)程的需要，故進(jìn)程進(jìn)入不安全狀態(tài)，程的需要，故進(jìn)程進(jìn)入不安全狀態(tài)，此時(shí)系統(tǒng)不分配資源給該進(jìn)程此時(shí)系統(tǒng)不分配資源給該進(jìn)程。8.8.8.252525/38/38/38 202220222022年年年3 3 3月月月操作系統(tǒng)操作系統(tǒng)操作系統(tǒng)練練 習(xí)習(xí) 如果將如果將P0P0的請(qǐng)求的請(qǐng)求(0,2,0)(0,2,0)改為改為(0,1

33、,0),(0,1,0),系統(tǒng)能否系統(tǒng)能否講資源分配給它？講資源分配給它？8.8.8.262626/38/38/38 202220222022年年年3 3 3月月月操作系統(tǒng)操作系統(tǒng)操作系統(tǒng)3.4.4 3.4.4 死鎖的檢測(cè)死鎖的檢測(cè)進(jìn)行死鎖檢測(cè)：必須進(jìn)行死鎖檢測(cè)：必須1.1.保存資源的請(qǐng)求和分配信息保存資源的請(qǐng)求和分配信息; ;2.2.利用某種算法對(duì)這些信息加以檢查，以利用某種算法對(duì)這些信息加以檢查，以判斷是否存在死鎖。判斷是否存在死鎖。8.8.8.272727/38/38/38 202220222022年年年3 3 3月月月操作系統(tǒng)操作系統(tǒng)操作系統(tǒng)1.1.資源分配圖資源分配圖( (resour

34、ce allocation graph)resource allocation graph)用于描述系統(tǒng)的死鎖用于描述系統(tǒng)的死鎖是一個(gè)有向圖是一個(gè)有向圖G G；結(jié)點(diǎn)結(jié)點(diǎn): :為資源或進(jìn)程，為資源或進(jìn)程，邊邊: : 從資源從資源R R到進(jìn)程到進(jìn)程P P的邊表示的邊表示R R已分配給已分配給P P，從進(jìn)程從進(jìn)程P P到資源到資源R R的邊表示的邊表示P P正因請(qǐng)求正因請(qǐng)求R R而處于等而處于等待狀態(tài)。待狀態(tài)。有向圖的有向圖的循環(huán)循環(huán)是死鎖存在的必要條件是死鎖存在的必要條件8.8.8.282828/38/38/38 202220222022年年年3 3 3月月月操作系統(tǒng)操作系統(tǒng)操作系統(tǒng)有環(huán)有死鎖有環(huán)

35、有死鎖8.8.8.292929/38/38/38 202220222022年年年3 3 3月月月操作系統(tǒng)操作系統(tǒng)操作系統(tǒng)有環(huán)無(wú)死鎖有環(huán)無(wú)死鎖8.8.8.303030/38/38/38 202220222022年年年3 3 3月月月操作系統(tǒng)操作系統(tǒng)操作系統(tǒng)2.2.死鎖定理死鎖定理當(dāng)且僅當(dāng)當(dāng)且僅當(dāng)S S狀態(tài)的資源分配圖是狀態(tài)的資源分配圖是不可完全簡(jiǎn)化不可完全簡(jiǎn)化的，稱的，稱S S為死鎖狀態(tài)為死鎖狀態(tài). .該充分條件稱為該充分條件稱為死鎖定理死鎖定理。其中的有邊進(jìn)程就是其中的有邊進(jìn)程就是死鎖進(jìn)程死鎖進(jìn)程。8.8.8.313131/38/38/38 202220222022年年年3 3 3月月月操作系

36、統(tǒng)操作系統(tǒng)操作系統(tǒng)死鎖檢測(cè)的計(jì)算機(jī)實(shí)現(xiàn)死鎖檢測(cè)的計(jì)算機(jī)實(shí)現(xiàn) P1131 1、教材、教材P113P113方法；方法；2 2、上述方法難于實(shí)現(xiàn)：、上述方法難于實(shí)現(xiàn)： 通常的方法是程序員的經(jīng)驗(yàn)，如通常的方法是程序員的經(jīng)驗(yàn)，如UNIXUNIX系統(tǒng)中，可考系統(tǒng)中，可考察進(jìn)程的運(yùn)行時(shí)間。在察進(jìn)程的運(yùn)行時(shí)間。在UNIXUNIX系統(tǒng)中有命令系統(tǒng)中有命令PSPS可顯示進(jìn)程可顯示進(jìn)程占用占用CPUCPU的時(shí)間，若發(fā)現(xiàn)有一組進(jìn)程在一段時(shí)間內(nèi)沒(méi)有的時(shí)間，若發(fā)現(xiàn)有一組進(jìn)程在一段時(shí)間內(nèi)沒(méi)有占用占用CPUCPU，就認(rèn)為這類進(jìn)程出現(xiàn)了死鎖。，就認(rèn)為這類進(jìn)程出現(xiàn)了死鎖。8.8.8.323232/38/38/38 2022202

37、22022年年年3 3 3月月月操作系統(tǒng)操作系統(tǒng)操作系統(tǒng)3.4.5 3.4.5 死鎖的解除死鎖的解除重新啟動(dòng)重新啟動(dòng)進(jìn)程回退進(jìn)程回退回滾每個(gè)死鎖進(jìn)程到前一個(gè)檢查點(diǎn)，重新執(zhí)行每個(gè)進(jìn)程?；貪L每個(gè)死鎖進(jìn)程到前一個(gè)檢查點(diǎn)，重新執(zhí)行每個(gè)進(jìn)程。撤銷死鎖進(jìn)程撤銷死鎖進(jìn)程全部撤銷；全部撤銷；按照某種原則逐個(gè)選擇死鎖進(jìn)程進(jìn)行撤消，直到解除系統(tǒng)死鎖按照某種原則逐個(gè)選擇死鎖進(jìn)程進(jìn)行撤消，直到解除系統(tǒng)死鎖選擇原則：選擇原則：一般選擇系統(tǒng)付出代價(jià)最小的進(jìn)程，即：一般選擇系統(tǒng)付出代價(jià)最小的進(jìn)程，即：花費(fèi)處理機(jī)的時(shí)間最少、輸出最少、估計(jì)未執(zhí)行部分最多、花費(fèi)處理機(jī)的時(shí)間最少、輸出最少、估計(jì)未執(zhí)行部分最多、已分配的資源量最少、

38、優(yōu)先級(jí)最低已分配的資源量最少、優(yōu)先級(jí)最低 剝奪資源剝奪資源按照某種原則逐個(gè)剝奪進(jìn)程資源，直到解除死鎖。按照某種原則逐個(gè)剝奪進(jìn)程資源，直到解除死鎖。8.8.8.333333/38/38/38 202220222022年年年3 3 3月月月操作系統(tǒng)操作系統(tǒng)操作系統(tǒng)課后練習(xí)課后練習(xí)系統(tǒng)可供用戶使用的內(nèi)存共系統(tǒng)可供用戶使用的內(nèi)存共150MB150MB，目前分配給，目前分配給3 3個(gè)進(jìn)程的數(shù)量個(gè)進(jìn)程的數(shù)量如下表所示。這時(shí)，第個(gè)如下表所示。這時(shí)，第個(gè)4 4進(jìn)程產(chǎn)生，它最終需要內(nèi)存進(jìn)程產(chǎn)生，它最終需要內(nèi)存60MB60MB，目，目前的申請(qǐng)數(shù)為前的申請(qǐng)數(shù)為25MB25MB。應(yīng)用關(guān)于死鎖問(wèn)題的銀行家算法，回答是。應(yīng)用關(guān)于死鎖問(wèn)題的銀行家算法，回答是否可以分配給第否可以分配給第4 4個(gè)進(jìn)程個(gè)進(jìn)程25MB25MB內(nèi)存，