第04章死鎖及其對(duì)策

1、今天日期：今天日期：2021-11-12第四章第四章 死鎖及其對(duì)策死鎖及其對(duì)策第第 1 頁(yè)頁(yè)第四章 死鎖及其對(duì)策4.1 死鎖的基本概念死鎖的基本概念4.2 死鎖原理及對(duì)策死鎖原理及對(duì)策4.3 鴕鳥算法鴕鳥算法4.4 死鎖的檢測(cè)和恢復(fù)死鎖的檢測(cè)和恢復(fù)4.5 死鎖預(yù)防死鎖預(yù)防4.6 死鎖避免死鎖避免今天日期：今天日期：2021-11-12第四章第四章 死鎖及其對(duì)策死鎖及其對(duì)策第第 2 頁(yè)頁(yè)4.1 死鎖的基本概念死鎖的基本概念在計(jì)算機(jī)系統(tǒng)中，產(chǎn)生死鎖的直接原因是多個(gè)進(jìn)在計(jì)算機(jī)系統(tǒng)中，產(chǎn)生死鎖的直接原因是多個(gè)進(jìn)程的并發(fā)執(zhí)行。多個(gè)進(jìn)程的并發(fā)執(zhí)行改善了系統(tǒng)資源程的并發(fā)執(zhí)行。多個(gè)進(jìn)程的并發(fā)執(zhí)行改善了系統(tǒng)資源

2、的利用率，提高了系統(tǒng)的處理能力，但由于每個(gè)系統(tǒng)的利用率，提高了系統(tǒng)的處理能力，但由于每個(gè)系統(tǒng)資源都由多個(gè)進(jìn)程共享，有些資源本身又要求互斥的資源都由多個(gè)進(jìn)程共享，有些資源本身又要求互斥的使用，所以如果處理不當(dāng)就可能產(chǎn)生死鎖。使用，所以如果處理不當(dāng)就可能產(chǎn)生死鎖。今天日期：今天日期：2021-11-12第四章第四章 死鎖及其對(duì)策死鎖及其對(duì)策第第 3 頁(yè)頁(yè)4.1.1 4.1.1 資源資源依資源的性質(zhì)：可剝奪和非可剝奪資源依資源的性質(zhì)：可剝奪和非可剝奪資源可剝奪資源可剝奪資源：處理機(jī)和內(nèi)存處理機(jī)和內(nèi)存非可剝奪資源非可剝奪資源：磁帶和打印機(jī)磁帶和打印機(jī)依資源的使用方式：共享資源和獨(dú)享資源依資源的使用方式

3、：共享資源和獨(dú)享資源共享資源共享資源：處理機(jī)、內(nèi)存、磁盤等處理機(jī)、內(nèi)存、磁盤等獨(dú)享資源獨(dú)享資源：磁帶機(jī)、讀卡機(jī)和打印機(jī)等磁帶機(jī)、讀卡機(jī)和打印機(jī)等依資源的使用期限：永久資源和臨時(shí)資源依資源的使用期限：永久資源和臨時(shí)資源永久資源永久資源：硬資源和可重入的純代碼過程硬資源和可重入的純代碼過程臨時(shí)資源臨時(shí)資源：進(jìn)程同步和通信過程中出現(xiàn)的消息、信號(hào)的數(shù)據(jù)。進(jìn)程同步和通信過程中出現(xiàn)的消息、信號(hào)的數(shù)據(jù)。 在進(jìn)行資源分配時(shí)，一定要先認(rèn)清相應(yīng)資源的特性，以便選擇在進(jìn)行資源分配時(shí)，一定要先認(rèn)清相應(yīng)資源的特性，以便選擇合適的分配策略，在競(jìng)爭(zhēng)非剝奪資源和臨時(shí)性資源時(shí)都可能產(chǎn)生死合適的分配策略，在競(jìng)爭(zhēng)非剝奪資源和臨時(shí)性

4、資源時(shí)都可能產(chǎn)生死鎖。在并發(fā)進(jìn)程的活動(dòng)中，若選擇一種合理的推進(jìn)順序就可以避免鎖。在并發(fā)進(jìn)程的活動(dòng)中，若選擇一種合理的推進(jìn)順序就可以避免死鎖的發(fā)生。死鎖的發(fā)生。今天日期：今天日期：2021-11-12第四章第四章 死鎖及其對(duì)策死鎖及其對(duì)策第第 4 頁(yè)頁(yè)4.1.2 死鎖的定義死鎖的定義死鎖是計(jì)算機(jī)系統(tǒng)中多道程序并發(fā)執(zhí)行時(shí)，兩個(gè)或死鎖是計(jì)算機(jī)系統(tǒng)中多道程序并發(fā)執(zhí)行時(shí)，兩個(gè)或兩個(gè)以上的進(jìn)程由于競(jìng)爭(zhēng)系統(tǒng)資源而出現(xiàn)的一種互相等兩個(gè)以上的進(jìn)程由于競(jìng)爭(zhēng)系統(tǒng)資源而出現(xiàn)的一種互相等待的現(xiàn)象。待的現(xiàn)象。此時(shí)，每個(gè)進(jìn)程都此時(shí)，每個(gè)進(jìn)程都“占用占用”一些其他進(jìn)程正在等待一些其他進(jìn)程正在等待的資源，而用，每個(gè)進(jìn)程都的資源

5、，而用，每個(gè)進(jìn)程都 沒有完全得到所有的資源，沒有完全得到所有的資源，結(jié)果所有這些進(jìn)程互相等待，誰(shuí)也無法繼續(xù)，我們稱這結(jié)果所有這些進(jìn)程互相等待，誰(shuí)也無法繼續(xù)，我們稱這些進(jìn)程是死鎖的，相應(yīng)的計(jì)算機(jī)系統(tǒng)處于死鎖狀態(tài)。些進(jìn)程是死鎖的，相應(yīng)的計(jì)算機(jī)系統(tǒng)處于死鎖狀態(tài)。今天日期：今天日期：2021-11-12第四章第四章 死鎖及其對(duì)策死鎖及其對(duì)策第第 5 頁(yè)頁(yè)4.1.3 產(chǎn)生死鎖的原因產(chǎn)生死鎖的原因系統(tǒng)競(jìng)爭(zhēng)臨界資源系統(tǒng)競(jìng)爭(zhēng)臨界資源。當(dāng)系統(tǒng)所擁有的某種臨界資源當(dāng)系統(tǒng)所擁有的某種臨界資源個(gè)數(shù)比各個(gè)進(jìn)程要求該資源的總數(shù)要少時(shí)，則有可能引個(gè)數(shù)比各個(gè)進(jìn)程要求該資源的總數(shù)要少時(shí)，則有可能引起多個(gè)并發(fā)進(jìn)程對(duì)資源的競(jìng)爭(zhēng)而產(chǎn)

