操作系統(tǒng)課件os10死鎖

1、3.4 死鎖問(wèn)題(DEADLOCK) P103 3.4.1 概述3.4.2 死鎖的預(yù)防3.4.3 死鎖的避免3.4.4 死鎖的檢測(cè)3.4.5 死鎖的解除3.4.1 概述死鎖指多個(gè)進(jìn)程因競(jìng)爭(zhēng)資源而造成的一種僵局，若無(wú)外力作用，這些進(jìn)程都將永遠(yuǎn)不能再向前推進(jìn)。1. 死鎖發(fā)生原因（1）競(jìng)爭(zhēng)資源（2）進(jìn)程推進(jìn)順序非法資源分類：可剝奪資源CPU、主存非剝奪資源磁帶機(jī)、打印機(jī)永久性資源可順序重復(fù)使用的資源 如：打印機(jī)等臨時(shí)性資源可以動(dòng)態(tài)生成和消耗。 如：硬件中斷、消息等(1) 競(jìng)爭(zhēng)資源引起死鎖. Request(B); Request(A); Release(A); Release(B);P2. Requ

2、est(A); Request(B); Release(B); Release(A);P1死鎖發(fā)生：雙方都擁有部分資源，同時(shí)在請(qǐng)求對(duì)方已占有的資源。如次序：P1 P2 P1 P2A.競(jìng)爭(zhēng)非剝奪資源引起死鎖. Receive(P1,Q); Send(P1,R);P2. Receive(P2,M); Send(P2,N);P1死鎖發(fā)生：雙方都等待對(duì)方去生成資源，如次序：P1 P2B.競(jìng)爭(zhēng)臨時(shí)性資源引起死鎖詳見(jiàn)書(shū) P104 圖3-13,圖3-14P1R2P2R1P1PP2s2s3s1從資源出發(fā)的箭頭表示該資源已分配,如R1已分配給P1從進(jìn)程出發(fā)的箭頭表示進(jìn)程正在申請(qǐng)資源,如P1正申請(qǐng)R2S1P1:表

3、示由P1產(chǎn)生的消息S1,即:S1隸屬于P1P1S2 表示由P1要求接收消息S2,S2是另一個(gè)進(jìn)程產(chǎn)生的。(2)進(jìn)程推進(jìn)順序不當(dāng)引起死鎖ProcessQReleaseAReleaseBGet AGet BGet AGet BRelease ARelease BProcess Pdeadlockinevitable123456P105 圖3-152. 死鎖發(fā)生條件死鎖的發(fā)生必須具備下列4個(gè)必要條件：互斥：任一時(shí)刻只允許一個(gè)進(jìn)程使用資源請(qǐng)求和保持：進(jìn)程在請(qǐng)求其余資源時(shí)，不主動(dòng)釋放已經(jīng)占用的資源非剝奪：進(jìn)程已經(jīng)占用的資源，不會(huì)被強(qiáng)制剝奪環(huán)路等待：環(huán)路中的每一條邊是進(jìn)程在請(qǐng)求另一進(jìn)程已經(jīng)占有的資源。3.

4、 處理死鎖的基本方法預(yù)防死鎖：破壞四個(gè)必要條件中的一個(gè)或幾個(gè)條件； 易于實(shí)現(xiàn)，但會(huì)導(dǎo)致資源利用率和系統(tǒng)吞吐量降低避免死鎖：用某種方法在資源動(dòng)態(tài)分配過(guò)程中，防止系統(tǒng)進(jìn)入不安全狀態(tài)。實(shí)現(xiàn)有難度，但可獲得較高的資源利用率和系統(tǒng)吞吐量。檢測(cè)死鎖：允許死鎖發(fā)生。通過(guò)檢測(cè)機(jī)構(gòu)檢測(cè)，然后采取措施，清除死鎖。解除死鎖：與檢測(cè)配套完成。常通過(guò)撤銷或掛起一些進(jìn)程實(shí)現(xiàn)。3.4.2 死鎖的預(yù)防預(yù)防是采用某種策略，限制并發(fā)進(jìn)程對(duì)資源的請(qǐng)求，使系統(tǒng)在任何時(shí)刻都不滿足死鎖的必要條件。預(yù)防死鎖的3種策略：摒棄“請(qǐng)求和保持”條件：要求所有進(jìn)程一次性申請(qǐng)所需全部資源，保證不等待資源；簡(jiǎn)單、易于實(shí)現(xiàn)，但：降低了對(duì)資源的利用率，降低

