計算機(jī)操作系統(tǒng)第5章死鎖

1、. 從進(jìn)程同步的概念可以知道，當(dāng)并發(fā)進(jìn)程需要競爭使用資源或需要相互協(xié)作向前推進(jìn)時，如果不采取同步措施，或同步措施不恰當(dāng)，則很容易導(dǎo)致并發(fā)進(jìn)程不能向前推進(jìn)而陷入僵局，即死鎖現(xiàn)象。死鎖是發(fā)生在一組相互競爭或協(xié)作的進(jìn)程與線程之間的一個非正?，F(xiàn)象。 死鎖是所有操作系統(tǒng)都面臨著的潛在問題，操作系統(tǒng)除了需要預(yù)防死鎖、避免死鎖外，還需要能夠檢測死鎖，并從死鎖中進(jìn)行恢復(fù)。.本章的主要內(nèi)容如下：l 死鎖的產(chǎn)生；l 死鎖的預(yù)防；l 死鎖的避免；l 死鎖的檢測和解除；l 線程死鎖。.5.1 5.1 死鎖的產(chǎn)生死鎖的產(chǎn)生5.1.1 5.1.1 死鎖產(chǎn)生的原因死鎖產(chǎn)生的原因 競爭資源引起死鎖競爭資源引起死鎖 在多道程序

2、系統(tǒng)，多個進(jìn)程共享系統(tǒng)的資源。系統(tǒng)資源分為二類，一類是不可搶占的資源，如打印機(jī)、磁帶機(jī)等。當(dāng)系統(tǒng)把這類資源分配給某進(jìn)程后，再不能強(qiáng)行收回，只能在進(jìn)程用完后自動釋放。另一類是可搶占的資源，如CPU、內(nèi)存等。由于系統(tǒng)擁有的不可搶占的資源有限，多個進(jìn)程共享競爭不可搶占的資源就可能引起死鎖。 進(jìn)程推進(jìn)順序不當(dāng)引起死鎖進(jìn)程推進(jìn)順序不當(dāng)引起死鎖 在多道程序系統(tǒng)中，并發(fā)執(zhí)行的進(jìn)程推進(jìn)序列不可予測，有些推進(jìn)順序，進(jìn)程可以順利完成，這些推進(jìn)順序是合法的；而有的推進(jìn)順序會引起進(jìn)程無限期地等待永遠(yuǎn)不會發(fā)生的條件而不能向前推進(jìn)，造成了死鎖。.5.1.1 5.1.1 死鎖產(chǎn)生的原因（續(xù)）死鎖產(chǎn)生的原因（續(xù)） 進(jìn)程推進(jìn)順

3、序不當(dāng)引起死鎖例：進(jìn)程P和Q并發(fā)執(zhí)行，進(jìn)程P和Q程序如下：Process P Process Q. .Get A Get B. .Get B Get A. .Release A Release B. .Release B Release A. . .5.1.1 5.1.1 死鎖產(chǎn)生的原因（續(xù)）死鎖產(chǎn)生的原因（續(xù)）PAQB當(dāng)當(dāng)P、Q按如下次序執(zhí)行時：按如下次序執(zhí)行時：P: GET A Q:GET BP:GET BQ:GET A.ABCS2S1S3哲學(xué)家吃面的問題哲學(xué)家吃面的問題.A:P(S1)P(S3)EatingV(S3)V(S1)B:P(S2)P(S1)EatingV(S1)V(S2)C:P

4、(S3)P(S2)EatingV(S2)V(S3).A: P(S1), B:P(S2),C:P(S3)A:P(S3) :阻塞阻塞B:P(S1):阻塞阻塞C: P(S2):阻塞阻塞AS1CS3S2B.5.1.2 5.1.2 死鎖產(chǎn)生的條件死鎖產(chǎn)生的條件1.1.產(chǎn)生死鎖的必要條件（產(chǎn)生死鎖的必要條件（ Conditions for Deadlock ） 互斥（互斥（ Mutual exclusion ）條件）條件：一個資源一次只能被一個進(jìn)程所使用，即是排它性使用。 不可搶占（不可搶占（ No preemption ）條件）條件：一個資源僅能被占有它的進(jìn)程所釋放，而不能被別的進(jìn)程強(qiáng)占。 請求和保持（

