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

1、13.5產(chǎn)生死鎖的原因死鎖的原因和必要條件和必要條件2 3.8 3.8 死鎖問題死鎖問題在多道程序系統(tǒng)中，多個進程并發(fā)運行，共享資在多道程序系統(tǒng)中，多個進程并發(fā)運行，共享資源，從而提高了資源的利用率。但是若對資源源，從而提高了資源的利用率。但是若對資源的管理和使用不當(dāng)，在一定條件下會導(dǎo)致系統(tǒng)的管理和使用不當(dāng)，在一定條件下會導(dǎo)致系統(tǒng)發(fā)生一種隨機性故障發(fā)生一種隨機性故障死鎖。在一些系統(tǒng)中，死鎖。在一些系統(tǒng)中，比如實時控制系統(tǒng)，系統(tǒng)一旦發(fā)生死鎖將導(dǎo)致比如實時控制系統(tǒng)，系統(tǒng)一旦發(fā)生死鎖將導(dǎo)致災(zāi)難性的后果。災(zāi)難性的后果。33.8.1 死鎖的基本概念死鎖的基本概念資源死鎖的定義產(chǎn)生死鎖的原因產(chǎn)生死鎖的必要

2、條件處理死鎖的基本方法4資源的概念 os是計算機系統(tǒng)中資源的管理者，而進是計算機系統(tǒng)中資源的管理者，而進程是競爭資源的基本單位，故對系統(tǒng)中程是競爭資源的基本單位，故對系統(tǒng)中所有進程的資源分配工作，都由所有進程的資源分配工作，都由os完成。完成。 研究資源分配時，我們必須搞清該資源研究資源分配時，我們必須搞清該資源是可以被幾個進程同時使用，還是只能是可以被幾個進程同時使用，還是只能為一個進程使用，資源的不同使用性質(zhì)為一個進程使用，資源的不同使用性質(zhì)正是引起系統(tǒng)死鎖的原因。正是引起系統(tǒng)死鎖的原因。 5 根據(jù)資源性質(zhì)：可剝奪（搶占）和不可剝奪根據(jù)資源性質(zhì)：可剝奪（搶占）和不可剝奪（搶占）資源。（搶占

3、）資源。 可搶占資源可搶占資源指資源占有進程雖然需要使用該指資源占有進程雖然需要使用該資源，但另一個進程卻強行把資源從占有者進資源，但另一個進程卻強行把資源從占有者進程處搶來。程處搶來。 不可搶占資源不可搶占資源指只有占用者進程不再需要使指只有占用者進程不再需要使用該資源而主動釋放資源外，其它進程不得在用該資源而主動釋放資源外，其它進程不得在占有者進程使用資源過程中強行搶占。占有者進程使用資源過程中強行搶占。資源的分類6 根據(jù)使用方式：共享資源和獨享資源。根據(jù)使用方式：共享資源和獨享資源。根據(jù)使用期限；根據(jù)使用期限；永久資源永久資源和和臨時性資源臨時性資源。資源資源cpu、主存、硬盤，該類資源

4、可為幾個進程、主存、硬盤，該類資源可為幾個進程共同使用（可搶占）共同使用（可搶占）打印機，讀卡機，磁帶驅(qū)動器，可為某個進打印機，讀卡機，磁帶驅(qū)動器，可為某個進程獨享（不可搶占）程獨享（不可搶占）可順序重復(fù)使用的資源由一個進程產(chǎn)生，被另外一個進程使用短暫時間之后便無用的資源7死鎖的定義 死鎖死鎖deadlock：是計算機系統(tǒng)中多道程序并發(fā)：是計算機系統(tǒng)中多道程序并發(fā)執(zhí)行時，兩個或兩個以上的進程由于競爭資源執(zhí)行時，兩個或兩個以上的進程由于競爭資源而造成的一種互相等待的現(xiàn)象（僵局），如無而造成的一種互相等待的現(xiàn)象（僵局），如無外力作用，這些進程將永遠(yuǎn)不能再向前推進。外力作用，這些進程將永遠(yuǎn)不能再向前