6、生死鎖。起多個(gè)并發(fā)進(jìn)程對(duì)資源的競(jìng)爭(zhēng)而產(chǎn)生死鎖。進(jìn)程推進(jìn)順序不當(dāng)進(jìn)程推進(jìn)順序不當(dāng)，進(jìn)程運(yùn)行過程中，由于請(qǐng)示和進(jìn)程運(yùn)行過程中，由于請(qǐng)示和釋放資源的順序不當(dāng)，而產(chǎn)生死鎖。釋放資源的順序不當(dāng)，而產(chǎn)生死鎖。今天日期：今天日期：2021-11-12第四章第四章 死鎖及其對(duì)策死鎖及其對(duì)策第第 6 頁(yè)頁(yè)1、競(jìng)爭(zhēng)臨界資源引起的死鎖、競(jìng)爭(zhēng)臨界資源引起的死鎖u 競(jìng)爭(zhēng)非剝奪性資源引起的死鎖競(jìng)爭(zhēng)非剝奪性資源引起的死鎖u 競(jìng)爭(zhēng)臨時(shí)性資源引起的死鎖競(jìng)爭(zhēng)臨時(shí)性資源引起的死鎖u 競(jìng)爭(zhēng)同一類資源引起的死鎖競(jìng)爭(zhēng)同一類資源引起的死鎖2、進(jìn)程推進(jìn)順序不當(dāng)引起的死鎖、進(jìn)程推進(jìn)順序不當(dāng)引起的死鎖今天日期：今天日期：2021-11-12第四

7、章第四章 死鎖及其對(duì)策死鎖及其對(duì)策第第 7 頁(yè)頁(yè)0 0g1g1g2g2g3g3a1a1b1b1c1c1d1d1p1p1進(jìn)展進(jìn)展p2p2進(jìn)展進(jìn)展a2a2b2b2c2c2d2d2占占用用r2r2占用占用r2r21dn2占用占用r1r1占用占用r2r23占占用用r1r1占用占用r1r1今天日期：今天日期：2021-11-12第四章第四章 死鎖及其對(duì)策死鎖及其對(duì)策第第 8 頁(yè)頁(yè)4.2 死鎖原理及對(duì)策死鎖原理及對(duì)策4.2.1 死鎖原理及產(chǎn)生死鎖的必要條件死鎖原理及產(chǎn)生死鎖的必要條件 死鎖是與時(shí)間有關(guān)的一種現(xiàn)象，它涉及到多進(jìn)程死鎖是與時(shí)間有關(guān)的一種現(xiàn)象，它涉及到多進(jìn)程的并發(fā)，并發(fā)進(jìn)程對(duì)一些特殊資源的共享，

8、以及具體的并發(fā)，并發(fā)進(jìn)程對(duì)一些特殊資源的共享，以及具體進(jìn)行并發(fā)進(jìn)程資源調(diào)度的時(shí)機(jī)等。綜上所述，產(chǎn)生死進(jìn)行并發(fā)進(jìn)程資源調(diào)度的時(shí)機(jī)等。綜上所述，產(chǎn)生死鎖的四個(gè)必要條件如下：鎖的四個(gè)必要條件如下：互斥條件、不可剝奪條件、部分分配條件、環(huán)路等待互斥條件、不可剝奪條件、部分分配條件、環(huán)路等待條件條件今天日期：今天日期：2021-11-12第四章第四章 死鎖及其對(duì)策死鎖及其對(duì)策第第 9 頁(yè)頁(yè)4.2.2 死鎖的描述死鎖的描述1、資源分配圖、資源分配圖p2p1r1r2今天日期：今天日期：2021-11-12第四章第四章 死鎖及其對(duì)策死鎖及其對(duì)策第第 10 頁(yè)頁(yè)2 2、死鎖舉例、死鎖舉例u競(jìng)爭(zhēng)非剝奪性資源引起的

9、死鎖競(jìng)爭(zhēng)非剝奪性資源引起的死鎖u競(jìng)爭(zhēng)臨時(shí)性資源引起的死鎖競(jìng)爭(zhēng)臨時(shí)性資源引起的死鎖u競(jìng)爭(zhēng)同一類資源引起的死鎖競(jìng)爭(zhēng)同一類資源引起的死鎖r1p1r2p2s1p1s3p3p2s2p1p2p3今天日期：今天日期：2021-11-12第四章第四章 死鎖及其對(duì)策死鎖及其對(duì)策第第 11 頁(yè)頁(yè)4.2.3 解決死鎖的方法解決死鎖的方法1.預(yù)防死鎖預(yù)防死鎖：為了使系統(tǒng)不發(fā)生死鎖現(xiàn)象，在系統(tǒng)設(shè)計(jì)初期即為了使系統(tǒng)不發(fā)生死鎖現(xiàn)象，在系統(tǒng)設(shè)計(jì)初期即選擇一些限制條件，來破壞產(chǎn)生死鎖的四個(gè)必要選擇一些限制條件，來破壞產(chǎn)生死鎖的四個(gè)必要條件之一或其中幾個(gè)。這樣，系統(tǒng)中就不會(huì)出現(xiàn)條件之一或其中幾個(gè)。這樣，系統(tǒng)中就不會(huì)出現(xiàn)死鎖現(xiàn)象。

10、死鎖現(xiàn)象。2.避免死鎖避免死鎖：一方面預(yù)防死鎖的方法會(huì)降低系統(tǒng)資源利用率；一方面預(yù)防死鎖的方法會(huì)降低系統(tǒng)資源利用率；另一方面死鎖的必要條件在存在未必就一定會(huì)使另一方面死鎖的必要條件在存在未必就一定會(huì)使系統(tǒng)發(fā)生死鎖。因此為提高系統(tǒng)資源的利用率，系統(tǒng)發(fā)生死鎖。因此為提高系統(tǒng)資源的利用率，避免死鎖并不嚴(yán)格限制死鎖必要條件的存在，而避免死鎖并不嚴(yán)格限制死鎖必要條件的存在，而是在資源的動(dòng)態(tài)分配過程中，使用某種方法去防是在資源的動(dòng)態(tài)分配過程中，使用某種方法去防止系統(tǒng)進(jìn)入不安全狀態(tài)，從而避免死鎖的最終出止系統(tǒng)進(jìn)入不安全狀態(tài)，從而避免死鎖的最終出現(xiàn)。現(xiàn)。今天日期：今天日期：2021-11-12第四章第四章 死

