資源分配圖.doc

資源分配圖P1 表示：進(jìn)程p1 R1 表示：有3個R1類資源 R1P1 表示：進(jìn)程p1申請一個R1類資源 P1R1 表示：系統(tǒng)分配一個R1類資源給進(jìn)程p1，此時，系統(tǒng)還剩下2個R1類資源R1P1 表示：進(jìn)程p1申請2個R1類資源P1R1 表示：系統(tǒng)分配2個R1類資源給進(jìn)程p1，此時，系統(tǒng)還剩下1個R1類資源R1P1P2表示：系統(tǒng)分配一個R1資源給進(jìn)程p2，然后又分配一個R1類資源給進(jìn)程p1，最后進(jìn)程p1收到一個R1類資源后又繼續(xù)申請1個R1類資源，此時，還剩下一個R1類資源可以分配給P1，但還沒分配給P1。（注意：圖中P1的申請是還沒得到響應(yīng)的，不要以為R1指向P1的那個箭頭是響應(yīng)P1的申請，而分配了資源給P1）P1R1R1P2P1表示：系統(tǒng)分配一個R1資源給進(jìn)程p2，然后又分配一個R1類資源給進(jìn)程p1，最后進(jìn)程p1收到一個R1類資源后又繼續(xù)申請1個R1類資源，此時，系統(tǒng)已經(jīng)沒有R1類資源可以分配給進(jìn)程P1了，于是p1進(jìn)程受到阻塞。（注意：千萬不要誤認(rèn)為：進(jìn)程P1申請一個R1類資源，然后系統(tǒng)便分配一個R1類資源給P1。上圖的“右箭頭”跟“左箭頭”是沒任何關(guān)系的，并不是“右箭頭響應(yīng)左箭頭的申請，而分配內(nèi)存給P1”，先后順序不能亂，時間順序是先“分配一個R1類資源給P1”，再“P1申請一個R1類資源”；而不是先“P1申請一個R1類資源”，再“分配一個R1類資源給P1”）化簡資源分配圖方法步驟：先看系統(tǒng)還剩下多少資源沒分配，再看有哪些進(jìn)程是不阻塞（“不阻塞”即：系統(tǒng)有足夠的空閑資源分配給它）的，接著把不阻塞的進(jìn)程的所有邊都去掉，形成一個孤立的點(diǎn)，再把系統(tǒng)分配給這個進(jìn)程的資源回收回來，這樣，系統(tǒng)剩余的空閑資源便多了起來，接著又去看看剩下的進(jìn)程有哪些是不阻塞的，然后又把它們逐個變成孤立的點(diǎn)。最后，所有的資源和進(jìn)程都變成孤立的點(diǎn)。這樣的圖就叫做“可完全簡化”。如果一個圖可完全簡化，則不會產(chǎn)生死鎖；如果一個圖不可完全簡化（即：圖中還有“邊”存在），則會產(chǎn)生死鎖。這就是“死鎖定理”例1第一步：先看R1資源，它有三個箭頭是向外的，因此它一共給進(jìn)程分配了3個資源，此時，R1沒有空閑的資源剩余。第二步：再看R2資源，它有一個箭頭是向外的，因此它一共給進(jìn)程分配了1個資源，此時，R2還剩余一個空閑的資源沒分配。 第三步：看完資源，再來看進(jìn)程，先看進(jìn)程P2，它只申請一個R1資源，但此時R1資源已經(jīng)用光了，所以，進(jìn)程P2進(jìn)入阻塞狀態(tài)，因此，進(jìn)程P2暫時不能化成孤立的點(diǎn)。 第四步：再看進(jìn)程P1，它只申請一個R2資源，此時，系統(tǒng)還剩余一個R2資源沒分配，因此，可以滿足P1的申請。這樣，進(jìn)程P1便得到了它的全部所需資源，所以它不會進(jìn)入阻塞狀態(tài)，可以一直運(yùn)行，等它運(yùn)行完后，我們再把它的所有的資源釋放。相當(dāng)于：可以把P1的所有的邊去掉，變成一個孤立的點(diǎn)，如下圖所示： 第五步：進(jìn)程P1運(yùn)行完后，釋放其所占有的資源（2個R1資源和1個R2資源），系統(tǒng)回收這些資源后，空閑的資源便變成2個R1資源和1個R2資源，由于進(jìn)程P2一直在申請一個R1資源，所以此時，系統(tǒng)能滿足它的申請。這樣，進(jìn)程P2便得到了它的全部所需資源，所以它不會進(jìn)入阻塞狀態(tài)，可以一直運(yùn)行，等它運(yùn)行完后，我們再把它的所有的資源釋放。相當(dāng)于：可以把P2的所有的邊都去掉，化成一個孤立的點(diǎn)，變成下圖：由于這個資源分配圖可完全簡化，因此，不會產(chǎn)生死鎖。例2化簡下面的進(jìn)程-資源圖第一步：先看R1資源，它有2個箭頭是向外的，因此它一共給進(jìn)程分配了2個資源，此時，R1沒有空閑的資源剩余。第二步：再看R2資源，它有2個箭頭是向外的，因此它一共給進(jìn)程分配了2個資源，此時，R2還剩余一個空閑的資源沒分配。第三步：看完資源，再來看進(jìn)程，先看進(jìn)程P1，它申請一個R1資源和一個R2資源，但此時R1資源已經(jīng)用光了，所以，進(jìn)程P2進(jìn)入阻塞狀態(tài)，因此，進(jìn)程P2暫時不能化成孤立的點(diǎn)。第四步：再看進(jìn)程P2，它只申請一個R2資源，此時，系統(tǒng)還剩余一個R2資源沒分配，因此，可以滿足P2的申請。這樣，進(jìn)程P2便得到了它的全部所需資源，所以它不會進(jìn)入阻塞狀態(tài)，可以一直運(yùn)行，等它運(yùn)行完后，我們再把它的所有的資源釋放。相當(dāng)于：可以把P2的所有的邊去掉，變成一個孤立的點(diǎn)，如下圖所示：第五步：進(jìn)程P2運(yùn)行完后，釋放其所占有的資源（1個R1資源和2個R2資源），系統(tǒng)回收這些資源后，空閑的資源便變成1個R1資源和2個R2資源，由于進(jìn)程P1一直在申請一個R1資源，所以此時，系統(tǒng)能滿足它的申請。這樣，進(jìn)程P1便得到了它的全部所需資源，所以它不會進(jìn)入阻塞狀態(tài)，可以一直運(yùn)行，等它運(yùn)行完后，我們再把它的所有的資源釋放。相當(dāng)于：可以把P1的所有的邊都去掉，化成一個孤立的點(diǎn)，變成下圖：由于這個資源分配圖可完全簡化，因此，不會產(chǎn)生死鎖。例3第一步：先看R1資源，它有1個箭頭是向外的，因此它一共給進(jìn)程分配了1個資源，此時，R1沒有空閑的資源剩余。第二步：再看R2資源，它有2個箭頭是向外的，因此它一共給進(jìn)程分配了2個資源，此時，R2沒有空閑的資源剩余。第三步：再看R3資源，它有1個箭頭是向外的，因此它一共給進(jìn)程分配了1個資源，此時，R3還剩余一個空閑的資源沒分配。第四步：再看R4資源，它有1個箭頭是向外的，因此它一共給進(jìn)程分配了1個資源，此時，R4沒有空閑的資源剩余。 第五步：從上面4步可以看出，整個系統(tǒng)只剩下R3一個空閑資源沒分配，第六步：看完資源，再來看進(jìn)程，先看進(jìn)程P1，它只申請一個R1資源，但此時R1資源已經(jīng)用光了，所以，進(jìn)程P1進(jìn)入阻塞狀態(tài)，因此，進(jìn)程P1暫時不能化成孤立的點(diǎn)。第七步：再看進(jìn)程P2，它只申請一個R4資源，但此時R4資源已經(jīng)用光了，所以，進(jìn)程P2進(jìn)入阻塞狀態(tài)，因此，進(jìn)程P2暫時不能化成孤立的點(diǎn)。第八步：再看