5、進(jìn)程的并發(fā)程度；進(jìn)程延遲運(yùn)行；有可能無(wú)法預(yù)先知道所需資源；對(duì)于已經(jīng)保持了某些資源的進(jìn)程，當(dāng)他再提出新的資源要求而不能立即滿足時(shí)，必須釋放已保持的所有資源，待以后需要時(shí)重新申請(qǐng)。摒棄“環(huán)路等待”條件：把資源分類按順序排列，所有進(jìn)程對(duì)資源的請(qǐng)求必須嚴(yán)格按照資源序號(hào)遞增的次序提出，保證不形成環(huán)路；改善了資源利用率和系統(tǒng)吞吐量，但： 1. 限制了新設(shè)備類型的增加 2. 進(jìn)程申請(qǐng)資源的順序很難與系統(tǒng)為資源分配的序號(hào)總保持一致。 3. 限制了用戶簡(jiǎn)單、自主的編程-摒棄“不剝奪”條件：3.4.3 死鎖的避免用預(yù)防死鎖的方法解決死鎖問(wèn)題，是通過(guò)增加了較強(qiáng)的限制條件來(lái)完成的，實(shí)現(xiàn)簡(jiǎn)單，但嚴(yán)重?fù)p害了系統(tǒng)的性能。避

6、免死鎖來(lái)解決死鎖問(wèn)題，可施加較弱的條件，獲得令人滿意的系統(tǒng)性能。避免死鎖在系統(tǒng)運(yùn)行過(guò)程中，對(duì)進(jìn)程發(fā)出的每一個(gè)系統(tǒng)能夠滿足的資源申請(qǐng)進(jìn)行動(dòng)態(tài)檢查，并根據(jù)檢查結(jié)果決定是否分配資源，若分配后系統(tǒng)可能發(fā)生死鎖，則不予分配，否則予以分配。1.系統(tǒng)的安全狀態(tài)（見(jiàn)書(shū)107） 如果系統(tǒng)能夠按照某種順序?yàn)槊總€(gè)進(jìn)程分配其所需資源，直至最大需求，則當(dāng)前狀態(tài)為安全狀態(tài)。否則 進(jìn)程推進(jìn)的順序稱為安全序列.可為資源分配提供借鑒： 當(dāng)有進(jìn)程提出資源請(qǐng)求時(shí)，若分配后能夠安全，則執(zhí)行資源分配。否則不予分配，將進(jìn)程阻塞安全狀態(tài)舉例進(jìn)程最大需求To時(shí)刻獲得資源狀態(tài)(已分配)可用P11053P242P392假定系統(tǒng)有三個(gè)進(jìn)程P1,P

7、2,P3, 12臺(tái)磁帶機(jī)。1、當(dāng)前是否為安全狀態(tài)?2、若進(jìn)程2提出2個(gè)資源需求是否可以分配？3、若進(jìn)程3提出1個(gè)資源需求是否可以分配？是， P2，P1，P32.利用銀行家算法避免死鎖銀行家算法（Dijkstra, 1965）問(wèn)題一個(gè)銀行家把他的固定資金（capital）貸給若干顧客。只要不出現(xiàn)一個(gè)顧客借走所有資金后還不夠，銀行家的資金應(yīng)是安全的。銀行家需一個(gè)算法保證借出去的資金在有限時(shí)間內(nèi)可收回。具體步驟如下：假定顧客分成若干次進(jìn)行；并在第一次借款時(shí)，能說(shuō)明他的最大借款額。顧客的借款操作依次順序進(jìn)行，直到全部操作完成；銀行家對(duì)當(dāng)前顧客的借款操作進(jìn)行判斷，以確定其安全性（能否支持顧客借款，直到全

8、部歸還）；安全時(shí)，貸款；否則，暫不貸款。銀行家算法的實(shí)現(xiàn)：可利用資源向量Available: m個(gè)元素的數(shù)組；最大需求矩陣Max：n m矩陣；分配矩陣Allocation: nm矩陣；需求矩陣Need:n m矩陣；設(shè)系統(tǒng)中有n個(gè)進(jìn)程， m種資源：三個(gè)矩陣間的關(guān)系：Needi,j=Maxi,j-Allocationi,j算法中用到的數(shù)據(jù)結(jié)構(gòu)：銀行家算法 P109 假設(shè)用Requestij=k表示并發(fā)執(zhí)行時(shí)進(jìn)程i提出請(qǐng)求j類資源k個(gè)。系統(tǒng)按下述步驟進(jìn)行檢查： (1)如果RequestiNeedi則繼續(xù)以下檢查，否則顯示需求申請(qǐng)超出最大需求值的錯(cuò)誤。 (2)如果RequestiAvailable則繼