11、鎖及其對(duì)策死鎖及其對(duì)策第第 12 頁(yè)頁(yè)3.檢測(cè)和解除死鎖檢測(cè)和解除死鎖：在一些相對(duì)簡(jiǎn)單的系統(tǒng)中，為節(jié)省預(yù)防在一些相對(duì)簡(jiǎn)單的系統(tǒng)中，為節(jié)省預(yù)防和避免死鎖而增加的系統(tǒng)開銷，又因?yàn)樗梨i產(chǎn)生和避免死鎖而增加的系統(tǒng)開銷，又因?yàn)樗梨i產(chǎn)生的概率總是比較小的，所以系統(tǒng)中允許出現(xiàn)死鎖的概率總是比較小的，所以系統(tǒng)中允許出現(xiàn)死鎖狀態(tài)。在這種系統(tǒng)中，專門設(shè)置了一個(gè)檢測(cè)機(jī)構(gòu)，狀態(tài)。在這種系統(tǒng)中，專門設(shè)置了一個(gè)檢測(cè)機(jī)構(gòu)，可以隨時(shí)檢測(cè)出死鎖的發(fā)生，并能確定與死鎖有可以隨時(shí)檢測(cè)出死鎖的發(fā)生，并能確定與死鎖有關(guān)的進(jìn)程和資源，然后采用適當(dāng)?shù)姆椒ń獬到y(tǒng)關(guān)的進(jìn)程和資源，然后采用適當(dāng)?shù)姆椒ń獬到y(tǒng)中的死鎖狀態(tài)。常用的方法有：中的死鎖

12、狀態(tài)。常用的方法有：l一是強(qiáng)制性的撤銷一些死鎖進(jìn)程，并剝奪它一是強(qiáng)制性的撤銷一些死鎖進(jìn)程，并剝奪它們的資源給其余進(jìn)程；們的資源給其余進(jìn)程；l一是使用一個(gè)有效的掛起和解除掛起機(jī)構(gòu)來一是使用一個(gè)有效的掛起和解除掛起機(jī)構(gòu)來掛起一些進(jìn)程，以便從被掛起的進(jìn)程中剝奪掛起一些進(jìn)程，以便從被掛起的進(jìn)程中剝奪一些資源用來解除死鎖。一些資源用來解除死鎖。今天日期：今天日期：2021-11-12第四章第四章 死鎖及其對(duì)策死鎖及其對(duì)策第第 13 頁(yè)頁(yè)4.4 死鎖的檢測(cè)與恢復(fù)死鎖的檢測(cè)與恢復(fù)檢測(cè)系統(tǒng)中是否存在死鎖產(chǎn)生的必要條件：檢測(cè)系統(tǒng)中是否存在死鎖產(chǎn)生的必要條件：環(huán)路等待環(huán)路等待4.4.1 利用資源分配圖描述系統(tǒng)狀態(tài)

13、利用資源分配圖描述系統(tǒng)狀態(tài)1、死鎖狀態(tài)的推斷思想、死鎖狀態(tài)的推斷思想封鎖進(jìn)程封鎖進(jìn)程：是指某個(gè)進(jìn)程由于請(qǐng)求了超過系統(tǒng)中現(xiàn)有是指某個(gè)進(jìn)程由于請(qǐng)求了超過系統(tǒng)中現(xiàn)有的未分配資源數(shù)目的資源，而被系統(tǒng)封鎖的進(jìn)程。的未分配資源數(shù)目的資源，而被系統(tǒng)封鎖的進(jìn)程。非封鎖進(jìn)程非封鎖進(jìn)程：沒有被系統(tǒng)封鎖的進(jìn)程沒有被系統(tǒng)封鎖的進(jìn)程今天日期：今天日期：2021-11-12第四章第四章 死鎖及其對(duì)策死鎖及其對(duì)策第第 14 頁(yè)頁(yè)2、資源分配圖的化簡(jiǎn)、資源分配圖的化簡(jiǎn) 假設(shè)某個(gè)資源分配圖中存在一個(gè)進(jìn)程假設(shè)某個(gè)資源分配圖中存在一個(gè)進(jìn)程pipi，此刻，此刻 pipi 是非是非封鎖進(jìn)程，那么可對(duì)此資源分配圖作以下化簡(jiǎn)：當(dāng)封鎖進(jìn)程，

14、那么可對(duì)此資源分配圖作以下化簡(jiǎn)：當(dāng) pipi 有請(qǐng)有請(qǐng)求邊時(shí)，首先將其請(qǐng)求邊變成分配邊，即滿足求邊時(shí)，首先將其請(qǐng)求邊變成分配邊，即滿足pipi 進(jìn)程的相應(yīng)進(jìn)程的相應(yīng)資源請(qǐng)求，而一旦資源請(qǐng)求，而一旦pipi 進(jìn)程的所有資源請(qǐng)求都得到滿足，進(jìn)程的所有資源請(qǐng)求都得到滿足， pipi 進(jìn)程就能在有限時(shí)間內(nèi)運(yùn)行結(jié)束，并釋放它所占用的所有資進(jìn)程就能在有限時(shí)間內(nèi)運(yùn)行結(jié)束，并釋放它所占用的所有資源。所以此時(shí)源。所以此時(shí)pipi 只有分配邊，可以將所有這些分配邊刪去。只有分配邊，可以將所有這些分配邊刪去?？傊?，對(duì)非封鎖進(jìn)程總之，對(duì)非封鎖進(jìn)程pipi 的化簡(jiǎn)即刪除資源分配圖中與的化簡(jiǎn)即刪除資源分配圖中與pipi

