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

1、 死鎖的定義死鎖的定義 死鎖的描述死鎖的描述 死鎖的預(yù)防和避免死鎖的預(yù)防和避免 死鎖的檢測死鎖的檢測 死鎖的解除死鎖的解除一、死鎖定義一、死鎖定義死鎖定義：死鎖定義： 多個進程由于競爭資源（或者等待對多個進程由于競爭資源（或者等待對方消息）而造成的彼此無休止的互相等待，方消息）而造成的彼此無休止的互相等待，在無外力作用下，永遠不能向前推進，這在無外力作用下，永遠不能向前推進，這種僵持局面稱為死鎖。種僵持局面稱為死鎖。（也可以敘述為：一組進程處于死鎖狀態(tài)，（也可以敘述為：一組進程處于死鎖狀態(tài)，僅當這組中的每一進程都在等待一個事件，僅當這組中的每一進程都在等待一個事件，且這個事件僅被同組中的另一進

2、程所引發(fā)）且這個事件僅被同組中的另一進程所引發(fā)）例子：設(shè)有進程例子：設(shè)有進程P1P1、P2P2和和I/OI/O設(shè)備設(shè)備D DI I、D DO O P1 P2 P1 P2申請一臺輸入設(shè)備申請一臺輸入設(shè)備D DI I 申請一臺輸出設(shè)備申請一臺輸出設(shè)備D DO O 使用之使用之 釋放輸入設(shè)備釋放輸入設(shè)備D DI I 釋放輸出設(shè)備釋放輸出設(shè)備D DO O 申請一臺輸出設(shè)備申請一臺輸出設(shè)備D DO O申請一臺輸入設(shè)備申請一臺輸入設(shè)備D DI I使用之使用之釋放輸出設(shè)備釋放輸出設(shè)備D DO O釋放輸入設(shè)備釋放輸入設(shè)備D DI I例子：哲學(xué)家用餐問題例子：哲學(xué)家用餐問題定義信號量定義信號量 fork5: s

3、emaphorefork5: semaphore，初值均為，初值均為1 1。PROCESS Pibegin L1: 思考思考; P(fork i ); P(fork ( i +1 ) mod 5 ; 用餐用餐; V(fork i ); V(fork ( i +1 ) mod 5 ; goto L1;end;例子：生產(chǎn)者例子：生產(chǎn)者 消費者問題消費者問題（多緩沖區(qū)）（多緩沖區(qū)）定義：整型變量：定義：整型變量：k = 0, t = 0k = 0, t = 0 整型數(shù)組：整型數(shù)組：B0n-1B0n-1 信號量：信號量：SP = n, SG = 0 SP = n, SG = 0 PROCESS Pro

4、ducerbegin L1: produce a product; P(SP); Bk := product; k := (k + 1) mod n; V(SG); goto L1endPROCESS Consumerbegin L2: P(SG); Take a product form Bt; t := (t + 1) mod n V(SP); consumer; goto L2end能否這樣改寫：能否這樣改寫：定義：信號量：定義：信號量：mutex=1, empty=n full=0;mutex=1, empty=n full=0; PROCESS Producerbegin L1: p

5、roduce a product; P(mutex); P(empty); 送一個產(chǎn)品到有界緩沖區(qū)送一個產(chǎn)品到有界緩沖區(qū); k := (k + 1) mod n; V(mutex); V(full); goto L1endPROCESS Producerbegin L1: produce a product; P(mutex); P(empty); 送一個產(chǎn)品到有界緩沖區(qū)送一個產(chǎn)品到有界緩沖區(qū); k := (k + 1) mod n; V(mutex); V(full); goto L1end當緩沖區(qū)滿時，生產(chǎn)者仍可順利執(zhí)行p(mutex)操作，于是它對緩沖區(qū)有控制權(quán)，然后，當它執(zhí)行p(emp

6、ty)時，由于沒有空緩沖區(qū)被掛起。能將這個生產(chǎn)者釋放的是有一個消費者從緩沖區(qū)中取走一個產(chǎn)品，并執(zhí)行v(empty)操作，但由于緩沖區(qū)已被生產(chǎn)者占用，出現(xiàn)了死鎖。出現(xiàn)了死鎖。死鎖的必要條件：死鎖的必要條件：互斥：資源是獨占的且排它使用（至少有一個資源處互斥：資源是獨占的且排它使用（至少有一個資源處于非共享方式）；于非共享方式）；占用并等待：已獲得資源未獲釋放，又有新的申請請占用并等待：已獲得資源未獲釋放，又有新的申請請求（至少存在一個進程，它至少占用一個以上的資源并求（至少存在一個進程，它至少占用一個以上的資源并等待得到另外的被其它進程占用的資源）；等待得到另外的被其它進程占用的資源）；非搶占：

7、進程已獲得的資源只能由它自己釋放，不允非搶占：進程已獲得的資源只能由它自己釋放，不允許剝奪（資源不可搶占）；許剝奪（資源不可搶占）；循環(huán)等待：在發(fā)生死鎖時，必然存在一個進程資循環(huán)等待：在發(fā)生死鎖時，必然存在一個進程資源的環(huán)形鏈，即前一個進程保持后一個進程所申請的資源的環(huán)形鏈，即前一個進程保持后一個進程所申請的資源（存在一組等待進程源（存在一組等待進程PP0 0，P P1 1，P Pn n ，其中，其中P P0 0要等要等待待P P1 1占用的資源，占用的資源，P P1 1等待等待P P2 2占用的資源，占用的資源，P Pn n等待等待P P0 0占占用的資源）。用的資源）。二、死鎖的描述（資源

8、分配圖方法）二、死鎖的描述（資源分配圖方法）死鎖的一種描述方法資源分配圖：死鎖的一種描述方法資源分配圖：資源分配圖定義為資源分配圖定義為G G（V V，E E），其中），其中V V是頂點集，是頂點集，E E是邊集。是邊集。頂點集分兩類：集合頂點集分兩類：集合SpSpPP1 1,P,P2 2,P,Pn n 包括系統(tǒng)中所有進包括系統(tǒng)中所有進程，集合程，集合SrSrRR1 1,R,R1 1,R,Rm m 包括系統(tǒng)中的所有資源。邊集包括系統(tǒng)中的所有資源。邊集E E中的每個元素均為有序?qū)Γㄖ械拿總€元素均為有序?qū)Γ≒ Pi i,R,Rj j）或（）或（R Rj j,P,Pi i）。若（）。若（P Pi i