5、請求和保持（ Hold-and-wait ）條件）條件：進(jìn)程已經(jīng)保持了至少一個資源，但又提出了新的資源要求，而該資源又已被其它進(jìn)程占有，此時請求進(jìn)程阻塞，但又對已經(jīng)獲得的其它資源保持不放。 環(huán)路等待（環(huán)路等待（ Circular wait ）條件）條件：當(dāng)每類資源只有一個時，在發(fā)生死鎖時，必然存在一個進(jìn)程-資源的環(huán)形鏈。如一系統(tǒng)狀態(tài)的資源分配圖所示，P1正在等待一個P2 占用的資源R2，P2正在等待一個P1占用的資源R1。. 5.1.2 5.1.2 死鎖產(chǎn)生的條件死鎖產(chǎn)生的條件( (續(xù)續(xù)) )2. 資源分配圖由結(jié)點(diǎn)和邊組成。結(jié)點(diǎn)有二類，一類是進(jìn)程結(jié)點(diǎn)，用園圈表示；另一類是資源結(jié)點(diǎn)，用小方框表示

6、一類資源，用方框中的小圈表示資源數(shù)。邊也有二類，一類是分配邊，它由資源結(jié)點(diǎn)指向進(jìn)程結(jié)點(diǎn)，另一類是申請邊，它由進(jìn)程結(jié)點(diǎn)指向資源結(jié)點(diǎn)。返回 R1R2 P1P2.5.1.2 5.1.2 死鎖產(chǎn)生的條件死鎖產(chǎn)生的條件( (續(xù)續(xù)) )3 3. . 處理死鎖的基本方法處理死鎖的基本方法a. 死鎖的預(yù)防 靜態(tài)方法：在進(jìn)程執(zhí)行前采取的措施，通過設(shè)置某些限制條件，去破壞產(chǎn)生死鎖的四個必要條件之一，防止發(fā)生死鎖。B.死鎖的避免 動態(tài)的方法：在進(jìn)程執(zhí)行過程中采取的措施，不需事先采取限制措施破壞產(chǎn)生死鎖的必要條件，而是在進(jìn)程申請資源時用某種方法去防止系統(tǒng)進(jìn)入不安全狀態(tài)，從而避免發(fā)生死鎖。C.死鎖的檢測和解除 這種方法

7、預(yù)先并不采用任何限制措施，允許系統(tǒng)在運(yùn)行過程中發(fā)生死鎖，但可通過系統(tǒng)設(shè)置的檢測機(jī)構(gòu)及時檢測死鎖的發(fā)生，如檢測到死鎖，則采用撤消進(jìn)程等死鎖解除方法使系統(tǒng)正常工作。.5.2 5.2 死死 鎖鎖 預(yù)預(yù) 防防(Deadlock Prevention) 預(yù)防死鎖的方法是破壞四個產(chǎn)生死鎖的必要條件之一。1。破壞互斥條件破壞互斥條件 互斥使用是資源本身特征所決定的。使用硬軟件結(jié)合可改變資源本身特性，例如采用SPOOLing技術(shù)可將“獨(dú)享” 打印機(jī)改變?yōu)椤肮蚕怼钡拇蛴C(jī)。2。破壞不可搶占條件破壞不可搶占條件 搶占式調(diào)度法主要用于處理機(jī)和存貯器資源調(diào)度，它們的狀態(tài)容易保存和恢復(fù)。但此法對外部設(shè)備和私存數(shù)據(jù)不宜使

8、用。.5.2 5.2 死死 鎖鎖 預(yù)預(yù) 防防(Deadlock Prevention) -13。破壞請求和保持條件破壞請求和保持條件 系統(tǒng)可采用資源靜態(tài)予分配方式資源靜態(tài)予分配方式來破壞請求保持條件。系統(tǒng)要求所有進(jìn)程一次性地申請?jiān)谡麄€運(yùn)行過程中全部資源，若系統(tǒng)有足夠資源滿足給進(jìn)程，則在運(yùn)行前，一次性將其所需要的所有資源分配給該進(jìn)程。這樣該進(jìn)程在整個運(yùn)行期間，便不再提出資源要求，從而摒棄了請求條件。這種預(yù)防死鎖的方法，優(yōu)點(diǎn)是簡單、易予實(shí)現(xiàn)且很安全，但其資源利用率很低，進(jìn)程也延遲運(yùn)行。4。破壞循環(huán)等待條件破壞循環(huán)等待條件 有序資源使用法有序資源使用法 該方法將所有的資源按類型進(jìn)行線性排隊(duì)，并賦予不