15、連接的所有有向邊，使連接的所有有向邊，使pipi 成為孤立結(jié)點(diǎn)。成為孤立結(jié)點(diǎn)。p2p1r1r2p2p1r1r2p2p1r1r2(a)(b)(c)今天日期：今天日期：2021-11-12第四章第四章 死鎖及其對(duì)策死鎖及其對(duì)策第第 15 頁(yè)頁(yè)假如一個(gè)資源分配圖可以被其上的所有進(jìn)程所化簡(jiǎn)，則假如一個(gè)資源分配圖可以被其上的所有進(jìn)程所化簡(jiǎn)，則稱該圖為稱該圖為完全可化簡(jiǎn)的完全可化簡(jiǎn)的。反之，若一個(gè)資源分配圖不能被其上的任一進(jìn)程化簡(jiǎn)，反之，若一個(gè)資源分配圖不能被其上的任一進(jìn)程化簡(jiǎn)，則稱其為則稱其為不可化簡(jiǎn)的不可化簡(jiǎn)的。若某個(gè)資源分配圖只能被其上的一些進(jìn)程所化簡(jiǎn)，則該若某個(gè)資源分配圖只能被其上的一些進(jìn)程所化簡(jiǎn)

16、，則該圖為圖為非完全可化簡(jiǎn)的非完全可化簡(jiǎn)的。p2p1r1r2圖圖 完全可化簡(jiǎn)的資源分配圖完全可化簡(jiǎn)的資源分配圖p2p1r1r2圖圖 不可化簡(jiǎn)的資源分配圖不可化簡(jiǎn)的資源分配圖今天日期：今天日期：2021-11-12第四章第四章 死鎖及其對(duì)策死鎖及其對(duì)策第第 16 頁(yè)頁(yè)3、死鎖定理：當(dāng)一個(gè)資源分配圖是完全可化簡(jiǎn)時(shí)，該資當(dāng)一個(gè)資源分配圖是完全可化簡(jiǎn)時(shí)，該資源分配圖能被其上所有的進(jìn)程所化簡(jiǎn)。也就是此時(shí)系統(tǒng)中存源分配圖能被其上所有的進(jìn)程所化簡(jiǎn)。也就是此時(shí)系統(tǒng)中存在一個(gè)進(jìn)程序列，按此安全序列的順序運(yùn)行，可使每個(gè)進(jìn)程在一個(gè)進(jìn)程序列，按此安全序列的順序運(yùn)行，可使每個(gè)進(jìn)程都順利完成，所以此時(shí)系統(tǒng)處于都順利完成，

17、所以此時(shí)系統(tǒng)處于安全狀態(tài)安全狀態(tài)，即系統(tǒng)不會(huì)發(fā)生，即系統(tǒng)不會(huì)發(fā)生死鎖。反之當(dāng)某資源分配圖是非完全可化簡(jiǎn)的時(shí)候，說明該死鎖。反之當(dāng)某資源分配圖是非完全可化簡(jiǎn)的時(shí)候，說明該資源分配圖不能被中的一些進(jìn)程所化簡(jiǎn)。也就是此刻系統(tǒng)中資源分配圖不能被中的一些進(jìn)程所化簡(jiǎn)。也就是此刻系統(tǒng)中出現(xiàn)了一些互相等待的封鎖進(jìn)程，系統(tǒng)中不存在一個(gè)進(jìn)程的出現(xiàn)了一些互相等待的封鎖進(jìn)程，系統(tǒng)中不存在一個(gè)進(jìn)程的安全序列。這些互相等待的封鎖進(jìn)程永遠(yuǎn)無法運(yùn)行到終點(diǎn)，安全序列。這些互相等待的封鎖進(jìn)程永遠(yuǎn)無法運(yùn)行到終點(diǎn)，所以此時(shí)系統(tǒng)處于死鎖狀態(tài)。資源分配圖中不能化簡(jiǎn)的進(jìn)程所以此時(shí)系統(tǒng)處于死鎖狀態(tài)。資源分配圖中不能化簡(jiǎn)的進(jìn)程即為死鎖進(jìn)程。即

18、為死鎖進(jìn)程。死鎖定理：系統(tǒng)中某個(gè)時(shí)刻死鎖定理：系統(tǒng)中某個(gè)時(shí)刻s為死鎖狀態(tài)的充分必要條為死鎖狀態(tài)的充分必要條件是，件是，s時(shí)刻系統(tǒng)的資源分配圖是非完全可化簡(jiǎn)的。時(shí)刻系統(tǒng)的資源分配圖是非完全可化簡(jiǎn)的。今天日期：今天日期：2021-11-12第四章第四章 死鎖及其對(duì)策死鎖及其對(duì)策第第 17 頁(yè)頁(yè)4.4.2 死鎖檢測(cè)中的數(shù)據(jù)結(jié)構(gòu)死鎖檢測(cè)中的數(shù)據(jù)結(jié)構(gòu) 假設(shè)系統(tǒng)中的假設(shè)系統(tǒng)中的n n個(gè)進(jìn)程個(gè)進(jìn)程p1,p2,p1,p2,pn,pn，有，有m m種資種資源，源，r1,r2,r1,r2,rm,rm，則請(qǐng)求矩陣和分配矩陣都，則請(qǐng)求矩陣和分配矩陣都是一個(gè)是一個(gè)n nm m的二維數(shù)組：的二維數(shù)組：(1) 請(qǐng)求矩陣請(qǐng)求

19、矩陣re：是一個(gè)是一個(gè)n nm m的二維數(shù)組，的二維數(shù)組，每行代表一個(gè)進(jìn)程當(dāng)前對(duì)各類資源的請(qǐng)求數(shù)目。每行代表一個(gè)進(jìn)程當(dāng)前對(duì)各類資源的請(qǐng)求數(shù)目。若若re( i,j)=k,re( i,j)=k,則代表第則代表第 i i個(gè)進(jìn)程個(gè)進(jìn)程pipi請(qǐng)求了請(qǐng)求了rjrj類資源類資源k k個(gè)分配單位。個(gè)分配單位。(2) 分配矩陣分配矩陣al：是一個(gè)是一個(gè)n nm m的二維數(shù)組，的二維數(shù)組，代表某個(gè)時(shí)刻系統(tǒng)中資源的分配情況。若代表某個(gè)時(shí)刻系統(tǒng)中資源的分配情況。若al( i,j)=k,al( i,j)=k,則代表第則代表第 i i個(gè)進(jìn)程個(gè)進(jìn)程pipi已分配到了已分配到了rjrj類資源類資源k k個(gè)分配單位。個(gè)分配單