9、,R,Rj j）EE說明進程說明進程P Pi i正等待系統(tǒng)分配資源正等待系統(tǒng)分配資源R Rj j，此邊稱作請求邊；，此邊稱作請求邊；若（若（R Rj j,P,Pi i）EE說明資源說明資源R Rj j的一個示例已分配給了進程的一個示例已分配給了進程P Pi i，此邊稱作分配邊。此邊稱作分配邊。R R1 1R R2 2P P1 1P P2 2R R1 1R R3 3R R2 2P P3 3P P2 2P P1 1p2p1p3r4r2r3r1有死鎖的資源分配圖有死鎖的資源分配圖p2p1p3r4r2r3r1p1 r1 p2 r3 p3 r2 p1有環(huán)路但沒有死鎖的資源分配圖有環(huán)路但沒有死鎖的資源分配

10、圖 P1P3P2r2死鎖產(chǎn)生的原因：死鎖產(chǎn)生的原因：競爭資源引起死鎖競爭資源引起死鎖可剝奪和非剝奪性資源可剝奪和非剝奪性資源競爭非剝奪性資源競爭非剝奪性資源競爭臨時性資源競爭臨時性資源P1P2r1r2P1：; Release(S1); Request(S3); P2：; Release(S2); Request(S1); P3：; Release(S3); Request(S2); 不會發(fā)生死鎖不會發(fā)生死鎖P1：; Request(S3); Release(S1); P2：; Request(S1); Release(S2); P3：; Request(S2); Release(S3); 則可

11、能發(fā)生死鎖則可能發(fā)生死鎖P1P2s1s2P3s3進程推進順序不當死鎖進程推進順序不當死鎖進程推進順序合法進程推進順序合法進程推進順序非法進程推進順序非法 P1: P1req(R1) P1req(R2) P1rel(R1) P1rel(R2)P1: P2req(R2) P2req(R1) P2rel(R2) P2rel(R1)P1req(R1)P1req(R2)P1rel(R1)P1rel(R2)P2req(R2)P2req(R1)P2rel(R2)P2rel(R1)P1req(R1)P1req(R2)P1rel(R1)P1rel(R2)P2req(R2)P2req(R1)P2rel(R2)P2

12、rel(R1)P1req(R1) P1req(R2) P1rel(R1) P1rel(R2) P2req(R2) P2req(R1) P2rel(R2) P2rel(R1) 進程推進順序不當進程推進順序不當P1req(R1) P2req(R2) P1req(R2) P2req(R1) 用資源分配圖討論死鎖問題，可得到如用資源分配圖討論死鎖問題，可得到如下結(jié)論：下結(jié)論： 如果資源分配圖中無環(huán)路，則系統(tǒng)中沒如果資源分配圖中無環(huán)路，則系統(tǒng)中沒 有死鎖發(fā)生有死鎖發(fā)生 如果資源分配圖有環(huán)路，且每個資源類如果資源分配圖有環(huán)路，且每個資源類 中只有一個資源，則環(huán)路的存在就意味著中只有一個資源，則環(huán)路的存在就

