資源分配圖.doc

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