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

1,3.5產(chǎn)生死鎖的原因 和必要條件,2,3.8 死鎖問題,在多道程序系統(tǒng)中，多個(gè)進(jìn)程并發(fā)運(yùn)行，共享資源，從而提高了資源的利用率。但是若對(duì)資源的管理和使用不當(dāng)，在一定條件下會(huì)導(dǎo)致系統(tǒng)發(fā)生一種隨機(jī)性故障死鎖。在一些系統(tǒng)中，比如實(shí)時(shí)控制系統(tǒng)，系統(tǒng)一旦發(fā)生死鎖將導(dǎo)致災(zāi)難性的后果。,3,3.8.1 死鎖的基本概念,資源 死鎖的定義 產(chǎn)生死鎖的原因 產(chǎn)生死鎖的必要條件 處理死鎖的基本方法,4,資源的概念,OS是計(jì)算機(jī)系統(tǒng)中資源的管理者，而進(jìn)程是競(jìng)爭(zhēng)資源的基本單位，故對(duì)系統(tǒng)中所有進(jìn)程的資源分配工作，都由OS完成。 研究資源分配時(shí)，我們必須搞清該資源是可以被幾個(gè)進(jìn)程同時(shí)使用，還是只能為一個(gè)進(jìn)程使用，資源的不同使用性質(zhì)正是引起系統(tǒng)死鎖的原因。,5,根據(jù)資源性質(zhì)：可剝奪（搶占）和不可剝奪（搶占）資源。 可搶占資源指資源占有進(jìn)程雖然需要使用該資源，但另一個(gè)進(jìn)程卻強(qiáng)行把資源從占有者進(jìn)程處搶來(lái)。 不可搶占資源指只有占用者進(jìn)程不再需要使用該資源而主動(dòng)釋放資源外，其它進(jìn)程不得在占有者進(jìn)程使用資源過程中強(qiáng)行搶占。,資源的分類,6,根據(jù)使用方式：共享資源和獨(dú)享資源。 根據(jù)使用期限；永久資源和臨時(shí)性資源。,可順序重復(fù)使用的資源,由一個(gè)進(jìn)程產(chǎn)生，被另外一個(gè)進(jìn)程使用短暫時(shí)間 之后便無(wú)用的資源,7,死鎖的定義,死鎖Deadlock：是計(jì)算機(jī)系統(tǒng)中多道程序并發(fā)執(zhí)行時(shí)，兩個(gè)或兩個(gè)以上的進(jìn)程由于競(jìng)爭(zhēng)資源而造成的一種互相等待的現(xiàn)象（僵局），如無(wú)外力作用，這些進(jìn)程將永遠(yuǎn)不能再向前推進(jìn)。 陷入死鎖狀態(tài)的進(jìn)程稱為死鎖進(jìn)程，所占用的資源或者需要它們進(jìn)行某種合作的其它進(jìn)程就會(huì)相繼陷入死鎖，最終可能導(dǎo)致整個(gè)系統(tǒng)處于癱瘓狀態(tài)。,8,產(chǎn)生死鎖的原因,1 競(jìng)爭(zhēng)資源。當(dāng)系統(tǒng)中供多個(gè)進(jìn)程所共享的資源，不足以同時(shí)滿足它們的需要時(shí)，引起它們對(duì)資源的競(jìng)爭(zhēng)而產(chǎn)生死鎖； 2 進(jìn)程推進(jìn)的順序不當(dāng) 。進(jìn)程在運(yùn)行過程中，請(qǐng)求和釋放資源的順序不當(dāng)，導(dǎo)致進(jìn)程的死鎖。,9,競(jìng)爭(zhēng)資源,1 競(jìng)爭(zhēng)非剝奪性資源： 2 競(jìng)爭(zhēng)臨時(shí)性資源,打印機(jī)R1,磁帶機(jī)R2,P1,P2,10,P1：Release(S1);Request(S3) P2：Release(S2);Request(S1) P3：Release(S3);Request(S2) 不可能發(fā)生死鎖,P1：Request(S3);Release(S1) P2：Request(S1);Release(S2) P3：Request(S2);Release(S3) 可能發(fā)生死鎖,S1、S2、S3是臨時(shí)資源,11,若干死鎖的例子(1),例進(jìn)程推進(jìn)順序不當(dāng)產(chǎn)生死鎖 設(shè)系統(tǒng)有打印機(jī)、讀卡機(jī)各一臺(tái)，被進(jìn)程和共享。兩個(gè)進(jìn)程并發(fā)執(zhí)行，按下列次序請(qǐng)求和釋放資源： 進(jìn)程 進(jìn)程 請(qǐng)求讀卡機(jī) 請(qǐng)求打印機(jī) 請(qǐng)求打印機(jī) 請(qǐng)求讀卡機(jī) 釋放讀卡機(jī) 釋放讀卡機(jī) 釋放打印機(jī) 釋放打印機(jī),12,P2Rel(R1),P2Rel(R2),P2Req(R1),P2Req(R2),P1Req(R1),P1Req(R2),P1Rel(R1),P1Rel(R2),進(jìn)程P1、P2并發(fā)執(zhí)行。 資源R1、R2,曲線4將進(jìn)入不安全區(qū)域（進(jìn)程推進(jìn)順序非法）,13,R2已經(jīng)分配給P1、R1已經(jīng)分配給P2,14,產(chǎn)生死鎖的四個(gè)必要條件,互斥條件:進(jìn)程訪問的是臨界資源，那個(gè)資源一次只能被一個(gè)進(jìn)程所使用。 不剝奪條件:一個(gè)資源僅能被占有它的進(jìn)程所釋放，而不能被其他進(jìn)程剝奪。 部分分配:（請(qǐng)求和保持條件）一個(gè)進(jìn)程在請(qǐng)求新的資源的同時(shí)，保持對(duì)某些資源的占有。 環(huán)路等待條件:存在一個(gè)進(jìn)程的環(huán)路鏈，鏈中每一個(gè)進(jìn)程占用有著某個(gè)或某些資源，又在等待鏈中的另一個(gè)進(jìn)程占有的資源。,15,若干死鎖的例子(2) 例 PV操作使用不當(dāng)產(chǎn)生死鎖,進(jìn)程Q1 進(jìn)程Q2 P(S1); P(s2); P(s2); P(s1); 使用r1和r2; 使用r1和r2 V(S1); V(s2); V(S2); V(S1);,16,若干死鎖的例子(3) 例 資源分配不當(dāng)引起死鎖,若系統(tǒng)中有m個(gè)資源被n個(gè)進(jìn)程共享，每個(gè)進(jìn)程都要求個(gè)資源，而m nK時(shí)，即資源數(shù)小于進(jìn)程所要求的總數(shù)時(shí)，如果分配不得當(dāng)就可能引起死鎖。,17,若干死鎖的例子(4) 例對(duì)臨時(shí)性資源使用不加限制引起死鎖,進(jìn)程通信使用的信件是一種臨時(shí)性資源，如果對(duì)信件的發(fā)送和接收不加限制，可能引起死鎖。 進(jìn)程P1等待進(jìn)程P3的信件S3來(lái)到后再向進(jìn)程P2發(fā)送信件S1；P2又要等待P1的信件S1來(lái)到后再向P3發(fā)送信件S2；而P3也要等待P2的信件S2來(lái)到后才能發(fā)出信件S3。這種情況下形成了循環(huán)等待，產(chǎn)生死鎖。,18,3.6預(yù)防死鎖的方法,破壞第一個(gè)條件 使資源可同時(shí)訪問而不是互斥使用，是個(gè)簡(jiǎn)單的辦法，磁盤可用這種辦法管理,但有許多資源往往是不能同時(shí)訪問，所以這種做法許多場(chǎng)合行不通。,19,死鎖防止,破壞第二個(gè)條件或第四個(gè)條件 種種死鎖防止辦法施加于資源的限制條件太嚴(yán)格,會(huì)造成資源利用率和吞吐率低。兩種比較實(shí)用的死鎖防止方法，它們能破壞第二個(gè)條件或第四個(gè)條件。,20,死鎖防止 1.摒棄”請(qǐng)求和保持” 靜態(tài)分配策略（破壞條件2）,靜態(tài)分配是指一個(gè)進(jìn)程必須在執(zhí)行前就申請(qǐng)它所要的全部資源，并且直到它所要的資源都得到滿足后才開始執(zhí)行。,21,死鎖防止,2.摒棄”不剝奪”條件破壞第三個(gè)條件 采用剝奪式調(diào)度方法可破壞第三個(gè)條件，但只適用于對(duì)主存資源和處理器資源的分配， 當(dāng)進(jìn)程在申請(qǐng)資源未獲準(zhǔn)許的情況下,如主動(dòng)釋放資源(一種剝奪式),然后才去等待，以后再一起向系統(tǒng)提出申請(qǐng),也能防止死鎖。,22,死鎖的防止 3.摒棄”環(huán)路等待”條件層次分配策略（破壞條件2和4）,資源被分成多個(gè)層次 當(dāng)進(jìn)程得到某一層的一個(gè)資源后，它只能再申請(qǐng)較高層次的資源 當(dāng)進(jìn)程要釋放某層的一個(gè)資源時(shí)，必須先釋放占有的較高層次的資源 當(dāng)進(jìn)程得到某一層的一個(gè)資源后，它想申請(qǐng)?jiān)搶拥牧硪粋€(gè)資源時(shí)，必須先釋放該層中的已占資源,23,死鎖防止 層次策略的變種按序分配策略,把系統(tǒng)的所有資源排一個(gè)順序，例如，系統(tǒng)若共有n個(gè)進(jìn)程,共有m個(gè)資源，用ri表示第i個(gè)資源，于是這m個(gè)資源是： r1,r2,rm 規(guī)定如果進(jìn)程不得在占用資源ri(1im)后再申請(qǐng)rj(ji)。不難證明，按這種策略分配資源時(shí)系統(tǒng)不會(huì)發(fā)生死鎖。,24,2 預(yù)防死鎖,根據(jù)生產(chǎn)死鎖的四個(gè)必要條件，只要使用其中之一不能成立，死鎖就不會(huì)出現(xiàn)。但必要條件是由設(shè)備的固有特性所決定的，不僅不能改變，相反還應(yīng)加以保證，因此實(shí)際上只有三種方法。 預(yù)防死鎖是一種較易實(shí)現(xiàn)的方法，已被廣泛使用，但由于所施加的限制條件往往太嚴(yán)格，可能導(dǎo)致系統(tǒng)資源利用率和系統(tǒng)吞吐量降低。,1 互斥條件 2 請(qǐng)求和保持條件 3 不剝奪條件 4 環(huán)路等待條件,25,1:防止部分分配（摒棄請(qǐng)求和保持條件）,系統(tǒng)要求任一進(jìn)程必須預(yù)先申請(qǐng)它所需的全部資源，而且僅當(dāng)該進(jìn)程的全部資源要求能得到滿足時(shí)，系統(tǒng)才能給予一次性分配，然后啟動(dòng)該進(jìn)程運(yùn)行，但是在分配時(shí)只要由一種資源不滿足，系統(tǒng)就不會(huì)給進(jìn)程分配資源。進(jìn)程運(yùn)行期間，不會(huì)再請(qǐng)求新的資源，所以，再分配就不會(huì)發(fā)生（摒棄了部分分配）。 特點(diǎn)：資源嚴(yán)重浪費(fèi) 進(jìn)程延遲進(jìn)行,26,3 防止“不剝奪”條件的出現(xiàn) 采用的策略：一個(gè)已經(jīng)保持了某些資源的進(jìn)程，當(dāng)它再提出新的資源要求而不能立即得到滿足時(shí)，必須釋放它已經(jīng)保持的所有資源，待以后需要時(shí)再重新申請(qǐng)。 實(shí)現(xiàn)比較復(fù)雜，且要付出很大代價(jià)；此外，還因?yàn)榉磸?fù)地申請(qǐng)和釋放資源，而使進(jìn)程的執(zhí)行無(wú)限地推遲，延長(zhǎng)了周轉(zhuǎn)時(shí)間，增加了系統(tǒng)的開銷，降低了系統(tǒng)吞吐量。（例如打印機(jī)打印的結(jié)果不連續(xù)）,27,2.防止“環(huán)路等待”條件的出現(xiàn)。,采用資源順序使用法，基本思想是：把系統(tǒng)中所有資源類型線性排隊(duì)，并按遞增規(guī)則賦予每類資源以唯一的編號(hào)。例如輸入機(jī)1，打印機(jī)2，磁帶機(jī)3，磁盤4等等。進(jìn)程申請(qǐng)資源時(shí)，必須嚴(yán)格按資源編號(hào)的遞增順序進(jìn)行，否則系統(tǒng)不予分配。 優(yōu)點(diǎn)：資源利用率和系統(tǒng)吞吐量與另兩種方法相比有較明顯的改善。 缺點(diǎn)： 1 為系統(tǒng)中各種類型的資源所分配的序號(hào)必須相對(duì)穩(wěn)定，這就限制了新設(shè)備類型的增加 2 作業(yè)實(shí)際使用資源的順序與系統(tǒng)規(guī)定的順序不同而造成資源的浪費(fèi)；,28,3 死鎖避免,避免死鎖與預(yù)防死鎖的區(qū)別在于，預(yù)防死鎖是設(shè)法至少破壞產(chǎn)生死鎖的必要條件之一，嚴(yán)格地防止死鎖的出現(xiàn)。 避免死鎖，它是在進(jìn)程請(qǐng)求分配資源時(shí)，采用銀行家算法等防止系統(tǒng)進(jìn)入不安全狀態(tài)。,29,在資源的動(dòng)態(tài)分配的過程中，使用某種方法去防止系統(tǒng)進(jìn)入不安全狀態(tài)，從而避免死鎖的發(fā)生。 系統(tǒng)狀態(tài)： 安全狀態(tài)：指系統(tǒng)能按照某種順序如(稱為序列為安全序列)，為每個(gè)進(jìn)程分配所需的資源，直至最大需求，使得每個(gè)進(jìn)程都能順利完成。 非安全狀態(tài)：即在某個(gè)時(shí)刻系統(tǒng)中不存在一個(gè)安全序列，則稱系統(tǒng)處于不安全狀態(tài)或非安全狀態(tài)。,30,雖然并非所有不安全狀態(tài)都是死鎖狀態(tài)，但當(dāng)系統(tǒng)進(jìn)入不安全狀態(tài)后，便有可能進(jìn)入死鎖狀態(tài)；反之只要系統(tǒng)處于安全狀態(tài)，系統(tǒng)便可避免進(jìn)入死鎖狀態(tài)。因此，避免死鎖的實(shí)質(zhì)是如何使系統(tǒng)不進(jìn)入不安全狀態(tài)。,31,安全狀態(tài)的例子,例：假定系統(tǒng)有三個(gè)進(jìn)程P1、P2、P3，共有12臺(tái)磁帶機(jī)。進(jìn)程P1總共要求10臺(tái)磁帶機(jī)，P2和P3分別要求4臺(tái)和九臺(tái)。設(shè)在T0時(shí)刻，進(jìn)程P1、P2和P3已經(jīng)獲得5臺(tái)、2臺(tái)和2臺(tái)，還有3臺(tái)空閑沒有分配。,進(jìn)程,最大需求,已分配,可用,P1,10,5,3,P2,P3,4,2,2,9,T0時(shí)刻系統(tǒng)時(shí)安全的。這時(shí)存在一個(gè)安全序列,32,安全狀態(tài)的例子,例：假定系統(tǒng)有三個(gè)進(jìn)程P1、P2、P3，共有12臺(tái)磁帶機(jī)。進(jìn)程P1總共要求10臺(tái)磁帶機(jī)，P2和P3分別要求4臺(tái)和九臺(tái)。設(shè)在T0時(shí)刻，進(jìn)程P1、P2和P3已經(jīng)獲得5臺(tái)、2臺(tái)和2臺(tái)，還有3臺(tái)空閑沒有分配。,進(jìn)程,最大需求,已分配,可用,P1,10,5,3,P2,P3,4,2,2,9,T0時(shí)刻系統(tǒng)時(shí)安全的。這時(shí)存在一個(gè)安全序列,33,雖然并非所有不安全狀態(tài)都是死鎖狀態(tài)，但當(dāng)系統(tǒng)進(jìn)入不安全狀態(tài)后，便有可能進(jìn)入死鎖狀態(tài)；反之只要系統(tǒng)處于安全狀態(tài)，系統(tǒng)便可避免進(jìn)入死鎖狀態(tài)。因此，避免死鎖的實(shí)質(zhì)是如何使系統(tǒng)不進(jìn)入不安全狀態(tài)。 系統(tǒng)的狀態(tài)可能通過下述來(lái)描述： 進(jìn)程剩余申請(qǐng)數(shù)最大申請(qǐng)數(shù)占有數(shù)。 可分配資源數(shù)總數(shù)占有數(shù)之和。,34,3.6.3利用銀行家算法避免死鎖,銀行家算法 銀行家擁有一筆周轉(zhuǎn)資金 客戶要求分期貸款，如果客戶能夠得到各期貸款，就一定能夠歸還貸款，否則就一定不能歸還貸款 銀行家應(yīng)謹(jǐn)慎的貸款，防止出現(xiàn)壞帳 用銀行家算法避免死鎖 操作系統(tǒng)（銀行家） 操作系統(tǒng)管理的資源(周轉(zhuǎn)資金) 進(jìn)程（要求貸款的客戶）,35,銀行家算法,銀行家算法是最有代表性的避免死鎖算法，是Dijkstra提出的銀行家算法。這是由于該算法能用于銀行系統(tǒng)現(xiàn)金貸款的發(fā)放而得名。為實(shí)現(xiàn)銀行家算法，系統(tǒng)中必須設(shè)置若干數(shù)據(jù)結(jié)構(gòu)。,36,一、銀行家算法中的數(shù)據(jù)結(jié)構(gòu) 1 可利用資源向量Available 是一個(gè)含有m個(gè)元素，其中的每一個(gè)元素代表一類可利用的資源數(shù)目，其初值是系統(tǒng)中所配置的該類全部可用資源數(shù)目。如果Availablej=k， 表示系統(tǒng)中現(xiàn)有Rj類資源k個(gè)。 2 最大需求矩陣Max 是一個(gè)含有nm的矩陣，它定義了系統(tǒng)中n個(gè)進(jìn)程中的每一個(gè)進(jìn)程對(duì)m類資源的最大需求。如果Max(i,j)=k， 表示進(jìn)程i需要Rj類資源的最大數(shù)目為k。,Available= 3 5 4 2 8 3 8 6 1,37,3 分配矩陣Allocation 是一個(gè)含有nm的矩陣，它定義了系統(tǒng)中每一類資源當(dāng)前已分配給每一進(jìn)程的資源數(shù)。如果Allocation(i,j)=k， 表示進(jìn)程i當(dāng)前已分得Rj類資源k個(gè)。 4 需求矩陣Need 是一個(gè)含有nm的矩陣，用以表示每一個(gè)進(jìn)程尚需的各類資源數(shù)。如果Need(i,j)=k， 表示進(jìn)程i還需要Rj類資源k個(gè)，方能完成其任務(wù)。 Need(i,j)= Max(i,j)-Allocation(i,j),38,二、銀行家算法 設(shè)Requesti是進(jìn)程Pi的請(qǐng)求向量，如果進(jìn)程Pi需要K個(gè)Rj類資源，當(dāng)Pi發(fā)出資源請(qǐng)求后，系統(tǒng)按下述步驟進(jìn)行檢查： 1 如果RequestiNeedi,則轉(zhuǎn)向步驟2；否則認(rèn)為出錯(cuò)。（因?yàn)樗枰馁Y源數(shù)已超過它所宣布的最大值。 2如果RequestiAvailable,則轉(zhuǎn)向步驟3；否則，表示系統(tǒng)中尚無(wú)足夠的資源，Pi必須等待 3 系統(tǒng)試探把要求的資源分配給進(jìn)程Pi，并修改下面數(shù)據(jù)結(jié)構(gòu)中的數(shù)值： Available:=Available-Requesti; Allocation:=Allocation+Requesti; Needi:= Needi- Requesti; 4 系統(tǒng)執(zhí)行安全性算法，檢查此次資源分配后，系統(tǒng)是否處于安全狀態(tài)。若安全，正式將資源分配給進(jìn)程Pi，以完成本次分配；否則，將試探分配作廢，恢復(fù)原來(lái)的資源分配狀態(tài)，讓進(jìn)程Pi等待。,39,三、安全性算法 系統(tǒng)所執(zhí)行的安全性算法可描述如下： 1 設(shè)置兩個(gè)向量 工作向量Work.它表示系統(tǒng)可提供給進(jìn)程繼續(xù)運(yùn)行所需要的各類資源的數(shù)目，它含有m個(gè)元素，執(zhí)行安全算法開始時(shí)，Work:=Available。 Finish.它表示系統(tǒng)是否有足夠的資源分配給進(jìn)程，使之運(yùn)行完成。開始時(shí)先做Finishi:=false；當(dāng)有足夠的資源分配給進(jìn)程時(shí)，令Finishi:=true. 2 從進(jìn)程集合中找到一個(gè)能滿足下述條件的進(jìn)程：Finishi=false; NeediWork. 如找到，執(zhí)行步驟3；否則執(zhí)行步驟4。 3 當(dāng)進(jìn)程Pi獲得資源后，可順利執(zhí)行，直至完成，并釋放出分配給它的資源，故執(zhí)行： Work:=Work+Allocation; Finishi:=true; Goto step2; 4 如果所有進(jìn)程的Finishi=true，則表示系統(tǒng)處于安全狀態(tài)；否則，系統(tǒng)處于不安全狀態(tài)。,40,要記住的一些變量的名稱,1 Available（可利用資源向量） 某類可利用的資源數(shù)目，其初值是系統(tǒng)中所配置的該類全部可用資源數(shù)目。 2 Max最大需求矩陣 某個(gè)進(jìn)程對(duì)某類資源的最大需求數(shù) 3 Allocation分配矩陣 某類資源當(dāng)前非配給某進(jìn)程的資源數(shù)。 4 Need需求矩陣 某個(gè)進(jìn)程還需要的各類資源數(shù)。 Need= Max-Allocation 系統(tǒng)把進(jìn)程請(qǐng)求的資源分配給它以后要修改的變量 Available:=Available-Request; Allocation:=Allocation+Request; Need:= Need- Request;,41,銀行家算法之例,假定系統(tǒng)中有五個(gè)進(jìn)程P0、P1、P2、P3、P4和三種類型的資源A，B，C，每一種資源的數(shù)量分別為10、5、7，在T0時(shí)刻的資源分配情況如圖,資源情況,進(jìn)程,Allocation A B C,Max A B C,Need A B C,Available A B C,P0 P1 P2 P3 P4,0 1 0,3 2 2,9 0 2,2 2 2,4 3 3,2 0 0,( 3 0 2 ),3 0 2,2 1 1,0 0 2,7 4 3,1 2 2,( 0 2 0 ),0 0,0 1 1,4 3 1,3 3 2,( 2 3 0 ),42,3 3 2,1 2 2,2 0 0,5 3 2,true,true,true,true,true,0 1 1,2 1 1,5 3 2,7 4 3,7 4 3,4 3 1,0 0 2,7 4 5,7 4 5,6 0 0,3 0 2,10 4 7,10 4 7,7 4 3,0 1 0,10 5 7,最大值,已分配,還需要,可用,若P1發(fā)出請(qǐng)求向量 Request（1，0，2）,工作向量Work.它表示系統(tǒng)可提供給進(jìn)程繼續(xù)運(yùn)行所需要的各類資源的數(shù)目,10,5 7,43,思考和練習(xí) 假定系統(tǒng)中有五個(gè)進(jìn)程P0、P1、P2、P3、P4和 三種類型的資源A，B，C，每一種資源的數(shù)量 分別為10、5、7，在T0時(shí)刻的資源分配情況如圖 請(qǐng)找出該表中T0時(shí)刻以后存在的安全序列（至少2種）,資源情況,進(jìn)程,Allocation A B C,Max A B C,Need A B C,Available A B C,P0 P1 P2 P3 P4,0 1 0,3 2 2,9 0 2,2 2 2,4 3 3,2 0 0,3 0 2,2 1 1,0 0 2,7 4 3,1 2 2,6 0 0,0 1 1,4 3 1,3 3 2,7 5 3,44,3 死鎖的檢測(cè)和恢復(fù) 死鎖的檢測(cè)和恢復(fù)技術(shù)是指定期啟動(dòng)一個(gè)軟件檢測(cè)系統(tǒng)的狀態(tài)，若發(fā)現(xiàn)有死鎖存在，則采取措施恢復(fù)之。 (1)死鎖的檢測(cè) 檢查死鎖的辦法就是由軟件檢查系統(tǒng)中由進(jìn)程和資源構(gòu)成的有向圖是否構(gòu)成一個(gè)或多個(gè)環(huán)路，若是，則存在死鎖，否則不存在。,45,死鎖的檢測(cè)：實(shí)質(zhì)是確定是否存在環(huán)路等待現(xiàn)象，一旦發(fā)現(xiàn)這種環(huán)路便認(rèn)定死鎖存在，并識(shí)別出該環(huán)路所涉及的有關(guān)進(jìn)程，以供系統(tǒng)采取適當(dāng)?shù)拇胧﹣?lái)解除死鎖。最常用的是一種基于資源分配圖RAG和死鎖定理的檢測(cè)死鎖算法。,46,資源分配圖（RAG） 系統(tǒng)死鎖可用資源分配圖來(lái)描述，該圖是由一組結(jié)點(diǎn)N和一組邊E所組成的一對(duì)偶G=(N,E)。（用圓圈代表一個(gè)進(jìn)程，用方框代表一類資源，由于一種類型的資源可能有多個(gè)，可用方框中的一個(gè)點(diǎn)代表一類資源中的一個(gè)資源） 幾個(gè)概念：請(qǐng)求邊，分配邊,P1,P2,r1,r2,請(qǐng)求r2,資源分配圖,47,封鎖進(jìn)程：是指某個(gè)進(jìn)程由于請(qǐng)求了超過了系統(tǒng)中現(xiàn)有的未分配資源數(shù)目的資源，而被系統(tǒng)封鎖的進(jìn)程。 非封鎖進(jìn)程：即沒有被系統(tǒng)封鎖的進(jìn)程資源分配圖的化簡(jiǎn)方法：假設(shè)某個(gè)RAG中存在一個(gè)進(jìn)程Pi，此刻Pi是非封鎖進(jìn)程，那么可以進(jìn)行如下化簡(jiǎn)：當(dāng)Pi有請(qǐng)求邊時(shí)，首先將其請(qǐng)求邊變成分配邊(即滿足Pi的資源請(qǐng)求)，而一旦Pi的所有資源請(qǐng)求都得到滿足，Pi就能在有限的時(shí)間內(nèi)運(yùn)行結(jié)束，并釋放其所占用的全部資源，此時(shí)Pi只有分配邊，刪去這些分配邊（實(shí)際上相當(dāng)于消去了Pi的所有請(qǐng)求邊和分配邊），使Pi成為孤立結(jié)點(diǎn)。（反復(fù)進(jìn)行） 。,48,死鎖定理： 系統(tǒng)中某個(gè)時(shí)刻S為死鎖狀態(tài)的充要條件是S時(shí)刻系統(tǒng)的資源分配圖是不可完全簡(jiǎn)化的。 在經(jīng)過一系列的簡(jiǎn)化后，若能消去圖中的所有邊，使所有的進(jìn)程都成為孤立結(jié)點(diǎn)，則稱該圖是可完全簡(jiǎn)化的；反之的是不可完全簡(jiǎn)化的。,P1,P2,r1,r2,P1,P2,r1,r2,49,死鎖的恢復(fù)。是與檢測(cè)死鎖相配套的一種措施，用于將進(jìn)程從死鎖狀態(tài)下解脫出來(lái)。常用的方法有： 1撤消進(jìn)程；最簡(jiǎn)單撤消進(jìn)程的方法是使全部死鎖的進(jìn)程夭折掉；另一方法是按照某種順序逐個(gè)地撤消進(jìn)程，直至有足夠的資源可用，死鎖狀態(tài)消除為止,2掛起進(jìn)程（剝奪資源）。使用掛起/激活機(jī)構(gòu)掛起一些進(jìn)程，剝奪它們的資源以解除死鎖，待條件滿足時(shí)，再激活進(jìn)程。目前掛起法比較受到重視。,50,1（北大95）一個(gè)OS有20個(gè)進(jìn)程，競(jìng)爭(zhēng)使用65個(gè)同類資源，申請(qǐng)方式是逐個(gè)進(jìn)行的，一旦某個(gè)進(jìn)程獲得它所需要的全部資源，則立即歸還所有資源。每個(gè)進(jìn)程最多使用三個(gè)資源。若僅考慮這類資源，該系統(tǒng)有無(wú)可能產(chǎn)生死鎖，為什么？ 2死鎖和饑餓的主要差別是什么？,例題,51,1 答：不可能。因?yàn)樗梨i產(chǎn)生的原因有兩點(diǎn)：系統(tǒng)資源不足或推進(jìn)順序不當(dāng)，在本題中，進(jìn)程所需的最大資源數(shù)為60，而系統(tǒng)共有該類資源65個(gè)，其資源數(shù)已足夠系統(tǒng)內(nèi)各進(jìn)程使用。 2 答：簡(jiǎn)言之，死鎖是某進(jìn)程等待一個(gè)不會(huì)發(fā)生的事件的一種現(xiàn)象；而饑餓現(xiàn)象是某進(jìn)程正等待這樣一個(gè)事件，它發(fā)生了但總是受到其它進(jìn)程的影響，以至輪不到（或很難輪到）該進(jìn)程。,52,銀行家算法的基本思想(1),系統(tǒng)中的所有進(jìn)程進(jìn)入進(jìn)程集合, 在安全狀態(tài)下系統(tǒng)收到進(jìn)程的資源請(qǐng)求后,先把資源試探性分配給它。 系統(tǒng)用剩下的可用資源和進(jìn)程集合中其他進(jìn)程還要的資源數(shù)作比較，在進(jìn)程集合中找到剩余資源能滿足最大需求量的進(jìn)程,從而,保證這個(gè)進(jìn)程運(yùn)行完畢并歸還全部資源。,53,銀行家算法的基本思想(2),把這個(gè)進(jìn)程從集合中去掉, 系統(tǒng)的剩余資源更多了,反復(fù)執(zhí)行上述步驟。 最后,檢查進(jìn)程集合,若為空表明本次申請(qǐng)可行,系統(tǒng)處于安全狀態(tài),可實(shí)施本次分配;否則,有進(jìn)程執(zhí)行不完，系統(tǒng)處于不安全狀態(tài),本次資源分配暫不實(shí)施,讓申請(qǐng)進(jìn)程等待。,54,3.7 死鎖的檢測(cè)與解除,1 資源分配圖和死鎖定理 2 借助于死鎖的安全性測(cè)試算法的死鎖檢測(cè) 3 warshall傳遞閉包算法的死鎖檢測(cè),55,簡(jiǎn)化進(jìn)程-資源分配圖檢測(cè)系統(tǒng)是否處于死鎖狀態(tài)(1),(1)如果進(jìn)程-資源分配圖中無(wú)環(huán)路，則此時(shí)系統(tǒng)沒有發(fā)生死鎖。 (2)如果進(jìn)程-資源分配圖中有環(huán)路，且每個(gè)資源類中僅有一個(gè)資源，則系統(tǒng)中發(fā)生了死鎖，此時(shí)，環(huán)路是系統(tǒng)發(fā)生死鎖的充要條件，環(huán)路中的進(jìn)程便為死鎖進(jìn)程。,56,簡(jiǎn)化進(jìn)程-資源分配圖檢測(cè)系統(tǒng)是否處于死鎖狀態(tài)(2),(3)如果進(jìn)程-資源分配圖中有環(huán)路，且涉及的資源類中有多個(gè)資源，則環(huán)路的存在只是產(chǎn)生死鎖的必要條件而不是充分條件。,57,簡(jiǎn)化進(jìn)程-資源分配圖檢測(cè)系統(tǒng)是否處于死鎖狀態(tài)