13、意味著 死鎖死鎖 如果資源分配圖有無環(huán)路，但涉及到的資如果資源分配圖有無環(huán)路，但涉及到的資 源類中有多個資源，則環(huán)路的存在未必就源類中有多個資源，則環(huán)路的存在未必就 有死鎖形成。有死鎖形成。 例題例題： 考慮下列資源分配策略：對資源的申請和釋放可考慮下列資源分配策略：對資源的申請和釋放可以在任何時刻進行。如果一進程的資源得不到滿足，則以在任何時刻進行。如果一進程的資源得不到滿足，則檢查所有由于等待資源而被阻塞的進程。如果它們有申檢查所有由于等待資源而被阻塞的進程。如果它們有申請進程所需要資源，則將這些資源取出分配給申請進程。請進程所需要資源，則將這些資源取出分配給申請進程。例如，考慮一個有三類

14、資源的系統(tǒng)，系統(tǒng)所有可用資源例如，考慮一個有三類資源的系統(tǒng)，系統(tǒng)所有可用資源為（為（4 4，2 2，2 2），進程），進程A A申請（申請（2 2，2 2，1 1），可滿足，進），可滿足，進程程B B申請（申請（1 1，0 0，1 1），也可滿足，若），也可滿足，若A A再請求（再請求（0 0，0 0，1 1），則被阻塞。此時，若），則被阻塞。此時，若C C請求（請求（2 2，0 0，0 0），它可以），它可以分到剩余資源（分到剩余資源（1 1，0 0，0 0），并從），并從A A已分到的資源中獲得已分到的資源中獲得一個資源，于是，進程一個資源，于是，進程A A的分配向量變?yōu)椋ǖ姆峙湎蛄孔優(yōu)椋?/p>

15、1 1，2 2，1 1），），而需求向量變成（而需求向量變成（1 1，0 0，1 1）。）。 這種分配方式會導(dǎo)致死鎖嗎？如果會，請舉一個例這種分配方式會導(dǎo)致死鎖嗎？如果會，請舉一個例子；如果不會，請說明死鎖的那一個必要條件不成立？子；如果不會，請說明死鎖的那一個必要條件不成立？ 這種分配方式會導(dǎo)致某些進程的無限等待嗎？這種分配方式會導(dǎo)致某些進程的無限等待嗎？ 解答解答： 本方法不會產(chǎn)生死鎖，因為它破壞了死鎖的本方法不會產(chǎn)生死鎖，因為它破壞了死鎖的 不可搶奪條件。不可搶奪條件。 這種方法會導(dǎo)致某些進程無限期的等待。這種方法會導(dǎo)致某些進程無限期的等待。 例題例題： 一個操作系統(tǒng)有一個操作系統(tǒng)有20

16、20個進程，競爭使個進程，競爭使用用6565個同類資源，申請方式是逐個進行的，個同類資源，申請方式是逐個進行的，一旦某進程獲得它所需要的全部資源，立即一旦某進程獲得它所需要的全部資源，立即歸還所有資源。每個進程最多使用三個資源。歸還所有資源。每個進程最多使用三個資源。若僅考慮這類資源，該系統(tǒng)有無可能全部死若僅考慮這類資源，該系統(tǒng)有無可能全部死鎖，為什么？鎖，為什么？ 解答解答：不會產(chǎn)生死鎖：不會產(chǎn)生死鎖 例題例題：一個計算機有：一個計算機有8 8臺磁帶機，它們由臺磁帶機，它們由N N個個進程競爭使用，每個進程可能需要三臺磁帶進程競爭使用，每個進程可能需要三臺磁帶機，請問機，請問N N為多少時，

17、系統(tǒng)沒有死鎖的危險？為多少時，系統(tǒng)沒有死鎖的危險？ 解答解答：當：當N N為為3 3或更少時，系統(tǒng)沒有死鎖的?；蚋贂r，系統(tǒng)沒有死鎖的危險。險。解決死鎖的基本方法解決死鎖的基本方法A A、預(yù)防死鎖預(yù)防死鎖 破壞四個必要條件之一，防止發(fā)破壞四個必要條件之一，防止發(fā)生死鎖（但可能導(dǎo)致資源利用率降低）。生死鎖（但可能導(dǎo)致資源利用率降低）。B B、避免死鎖避免死鎖 在資源的動態(tài)分配過程中，采用在資源的動態(tài)分配過程中，采用某種方法防止系統(tǒng)進入不安全狀態(tài)，比如銀行某種方法防止系統(tǒng)進入不安全狀態(tài)，比如銀行家算法。家算法。C C、檢測死鎖檢測死鎖 允許死鎖發(fā)生，但通過某種檢測允許死鎖發(fā)生，但通過某種檢測機構(gòu)及