5、推進。 陷入死鎖狀態(tài)的進程稱為陷入死鎖狀態(tài)的進程稱為死鎖進程死鎖進程，所占用的，所占用的資源或者需要它們進行某種合作的其它進程就資源或者需要它們進行某種合作的其它進程就會相繼陷入死鎖，最終可能導(dǎo)致整個系統(tǒng)處于會相繼陷入死鎖，最終可能導(dǎo)致整個系統(tǒng)處于癱瘓狀態(tài)。癱瘓狀態(tài)。 8產(chǎn)生死鎖的原因 1 競爭資源競爭資源。當(dāng)系統(tǒng)中供多個進程所共享的資。當(dāng)系統(tǒng)中供多個進程所共享的資源，不足以同時滿足它們的需要時，引起它們源，不足以同時滿足它們的需要時，引起它們對資源的競爭而產(chǎn)生死鎖；對資源的競爭而產(chǎn)生死鎖； 2 進程推進的順序不當(dāng)進程推進的順序不當(dāng) 。進程在運行過程中，。進程在運行過程中，請求和釋放資源的順序

6、不當(dāng)，導(dǎo)致進程的死鎖。請求和釋放資源的順序不當(dāng)，導(dǎo)致進程的死鎖。 9競爭資源1 競爭非剝奪性資源：2 競爭臨時性資源打印機r1磁帶機r2p1p210p1s1s3p2p3s2p1：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是臨時資源11 若干死鎖的例子(1) 例進程推進順序不當(dāng)產(chǎn)生死鎖 設(shè)系統(tǒng)有

7、打印機、讀卡機各一臺，被進程和共享。兩個進程并發(fā)執(zhí)行，按下列次序請求和釋放資源： 進程 進程 請求讀卡機 請求打印機 請求打印機 請求讀卡機 釋放讀卡機 釋放讀卡機 釋放打印機 釋放打印機 12p2rel(r1)p2rel(r2)p2req(r1)p2req(r2)p1req(r1) p1req(r2) p1rel(r1) p1rel(r2)進程p1、p2并發(fā)執(zhí)行。資源r1、r2曲線4將進入不安全區(qū)域（進程推進順序非法）13死鎖模型死鎖模型r1r2p1p2申請r2已分配給p2申請r1已分配給p1r2已經(jīng)分配給p1、r1已經(jīng)分配給p214產(chǎn)生死鎖的四個必要條件互斥條件互斥條件: :進程訪問的是臨

8、界資源，那個資源進程訪問的是臨界資源，那個資源一次只能被一個進程所使用。一次只能被一個進程所使用。不剝奪條件不剝奪條件: :一個資源僅能被占有它的進程所一個資源僅能被占有它的進程所釋放，而不能被其他進程剝奪。釋放，而不能被其他進程剝奪。部分分配部分分配: :（請求和保持條件）一個進程在請（請求和保持條件）一個進程在請求新的資源的同時，保持對某些資源的占有。求新的資源的同時，保持對某些資源的占有。環(huán)路等待條件環(huán)路等待條件: :存在一個進程的環(huán)路鏈，鏈中存在一個進程的環(huán)路鏈，鏈中每一個進程占用有著某個或某些資源，又在等每一個進程占用有著某個或某些資源，又在等待鏈中的另一個進程占有的資源待鏈中的另一

9、個進程占有的資源。15若干死鎖的例子(2)例 pv操作使用不當(dāng)產(chǎn)生死鎖 進程q1 進程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個資源被n個進程共享，每個進程都要求個資源，而m nk時，即資源數(shù)小于進程所要求的總數(shù)時，如果分配不得當(dāng)就可能引起死鎖。 17若干死鎖的例子(4)例對臨時性資源使用不加限制引起死鎖 進程通信使用的信件是一種臨時性資源，如果對信件的發(fā)送和接收不加限制，可能引起死鎖。 進程p1等待進程p3的信件s3來到