20、位。p1pnp2r1r2rm )m,nre(.),nre(),nre(.)m,re(.),re(),re()m,re(.),re(),re(212221212111 )m,n(al.),n(al),n(al.)m,(al.),(al),(al)m,(al.),(al),(al212221212111今天日期：今天日期：2021-11-12第四章第四章 死鎖及其對(duì)策死鎖及其對(duì)策第第 18 頁(yè)頁(yè)(3)(3)可利用資源向量可利用資源向量av，是一個(gè)長(zhǎng)度為m的一維數(shù)組，表示系統(tǒng)中各類資源的可利用數(shù)目。(4)(4)工作向量工作向量work：是一個(gè)長(zhǎng)度為m的一維數(shù)組，動(dòng)態(tài)的反映系統(tǒng)中可讓進(jìn)程運(yùn)行的各類資源

21、的數(shù)目。(5)(5)進(jìn)程向量進(jìn)程向量l：是一個(gè)集合，所有已運(yùn)行結(jié)束的進(jìn)程都送入l中，若最后l中包括了所有的n個(gè)進(jìn)程，則說明系統(tǒng)處于安全狀態(tài)。 )m(a.,),(a),(aa 21 )m(work.,)(work),(workwork21 今天日期：今天日期：2021-11-12第四章第四章 死鎖及其對(duì)策死鎖及其對(duì)策第第 19 頁(yè)頁(yè)4.4.3 死鎖檢測(cè)算法死鎖檢測(cè)算法1 1、在某個(gè)時(shí)刻在某個(gè)時(shí)刻t t，j j從從1 1到到m m執(zhí)行執(zhí)行work(j)=av(j)work(j)=av(j)。2 2、檢查檢查alal矩陣和矩陣和rere矩陣，是否存在某個(gè)矩陣，是否存在某個(gè)i( ii( i從從1 1到

22、到m)m)使使alal矩陣第矩陣第i i行中所行中所有的有的al(i,jal(i,j) )和和rere矩陣第矩陣第i i行中所有的行中所有的re(i,jre(i,j) )均為零。若存在這個(gè)均為零。若存在這個(gè)i i說明在說明在資源分配圖中資源分配圖中pipi進(jìn)程已成為孤立結(jié)點(diǎn)，將進(jìn)程已成為孤立結(jié)點(diǎn)，將pipi進(jìn)程送入進(jìn)程向量進(jìn)程送入進(jìn)程向量l l中。中。3 3、在系統(tǒng)中除已送入在系統(tǒng)中除已送入l l之外的所有進(jìn)程中逐個(gè)尋找，若某個(gè)之外的所有進(jìn)程中逐個(gè)尋找，若某個(gè) i i使使re(i,jre(i,j)=work(j)=work(j)，(j(j的取值從的取值從1 1到到m)m)，則執(zhí)行：，則執(zhí)行：1

23、) j1) j從從1 1到到m m，work(j)=work(j)+al( i,j)work(j)=work(j)+al( i,j)2) j2) j從從1 1到到m m，令所有的，令所有的al( i,j)=0al( i,j)=0，所有的，所有的re( i,j)=0re( i,j)=03) 3) 將當(dāng)前的這個(gè)進(jìn)程也送入進(jìn)程向量將當(dāng)前的這個(gè)進(jìn)程也送入進(jìn)程向量l l中中這樣反復(fù)執(zhí)行，直到所有這樣反復(fù)執(zhí)行，直到所有l(wèi) l以外的進(jìn)程中再?zèng)]有滿足上述條件為止。以外的進(jìn)程中再?zèng)]有滿足上述條件為止。4 4、檢查檢查l l向量，若向量，若n n個(gè)進(jìn)程都在個(gè)進(jìn)程都在l l中，說明系統(tǒng)中不會(huì)發(fā)生死鎖，反之，系中，說

24、明系統(tǒng)中不會(huì)發(fā)生死鎖，反之，系統(tǒng)中存在死鎖，那些沒能進(jìn)入統(tǒng)中存在死鎖，那些沒能進(jìn)入l l向量的進(jìn)程均為死鎖進(jìn)程。向量的進(jìn)程均為死鎖進(jìn)程。今天日期：今天日期：2021-11-12第四章第四章 死鎖及其對(duì)策死鎖及其對(duì)策第第 20 頁(yè)頁(yè)由于當(dāng)系統(tǒng)中有了新的請(qǐng)求，而這種請(qǐng)求又不能立由于當(dāng)系統(tǒng)中有了新的請(qǐng)求，而這種請(qǐng)求又不能立即滿足時(shí)才可能發(fā)生死鎖。即滿足時(shí)才可能發(fā)生死鎖。所以在一個(gè)非死鎖狀態(tài)的前所以在一個(gè)非死鎖狀態(tài)的前提下，要判斷下一個(gè)狀態(tài)是否為死鎖，只需要在某個(gè)進(jìn)提下，要判斷下一個(gè)狀態(tài)是否為死鎖，只需要在某個(gè)進(jìn)程執(zhí)行新的進(jìn)程請(qǐng)求而又不能立即滿足時(shí)，進(jìn)行死鎖檢程執(zhí)行新的進(jìn)程請(qǐng)求而又不能立即滿足時(shí)，進(jìn)行

25、死鎖檢測(cè)測(cè)，由于死鎖檢測(cè)算法執(zhí)行時(shí)間長(zhǎng)、系統(tǒng)開銷大，可以，由于死鎖檢測(cè)算法執(zhí)行時(shí)間長(zhǎng)、系統(tǒng)開銷大，可以在較長(zhǎng)時(shí)間間隔后，執(zhí)行一次檢測(cè)算法。在較長(zhǎng)時(shí)間間隔后，執(zhí)行一次檢測(cè)算法。今天日期：今天日期：2021-11-12第四章第四章 死鎖及其對(duì)策死鎖及其對(duì)策第第 21 頁(yè)頁(yè)4.4.4 死鎖的恢復(fù)死鎖的恢復(fù)強(qiáng)制性地從系統(tǒng)中撤銷一些死鎖進(jìn)程，并剝奪它們的資源強(qiáng)制性地從系統(tǒng)中撤銷一些死鎖進(jìn)程，并剝奪它們的資源給其余進(jìn)程。給其余進(jìn)程。使用一個(gè)有效的掛起和解除機(jī)構(gòu)來掛起一些進(jìn)程，以便從使用一個(gè)有效的掛起和解除機(jī)構(gòu)來掛起一些進(jìn)程，以便從被掛起的進(jìn)程中剝奪一些資源用來解除死鎖被掛起的進(jìn)程中剝奪一些資源用來解除死鎖

