第六章 講稿lec12 死鎖

1、計算機與操作系統(tǒng)第十二講死鎖南京大學軟件學院112:03第十二講 死鎖12.1 死鎖產(chǎn)生12.2 死鎖防止12.3 死鎖避免12.4 死鎖檢測和解除212:0312.1 死鎖產(chǎn)生若鎖的例子(1)例進程推進順序不當產(chǎn)生死鎖設系統(tǒng)有打印機、繪圖儀各一臺，被進程Q1和Q2 共享。兩個進程并發(fā)執(zhí)行，按下列次序請求和釋放資源：進程Q1請求繪圖儀請求打印機釋放繪圖儀釋放打印機進程Q2請求打印機請求繪圖儀釋放繪圖儀釋放打印機312:03進程資源軌跡圖412:03若鎖的例子(2)例PV操作使用不當產(chǎn)生死鎖進程P1P(s1);P(s2);使用r1和r2; V(s1);V(s2);進程P2P(s2);P(s1);

2、使用r1和r2 V(s2);V(s1);*512:03若鎖的例子(3)例資源分配不當引起死鎖若系統(tǒng)中有m個資源被n個進程共享，每個進程都要求個資源，而m nK時， 即資源數(shù)小于進程所要求的總數(shù)時，如果分配不得當就可能引起死鎖612:03若鎖的例子(4)例對臨時性資源使用不加限制引起死鎖*進程通信使用的信件是一種臨時性資源，如果對信件的發(fā)送和接收不加限制，可能引起死鎖。進程P1等待進程P3的信件S3來到后再向進程P2發(fā)送信件S1；P2又要等待P1的信件S1來到后再向P3發(fā)送信件S2；而P3也要等待P2的信件S2來到后才能發(fā)出信件S3。這種情況下形成了循環(huán)等待，產(chǎn)生死鎖。*712:03獨木橋(例)

3、*只能在一個方向行車可能發(fā)生死鎖也可能發(fā)生饑餓812:03死鎖定義*操作系統(tǒng)中的死鎖指：如果在一個進程集合中的每個進程都在等待只能由該集合中的其他一個進程才能引發(fā)的，則稱一組進程或系統(tǒng)此時發(fā)生死鎖。*例如，n個進程P1、P2，Pn，Pi因為申請不到資源Rj而處于等待狀態(tài)，而Rj又被Pi+1占有，Pn欲申請的資源被P1占有，此時這n個進程的等待狀態(tài)永遠不能結(jié)束，則說這n個進程處于死鎖狀態(tài)。912:03產(chǎn)生死鎖因素*不僅與系統(tǒng)擁有的資源數(shù)量有關(guān)， 而且與資源分配策略，進程對資源的使用要求以及并發(fā)進程的推進順序有關(guān)1012:0312.2死鎖防止(1)系統(tǒng)形成死鎖的四個必要條件互斥條件(mutuale

4、xclusion)：系統(tǒng)中存在臨界資源，進程應互斥地使用這些資源占有和等待條件(holdandwait)：進程請求資源得不到滿足而等待時，不釋放已占有的資源*不條件(nopreemption)：已被占用的資源只能由屬主釋放，不允許被其它進程循環(huán)等待條件(circularwait)：存在循環(huán)等待鏈，其中，每個進程都在鏈中等待下一個進程所持有的資源，造成這組進程永遠等待*1112:031212:03死鎖防止(2)破壞第一個條件使資源可同時訪問而不是互斥使用，可再入程序、只讀數(shù)據(jù)文件、時鐘、磁盤等軟硬件資源均可用這種辦法管理，但有許多資源如可寫文件、磁帶機等由于特殊性質(zhì)決定只能互斥占有，而不能被同時

5、訪問，所以這種做法許多場合行不通。 /有些資源具有天生的互斥性破壞第二個條件靜態(tài)分配，進程在執(zhí)行中不再申請資源，就不會出現(xiàn)占有某些資源再等待另一些資源的情況。*實現(xiàn)簡單，被許多操作系統(tǒng)采用，但會嚴重地降低資源利用率，因為在每個進程占有的資源中，有些資源在運行后期使用，甚至有些資源在例外情況下才被使用，可能造成進程占有一些幾乎不用的資源，而使其他想用這些資源的進程產(chǎn)生等待死鎖防止(2)破壞第一個條件使資源可同時訪問而不是互斥使用， 破壞第二個條件靜態(tài)分配，破壞第三個條件*采用式調(diào)度方法，當進程在申請資源未獲準許的情況下,如主動釋放資源(一種式),然后才去等待。破壞第四個條件上述死鎖防止辦法造成資