10、后再向進程p2發(fā)送信件s1；p2又要等待p1的信件s1來到后再向p3發(fā)送信件s2；而p3也要等待p2的信件s2來到后才能發(fā)出信件s3。這種情況下形成了循環(huán)等待，產(chǎn)生死鎖。 183.6預(yù)防死鎖的方法 破壞第一個條件破壞第一個條件 使資源可同時訪問而不是互斥使用，是個簡單的辦法，磁盤可用這種辦法管理,但有許多資源往往是不能同時訪問，所以這種做法許多場合行不通。19死鎖防止 破壞第二個條件或第四個條件破壞第二個條件或第四個條件 種種死鎖防止辦法施加于資源的限制條件太嚴(yán)格,會造成資源利用率和吞吐率低。兩種比較實用的死鎖防止方法，它們能破壞第二個條件或第四個條件。20死鎖防止1.摒棄”請求和保持”靜態(tài)分

11、配策略（破壞條件2） 靜態(tài)分配是指一個進程必須靜態(tài)分配是指一個進程必須在執(zhí)行前就申請它所要的全部在執(zhí)行前就申請它所要的全部資源，并且直到它所要的資源資源，并且直到它所要的資源都得到滿足后才開始執(zhí)行。都得到滿足后才開始執(zhí)行。 21死鎖防止2.摒棄”不剝奪”條件破壞第三個條件 采用剝奪式調(diào)度方法可破壞第三個條件，但只適用于對主存資源和處理器資源的分配， 當(dāng)進程在申請資源未獲準(zhǔn)許的情況下,如主動釋放資源(一種剝奪式),然后才去等待，以后再一起向系統(tǒng)提出申請,也能防止死鎖。 22死鎖的防止3.摒棄”環(huán)路等待”條件層次分配策略（破壞條件2和4） 資源被分成多個層次資源被分成多個層次 當(dāng)進程得到某一層的一

12、個資源后，它當(dāng)進程得到某一層的一個資源后，它只能再申請較高層次的資源只能再申請較高層次的資源 當(dāng)進程要釋放某層的一個資源時，必當(dāng)進程要釋放某層的一個資源時，必須先釋放占有的較高層次的資源須先釋放占有的較高層次的資源 當(dāng)進程得到某一層的一個資源后，它當(dāng)進程得到某一層的一個資源后，它想申請該層的另一個資源時，必須先想申請該層的另一個資源時，必須先釋放該層中的已占資源釋放該層中的已占資源23死鎖防止層次層次策略的變種按序分配策略 把系統(tǒng)的所有資源排一個順序，例如，系統(tǒng)若共有n個進程,共有m個資源，用ri表示第i個資源，于是這m個資源是：r1,r2,rm 規(guī)定如果進程不得在占用資源ri(1im)后再申

13、請rj(ji)。不難證明，按這種策略分配資源時系統(tǒng)不會發(fā)生死鎖。 24 2 2 預(yù)防死鎖預(yù)防死鎖根據(jù)生產(chǎn)死鎖的四個必要條件，只要使用其中之根據(jù)生產(chǎn)死鎖的四個必要條件，只要使用其中之一不能成立，死鎖就不會出現(xiàn)。一不能成立，死鎖就不會出現(xiàn)。但必要條件但必要條件是由設(shè)備的固有特性所決定的，不僅不能改變，是由設(shè)備的固有特性所決定的，不僅不能改變，相反還應(yīng)加以保證，因此實際上只相反還應(yīng)加以保證，因此實際上只有三種方法。有三種方法。 預(yù)防死鎖是一種較易實現(xiàn)的方法，已被廣泛預(yù)防死鎖是一種較易實現(xiàn)的方法，已被廣泛使用，但由于所施加的限制條件往往太嚴(yán)格，使用，但由于所施加的限制條件往往太嚴(yán)格，可能導(dǎo)致系統(tǒng)資源利

14、用率和系統(tǒng)吞吐量降低?？赡軐?dǎo)致系統(tǒng)資源利用率和系統(tǒng)吞吐量降低。1 互斥條件2 請求和保持條件3 不剝奪條件4 環(huán)路等待條件251:1:防止部分分配（摒棄請求和保持條件）防止部分分配（摒棄請求和保持條件） 系統(tǒng)要求任一進程必須預(yù)先申請它所需的系統(tǒng)要求任一進程必須預(yù)先申請它所需的全部資源，而且僅當(dāng)該進程的全部資源要求能全部資源，而且僅當(dāng)該進程的全部資源要求能得到滿足時，系統(tǒng)才能給予一次性分配，然后得到滿足時，系統(tǒng)才能給予一次性分配，然后啟動該進程運行，但是在分配時只要由一種資啟動該進程運行，但是在分配時只要由一種資源不滿足，系統(tǒng)就不會給進程分配資源。進程源不滿足，系統(tǒng)就不會給進程分配資源。進程運行