26、1、撤銷進(jìn)程、撤銷進(jìn)程：為了保證系統(tǒng)所受到的影響最小，可以逐為了保證系統(tǒng)所受到的影響最小，可以逐個(gè)撤銷進(jìn)程，直到死鎖不復(fù)存在為止。一般依次選擇撤銷代價(jià)個(gè)撤銷進(jìn)程，直到死鎖不復(fù)存在為止。一般依次選擇撤銷代價(jià)最小的進(jìn)程。最小的進(jìn)程。撤銷代價(jià)包括：撤銷代價(jià)包括：進(jìn)程的優(yōu)先數(shù)、運(yùn)行代價(jià)（從重新啟動(dòng)進(jìn)程的優(yōu)先數(shù)、運(yùn)行代價(jià)（從重新啟動(dòng)該進(jìn)程并運(yùn)行到此撤銷時(shí)刻所需要的時(shí)該進(jìn)程并運(yùn)行到此撤銷時(shí)刻所需要的時(shí)間）、該進(jìn)程對(duì)應(yīng)作業(yè)的外部代價(jià)。間）、該進(jìn)程對(duì)應(yīng)作業(yè)的外部代價(jià)。2、掛起進(jìn)程、掛起進(jìn)程今天日期：今天日期：2021-11-12第四章第四章 死鎖及其對(duì)策死鎖及其對(duì)策第第 22 頁(yè)頁(yè)4.5 死鎖的預(yù)防死鎖的預(yù)防

27、4.5.1 4.5.1 打破打破“不剝奪不剝奪”條件條件強(qiáng)迫那些請(qǐng)求新資源而沒有立即得到滿足的進(jìn)程釋放它已保持的其它強(qiáng)迫那些請(qǐng)求新資源而沒有立即得到滿足的進(jìn)程釋放它已保持的其它資源，即一個(gè)進(jìn)程已占用的資源在運(yùn)行過程中可能要暫時(shí)釋放。實(shí)現(xiàn)復(fù)雜，資源，即一個(gè)進(jìn)程已占用的資源在運(yùn)行過程中可能要暫時(shí)釋放。實(shí)現(xiàn)復(fù)雜，只適用于只適用于cpucpu和內(nèi)存。和內(nèi)存。4.5.2 4.5.2 打破打破“部分分配部分分配”條件條件對(duì)某進(jìn)程所要求的資源一次性地分配完畢，又稱預(yù)先靜態(tài)分配法。對(duì)某進(jìn)程所要求的資源一次性地分配完畢，又稱預(yù)先靜態(tài)分配法。4.5.3 4.5.3 打破打破“環(huán)路等待環(huán)路等待”條件條件在資源的分配

28、過程中，對(duì)資源的請(qǐng)求作出某種限制，使環(huán)路不可能出在資源的分配過程中，對(duì)資源的請(qǐng)求作出某種限制，使環(huán)路不可能出現(xiàn)?，F(xiàn)。今天日期：今天日期：2021-11-12第四章第四章 死鎖及其對(duì)策死鎖及其對(duì)策第第 23 頁(yè)頁(yè)具體的方法是具體的方法是：為系統(tǒng)中每種資源規(guī)定一個(gè)唯一的為系統(tǒng)中每種資源規(guī)定一個(gè)唯一的序號(hào)，例如，輸入機(jī)為序號(hào)，例如，輸入機(jī)為1 1，打印機(jī)為，打印機(jī)為2 2，穿孔機(jī)為，穿孔機(jī)為3 3，磁帶，磁帶機(jī)為機(jī)為4 4，磁盤機(jī)為，磁盤機(jī)為5 5等，而且要求每個(gè)進(jìn)程都要嚴(yán)格按照等，而且要求每個(gè)進(jìn)程都要嚴(yán)格按照遞增的順序請(qǐng)求資源。若能認(rèn)真的安排資源序號(hào)，將各遞增的順序請(qǐng)求資源。若能認(rèn)真的安排資源序號(hào)

29、，將各作業(yè)經(jīng)常使用的、比較普通的資源安排成低序號(hào)，不常作業(yè)經(jīng)常使用的、比較普通的資源安排成低序號(hào)，不常使用的資源、比較繁重的資源安排成高序號(hào)，便能提高使用的資源、比較繁重的資源安排成高序號(hào)，便能提高資源的利用率。但在各資源的序號(hào)安排好后，不能經(jīng)常資源的利用率。但在各資源的序號(hào)安排好后，不能經(jīng)常變動(dòng)。變動(dòng)。今天日期：今天日期：2021-11-12第四章第四章 死鎖及其對(duì)策死鎖及其對(duì)策第第 24 頁(yè)頁(yè)4.6 死鎖避免4.6.1 系統(tǒng)狀態(tài)的安全性系統(tǒng)狀態(tài)的安全性1 1、安全狀態(tài)、安全狀態(tài)：是指系統(tǒng)能按照某種順序?yàn)槊總€(gè)進(jìn)程分配是指系統(tǒng)能按照某種順序?yàn)槊總€(gè)進(jìn)程分配所需的資源，使每個(gè)進(jìn)程都能順利完成。所需

30、的資源，使每個(gè)進(jìn)程都能順利完成。當(dāng)且僅當(dāng)系統(tǒng)中存在此安全序列時(shí)，系統(tǒng)當(dāng)且僅當(dāng)系統(tǒng)中存在此安全序列時(shí)，系統(tǒng)處于安全狀態(tài)。處于安全狀態(tài)。假設(shè)系統(tǒng)中有假設(shè)系統(tǒng)中有3 3個(gè)進(jìn)程，個(gè)進(jìn)程，1010個(gè)可供分配的資源單位個(gè)可供分配的資源單位進(jìn)程進(jìn)程 已分配資源已分配資源 還需申請(qǐng)的資源還需申請(qǐng)的資源p1 4 4p2 2 2p3 2 7今天日期：今天日期：2021-11-12第四章第四章 死鎖及其對(duì)策死鎖及其對(duì)策第第 25 頁(yè)頁(yè)2 2、不安全狀態(tài)、不安全狀態(tài)：某個(gè)時(shí)刻系統(tǒng)中不存在一個(gè)安全序列，某個(gè)時(shí)刻系統(tǒng)中不存在一個(gè)安全序列，能使所有的進(jìn)程都順利完成。不安全狀能使所有的進(jìn)程都順利完成。不安全狀態(tài)不是死鎖狀態(tài)，