18、時檢測出死鎖的發(fā)生，并精確的確定與機構(gòu)及時檢測出死鎖的發(fā)生，并精確的確定與死鎖有關(guān)的進程和資源，然后采取適當措施解死鎖有關(guān)的進程和資源，然后采取適當措施解除死鎖。除死鎖。D D、解除死鎖解除死鎖 一般采用資源剝奪和資源搶占方一般采用資源剝奪和資源搶占方式。解除死鎖需付出代價，原則上以代價越小式。解除死鎖需付出代價，原則上以代價越小越好。越好。 三、死鎖的預(yù)防和避免三、死鎖的預(yù)防和避免 1 1、死鎖的預(yù)防、死鎖的預(yù)防思路是破壞四個必要條件之一（死鎖的條件思路是破壞四個必要條件之一（死鎖的條件1 1是固有的，是固有的，一般不能改變），或者在分配臨界資源分之前，檢查系一般不能改變），或者在分配臨界資

19、源分之前，檢查系統(tǒng)的狀態(tài)，如是安全的，則分配之。統(tǒng)的狀態(tài)，如是安全的，則分配之。破壞破壞“占用并等待占用并等待”條件條件 資源作為一個整體，一次性分配。優(yōu)點是簡單、安全、資源作為一個整體，一次性分配。優(yōu)點是簡單、安全、 易于實現(xiàn)，缺點是資源浪費嚴重，進程延遲運行。易于實現(xiàn)，缺點是資源浪費嚴重，進程延遲運行。 可制定相應(yīng)的規(guī)則，例如，當一個進程（程序）申請可制定相應(yīng)的規(guī)則，例如，當一個進程（程序）申請 某資源被拒絕，則必須釋放已占用的資源，如需要再某資源被拒絕，則必須釋放已占用的資源，如需要再 與其它所需資源一起申請。對與其它所需資源一起申請。對CPUCPU還可進行可剝奪分配還可進行可剝奪分配。

20、破壞破壞“非搶占非搶占”條件條件進程已經(jīng)占有的資源，運行時可以暫時釋放，以后進程已經(jīng)占有的資源，運行時可以暫時釋放，以后再次申請。問題：實現(xiàn)復(fù)雜，且要付出代價。由于再次申請。問題：實現(xiàn)復(fù)雜，且要付出代價。由于可能反復(fù)的釋放和申請資源，因而可能極大的延遲可能反復(fù)的釋放和申請資源，因而可能極大的延遲進程的完成時間。進程的完成時間。 破壞破壞“循環(huán)等待循環(huán)等待”條件條件進程有序的申請資源。與前兩種方法相比，資源的進程有序的申請資源。與前兩種方法相比，資源的使用效率和系統(tǒng)性能都有較明顯地改善。問題：限使用效率和系統(tǒng)性能都有較明顯地改善。問題：限制了新設(shè)備的增加；用戶需求與系統(tǒng)規(guī)定有沖突；制了新設(shè)備的增

21、加；用戶需求與系統(tǒng)規(guī)定有沖突；對用戶不方便。對用戶不方便。系統(tǒng)的安全狀態(tài)系統(tǒng)的安全狀態(tài)安全狀態(tài)安全狀態(tài)一般地，稱系統(tǒng)處于安全狀態(tài)，僅當存在一個安全（進一般地，稱系統(tǒng)處于安全狀態(tài)，僅當存在一個安全（進程）序列程）序列PP1 1,P,P2 2,P,Pn n ，其中任一進程，其中任一進程P Pi i所可能請求的所可能請求的最大資源數(shù)可被當前可用資源加上所有最大資源數(shù)可被當前可用資源加上所有P Pj j（j ij i）已）已占用的資源所滿足。占用的資源所滿足。例子：三個進程，共有例子：三個進程，共有1212臺設(shè)備臺設(shè)備進程進程最大需求最大需求t0時分配時分配可用可用P1 11053P2 242P3 3

22、92不安全狀態(tài)不安全狀態(tài)當不存在上述的安全序列時，系統(tǒng)狀態(tài)稱之為不安全的。當不存在上述的安全序列時，系統(tǒng)狀態(tài)稱之為不安全的。注意：不安全狀態(tài)不等于死鎖，不安全狀態(tài)僅僅意味著注意：不安全狀態(tài)不等于死鎖，不安全狀態(tài)僅僅意味著系統(tǒng)將可能進入死鎖狀態(tài)。系統(tǒng)將可能進入死鎖狀態(tài)。 由安全狀態(tài)向不安全狀態(tài)的轉(zhuǎn)換由安全狀態(tài)向不安全狀態(tài)的轉(zhuǎn)換如果在如果在t t1 1時刻時刻P P3 3又申請又申請1 1臺設(shè)備，若系統(tǒng)滿足臺設(shè)備，若系統(tǒng)滿足P P3 3的要求，的要求，分配給分配給P P3 3一臺設(shè)備，則系統(tǒng)將進入不安全狀態(tài)。一臺設(shè)備，則系統(tǒng)將進入不安全狀態(tài)。 此時存在安全序列此時存在安全序列 P P2 2,P,P