15、期間，不會再請求新的資源，所以，再分運行期間，不會再請求新的資源，所以，再分配就不會發(fā)生（摒棄了部分分配）。配就不會發(fā)生（摒棄了部分分配）。特點：資源嚴(yán)重浪費特點：資源嚴(yán)重浪費 進程延遲進行進程延遲進行26 3 3 防止防止“不剝奪不剝奪”條件的出現(xiàn)條件的出現(xiàn) 采用的策略：采用的策略：一個已經(jīng)保持了某些資源的進程，一個已經(jīng)保持了某些資源的進程，當(dāng)它再提出新的資源要求而不能立即得到滿足當(dāng)它再提出新的資源要求而不能立即得到滿足時，必須釋放它已經(jīng)保持的所有資源，待以后時，必須釋放它已經(jīng)保持的所有資源，待以后需要時再重新申請。需要時再重新申請。 實現(xiàn)比較復(fù)雜，且要付出很大代價；此外，還實現(xiàn)比較復(fù)雜，且

16、要付出很大代價；此外，還因為反復(fù)地申請和釋放資源，而使進程的執(zhí)行因為反復(fù)地申請和釋放資源，而使進程的執(zhí)行無限地推遲，延長了周轉(zhuǎn)時間，增加了系統(tǒng)的無限地推遲，延長了周轉(zhuǎn)時間，增加了系統(tǒng)的開銷，降低了系統(tǒng)吞吐量。（例如打印機打印開銷，降低了系統(tǒng)吞吐量。（例如打印機打印的結(jié)果不連續(xù)）的結(jié)果不連續(xù)）272.2.防止防止“環(huán)路等待環(huán)路等待”條件的出現(xiàn)。條件的出現(xiàn)。 采用資源順序使用法，基本思想是：把系統(tǒng)中所有資采用資源順序使用法，基本思想是：把系統(tǒng)中所有資源類型線性排隊，并按遞增規(guī)則賦予每類資源以唯一源類型線性排隊，并按遞增規(guī)則賦予每類資源以唯一的編號。例如輸入機的編號。例如輸入機1 1，打印機，打印機

17、2 2，磁帶機，磁帶機3 3，磁，磁盤盤4 4等等。進程申請資源時，必須嚴(yán)格按資源編號的等等。進程申請資源時，必須嚴(yán)格按資源編號的遞增順序進行，否則系統(tǒng)不予分配。遞增順序進行，否則系統(tǒng)不予分配。優(yōu)點：資源利用率和系統(tǒng)吞吐量與另兩種方法相比有較優(yōu)點：資源利用率和系統(tǒng)吞吐量與另兩種方法相比有較明顯的改善。明顯的改善。缺點：缺點： 1 為系統(tǒng)中各種類型的資源所分配的序號必須相對穩(wěn)為系統(tǒng)中各種類型的資源所分配的序號必須相對穩(wěn)定，這就限制了新設(shè)備類型的增加定，這就限制了新設(shè)備類型的增加 2 作業(yè)實際使用資源的順序與系統(tǒng)規(guī)定的順序不同而作業(yè)實際使用資源的順序與系統(tǒng)規(guī)定的順序不同而造成資源的浪費；造成資源的