31、進(jìn)入不安全狀態(tài)的進(jìn)態(tài)不是死鎖狀態(tài)，進(jìn)入不安全狀態(tài)的進(jìn)程有可能進(jìn)入死鎖。程有可能進(jìn)入死鎖。4.6.2 銀行家算法銀行家算法 前提條件：前提條件：分配資源的單位是固定的，請(qǐng)求資源的分配資源的單位是固定的，請(qǐng)求資源的進(jìn)程數(shù)也固定不變，而且每個(gè)進(jìn)程必須先告訴系統(tǒng)對(duì)某進(jìn)程數(shù)也固定不變，而且每個(gè)進(jìn)程必須先告訴系統(tǒng)對(duì)某類資源的最大需求量，當(dāng)某個(gè)進(jìn)程要求的資源數(shù)量小于類資源的最大需求量，當(dāng)某個(gè)進(jìn)程要求的資源數(shù)量小于系統(tǒng)所擁有的該類資源的最大量時(shí)，系統(tǒng)會(huì)在有限的時(shí)系統(tǒng)所擁有的該類資源的最大量時(shí)，系統(tǒng)會(huì)在有限的時(shí)間內(nèi)滿足進(jìn)程的要求。間內(nèi)滿足進(jìn)程的要求。今天日期：今天日期：2021-11-12第四章第四章 死鎖及其

32、對(duì)策死鎖及其對(duì)策第第 26 頁(yè)頁(yè)銀行家算法是銀行家算法是最有代表性的避免死鎖算法，由最有代表性的避免死鎖算法，由dijkstradijkstra提出。提出。1 1、銀行家算法中的數(shù)據(jù)結(jié)構(gòu)、銀行家算法中的數(shù)據(jù)結(jié)構(gòu)(1)(1)可利用資源向量可利用資源向量avav 它是一個(gè)含有它是一個(gè)含有m m個(gè)元素的數(shù)組，其中每個(gè)元素個(gè)元素的數(shù)組，其中每個(gè)元素代表一類可利用資源的數(shù)目。代表一類可利用資源的數(shù)目。例如：例如：3253r2r1ravav數(shù)組數(shù)組今天日期：今天日期：2021-11-12第四章第四章 死鎖及其對(duì)策死鎖及其對(duì)策第第 27 頁(yè)頁(yè)(2)(2)最大需求矩陣最大需求矩陣maxmax n nm m矩陣

33、，表示矩陣，表示n n個(gè)進(jìn)程的每一個(gè)對(duì)個(gè)進(jìn)程的每一個(gè)對(duì)m m類資源的最大類資源的最大需求。需求。例如：假設(shè)例如：假設(shè)n=5,m=3 2983124435726155p4p3p2p1p3r2r1rmaxmax矩陣為：矩陣為：今天日期：今天日期：2021-11-12第四章第四章 死鎖及其對(duì)策死鎖及其對(duì)策第第 28 頁(yè)頁(yè)(3)(3)分配矩陣分配矩陣alal n nm m矩陣，表示每個(gè)進(jìn)程分配的資源數(shù)。矩陣，表示每個(gè)進(jìn)程分配的資源數(shù)。例如：設(shè)例如：設(shè)n=5,m=3 2001122030020105p4p3p2p1p3r2r1ralal矩陣為：矩陣為：今天日期：今天日期：2021-11-12第四章第四章

34、 死鎖及其對(duì)策死鎖及其對(duì)策第第 29 頁(yè)頁(yè)(4)(4)需求矩陣需求矩陣needneed n nm m矩陣，表示每個(gè)進(jìn)程還需要各類資源矩陣，表示每個(gè)進(jìn)程還需要各類資源數(shù)。數(shù)。例如：例如：n=5,m=3 1341100062213475p4p3p2p1p3r2r1rneedneed矩陣為：矩陣為：今天日期：今天日期：2021-11-12第四章第四章 死鎖及其對(duì)策死鎖及其對(duì)策第第 30 頁(yè)頁(yè)2.銀行家算法描述當(dāng)進(jìn)程pi提出資源申請(qǐng)時(shí)，系統(tǒng)執(zhí)行下列步驟：所有所有re(i,j)=need(i,j)？(j=1,2,m)所有所有re(i,j)=av(j)？(j=1,2,m)av(j)=av(j)-re(i,

35、j)al(i,j)=al(i,j)+re(i, j)need(i,j)=need(i,j)-re(i,j)(j=1,2,m)av(j)=av(j)+re(i,j)al(i,j)=al(i,j)-re(i,j)need(i,j)=need(i,j)+re(i,j)(j=1,2,m)出錯(cuò)處理系統(tǒng)是否處于安全狀態(tài)？系統(tǒng)是否處于安全狀態(tài)？斷定分配可以進(jìn)行斷定分配可以進(jìn)行否否否否是是是是是是否否結(jié)束結(jié)束pi必須等待執(zhí)行安全執(zhí)行安全性算法性算法恢復(fù)分配前資源狀態(tài)恢復(fù)分配前資源狀態(tài)今天日期：今天日期：2021-11-12第四章第四章 死鎖及其對(duì)策死鎖及其對(duì)策第第 31 頁(yè)頁(yè)3. 安全性算法work(j)=a

36、v(i,j)(j=1,2,m)finish(i)=false(i=1,2,n)找能滿足找能滿足finish(i)=false(i=1,2,n)且且need(i,j)=work(j) (j=1,2,m)的進(jìn)程的進(jìn)程piwork(j)=work(j)+al(i,j)(j=1,2,m)令令 finish(i)=true說明系統(tǒng)處于不安全狀態(tài)說明系統(tǒng)處于不安全狀態(tài)即、至少有一個(gè)即、至少有一個(gè)pi，使，使finish(i)=false所有的所有的finish(i)=true ？(i=1,2,n)則系統(tǒng)為安全狀態(tài)則系統(tǒng)為安全狀態(tài)安全性算法結(jié)束安全性算法結(jié)束找到找到是是找不到找不到否否今天日期：今天日期：2

