第04章死鎖及其對策

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

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

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

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

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

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

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

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

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

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

11、鎖及其對策死鎖及其對策第第 12 頁頁3.檢測和解除死鎖檢測和解除死鎖：在一些相對簡單的系統(tǒng)中，為節(jié)省預(yù)防在一些相對簡單的系統(tǒng)中，為節(jié)省預(yù)防和避免死鎖而增加的系統(tǒng)開銷，又因為死鎖產(chǎn)生和避免死鎖而增加的系統(tǒng)開銷，又因為死鎖產(chǎn)生的概率總是比較小的，所以系統(tǒng)中允許出現(xiàn)死鎖的概率總是比較小的，所以系統(tǒng)中允許出現(xiàn)死鎖狀態(tài)。在這種系統(tǒng)中，專門設(shè)置了一個檢測機構(gòu)，狀態(tài)。在這種系統(tǒng)中，專門設(shè)置了一個檢測機構(gòu)，可以隨時檢測出死鎖的發(fā)生，并能確定與死鎖有可以隨時檢測出死鎖的發(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一是強制性的撤銷一些死鎖進(jìn)程，并剝奪它一是強制性的撤銷一些死鎖進(jìn)程，并剝奪它們的資源給其余進(jìn)程；們的資源給其余進(jìn)程；l一是使用一個有效的掛起和解除掛起機構(gòu)來一是使用一個有效的掛起和解除掛起機構(gòu)來掛起一些進(jìn)程，以便從被掛起的進(jìn)程中剝奪掛起一些進(jìn)程，以便從被掛起的進(jìn)程中剝奪一些資源用來解除死鎖。一些資源用來解除死鎖。今天日期：今天日期：2021-11-12第四章第四章 死鎖及其對策死鎖及其對策第第 13 頁頁4.4 死鎖的檢測與恢復(fù)死鎖的檢測與恢復(fù)檢測系統(tǒng)中是否存在死鎖產(chǎn)生的必要條件：檢測系統(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)程：是指某個進(jìn)程由于請求了超過系統(tǒng)中現(xiàn)有是指某個進(jìn)程由于請求了超過系統(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第四章第四章 死鎖及其對策死鎖及其對策第第 14 頁頁2、資源分配圖的化簡、資源分配圖的化簡 假設(shè)某個資源分配圖中存在一個進(jìn)程假設(shè)某個資源分配圖中存在一個進(jìn)程pipi，此刻，此刻 pipi 是非是非封鎖進(jìn)程，那么可對此資源分配圖作以下化簡：當(dāng)封鎖進(jìn)程，

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

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

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

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

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

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

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第四章第四章 死鎖及其對策死鎖及其對策第第 18 頁頁(3)(3)可利用資源向量可利用資源向量av，是一個長度為m的一維數(shù)組，表示系統(tǒng)中各類資源的可利用數(shù)目。(4)(4)工作向量工作向量work：是一個長度為m的一維數(shù)組，動態(tài)的反映系統(tǒng)中可讓進(jìn)程運行的各類資源

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

22、到m)m)使使alal矩陣第矩陣第i i行中所行中所有的有的al(i,jal(i,j) )和和rere矩陣第矩陣第i i行中所有的行中所有的re(i,jre(i,j) )均為零。若存在這個均為零。若存在這個i i說明在說明在資源分配圖中資源分配圖中pipi進(jìn)程已成為孤立結(jié)點，將進(jìn)程已成為孤立結(jié)點，將pipi進(jìn)程送入進(jìn)程向量進(jìn)程送入進(jìn)程向量l l中。中。3 3、在系統(tǒng)中除已送入在系統(tǒng)中除已送入l l之外的所有進(jìn)程中逐個尋找，若某個之外的所有進(jìn)程中逐個尋找，若某個 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)前的這個進(jìn)程也送入進(jìn)程向量將當(dāng)前的這個進(jìn)程也送入進(jìn)程向量l l中中這樣反復(fù)執(zhí)行，直到所有這樣反復(fù)執(zhí)行，直到所有l(wèi) l以外的進(jìn)程中再沒有滿足上述條件為止。以外的進(jìn)程中再沒有滿足上述條件為止。4 4、檢查檢查l l向量，若向量，若n n個進(jìn)程都在個進(jìn)程都在l l中，說明系統(tǒng)中不會發(fā)生死鎖，反之，系中，說

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

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

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

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

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

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