18、浪費； 283 3 死鎖避免死鎖避免避免死鎖與預(yù)防死鎖的區(qū)別在于，預(yù)防死鎖是設(shè)避免死鎖與預(yù)防死鎖的區(qū)別在于，預(yù)防死鎖是設(shè)法至少破壞產(chǎn)生死鎖的必要條件之一，嚴(yán)格地法至少破壞產(chǎn)生死鎖的必要條件之一，嚴(yán)格地防止死鎖的出現(xiàn)。防止死鎖的出現(xiàn)。 避免死鎖，它是在進程請求分配資源避免死鎖，它是在進程請求分配資源時，采用銀行家算法等防止系統(tǒng)進入不時，采用銀行家算法等防止系統(tǒng)進入不安全狀態(tài)。安全狀態(tài)。29 在資源的動態(tài)分配的過程中，使用某種方法去防止系統(tǒng)進入不安全狀態(tài)，從而避免死鎖的發(fā)生。 系統(tǒng)狀態(tài)： 安全狀態(tài)：指系統(tǒng)能按照某種順序如(稱為序列為安全序列)，為每個進程分配所需的資源，直至最大需求，使得每個進程都

19、能順利完成。 非安全狀態(tài)：即在某個時刻系統(tǒng)中不存在一個安全序列，則稱系統(tǒng)處于不安全狀態(tài)或非安全狀態(tài)。 30 雖然并非所有不安全狀態(tài)都是死鎖狀態(tài)，但當(dāng)系統(tǒng)進入不安全狀態(tài)后，便有可能進入死鎖狀態(tài)；反之只要系統(tǒng)處于安全狀態(tài)，系統(tǒng)便可避免進入死鎖狀態(tài)。因此，避免死鎖的實質(zhì)是如何使系統(tǒng)不進入不安全狀態(tài)。 31安全狀態(tài)的例子例：假定系統(tǒng)有三個進程p1、p2、p3，共有12臺磁帶機。進程p1總共要求10臺磁帶機，p2和p3分別要求4臺和九臺。設(shè)在t0時刻，進程p1、p2和p3已經(jīng)獲得5臺、2臺和2臺，還有3臺空閑沒有分配。進程最大需求已分配可用p11053p2p34229t0時刻系統(tǒng)時安全的。這時存在一個安

20、全序列32安全狀態(tài)的例子例：假定系統(tǒng)有三個進程p1、p2、p3，共有12臺磁帶機。進程p1總共要求10臺磁帶機，p2和p3分別要求4臺和九臺。設(shè)在t0時刻，進程p1、p2和p3已經(jīng)獲得5臺、2臺和2臺，還有3臺空閑沒有分配。進程最大需求已分配可用p11053p2p34229t0時刻系統(tǒng)時安全的。這時存在一個安全序列33 雖然并非所有不安全狀態(tài)都是死鎖狀態(tài)，但當(dāng)系統(tǒng)進入不安全狀態(tài)后，便有可能進入死鎖狀態(tài)；反之只要系統(tǒng)處于安全狀態(tài)，系統(tǒng)便可避免進入死鎖狀態(tài)。因此，避免死鎖的實質(zhì)是如何使系統(tǒng)不進入不安全狀態(tài)。 系統(tǒng)的狀態(tài)可能通過下述來描述：系統(tǒng)的狀態(tài)可能通過下述來描述： 進程剩余申請數(shù)最大申請數(shù)占有

21、數(shù)。進程剩余申請數(shù)最大申請數(shù)占有數(shù)。 可分配資源數(shù)總數(shù)占有數(shù)之和?？煞峙滟Y源數(shù)總數(shù)占有數(shù)之和。 343.6.3利用銀行家算法避免死鎖 銀行家算法銀行家算法 銀行家擁有一筆周轉(zhuǎn)資金銀行家擁有一筆周轉(zhuǎn)資金 客戶要求分期貸款，如果客戶能夠得到各客戶要求分期貸款，如果客戶能夠得到各期貸款，就一定能夠歸還貸款，否則就一期貸款，就一定能夠歸還貸款，否則就一定不能歸還貸款定不能歸還貸款 銀行家應(yīng)謹(jǐn)慎的貸款，防止出現(xiàn)壞帳銀行家應(yīng)謹(jǐn)慎的貸款，防止出現(xiàn)壞帳 用銀行家算法避免死鎖用銀行家算法避免死鎖 操作系統(tǒng)（銀行家）操作系統(tǒng)（銀行家） 操作系統(tǒng)管理的資源操作系統(tǒng)管理的資源( (周轉(zhuǎn)資金周轉(zhuǎn)資金) ) 進程（要求貸