37、021-11-12第四章第四章 死鎖及其對(duì)策死鎖及其對(duì)策第第 32 頁(yè)頁(yè)4.6.3 銀行家算法舉例設(shè)系統(tǒng)有五個(gè)進(jìn)程和三類資源，每類資源分別有設(shè)系統(tǒng)有五個(gè)進(jìn)程和三類資源，每類資源分別有1010、5 5、7 7。在在t t1 1時(shí)刻資源分配情況如下圖：時(shí)刻資源分配情況如下圖： 2001122030020105p4p3p2p1p3r2r1ralal矩陣：矩陣： 1341100062213475p4p3p2p1p3r2r1rneedneed矩陣：矩陣：2333r2r1ravav數(shù)組：數(shù)組：今天日期：今天日期：2021-11-12第四章第四章 死鎖及其對(duì)策死鎖及其對(duì)策第第 33 頁(yè)頁(yè)假設(shè)假設(shè)t1t1時(shí)刻

38、時(shí)刻 初始狀態(tài)為初始狀態(tài)為 work(j)=3 3 2 finish(i)=f f f f f的的話。首先，判斷它是否處于安全狀態(tài)：話。首先，判斷它是否處于安全狀態(tài)：由于由于i=2i=2時(shí)，存在一個(gè)時(shí)，存在一個(gè)p2 p2 ，使，使finish(2)=f finish(2)=f ，且，且 故由故由 work(j)=work(j)+al(2,j) 得到得到 work(j)=5 3 2 finish(iwork(j)=5 3 2 finish(i)=f )=f t t f f f f f f由于由于i=4i=4時(shí)，存在一個(gè)時(shí)，存在一個(gè)p4 p4 ，使，使finish(4)=f finish(4)=f

39、 ，且，且 故由故由 work(j)=work(j)+al(4,j) 得到得到 work(j)=7 4 3 finish(iwork(j)=7 4 3 finish(i)=f )=f t t f f t t ff由于由于i=5i=5時(shí)，存在一個(gè)時(shí)，存在一個(gè)p5 p5 ，使，使finish(5)=f finish(5)=f ，且，且 故由故由 work(j)=work(j)+al(5,j) 得到得到 work(j)=7 4 5 finish(iwork(j)=7 4 5 finish(i)=f )=f t t f f t t t t 1341100062213475p4p3p2p1p3r2r1r

40、=work(j)=3 3 2 1341100062213475p4p3p2p1p3r2r1r=work(j)=5 3 2 1341100062213475p4p3p2p1p3r2r1r=work(j)=7 4 3今天日期：今天日期：2021-11-12第四章第四章 死鎖及其對(duì)策死鎖及其對(duì)策第第 34 頁(yè)頁(yè)由于由于i=3i=3時(shí)，存在一個(gè)時(shí)，存在一個(gè)p3 p3 ，使，使finish(3)=f finish(3)=f ，且，且 故由故由 work(j)=work(j)+al(3,j) 得到得到 work(j)=10 4 7 finish(iwork(j)=10 4 7 finish(i)=f )=

41、f t t t t t t t t 由于由于i=1i=1時(shí)，存在一個(gè)時(shí)，存在一個(gè)p1 p1 ，使，使finish(1)=f finish(1)=f ，且，且 故由故由 work(j)=work(j)+al(1,j) 得到得到 work(j)=10 5 7 finish(iwork(j)=10 5 7 finish(i)=)=f f t t t t t t t t 此時(shí)、安全標(biāo)志為真，存在一個(gè)安全序列（此時(shí)、安全標(biāo)志為真，存在一個(gè)安全序列（p2,p4,p5,p3,p1p2,p4,p5,p3,p1）, ,所以系所以系統(tǒng)是安全的。統(tǒng)是安全的。 1341100062213475p4p3p2p1p3r2

42、r1r=work(j)=7 4 5 1341100062213475p4p3p2p1p3r2r1r=work(j)=10 4 7今天日期：今天日期：2021-11-12第四章第四章 死鎖及其對(duì)策死鎖及其對(duì)策第第 35 頁(yè)頁(yè). .假設(shè)假設(shè)t2t2時(shí)刻時(shí)刻p2p2請(qǐng)求資源，即請(qǐng)求資源，即re(2,j)=1 0 2re(2,j)=1 0 2的話，使用銀行家算法來判斷，的話，使用銀行家算法來判斷，此時(shí)此時(shí)i=2i=2，need(2,j)=1 2 2need(2,j)=1 2 2alr1 r2 r3needr1 r2 r3avr1 r2 r3re r1 r2 r3p1p2p3p4p5 0 1 0 2 0

43、 0 3 0 2 2 1 1 0 0 2 7 4 3 1 2 2 6 0 0 0 1 1 4 3 1 3 3 2 1 0 2滿足滿足re(jre(j)=need(2,j)=need(2,j)滿足滿足re(j)=av(jre(j)=av(j) )alr1 r2 r3needr1 r2 r3avr1 r2 r3re r1 r2 r3p1p2p3p4p5 0 1 0 3 0 2 3 0 2 2 1 1 0 0 2 7 4 3 0 2 0 6 0 0 0 1 1 4 3 1 2 3 0 1 0 2執(zhí)行執(zhí)行av(j)=av(j)-re(2,j)al(2,j)=al(2,j)+re(2, j)need(2,j)=need(2,j)-re(2,j)(j=1,2,m)今天日期：今天日期：2021-11-12第四章第四章 死鎖及其對(duì)策死鎖及其對(duì)策第第 36 頁(yè)頁(yè)然后，對(duì)t2時(shí)刻進(jìn)行安全性檢查，方法同t1時(shí)刻。檢查結(jié)果，可以找到一個(gè)安全序列（p2,p4,p5,p1,p3)。可以得出p2的請(qǐng)求不會(huì)導(dǎo)致系統(tǒng)進(jìn)入不了安全狀態(tài)。所以可以將p2申請(qǐng)的資料分配給他。今天日期：今天日期：2021-11-12第四章第四章 死鎖及其對(duì)策死鎖及其對(duì)策第第 37 頁(yè)頁(yè)3.3.假設(shè)假設(shè)t3t3時(shí)刻時(shí)刻p5p5請(qǐng)求資源，即請(qǐng)求資源，即re(5,j)=3