9、同的序號。例如令輸入機(jī)的序號為1，打印機(jī)序號為2，磁盤機(jī)序號為3等。.5.2 5.2 死死 鎖鎖 預(yù)預(yù) 防防(Deadlock Prevention) -2 所有進(jìn)程對資源的請求必須嚴(yán)格按資源序號遞增的次序提出。這樣在所形成的資源分配圖中不可能再出現(xiàn)環(huán)路，因而摒棄了“環(huán)路等待”條件，在采用這種策略時總有一個進(jìn)程占據(jù)了較高序號的資源，它繼續(xù)請求的資源必然是空閑的，因而進(jìn)程可以一直向前推進(jìn)。這種預(yù)防死鎖的策略可以提高資源利用率，但在進(jìn)程使用各類資源的順序與系統(tǒng)規(guī)定的順序不同時會造成資源浪費(fèi)的情況。 資源按級分配法資源按級分配法 該方法是把資源遞增排序成若干等級（如L1、L2.Lm），其中每級可包含

10、幾類資源，要求每個進(jìn)程在獲得了Lj級中資源之后 ，它才能申請更高級的LK（LKLj）級中的資源；如果它還需申請比LK級低的LI級（LI 4 P2 4 2 2 = 4 因?yàn)檎也坏揭粋€安全序列使所有進(jìn)程順序地一個個地運(yùn)行完畢，所以T1狀態(tài)是不安全狀態(tài)，由于實(shí)施分配給1臺磁帶機(jī)給P3的操作會引起系統(tǒng)狀態(tài)由安全狀態(tài)T0向不安全狀態(tài)下的轉(zhuǎn)換，所以為了避免死鎖，上述的分配只是安全檢測，檢測后判定這樣的申請不能滿足，P3為申請1臺磁帶機(jī)而必須阻塞等待。.3.3.利用銀行家算法避免死鎖利用銀行家算法避免死鎖 最具代表的避免死鎖算法是Dijkstra的銀行家算法，這是由于該算法用于銀行系統(tǒng)現(xiàn)金貸款的發(fā)放而得名。

11、銀行家算法的數(shù)據(jù)結(jié)構(gòu)銀行家算法的數(shù)據(jù)結(jié)構(gòu)可用資源向量 Available m m為系統(tǒng)中資源種類數(shù)，Availablej=k表示系統(tǒng)中第j類資源數(shù)為k個。最大需求矩陣Maxn，m n為系統(tǒng)中進(jìn)程數(shù)，Maxi,j=k表示進(jìn)程i對j類資源的最大需求數(shù)為中k。分配矩陣Allocationn，m 它定義了系統(tǒng)中每一類資源當(dāng)前已分配給每一進(jìn)程資源數(shù)， Allocationi,j=k表示進(jìn)程i已分得j類資源的數(shù)目為k個。.3.3.利用銀行家算法避免死鎖利用銀行家算法避免死鎖-1-1需求矩陣Needn,m 它表示每個進(jìn)程尚需的各類資源數(shù)，Needi,j=k 表示進(jìn)程i還需要j類資源k個。Needi,j=Ma

12、xi,j-Allocationi,j銀行家算法銀行家算法 假設(shè)在進(jìn)程并發(fā)執(zhí)行時進(jìn)程i提出請求j類資源k個后，表示為Requestij=k。系統(tǒng)按下述步驟進(jìn)行安全檢查： 如果RequestiNeedi則繼續(xù)以下檢查，否則顯示需求申請超出最大需求值的錯誤。 如果RequestiAvailable則繼續(xù)以下檢查，否則顯示系統(tǒng)無足夠資源，Pi阻塞等待。 系統(tǒng)試探把要求的資源分配給進(jìn)程i并修改有關(guān)數(shù)據(jù)結(jié)構(gòu)的值： Available = Available-Requesti ； Allocationi =Allocationi+Requesti ； Needi=Needi-Requesti ；. 3.3.

13、利用銀行家算法避免死鎖利用銀行家算法避免死鎖-2-2 系統(tǒng)執(zhí)行安全性算法，檢查此次資源分配后，系統(tǒng)是否處于安全狀態(tài)，若安全，才正式將資源分配給進(jìn)程i，以完成本次分配；否則將試探分配作廢，恢復(fù)原來的資源分配狀態(tài)，讓進(jìn)程Pi等待。安全性算法安全性算法安全性算法執(zhí)行步驟如下：A.初始化設(shè)置工作向量Workm表示系統(tǒng)可提供的各類資源數(shù)目，用以保護(hù)原數(shù)據(jù)結(jié)構(gòu)有關(guān)值。Work = Available，設(shè)置完成標(biāo)志向量 Finishn。Finishi = false 表示i進(jìn)程尚末完成，如值為true則表示進(jìn)程i已完成。B.從進(jìn)程集合n中找到一個能滿足下述二個條件: Finishi = false和Necd