22、款的客戶）進程（要求貸款的客戶） 35銀行家算法銀行家算法 銀行家算法是最有代表性的避免死鎖算法，是dijkstra提出的銀行家算法。這是由于該算法能用于銀行系統(tǒng)現(xiàn)金貸款的發(fā)放而得名。為實現(xiàn)銀行家算法，系統(tǒng)中必須設(shè)置若干數(shù)據(jù)結(jié)構(gòu)。36 一、銀行家算法中的數(shù)據(jù)結(jié)構(gòu) 1 可利用資源向量available 是一個含有m個元素，其中的每一個元素代表一類可利用的資源數(shù)目，其初值是系統(tǒng)中所配 置 的 該 類 全 部 可 用 資 源 數(shù) 目 。 如 果availablej=k， 表示系統(tǒng)中現(xiàn)有rj類資源k個。 2 最大需求矩陣max 是一個含有nm的矩陣，它定義了系統(tǒng)中n個進程中的每一個進程對m類資源的最大

23、需求。如果max(i,j)=k， 表示進程i需要rj類資源的最大數(shù)目為k。available= 3 5 4 2 8 3 8 6 137 3 分配矩陣allocation 是一個含有nm的矩陣，它定義了系統(tǒng)中每一類資源當(dāng)前已分配給每一進程的資源數(shù)。如果allocation(i,j)=k， 表示進程i當(dāng)前已分得rj類資源k個。 4 需求矩陣need 是一個含有nm的矩陣，用以表示每一個進程尚需的各類資源數(shù)。如果need(i,j)=k， 表示進程i還需要rj類資源k個，方能完成其任務(wù)。 need(i,j)= max(i,j)-allocation(i,j) 38 二、銀行家算法 設(shè)requesti是

24、進程pi的請求向量，如果進程pi需要k個rj類資源，當(dāng)pi發(fā)出資源請求后，系統(tǒng)按下述步驟進行檢查：1 如果requestineedi,則轉(zhuǎn)向步驟2；否則認(rèn)為出錯。（因為它所需要的資源數(shù)已超過它所宣布的最大值。2如果requestiavailable,則轉(zhuǎn)向步驟3；否則，表示系統(tǒng)中尚無足夠的資源，pi必須等待3 系統(tǒng)試探把要求的資源分配給進程pi，并修改下面數(shù)據(jù)結(jié)構(gòu)中的數(shù)值：available:=available-requesti;allocation:=allocation+requesti;needi:= needi- requesti; 4 系統(tǒng)執(zhí)行安全性算法，檢查此次資源分配后，系統(tǒng)是

25、否處于安全狀態(tài)。若安全，正式將資源分配給進程pi，以完成本次分配；否則，將試探分配作廢，恢復(fù)原來的資源分配狀態(tài)，讓進程pi等待。 39三、安全性算法系統(tǒng)所執(zhí)行的安全性算法可描述如下：1 設(shè)置兩個向量工作向量work.它表示系統(tǒng)可提供給進程繼續(xù)運行所需要的各類資源 的 數(shù) 目 ， 它 含 有 m 個 元 素 ， 執(zhí) 行 安 全 算 法 開 始 時 ，work:=available。finish.它表示系統(tǒng)是否有足夠的資源分配給進程，使之運行完成。開始時先做finishi:=false；當(dāng)有足夠的資源分配給進程時，令finishi:=true.2 從 進 程 集 合 中 找 到 一 個 能 滿 足

26、 下 述 條 件 的 進 程 ：finishi=false; neediwork. 如找到，執(zhí)行步驟3；否則執(zhí)行步驟4。3 當(dāng)進程pi獲得資源后，可順利執(zhí)行，直至完成，并釋放出分配給它的資源，故執(zhí)行：work:=work+allocation;finishi:=true;goto step2;4 如果所有進程的finishi=true，則表示系統(tǒng)處于安全狀態(tài)；否則，系統(tǒng)處于不安全狀態(tài)。 40要記住的一些變量的名稱 1 available（可利用資源向量） 某類可利用的資源數(shù)目，其初值是系統(tǒng)中所配置的該類全部可用資源數(shù)目。 2 max最大需求矩陣某個進程對某類資源的最大需求數(shù) 3 allocat