6、源利用率和吞吐率低。介紹兩種比較實用的死鎖防止方法。*1312:03死鎖的防止(3)采用層次分配策略(破壞條件2和4)* 資源被分成多個層次* 當進程得到某一層的一個資源后，它只能再申請較高層次的資源* 當進程要釋放某層的一個資源時，必須先釋放占有的較高層次的資源* 當進程得到某一層的一個資源后，它想申請該層的另一個資源時，必須先釋放該層中的已占資源1412:03死鎖防止(4)層次策略的變種按序分配策略*把系統(tǒng)的所有資源排一個順序，例如，系統(tǒng)若共有n個進程,共有m個資源，用ri表示第i個資源，于是這m個資源是：r1,r2,rm規(guī)定如果進程不得在占用資源ri(1im)后再申請rj(jclaimi

7、,*)error;else /申請量超過最大需求值if(request*available*)suspend process.;else /嘗試分配，define newstate by:allocationi,*=allocationi,*+request*;available*=available*-request*;if(safe(newstate)carry out allocation;else restore original state;suspend process;33412:銀行家算法的程序及簡短說明(3)*bool safe(state s) /安全性測試算法int cu

8、rrentavailm; set rest;currentavail*=available*; rest=all process; possible=true;while(possible)/rest中找一個Pk，滿足以下條件claimk,*-allocationk,*=currentavail*; if(found)currentavail*=currentavail*+allocationk,*; rest=restPk;elsepossible=false;return(rest=null);0312.4 死鎖檢測和解除資源分配圖和死鎖定理* 解決死鎖問題的一條途徑是死鎖檢測和解除，這

9、種方法對資源的分配不加任何限制，也不采取死 鎖避免措施，但系統(tǒng)定時地運行一個“死鎖檢測” 程序，判斷系統(tǒng)內(nèi)是否已出現(xiàn)死鎖，如果檢測到 系統(tǒng)已發(fā)生了死鎖，再采取措施解除它。3512:03進程-資源分配圖*約定PiRj為請求邊，表示進程Pi申請資源類Rj中的一個資源得不到滿足而處于等待Rj類資源的狀態(tài)，該有向邊從進程開始指到方框的邊緣，表示進程Pi申請Rj類中的一個資源。RjPi為分配邊，表示Rj類中的一個資源已被進程Pi 占用，由于已把一個具體的資源分給了進程Pi，故該有向邊從方框內(nèi)的某個黑圓點出發(fā)指向進程。*3612:03資源分配圖的一個例子R1R2P1P2P3死鎖的例37 子12:03R3資

10、源分配圖的另一個例子R1R2P2P3P4一個有環(huán)路而無死鎖的例子3812:03P1簡化進程-資源分配圖檢測系統(tǒng)是否處于死鎖狀態(tài)(1)(1) 如果進程-資源分配圖中無環(huán)路，則此時系統(tǒng)沒有發(fā)生死鎖(2) 如果進程-資源分配圖中有環(huán)路，且每個資源類中僅有一個資源，則系統(tǒng)中發(fā)生了死鎖，此時，環(huán)路是系統(tǒng)發(fā)生死鎖的充要條件，環(huán)路中的進程便為死鎖進程(3) 如果進程-資源分配圖中有環(huán)路，且涉及的資源類中有多個資源，則環(huán)路的存在只是產(chǎn)生死鎖的必要條件而不是充分條件3912:03簡化進程-資源分配圖檢測系統(tǒng)是否處于死鎖狀態(tài)(2)*如果能在進程-資源分配圖中消去此進程的所有請求邊和分配邊，成為孤立結(jié)點。經(jīng)一系列簡

11、化，使所有進程成為孤立結(jié) 點，則該圖是可完全簡化的；否則則稱該圖是不可完全簡化的系統(tǒng)為死鎖狀態(tài)的充分條件是：當且僅當該狀態(tài)的進程-資源分配圖是不可完全簡化的。該充分條件稱為死鎖定理*孤立結(jié)點含義?4012:03死鎖的檢測和解除方法(1)(1) 借助于死鎖的安全性測試算法來實現(xiàn)。死鎖檢測算法與死鎖避免算法是類似的，不同在于前者考慮了 檢查每個進程還需要的所有資源能否滿足要求；而 后者則僅要根據(jù)進程的當前申請資源量來判斷系統(tǒng)是否進入了不安全狀態(tài)4112:03死鎖的檢測和解除方法(2)一種具體的死鎖檢測方法，檢測算法步驟如下：*1) currentavail=available；2) 如果alloc

12、ationk,*!=0，令finishk=false;否則finishk=true； 3)尋找一個k，它應滿足條件：(finishk=false)&(requestk,*=currentavail*);若找不到這樣的k，則轉(zhuǎn)向5)；4) 修改currentavail*=Currentavail*+allocationk,*; finishk=true;然后轉(zhuǎn)向3)；5) 如果存在k(1kn),finishk=false,則系統(tǒng)處于死鎖狀態(tài)，并且finishk=false的Pk為處于死鎖的進程。*4212:03死鎖的解除(1)*結(jié)束所有進程的執(zhí)行，重新啟動操作系統(tǒng)。方法簡單，但以前工作全部作廢，損失很大。撤銷陷于死鎖的所有進程，解除死鎖繼續(xù)運行。逐個撤銷陷于死鎖的進程，回收其資