9、續(xù)以下檢查，否則顯示系統(tǒng)無(wú)足夠資源，Pi阻塞等待。 (3)系統(tǒng)試探性的把要求的資源分配給進(jìn)程i并修改有關(guān)數(shù)據(jù)結(jié)構(gòu)的值： Available=Available-Requesti； Allocationi=Allocationi+Requesti； Needi=Needi-Requesti；(4)系統(tǒng)執(zhí)行安全性算法，檢查此次資源分配后，系統(tǒng)是否處于安全狀態(tài)，若安全，才正式將資源分配給進(jìn)程i，以完成本次分配；否則將試探分配作廢，恢復(fù)原來(lái)的資源分配狀態(tài)，讓進(jìn)程Pi等待。安全性算法:安全性算法執(zhí)行步驟如下： A.初始化設(shè)置工作向量Workm表示系統(tǒng)可提供的各類資源數(shù)目，用以保護(hù)原數(shù)據(jù)結(jié)構(gòu)有關(guān)值。Wor

10、k = Available；設(shè)置完成標(biāo)志向量 Finishn。Finishi = false 表示進(jìn)程i尚末完成，如值為true則表示進(jìn)程i已完成(可以順利推進(jìn))。 B.從進(jìn)程集合n中找到一個(gè)能滿足下述二個(gè)條件: Finishi = false和NecdiWork，如找到則執(zhí)行步驟C，如找不到同時(shí)滿足以上二條件的進(jìn)程則執(zhí)行步驟D。 C.當(dāng)進(jìn)程i獲得資源后可順利執(zhí)行直到完成，并釋放出分配給它的資源，表示如下： work = work+Allocationi ； Finishi=true ；轉(zhuǎn)執(zhí)行步驟B。 D.如果所有的Finishitrue，則表示系統(tǒng)處于安全狀態(tài)，否則系統(tǒng)處于不安全狀態(tài)。銀行家

11、算法例：P110 假定系統(tǒng)中有五個(gè)進(jìn)程P0、P1、P2、P3、P4和三種類型資源A、B、C，每一種資源的數(shù)量分別為10、5、7。各進(jìn)程的最大需求、T0時(shí)刻資源分配情況如下所示。試問(wèn)： 1.T0時(shí)刻是否安全？ 2.P1請(qǐng)求資源Request1(1,0,2)是否允許？ 3.P4請(qǐng)求資源Request4(3,3,0)是否允許？ 4.P0請(qǐng)求資源Request(0,2,0)是否允許？Max A B CAllocation A B CNeed A B CAvailableA B CP0 P1 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

12、 1 0 0 2 7 4 31 2 26 0 0 0 1 1 4 3 13 3 23 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í)刻的資源分配表 falsefalsefalsefalsefalse0 1 02 0 03 0 22 1 10 0 27 4 31 2 26 0 00 1 14 3 1P0P1P2P3P4FinishWork

13、+AllocationA B CAllocation A B CNeed A B CWork A B C 資源情況進(jìn)程T0時(shí)刻的安全序列1、T0時(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 P43 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 Allocatio

14、nA 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 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í)刻的另一個(gè)安全序列1、T0時(shí)刻的安全性（2）P1發(fā)出請(qǐng)求向量Reques

15、t(1,0,2),系統(tǒng)按銀行家算法進(jìn)行檢查：2、 P1請(qǐng)求資源發(fā)現(xiàn)可以找到一個(gè)安全序列P1，P3，P4，P0，P2，因此系統(tǒng)是安全的，可以立即將P1所申請(qǐng)的資源分配給它。 （1）Request1(1,0,2)Need(1,2,2) （2）Request1(1,0,2) Available(3,3,2) （3）系統(tǒng)假定可為P1分配資源，并修改Available,Allocation1和Need向量。 （4）檢查此時(shí)系統(tǒng)是否安全。P4發(fā)出請(qǐng)求向量Request4(3,3,0),系統(tǒng)按銀行家算法進(jìn)行檢查：（1）Request4(3,3,0)Need4(4,3,1)（2）Request4(3,3,0)