27、ion分配矩陣 某類資源當(dāng)前非配給某進程的資源數(shù)。4 need需求矩陣 某個進程還需要的各類資源數(shù)。 need= max-allocation系統(tǒng)把進程請求的資源分配給它以后要修改的變量available:=available-request;allocation:=allocation+request;need:= need- request;41銀行家算法之例 假定系統(tǒng)中有五個進程p0、p1、p2、p3、p4和三種類型的資源a，b，c，每一種資源的數(shù)量分別為10、5、7，在t0時刻的資源分配情況如圖資源情況進程allocationa b cmaxa b cneeda b cavailabl

28、ea b cp0p1p2p3p40 1 03 2 29 0 22 2 24 3 32 0 0( 3 0 2 )3 0 22 1 10 0 27 4 31 2 2( 0 2 0 )60 00 1 14 3 13 3 2( 2 3 0 )423 3 21 2 22 0 0資源情況資源情況進程進程allocationa b cmaxa b cneeda b cavailablea b cp0p1p2p3p40 1 03 2 29 0 22 2 24 3 32 0 0( 3 0 2 )3 0 22 1 10 0 27 4 31 2 2( 0 2 0 )6 0 00 1 14 3 13 3 2( 2 3

29、 0 )7 5 3資源情況資源情況進程進程needa b cworka b cworkallocationa b callocationa b cp1p3p4p2p0finish5 3 2truetruetruetruetrue0 1 12 1 15 3 27 4 37 4 34 3 10 0 27 4 57 4 56 0 03 0 210 4 710 4 77 4 30 1 010 5 7最大值已分配還需要可用若p1發(fā)出請求向量request（1，0，2）工作向量work.它表示系統(tǒng)可提供給進程繼續(xù)運行所需要的各類資源的數(shù)目10,5 743思考和練習(xí)假定系統(tǒng)中有五個進程p0、p1、p2、p3

30、、p4和三種類型的資源a，b，c，每一種資源的數(shù)量分別為10、5、7，在t0時刻的資源分配情況如圖請找出該表中t0時刻以后存在的安全序列（至少2種）資源情況資源情況進程進程allocationa b cmaxa b cneeda b cavailablea b cp0p1p2p3p40 1 03 2 29 0 22 2 24 3 32 0 03 0 22 1 10 0 27 4 31 2 26 0 00 1 14 3 13 3 27 5 344 3 3 死鎖的檢測和恢復(fù)死鎖的檢測和恢復(fù) 死鎖的檢測和恢復(fù)技術(shù)是指定期啟動死鎖的檢測和恢復(fù)技術(shù)是指定期啟動一個軟件檢測系統(tǒng)的狀態(tài)，若發(fā)現(xiàn)有死一個軟件檢

31、測系統(tǒng)的狀態(tài)，若發(fā)現(xiàn)有死鎖存在，則采取措施恢復(fù)之。鎖存在，則采取措施恢復(fù)之。 (1)(1)死鎖的檢測死鎖的檢測 檢查死鎖的辦法就是由軟件檢查系統(tǒng)檢查死鎖的辦法就是由軟件檢查系統(tǒng)中由進程和資源構(gòu)成的有向圖是否構(gòu)成中由進程和資源構(gòu)成的有向圖是否構(gòu)成一個或多個環(huán)路，若是，則存在死鎖，一個或多個環(huán)路，若是，則存在死鎖，否則不存在。否則不存在。45 死鎖的檢測：實質(zhì)是確定是否存在環(huán)路等待現(xiàn)象，一旦發(fā)現(xiàn)這種環(huán)路便認(rèn)定死鎖存在，并識別出該環(huán)路所涉及的有關(guān)進程，以供系統(tǒng)采取適當(dāng)?shù)拇胧﹣斫獬梨i。最常用的是一種基于資源分配圖rag和死鎖定理的檢測死鎖算法。46資源分配圖（rag）系統(tǒng)死鎖可用資源分配圖來描述，該