30、的資源，使每個進(jìn)程都能順利完成。當(dāng)且僅當(dāng)系統(tǒng)中存在此安全序列時，系統(tǒng)當(dāng)且僅當(dāng)系統(tǒng)中存在此安全序列時，系統(tǒng)處于安全狀態(tài)。處于安全狀態(tài)。假設(shè)系統(tǒng)中有假設(shè)系統(tǒng)中有3 3個進(jìn)程，個進(jìn)程，1010個可供分配的資源單位個可供分配的資源單位進(jìn)程進(jìn)程 已分配資源已分配資源 還需申請的資源還需申請的資源p1 4 4p2 2 2p3 2 7今天日期：今天日期：2021-11-12第四章第四章 死鎖及其對策死鎖及其對策第第 25 頁頁2 2、不安全狀態(tài)、不安全狀態(tài)：某個時刻系統(tǒng)中不存在一個安全序列，某個時刻系統(tǒng)中不存在一個安全序列，能使所有的進(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 銀行家算法銀行家算法 前提條件：前提條件：分配資源的單位是固定的，請求資源的分配資源的單位是固定的，請求資源的進(jìn)程數(shù)也固定不變，而且每個進(jìn)程必須先告訴系統(tǒng)對某進(jìn)程數(shù)也固定不變，而且每個進(jìn)程必須先告訴系統(tǒng)對某類資源的最大需求量，當(dāng)某個進(jìn)程要求的資源數(shù)量小于類資源的最大需求量，當(dāng)某個進(jìn)程要求的資源數(shù)量小于系統(tǒng)所擁有的該類資源的最大量時，系統(tǒng)會在有限的時系統(tǒng)所擁有的該類資源的最大量時，系統(tǒng)會在有限的時間內(nèi)滿足進(jìn)程的要求。間內(nèi)滿足進(jìn)程的要求。今天日期：今天日期：2021-11-12第四章第四章 死鎖及其

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

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

34、 死鎖及其對策死鎖及其對策第第 29 頁頁(4)(4)需求矩陣需求矩陣needneed n nm m矩陣，表示每個進(jìn)程還需要各類資源矩陣，表示每個進(jìn)程還需要各類資源數(shù)。數(shù)。例如：例如：n=5,m=3 1341100062213475p4p3p2p1p3r2r1rneedneed矩陣為：矩陣為：今天日期：今天日期：2021-11-12第四章第四章 死鎖及其對策死鎖及其對策第第 30 頁頁2.銀行家算法描述當(dāng)進(jìn)程pi提出資源申請時，系統(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)出錯處理系統(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第四章第四章 死鎖及其對策死鎖及其對策第第 31 頁頁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)即、至少有一個即、至少有一個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第四章第四章 死鎖及其對策死鎖及其對策第第 32 頁頁4.6.3 銀行家算法舉例設(shè)系統(tǒng)有五個進(jìn)程和三類資源，每類資源分別有設(shè)系統(tǒng)有五個進(jìn)程和三類資源，每類資源分別有1010、5 5、7 7。在在t t1 1時刻資源分配情況如下圖：時刻資源分配情況如下圖： 2001122030020105p4p3p2p1p3r2r1ralal矩陣：矩陣： 1341100062213475p4p3p2p1p3r2r1rneedneed矩陣：矩陣：2333r2r1ravav數(shù)組：數(shù)組：今天日期：今天日期：2021-11-12第四章第四章 死鎖及其對策死鎖及其對策第第 33 頁頁假設(shè)假設(shè)t1t1時刻

38、時刻 初始狀態(tài)為初始狀態(tài)為 work(j)=3 3 2 finish(i)=f f f f f的的話。首先，判斷它是否處于安全狀態(tài)：話。首先，判斷它是否處于安全狀態(tài)：由于由于i=2i=2時，存在一個時，存在一個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時，存在一個時，存在一個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時，存在一個時，存在一個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第四章第四章 死鎖及其對策死鎖及其對策第第 34 頁頁由于由于i=3i=3時，存在一個時，存在一個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時，存在一個時，存在一個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 此時、安全標(biāo)志為真，存在一個安全序列（此時、安全標(biāo)志為真，存在一個安全序列（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第四章第四章 死鎖及其對策死鎖及其對策第第 35 頁頁. .假設(shè)假設(shè)t2t2時刻時刻p2p2請求資源，即請求資源，即re(2,j)=1 0 2re(2,j)=1 0 2的話，使用銀行家算法來判斷，的話，使用銀行家算法來判斷，此時此時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第四章第四章 死鎖及其對策死鎖及其對策第第 36 頁頁然后，對t2時刻進(jìn)行安全性檢查，方法同t1時刻。檢查結(jié)果，可以找到一個安全序列（p2,p4,p5,p1,p3)?？梢缘贸鰌2的請求不會導(dǎo)致系統(tǒng)進(jìn)入不了安全狀態(tài)。所以可以將p2申請的資料分配給他。今天日期：今天日期：2021-11-12第四章第四章 死鎖及其對策死鎖及其對策第第 37 頁頁3.3.假設(shè)假設(shè)t3t3時刻時刻p5p5請求資源，即請求資源，即re(5,j)=3