23、1 1,P,P3 3 進程進程最大需求最大需求t0時分配時分配t1時分配時分配可用可用P1 110552P2 2422P3 3923因此，避免死鎖就是找出安全狀態(tài)和不安全狀態(tài)的臨因此，避免死鎖就是找出安全狀態(tài)和不安全狀態(tài)的臨界點，以確定能否分配資源界點，以確定能否分配資源。銀行家算法銀行家算法銀行家算法的數(shù)據(jù)結(jié)構(gòu)：銀行家算法的數(shù)據(jù)結(jié)構(gòu)：可利用資源向量可利用資源向量AvailableAvailable：m m個元素的數(shù)組，其中個元素的數(shù)組，其中每個元素代表一類可利用的資源數(shù)目，其數(shù)值隨該類每個元素代表一類可利用的資源數(shù)目，其數(shù)值隨該類資源的分配和回收而動態(tài)的改變，初值為系統(tǒng)中可利資源的分配和回收

24、而動態(tài)的改變，初值為系統(tǒng)中可利用的該類全部資源的數(shù)目。如用的該類全部資源的數(shù)目。如AvailablejAvailablejk k，表示，表示R Rj j類資源全部有類資源全部有k k個。個。 最大需求矩陣最大需求矩陣MaxMax：n nm m矩陣，定義了系統(tǒng)中矩陣，定義了系統(tǒng)中n n個進個進程中每個進程對程中每個進程對m m類資源的最大需求。如類資源的最大需求。如Max(i,j)Max(i,j)k k，表示進程表示進程i i需要需要R Rj j類資源的最大數(shù)為類資源的最大數(shù)為k k個。個。分配矩陣分配矩陣AllocationAllocation：n nm m矩陣，定義了系統(tǒng)中每矩陣，定義了系統(tǒng)

25、中每一類資源當前已分配給每個進程的資源數(shù)。如果一類資源當前已分配給每個進程的資源數(shù)。如果Allocationi,jAllocationi,jk k，表示進程，表示進程i i當前已分得當前已分得R Rj j類資源類資源的數(shù)目為的數(shù)目為k k個。個。需求矩陣需求矩陣NeedNeed：n nm m矩陣，表示每個進程尚需的各矩陣，表示每個進程尚需的各類資源數(shù)。如果類資源數(shù)。如果Needi,jNeedi,jk k，表示進程，表示進程i i還需要還需要R Rj j類類資源資源k k個方能完成任務(wù)。個方能完成任務(wù)。 上述矩陣存在如下關(guān)系：上述矩陣存在如下關(guān)系： Needi,jNeedi,jMaxi,jMax

26、i,jAllocationi,jAllocationi,j銀行家算法銀行家算法：設(shè)設(shè)RequestRequesti i是進程是進程P Pi i的請求向量。如果的請求向量。如果RequestRequesti ijjk k，表示進程，表示進程P Pi i需要需要k k個個R Rj j類的資源。當類的資源。當P Pi i發(fā)出資源發(fā)出資源申請申請RequestRequesti i后，系統(tǒng)按下述步驟檢查：后，系統(tǒng)按下述步驟檢查：如果如果RequestRequesti i NeedNeedi i，則轉(zhuǎn)步驟，則轉(zhuǎn)步驟，否則認，否則認為出錯（所需資源已超過宣布的最大值）。為出錯（所需資源已超過宣布的最大值）。

27、如果如果RequestRequesti i AvailableAvailablei i，則轉(zhuǎn)向步驟，則轉(zhuǎn)向步驟，否則表示尚無足夠資源，否則表示尚無足夠資源，PiPi必須等待。必須等待。系統(tǒng)試探把資源分配給進程系統(tǒng)試探把資源分配給進程P Pi i，并修改下面數(shù)據(jù)，并修改下面數(shù)據(jù)結(jié)構(gòu)中的數(shù)值：結(jié)構(gòu)中的數(shù)值：AvailableAvailable RequestiAllocationAllocation RequestiNeedNeedi iNeedNeedi i RequestRequesti i系統(tǒng)執(zhí)行安全性算法，檢查資源分配后，系統(tǒng)執(zhí)行安全性算法，檢查資源分配后，系統(tǒng)是否處于安全狀態(tài)。如安全，則