16、Available(2,3,0),讓P4等待。3、P4請(qǐng)求資源P0發(fā)出請(qǐng)求向量Request0(0,2,0),系統(tǒng)按銀行家算法進(jìn)行檢查：2 1 07 2 30 2 06 0 0 0 1 14 3 10 3 03 0 23 0 22 1 10 0 2 P0 P1 P2 P3 P4AvaiableA B C NeedA B CAllocationA B C 資源情況進(jìn)程為P0分配資源后的有關(guān)資源數(shù)據(jù)4、P0請(qǐng)求資源（1）Request0(0,2,0)Need0(7,4,3)（2）Request0(0,2,0) Available(2,3,0)（3）系統(tǒng)暫時(shí)假定可為P0分配資源，并修改有關(guān)數(shù)據(jù)，下表

17、所示。（4）進(jìn)行安全性檢查，發(fā)現(xiàn)可用資源Available(2,1,0)已不能滿足任何進(jìn)程的需要，故進(jìn)程進(jìn)入不安全狀態(tài)，此時(shí)系統(tǒng)不分配資源給該進(jìn)程。練 習(xí) 如果將P0的請(qǐng)求(0,2,0)改為(0,1,0),系統(tǒng)能否講資源分配給它？3.4.4 死鎖的檢測(cè)進(jìn)行死鎖檢測(cè)：必須1.保存資源的請(qǐng)求和分配信息;2.利用某種算法對(duì)這些信息加以檢查，以判斷是否存在死鎖。資源分配圖(resource allocation graph)用于描述系統(tǒng)的死鎖是一個(gè)有向圖G；結(jié)點(diǎn):為資源或進(jìn)程，邊: 從資源R到進(jìn)程P的邊表示R已分配給P，從進(jìn)程P到資源R的邊表示P正因請(qǐng)求R而處于等待狀態(tài)。有向圖的循環(huán)是死鎖存在的必要條

18、件有環(huán)有死鎖有環(huán)無(wú)死鎖2.死鎖定理當(dāng)且僅當(dāng)S狀態(tài)的資源分配圖是不可完全簡(jiǎn)化的，稱S為死鎖狀態(tài).該充分條件稱為死鎖定理。其中的有邊進(jìn)程就是死鎖進(jìn)程。死鎖檢測(cè)的計(jì)算機(jī)實(shí)現(xiàn) P1131、教材P113方法；2、通常的方法是程序員的經(jīng)驗(yàn)，如UNIX系統(tǒng)中，可考察進(jìn)程的運(yùn)行時(shí)間。在UNIX系統(tǒng)中有命令PS可顯示進(jìn)程占用CPU的時(shí)間，若發(fā)現(xiàn)有一組進(jìn)程在一段時(shí)間內(nèi)沒(méi)有占用CPU，就認(rèn)為這類進(jìn)程出現(xiàn)了死鎖。3.4.5 死鎖的解除重新啟動(dòng)進(jìn)程回退回滾每個(gè)死鎖進(jìn)程到前一個(gè)檢查點(diǎn)，重新執(zhí)行每個(gè)進(jìn)程。撤銷死鎖進(jìn)程全部撤銷；按照某種原則逐個(gè)選擇死鎖進(jìn)程進(jìn)行撤消，直到解除系統(tǒng)死鎖選擇原則：一般選擇系統(tǒng)付出代價(jià)最小的進(jìn)程，即：花費(fèi)處理機(jī)的時(shí)間最少、輸出最少、估計(jì)未執(zhí)行部分最多、已分配的資源量最少、優(yōu)先級(jí)最低 剝奪資源按照某種原則逐個(gè)剝奪進(jìn)程資源，直到解除死鎖。課后練習(xí)系統(tǒng)可供用戶使用的內(nèi)存共150MB，目前分配給3個(gè)進(jìn)程的數(shù)量如下表所示。這時(shí)，第個(gè)4進(jìn)程產(chǎn)生，它最終需要內(nèi)存60MB，目前的申請(qǐng)數(shù)為25MB。應(yīng)用關(guān)于死鎖問(wèn)題的銀行家算法，回答是否可以分配給第4個(gè)進(jìn)程25MB內(nèi)存，為什么？進(jìn)程最大需要內(nèi)存量已經(jīng)得到內(nèi)存量 1 70MB 45MB 2 60MB 40MB 3 60MB 15MB-3 3 2(2 3 0)7 4 3 1 2 2(0 2 0)6 0 00 1 14