32、圖是由一組結(jié)點n和一組邊e所組成的一對偶g=(n,e)。（用圓圈代表一個進程，用方框代表一類資源，由于一種類型的資源可能有多個，可用方框中的一個點代表一類資源中的一個資源）幾個概念：請求邊，分配邊 p1p2r1r2請求r2資源分配圖47 封鎖進程：是指某個進程由于請求了超過了系統(tǒng)中現(xiàn)有的未分配資源數(shù)目的資源，而被系統(tǒng)封鎖的進程。 非封鎖進程：即沒有被系統(tǒng)封鎖的進程資源分配圖的化簡方法：假設(shè)某個rag中存在一個進程pi，此刻pi是非封鎖進程，那么可以進行如下化簡：當(dāng)pi有請求邊時，首先將其請求邊變成分配邊(即滿足pi的資源請求)，而一旦pi的所有資源請求都得到滿足，pi就能在有限的時間內(nèi)運行結(jié)束

33、，并釋放其所占用的全部資源，此時pi只有分配邊，刪去這些分配邊（實際上相當(dāng)于消去了pi的所有請求邊和分配邊），使pi成為孤立結(jié)點。（反復(fù)進行） 。48死鎖定理： 系統(tǒng)中某個時刻s為死鎖狀態(tài)的充要條件是s時刻系統(tǒng)的資源分配圖是不可完全簡化的。 在經(jīng)過一系列的簡化后，若能消去圖中的所有邊，使所有的進程都成為孤立結(jié)點，則稱該圖是可完全簡化的；反之的是不可完全簡化的。p1p2r1r2p1p2r1r2p1p2r1r249 死鎖的恢復(fù)。是與檢測死鎖相配套的一種措施，用于將進程從死鎖狀態(tài)下解脫出來。常用的方法有： 1撤消進程；最簡單撤消進程的方法是使全部死鎖的進程夭折掉；另一方法是按照某種順序逐個地撤消進程

34、，直至有足夠的資源可用，死鎖狀態(tài)消除為止2掛起進程（剝奪資源）。使用掛起/激活機構(gòu)掛起一些進程，剝奪它們的資源以解除死鎖，待條件滿足時，再激活進程。目前掛起法比較受到重視。50 1（北大95）一個os有20個進程，競爭使用65個同類資源，申請方式是逐個進行的，一旦某個進程獲得它所需要的全部資源，則立即歸還所有資源。每個進程最多使用三個資源。若僅考慮這類資源，該系統(tǒng)有無可能產(chǎn)生死鎖，為什么？ 2死鎖和饑餓的主要差別是什么？例題例題51 1 答：不可能。因為死鎖產(chǎn)生的原因有兩點：系統(tǒng)資源不足或推進順序不當(dāng)，在本題中，進程所需的最大資源數(shù)為60，而系統(tǒng)共有該類資源65個，其資源數(shù)已足夠系統(tǒng)內(nèi)各進程使

35、用。 2 答：簡言之，死鎖是某進程等待一個不會發(fā)生的事件的一種現(xiàn)象；而饑餓現(xiàn)象是某進程正等待這樣一個事件，它發(fā)生了但總是受到其它進程的影響，以至輪不到（或很難輪到）該進程。 52銀行家算法的基本思想(1) 系統(tǒng)中的所有進程進入進程集合, 在安全狀態(tài)下系統(tǒng)收到進程的資源請求后,先把資源試探性分配給它。 系統(tǒng)用剩下的可用資源和進程集合中其他進程還要的資源數(shù)作比較，在進程集合中找到剩余資源能滿足最大需求量的進程,從而,保證這個進程運行完畢并歸還全部資源。53銀行家算法的基本思想(2) 把這個進程從集合中去掉, 系統(tǒng)的剩余資源更多了,反復(fù)執(zhí)行上述步驟。 最后,檢查進程集合,若為空表明本次申請可行,系統(tǒng)處于安全狀態(tài),可實施本次分配;否則,有進程執(zhí)行不完，系統(tǒng)處于不安全狀態(tài),本次資源分配暫不實施,讓申請進程等待。 543.7 死鎖的檢測與解除1 資源分配圖和死鎖定理2 借助于死鎖的安全性測試算法的死鎖檢測3 warshall傳遞閉包算法的死