28、正式分系統(tǒng)是否處于安全狀態(tài)。如安全，則正式分配，否則上述試探作廢，恢復(fù)原來的資源分配，否則上述試探作廢，恢復(fù)原來的資源分配狀態(tài)，讓進程配狀態(tài)，讓進程P Pi i等待。等待。 安全性算法：安全性算法：設(shè)初值：設(shè)初值：工作向量工作向量Work(Work(長度長度m) m) 表示系統(tǒng)可提供的資源數(shù)表示系統(tǒng)可提供的資源數(shù)目。目。WorkWork的初值為的初值為AllocationAllocation。向量向量Finish (Finish (長度長度n)n) 表示系統(tǒng)是否有足夠的資源表示系統(tǒng)是否有足夠的資源分配給進程，使之運行完成。初始的分配給進程，使之運行完成。初始的FinishiFinishifal

29、sefalse，當有足夠的資源分配給當有足夠的資源分配給P Pi i時，令時，令FinishiFinishiTrueTrue。從進程集合中找一個能滿足下述條件的進程：從進程集合中找一個能滿足下述條件的進程：FinishiFinishifalsefalseNeedNeedi i WorkWork如找到，執(zhí)行步驟如找到，執(zhí)行步驟，否則執(zhí)行步驟，否則執(zhí)行步驟。當進程當進程P Pi i獲得資源后，順利執(zhí)行，直至完成并獲得資源后，順利執(zhí)行，直至完成并釋放出分配給它的資源，故應(yīng)執(zhí)行釋放出分配給它的資源，故應(yīng)執(zhí)行 WorkWorkWorkWorkAllocationAllocationi i Finishi

30、 Finishitruetrue 轉(zhuǎn)步驟轉(zhuǎn)步驟。如果所有進程的如果所有進程的FinishiFinishitruetrue，則表示系統(tǒng)，則表示系統(tǒng)處于安全狀態(tài)，否則系統(tǒng)處于不安全狀態(tài)。處于安全狀態(tài)，否則系統(tǒng)處于不安全狀態(tài)。 MAXA B CAllocationA B CNeedA B CAvailableA B CP0 07 5 30 1 07 4 33 3 2P1 13 2 22 0 01 2 2P2 29 0 23 0 26 0 0P3 32 2 22 1 10 1 1P4 44 3 30 0 24 3 1例子：現(xiàn)有五個進程例子：現(xiàn)有五個進程 P P0 0，P P1 1，P P2 2，P P

31、3 3，P P4 4 和和資源資源 A,B,C = 10 A,B,C = 10，5 5，7 7 。T T0 0時刻的資時刻的資源分配表為：源分配表為： T T0 0時刻的安全性時刻的安全性T T0 0時刻可找出安全序列時刻可找出安全序列 P P1 1，P P3 3，P P4 4，P P2 2，P P0 0 ，故，故此時系統(tǒng)是安全的。此時系統(tǒng)是安全的。 WorkA B CNeedA B CAllocationA B CWook+AllocationA B C FinishP1 13 3 21 2 22 0 05 3 2TrueP3 35 3 20 1 12 1 17 4 3TrueP4 47 4

32、 34 3 10 0 27 4 5TrueP2 27 4 56 0 03 0 210 4 7TrueP0 010 4 77 4 30 1 110 5 7TrueP P1 1請求請求RequestRequest1 1(1,0,2)(1,0,2)，系統(tǒng)按銀行家算法檢查：，系統(tǒng)按銀行家算法檢查： RequestRequest1 1(1,0,2) = Need(1,0,2) = Need1 1(1,2,2)(1,2,2) Request Request1 1(1,0,2) = Available(3,3,2)(1,0,2) = Available(3,3,2)假定可分配，修改假定可分配，修改Avail

33、ableAvailable，AllocationAllocation和和NeedNeed向量，向量，由此形成資源變化：由此形成資源變化： MAXA B CAllocationA B CNeedA B CAvailableA B CP0 07 5 30 1 07 4 32 3 0P1 13 2 23 0 20 2 0P2 29 0 23 0 26 0 0P3 32 2 22 1 10 1 1P4 44 3 30 0 24 3 1經(jīng)安全性檢查，可以找出一個安全序列經(jīng)安全性檢查，可以找出一個安全序列 P P1 1,P,P3 3,P,P4 4,P,P0 0,P,P2 2 。系統(tǒng)是安全的，可以實施分配。