14、iWork，如找到則執(zhí)行步驟C，如找不到同時滿足以上二條件的進(jìn)程則執(zhí)行步驟D。.3.3.利用銀行家算法避免死鎖利用銀行家算法避免死鎖-3-3C.當(dāng)進(jìn)程i獲得資源后可順利執(zhí)行直到完成，并釋放出分配給它的資源，表示如下： work = work+Allocationi ； Finishi=true ；轉(zhuǎn)執(zhí)行步驟B。D.如果所有的Finishiture，則表示系統(tǒng)處于安全狀態(tài)，否則系統(tǒng)處于不安全狀態(tài)。.銀行家算法銀行家算法例：例： 假定系統(tǒng)中有五個進(jìn)程P0、P1、P2、P3、P4和三種類型資源A、B、C，每一種資源的數(shù)量分別為10、5、7。各進(jìn)程的最大需求、T0時刻資源分配情況如下 所示。 Max

15、Allocation Need Available A B CA B C A B C A B C P0 7 5 3 0 1 0 7 4 3 3 3 2 P1 3 2 2 2 0 0 1 2 2P2 9 0 2 3 0 2 6 0 0P3 2 2 2 2 1 1 0 1 1P4 4 3 3 0 0 2 4 3 1試問： T0時刻是否安全？ P1請求資源Request1(1,0,2)是否允許？ P4請求資源Request4(3,3,0)是否允許？ .銀行家算法銀行家算法例例-1 T0時刻是否安全？從表中可找出一個序列(P1 、 P3、 P4 、 P2 、 P0）使各進(jìn)程順序地一個個地執(zhí)行完成。 M

16、axMax Allocation Need Available Available (分配資源前分配資源前) (釋放釋放資源資源后）后） A B C A B C A B C A B C A B CP0 7 5 3 0 1 0 7 4 3 = 10 4 7 10 5 7P1 3 2 2 2 0 0 1 2 2 = 3 3 2 5 3 2P2 9 0 2 3 0 2 6 0 0 = 7 4 5 10 4 7P3 2 2 2 2 1 1 0 1 1 = 5 3 2 7 4 3P4 4 3 3 0 0 2 4 3 1 = 7 4 3 7 4 5安全序列為P1、P3、P4、P2、P0，T0時刻系統(tǒng)是安全

17、的。 P1請求資源Request1(1,0,2)可否允許？.銀行家算法銀行家算法例例-2Request1(1,0,2)Need1(1,2,2)，P1請求在最大需求范圍內(nèi)。Request1(1,0,2) Available(3,3,2)，可用資源可滿足P1請求需要。試探把要求的資源分配給進(jìn)程P1并修改有關(guān)數(shù)據(jù)結(jié)構(gòu)的數(shù)值：Available = Available(3，3，2)Request1(1,0,2)=Available(2,3,0)；Need1 = Need1(1,2,2)Request1(1,0,2)= Need1(0,2,0)；Allocation1 =Allocation1(2,0,

18、0)+Request1(1,0,2)=Allocation1(3,0,2)；利用安全性算法檢查試探將資源分配后狀態(tài)的安全性如下：.銀行家算法銀行家算法例例-3 Max Max Allocation Need Available Available (分配資源前分配資源前) (釋放釋放資源資源后）后） A B C A B C A B C A B C A B CP0 7 5 3 0 1 0 7 4 3 = 10 4 7 10 5 7P1 3 2 2 3 0 2 0 2 0 = 2 3 0 5 3 2P29 0 2 3 0 2 6 0 0 = 7 4 5 10 4 7P32 2 2 2 1 1 0

19、1 1 = 5 3 2 7 4 3P44 3 3 0 0 2 4 3 1 = 7 4 3 7 4 5 因?yàn)橄确峙滟Y源給P1進(jìn)程符合按安全序列P1、P3、P4、P2、P0分配資源，所以試探將資源分配給進(jìn)程P1后的狀態(tài)是安全的，可將資源分配給進(jìn)程P1。 P4請求資源Request4(3,3,0)是否允許？Request4(3,3,0)Need4(4,3,1)，P4請求在最大需求范圍內(nèi)。Request4(3,3,0)Available(2,3,0)不成立，即可用資源暫不能滿足P4請求資源需要，P4阻塞等待。 .5.4 5.4 死鎖的檢測和解除死鎖的檢測和解除(Deadlock DetectionDe

20、adlock Detection) 5.4.1 5.4.1 死鎖的檢測死鎖的檢測 死鎖的避免算法增加了系統(tǒng)的開銷，死鎖的檢測采用資源分配圖的簡化判斷是否發(fā)生了不安全狀態(tài)。如發(fā)現(xiàn)系統(tǒng)處于不安全狀態(tài)時，即執(zhí)行死鎖解除的策略，采用此法開銷相對減少。1 1. .資源分配圖的簡化資源分配圖的簡化： 系統(tǒng)處于某S狀態(tài)時可用資源分配圖表示，可用資源分配圖簡化來判斷系統(tǒng)是否處于死鎖狀態(tài)。資源分配圖簡化的方法如下：在資源分配圖中找一個既不阻塞又非孤立的進(jìn)程結(jié)點(diǎn)PI（如某進(jìn)程既無已分配的資源也不需申請資源，即既無分配邊又無申請邊，則該進(jìn)程結(jié)點(diǎn)是孤立結(jié)點(diǎn)），讓它獲得所需資源而繼續(xù)運(yùn)行直至完畢，再釋放它擁有的所有的資

21、源，這相當(dāng)于取消PI的分配邊和請求邊，使它成為孤立結(jié)點(diǎn)。 經(jīng)過以上簡化，如所有的進(jìn)程結(jié)點(diǎn)都是孤立結(jié)點(diǎn)則稱資源分配圖是可完全簡化的。若不能通過任何過程使該圖完全簡化，則該圖是不可完全簡化的。資源分配圖簡化如下圖：. R R1 1 R R2 2 R R1 1 R R2 2 。P1 資源分配圖的簡化例資源分配圖的簡化例：。 。P1P2。 。 。P1P2。 。P2。R R1 1 R R2 2.5.4.1 5.4.1 死鎖的檢測死鎖的檢測-1-12 2. .死鎖定理：死鎖定理： S為死鎖狀態(tài)的充分條件是：尚且僅當(dāng)S狀態(tài)的資源分配圖是不可完全簡化的，該充分條件稱為死鎖定理。3. 死鎖檢測的數(shù)據(jù)和算法死鎖檢

22、測的數(shù)據(jù)和算法類似于銀行家算法。.5.4.2 5.4.2 死鎖解除死鎖解除 當(dāng)檢測死鎖的軟件判別死鎖存在時判別死鎖存在時，就要解除死鎖就要解除死鎖，使系統(tǒng)從死鎖中恢復(fù)。1 1利用結(jié)束死鎖進(jìn)程釋放資源利用結(jié)束死鎖進(jìn)程釋放資源 強(qiáng)制性地從系統(tǒng)中撤消一個或多個死鎖的進(jìn)程以斷開循環(huán)等強(qiáng)制性地從系統(tǒng)中撤消一個或多個死鎖的進(jìn)程以斷開循環(huán)等待鏈待鏈，并收回分配給終止進(jìn)程的全部資源供剩下的進(jìn)程使用。借助于撤消進(jìn)程來解除死鎖可以使用兩種方法。一種是撤消全部的死鎖進(jìn)程，這顯然會斷開死鎖環(huán)路，但代價太大。另一種方法是逐個撤消死鎖的進(jìn)程直至死鎖環(huán)路消除。這里存在一個按照什么原則進(jìn)行逐個撤消進(jìn)程的問題。目前較實(shí)用而又簡

23、便的方法是撤消那些代價最小的進(jìn)程。所謂影響一個進(jìn)程的撤消代價因素有該進(jìn)程的優(yōu)先權(quán)，該進(jìn)程運(yùn)行到今的運(yùn)行代價（包括CPU時間，使用資源的種類和時間等）、與相關(guān)的作業(yè)類型和外部代價等。.死鎖的解除死鎖的解除-12 2利用資源搶占利用資源搶占 死鎖恢復(fù)的另一種辦法是使用一個有效的掛起和解除機(jī)構(gòu)死鎖恢復(fù)的另一種辦法是使用一個有效的掛起和解除機(jī)構(gòu)來掛起一些死鎖的進(jìn)程來掛起一些死鎖的進(jìn)程，其實(shí)質(zhì)是從被掛起的進(jìn)程那里搶占資源以解除死鎖，許多學(xué)者認(rèn)為在此領(lǐng)域的研究工作比起其它死鎖恢復(fù)的辦法更為重要。問題：現(xiàn)場（包擴(kuò)CPU、內(nèi)存、外設(shè)的狀態(tài)）保護(hù)不好解決3 3利用回退釋放資源利用回退釋放資源 例如一個系統(tǒng)提供了檢查點(diǎn)和重新啟