【正文】 18 11 4 16 7 4 11 0 3 2 4 3 7 2 1 2 4 0 2 4 0 5 4 0 5 3 1 4 3 4 7 1 3 4 0 0 6 0 2 0 1 1 0 17 5 20 15 4 18 11 4 16 4 3 7 7 4 11 5 4 3 1 2 96 從上面安全性檢測表看出，此時存在一個安全序列 {P4,P5,P3,P2,P1}，故該狀態(tài)是安全的，可以立即將 P4所申請的資源分配給它。 97 解 (4). 在 (3)的基礎(chǔ)上若進(jìn)程 P1請求資源 (0,2,0)，按銀行家算法進(jìn)行檢查： ? Request(0,2,0)=Need(3,4,7),且 ? Request(0,2,0)=Available(0,3,2) ? P1請求資源后，試分配并修改相應(yīng)的數(shù)據(jù)結(jié)構(gòu)，形成如下的資源分配表： ? 再利用安全性算法檢查系統(tǒng)是否安全，發(fā)現(xiàn)可用資源Available（ 0， 1， 2）已不能滿足任何進(jìn)程的資源需求，故系統(tǒng)進(jìn)入不安全狀態(tài)，此時系統(tǒng)不能把資源分配給 P1 98 P1請求資源后的資源分配表 Allocation Need Available A B C A B C A B C P1 P2 P3 P4 P5 2 3 2 4 0 2 4 0 5 4 0 5 3 1 4 3 2 7 1 3 4 0 0 6 0 2 0 1 1 0 0 1 2 99 一個有用的結(jié)論： ? 若系統(tǒng)有 同類資源 m個 ，可并發(fā)執(zhí)行且共享該類資源的的 進(jìn)程最多是 n個 ，而每個進(jìn)程 申請?jiān)擃愘Y源的最大量為 x(1=x=m)只要不等式n(x1)+1=m成立，則系統(tǒng)就一定不會死鎖。 ? （可出填空題、選擇題、判斷題） 100 例如： 3個進(jìn)程競爭 7個同類資源，每個進(jìn)程競爭的資源數(shù)一樣多，問最大請求資源在什么范圍就一定不會引起死鎖？ 10個，每個進(jìn)程需要的最大資源數(shù)為 4，問競爭該類資源的進(jìn)程數(shù)為多少就一定不會死鎖？ 5個進(jìn)程各需要申請某類資源 4個，問系統(tǒng)有該類資源多少個就一定不會引起死鎖？ 101 ? 死鎖的預(yù)防和避免都可以不讓死鎖產(chǎn)生，但死鎖的預(yù)防過于嚴(yán)格，死鎖避免的銀行家算法又需要獲得難以得到的信息，都不利于系統(tǒng)資源的充分利用 ? 且前面介紹的死鎖預(yù)防和避免算法，都是在系統(tǒng)為進(jìn)程分配資源時施加限制條件或添加檢測。這些方法都屬于保守類方法，且都是以犧牲機(jī)器效率和浪費(fèi)資源為代價的，這與操作系統(tǒng)的宗旨相違背。 102 ? 若采用較為大膽的方法，即允許死鎖發(fā)生，但操作系統(tǒng)能不斷地監(jiān)督進(jìn)程的共同進(jìn)展路徑，判定和發(fā)現(xiàn)死鎖，一旦死鎖發(fā)生，就采取專門的措施加以克服，并以最小的代價使系統(tǒng)恢復(fù)正常，這正是我們所需要的。 ? 若系統(tǒng)為進(jìn)程分配資源時 不采取任何措施 ，則應(yīng)該提供死鎖檢測和解除的手段。 103 死鎖的檢測 —— 死鎖定理 ? 可以采用把 資源分配圖（ RAG） 加以簡化的方法，來檢測當(dāng)系統(tǒng)處于 S狀態(tài)時是否為死鎖狀態(tài)。 ? RAG可定義為由一個由頂點(diǎn)集合 V和有向邊集合 E組成的對偶 RAG=（ V， E） ? 頂點(diǎn)集合 V包括兩部分：由系統(tǒng)中 所有進(jìn)程 組成的集合P，和由系統(tǒng)中 所有的資源類 組成的集合 R； ? 邊集合 E中的有向邊也包括兩類：從進(jìn)程頂點(diǎn)到資源頂點(diǎn)的有向邊 Pi,Ri,稱為請求邊，以及從資源頂點(diǎn)到進(jìn)程頂點(diǎn)的有向邊 Ri,Pj，稱為分配邊。 104 死鎖的檢測 —— 死鎖定理 ? DAG簡化方法為： ? （ 1）如下圖。在資源分配圖中，找出一個 既不阻塞又非獨(dú)立的進(jìn)程結(jié)點(diǎn) Pi。在順利的情況下， Pi可獲得所需資源而繼續(xù)運(yùn)行，直至運(yùn)行完畢，再釋放其所占有的全部資源，這相當(dāng)于消去 Pi的請求邊和分配邊，使之成為孤立的結(jié)點(diǎn)。 105 資源分配圖 ： （ 資源 r1， r2；進(jìn)程 P1， P2） r1 r2 P1 P2 106 資源分配圖 ： （ 進(jìn)程 P1釋放資源后） r1 r2 P1 P2 107 死鎖定理（續(xù)） ? （ 2） P1釋放資源后，就可以使 P2獲得資源而繼續(xù)進(jìn)行，直至 P2完成后又釋放出它所占有的全部資源，形成下圖： 108 資源分配圖 ： （ P2釋放了資源后） r1 r2 P1 P2 109 死鎖定理（續(xù)） ? （ 3）在進(jìn)行一系列的簡化后，若能消去圖中所有的邊，使所有的進(jìn)程結(jié)點(diǎn)都成為孤立的結(jié)點(diǎn)，則稱該圖是可完全簡化的；若不能通過任何過程使該圖完全簡化，則稱該圖是不可完全簡化的 110 死鎖定理（續(xù)） ? 對于較復(fù)雜的資源分配圖，可能有多個既未阻塞又非孤立的進(jìn)程結(jié)點(diǎn)，不同的簡化順序，是否會得到不同的簡化圖？ ? 現(xiàn)已證明，所有的簡化順序，都將得到相同的不可簡化圖。 ? 可以證明：系統(tǒng)為死鎖狀態(tài)的 充分條件 是：當(dāng)且僅當(dāng)該系統(tǒng)狀態(tài)的資源分配圖是不可完全簡化的。 ? 該充分條件被稱為死鎖定理 。 111 死鎖的檢測手段 2—— 資源分配表 （選讀） ? 假定系統(tǒng)有 n個進(jìn)程 P1， P2， … ,Pn和 Pm種資源 R1，R2， … Rm。 ? 建立 資源分配表 S和進(jìn)程等待表 W，如下兩表所示。 ? S表中的 aij表示分配給 Pi進(jìn)程的資源 Rj的數(shù)目； W 表中的 bij表示 Pi進(jìn)程請求資源 Rj的數(shù)目； ? 另外為每個進(jìn)程設(shè)置一個 等待資源計(jì)數(shù)器 C1，C2， ..,Cn， 它們表示引起相應(yīng)進(jìn)程被阻塞的資源數(shù)目； ? 將未阻塞的進(jìn)程組成 一個表 L（或一個隊(duì)列） 112 資源分配表（ S） 資源 R1 R2 … Ri … Rm 進(jìn)程 P1 a11 a12 … a1i … a1m P2 a21 a22 … a2i … a2m … … … … … … … Pi ai1 ai2 … aii aim … Pn an1 an2 ani anm 113 進(jìn)程等待表表（ W） 資源 R1 R2 … Ri … Rm 進(jìn)程 P1 b11 b12 … b1i … b1m P2 b21 b22 … b2i … b2m … … … … … … … Pi bi1 bi2 … bii … bim … … … … … … … Pn bn1 bn2 … bni … bnm 114 資源分配表 發(fā)現(xiàn)死鎖的方法如下： （ Ⅰ ）把未阻塞（ Ci=0）的進(jìn)程 Pi紀(jì)錄在 L表 中（其全部資源得到滿足的進(jìn)程）； （ Ⅱ ）從 L表 中選擇一個進(jìn)程，根據(jù) 資源分配表 S釋放分配給該進(jìn)程的所有資源； （ Ⅲ ）由 進(jìn)程等待表 W依次檢查和修改需要該進(jìn)程釋放資源的每一個進(jìn)程的等待計(jì)數(shù)器 Cj； 115 發(fā)現(xiàn)死鎖的方法 （ Ⅳ ）若 Cj=0，則表示該進(jìn)程所請求的資源已得到滿足，不再阻塞，將 Pj記入 L表中。 （ Ⅴ ）再從 L表中選取另一個進(jìn)程，重復(fù)上述操作 （ Ⅵ ） 若所有進(jìn)程都記入 L表中， 則系統(tǒng)初始狀態(tài)為非死鎖狀態(tài)，否則為死鎖狀態(tài)。 116 資源分配表續(xù) （選讀） ? 這種方法僅提供了發(fā)現(xiàn)死鎖的必要條件，不是充分條件。也就是說，檢查出來的狀態(tài)是死鎖的，其初始狀態(tài)必定會發(fā)生死鎖；但由于是順序檢查的，當(dāng)檢查不出的時候，仍可能發(fā)生死鎖。 ? 有必要指出：死鎖通常是由計(jì)算機(jī)操作員發(fā)現(xiàn)的，而不是系統(tǒng)本身。經(jīng)驗(yàn)豐富的操作員根據(jù)機(jī)器運(yùn)行情況，可判斷一些進(jìn)程是否處于死鎖。通常的解決方法是作廢并重新啟動死鎖的進(jìn)程 117 死鎖的解除 ? 當(dāng)發(fā)現(xiàn)系統(tǒng)中存在死鎖時，就必須解除它，這才是最有價值的。一般來說，只要讓某個進(jìn)程釋放一個或多個資源就可以解除死鎖。死鎖解除后，釋放資源的進(jìn)程應(yīng)能恢復(fù)它原來的狀態(tài)，才能保證該進(jìn)程不出現(xiàn)錯誤。因此， 死鎖解除，實(shí)質(zhì)上就是如何讓釋放資源的進(jìn)程能夠繼續(xù)運(yùn)行。 118 解除死鎖的常用方法： ? （ 1）重新啟動計(jì)算機(jī)，立即結(jié)束所有進(jìn)程 ? （ 2）撤銷處于死鎖狀態(tài)的所有進(jìn)程。大部分 OS采用這種方法。 ? （ 3）逐個撤銷死鎖進(jìn)程，回收其占用的資源 ? （ 4）逐個剝奪死鎖進(jìn)程的資源，分配給其余死鎖進(jìn)程，直至解除死鎖為止 ? （ 5）讓所有死鎖進(jìn)程回退，直至死鎖解除。這要求系統(tǒng)保存所有進(jìn)程的檢查點(diǎn)。 119 解除死鎖的常用方法（續(xù)）： ? 在出現(xiàn)死鎖時，可采用各種策略來撤銷進(jìn)程：如，為解除死鎖狀態(tài)所需撤銷的進(jìn)程數(shù)目最少；撤銷進(jìn)程時所付出的代價最小等。 ? end 120