34、系統(tǒng)是安全的，可以實施分配。 WorkA B CNeedA B CAllocationA B CWook+AllocationA B C FinishP1 12 3 00 2 03 0 25 3 2TrueP3 35 3 20 1 12 1 17 4 3TrueP4 47 4 34 3 10 0 27 4 5TrueP0 07 4 57 4 30 1 07 5 5TrueP2 27 5 56 0 03 0 010 5 7TrueP P4 4請求請求RequestRequest4 4(3,3,0)(3,3,0)，系統(tǒng)按銀行家算法檢查：，系統(tǒng)按銀行家算法檢查： RequestRequest4 4(

35、3,3,0) = Need(3,3,0) = Need4 4(4,3,1)(4,3,1) Request Request4 4(3,3,0) != Available(2,3,0)(3,3,0) != Available(2,3,0)P P4 4必須等待。必須等待。 P P0 0請求請求RequestRequest0 0(0,2,0)(0,2,0)，系統(tǒng)按銀行家算法檢查：，系統(tǒng)按銀行家算法檢查： RequestRequest0 0(0,2,0) = Need(0,2,0) = Need0 0(7,4,3)(7,4,3) Request Request0 0(0,2,0) = Available

36、(2,3,0)(0,2,0) 0 0。 對每一進程對每一進程P Pi i，1 = max1 = maxi i = m P - P3232 P P1212PP2323 - P - P1313P P3131PP1313 - P - P3333 直觀的解釋：資源分配圖中如有環(huán)路直觀的解釋：資源分配圖中如有環(huán)路存在，則發(fā)生死鎖，環(huán)路上的進程都卷入存在，則發(fā)生死鎖，環(huán)路上的進程都卷入死鎖中死鎖中. .P1 1P2 2P3 3P1 1011 P2 2001P3 311 1 2 2、資源類中含有若干個資源、資源類中含有若干個資源 可以利用把資源分配圖加以簡化的方法來檢測系統(tǒng)可以利用把資源分配圖加以簡化的方法

37、來檢測系統(tǒng)在某狀態(tài)下是否處于死鎖。在某狀態(tài)下是否處于死鎖。在資源分配圖中，方框表示在資源分配圖中，方框表示資源的類，方框中的點的個數(shù)表示資源的數(shù)量。我們可資源的類，方框中的點的個數(shù)表示資源的數(shù)量。我們可以通過對資源分配圖的化簡來判斷系統(tǒng)是否處于死鎖狀以通過對資源分配圖的化簡來判斷系統(tǒng)是否處于死鎖狀態(tài)，具體方法如下：態(tài)，具體方法如下： 在資源分配圖中找出一個既不阻塞又非獨立的進程在資源分配圖中找出一個既不阻塞又非獨立的進程結(jié)點結(jié)點P P，在順利情況下，結(jié)點，在順利情況下，結(jié)點P P可獲得所需資源而繼續(xù)執(zhí)可獲得所需資源而繼續(xù)執(zhí)行，直至運行完畢，在釋放其占有的所有資源，這相當行，直至運行完畢，在釋放

38、其占有的所有資源，這相當于消取于消取P P所有的請求邊和分配邊，使之稱為孤立結(jié)點。所有的請求邊和分配邊，使之稱為孤立結(jié)點。P P釋放資源后，繼續(xù)尋找下一個既不阻塞又非獨立的結(jié)點，釋放資源后，繼續(xù)尋找下一個既不阻塞又非獨立的結(jié)點，使它獲得資源而繼續(xù)執(zhí)行，直至該結(jié)點完成后又釋放出使它獲得資源而繼續(xù)執(zhí)行，直至該結(jié)點完成后又釋放出它所占用的全部資源。它所占用的全部資源。 在進行了一系列的簡化后，若能消取圖中所有的邊，在進行了一系列的簡化后，若能消取圖中所有的邊，使所有進程都成為孤立結(jié)點，則稱該圖為可完全簡化的，使所有進程都成為孤立結(jié)點，則稱該圖為可完全簡化的，否則該圖使不可完全簡化的。否則該圖使不可完

39、全簡化的。 第一步第一步 在資源分配圖中找出一個既非阻塞又不孤立在資源分配圖中找出一個既非阻塞又不孤立且它的資源申請數(shù)量可以得到系統(tǒng)滿足的任何一個結(jié)且它的資源申請數(shù)量可以得到系統(tǒng)滿足的任何一個結(jié)點點P Pi i，如果不存在這樣的，如果不存在這樣的P Pi i，則系統(tǒng)已經(jīng)處于不安全，則系統(tǒng)已經(jīng)處于不安全或死鎖狀態(tài)，檢測結(jié)束?；蛩梨i狀態(tài)，檢測結(jié)束。第二步第二步 去掉去掉P Pi i的所有請求邊和分配邊，使之成為孤的所有請求邊和分配邊，使之成為孤立結(jié)點，并在立結(jié)點，并在P Pi i所歸還的資源的類方框中添加與歸還所歸還的資源的類方框中添加與歸還資源數(shù)量相對應(yīng)的圓點，然后轉(zhuǎn)第一步。資源數(shù)量相對應(yīng)的圓點

40、，然后轉(zhuǎn)第一步。 如果所有結(jié)點都成為孤立結(jié)點，則稱資源分配圖如果所有結(jié)點都成為孤立結(jié)點，則稱資源分配圖可完全簡化，否則為不可完全簡化?？赏耆喕?，否則為不可完全簡化。 資源分配圖的化簡過程（或者說得到的進程化簡資源分配圖的化簡過程（或者說得到的進程化簡序列）可以不同，但可以證明，它們都將得到相同的序列）可以不同，但可以證明，它們都將得到相同的不可簡化圖。同樣可以證明，系統(tǒng)的資源分配圖不可不可簡化圖。同樣可以證明，系統(tǒng)的資源分配圖不可完全簡化是死鎖的充分條件。完全簡化是死鎖的充分條件。例子例子 P1 1P2 2r1 1r2 2P1 1P2 2r1 1r2 2a 結(jié)點結(jié)點P1 1既不阻塞也不孤既不

41、阻塞也不孤立立b 給給P1 1分配資源變請求邊為分配資源變請求邊為分配邊分配邊P1 1P2 2r1 1r2 2c P1 1釋放資源成為孤立結(jié)點釋放資源成為孤立結(jié)點P1 1P2 2r1 1r2 2d 給給P2 2分配資源變請求邊為分配邊分配資源變請求邊為分配邊P1 1P2 2r1 1r2 2e P2 2釋放資源成為孤立結(jié)點釋放資源成為孤立結(jié)點例子例子 P1 1P2 2r1 1r2 2a 初始態(tài)初始態(tài)P3 3r3 3P1 1P2 2r1 1r2 2b 變變P1 1的申請邊為分配邊的申請邊為分配邊P3 3r3 3P1 1P2 2r1 1r2 2c P1 1釋放資源成為孤立結(jié)點釋放資源成為孤立結(jié)點P3

42、 3r3r3P1 1P2 2r1 1r2 2d 無法繼續(xù)化簡無法繼續(xù)化簡P3 3r3 3對上述方法進行形式化，可分為三步來進行：對上述方法進行形式化，可分為三步來進行：第一步第一步 找出資源已經(jīng)滿足的進程，將它們所占找出資源已經(jīng)滿足的進程，將它們所占用的資源和系統(tǒng)中還剩余的資源加在一起作為用的資源和系統(tǒng)中還剩余的資源加在一起作為“可分配的資源可分配的資源”，對這些處理過的進程加上標，對這些處理過的進程加上標志；志；第二步第二步 在新的在新的“可分配資源可分配資源”的約束下，繼續(xù)的約束下，繼續(xù)從未加上標志的進程中查找資源可以滿足的進程，從未加上標志的進程中查找資源可以滿足的進程，如果有這樣的進程

43、，轉(zhuǎn)第一步，否則轉(zhuǎn)下一步；如果有這樣的進程，轉(zhuǎn)第一步，否則轉(zhuǎn)下一步；第三步第三步 如系統(tǒng)中所有進程均有標志，表明系統(tǒng)如系統(tǒng)中所有進程均有標志，表明系統(tǒng)沒有死鎖，否則說明系統(tǒng)處于死鎖狀態(tài)，沒有標沒有死鎖，否則說明系統(tǒng)處于死鎖狀態(tài)，沒有標志的那一組進程就是死鎖進程。志的那一組進程就是死鎖進程。 死鎖檢測中的數(shù)據(jù)結(jié)構(gòu)：死鎖檢測中的數(shù)據(jù)結(jié)構(gòu)： 可利用資源向量可利用資源向量AvailableAvailable：表示了：表示了m m類資源中的類資源中的 每一類資源的可用數(shù)目。每一類資源的可用數(shù)目。 請求矩陣請求矩陣RequestRequest：一個：一個n nm m矩陣，用以表示進矩陣，用以表示進 程當前

44、對各類資源的請求數(shù)目。程當前對各類資源的請求數(shù)目。 分配矩陣分配矩陣AllocationAllocation：一個：一個n nm m矩陣，用以表示矩陣，用以表示 某一時刻的資源分配情況。某一時刻的資源分配情況。 工作向量工作向量WorkWork：表示系統(tǒng)可提供給進程繼續(xù)運行：表示系統(tǒng)可提供給進程繼續(xù)運行 的各類資源數(shù)目。的各類資源數(shù)目。 進程向量進程向量FinishFinish：記錄進程當前是否還占有資源。：記錄進程當前是否還占有資源。死鎖檢測算法死鎖檢測算法 work := available; L := Pi | allocationi = 0 requesti = 0 for all Pi !L do begin