蘇州大學(xué)操作系統(tǒng)概念第七章

1、6.21.死鎖問(wèn)題死鎖問(wèn)題2.死鎖系統(tǒng)模型死鎖系統(tǒng)模型3.死鎖預(yù)防死鎖預(yù)防4.死鎖避免死鎖避免5.死鎖檢測(cè)和恢復(fù)死鎖檢測(cè)和恢復(fù)6.46.5n只能一個(gè)方向通行n橋的每一個(gè)部分都可以看成資源n如果死鎖發(fā)生，它可以由一輛車返回而解決，搶占資源并回退n如果死鎖發(fā)生，可能很多車都不得不返回n有可能產(chǎn)生饑餓6.6n一組等待的進(jìn)程，其中每一個(gè)進(jìn)程都持有資源，并且等待著由這個(gè)組中其他進(jìn)程所持有的資源n所有死鎖進(jìn)程無(wú)法推進(jìn)n原因l競(jìng)爭(zhēng)互斥資源l進(jìn)程推進(jìn)不當(dāng)n例如l系統(tǒng)有兩個(gè)磁帶設(shè)備l進(jìn)程P1和P2各占有一個(gè)磁帶設(shè)備并且實(shí)際需要兩個(gè)磁帶6.7/* thread one runs in this function

2、*/ void *do_work_one(void *param) pthread_mutex_lock(&first_mutex); pthread_mutex_lock(&second_mutex); /* * Do some work */ pthread_mutex_unlock(&second_mutex); pthread_mutex_unlock(&first_mutex); pthread_exit(0); /* thread two runs in this function */ void *do_work_two(void *param) pthread_mutex_lo

3、ck(&second_mutex); pthread_mutex_lock(&first_mutex); /* * Do some work */ pthread_mutex_unlock(&first_mutex); pthread_mutex_unlock(&second_mutex); pthread_exit(0); 6.8：一次只有一個(gè)進(jìn)程可以使用一個(gè)資源：一次只有一個(gè)進(jìn)程可以使用一個(gè)資源n占有并等待占有并等待：一個(gè)至少持有一個(gè)資源的進(jìn)程等待獲得額外：一個(gè)至少持有一個(gè)資源的進(jìn)程等待獲得額外的由其他進(jìn)程所持有的資源的由其他進(jìn)程所持有的資源n不可搶占不可搶占：一個(gè)資源只有當(dāng)持有它的進(jìn)程完

4、成任務(wù)后，自：一個(gè)資源只有當(dāng)持有它的進(jìn)程完成任務(wù)后，自由的釋放由的釋放n循環(huán)等待循環(huán)等待：等待資源的進(jìn)程之間存在環(huán)：等待資源的進(jìn)程之間存在環(huán) P0, P1, , P0 lP0 等待等待P1占有的資源占有的資源, P1等待等待P2占有的資源占有的資源, , Pn1等等待待Pn占有的資源占有的資源, P0等待等待Pn占有的資源占有的資源 四個(gè)條件同時(shí)出現(xiàn)，死鎖將會(huì)發(fā)生（必要條件）四個(gè)條件同時(shí)出現(xiàn)，死鎖將會(huì)發(fā)生（必要條件）6.10n資源類型 R1, R2, . . ., Rm CPU周期，內(nèi)存空間，I/O設(shè)備n每一種資源Ri 有Wi 種實(shí)例n每一個(gè)進(jìn)程通過(guò)如下方法來(lái)使用資源l申請(qǐng)l使用l釋放n資源動(dòng)

5、態(tài)申請(qǐng)-常用方法l在進(jìn)程運(yùn)行過(guò)程中申請(qǐng)資源n資源靜態(tài)申請(qǐng)l在進(jìn)程運(yùn)行前一次申請(qǐng)所有資源6.11n（V被分為兩個(gè)部分lP = P1, P2, , Pn, 含有系統(tǒng)中全部的進(jìn)程lR = R1, R2, , Rm, 含有系統(tǒng)中全部的資源n請(qǐng)求邊：有向邊P1 Rj n分配邊：有向邊R1 P j 一個(gè)頂點(diǎn)的集合一個(gè)頂點(diǎn)的集合V和邊的集合和邊的集合E6.12n進(jìn)程進(jìn)程n有四個(gè)實(shí)例的資源類型有四個(gè)實(shí)例的資源類型nPi 請(qǐng)求一個(gè)請(qǐng)求一個(gè)Rj的實(shí)例的實(shí)例nPi 持有一個(gè)持有一個(gè)Rj的實(shí)例的實(shí)例PiPiRjRj6.136.146.156.16n如果圖沒(méi)有環(huán)，那么不會(huì)有死鎖n如果圖有環(huán)l如果每一種資源類型只有一個(gè)實(shí)

6、例，那么死鎖發(fā)生l如果一種資源類型有多個(gè)實(shí)例，可能死鎖6.17n確保系統(tǒng)永遠(yuǎn)不會(huì)進(jìn)入死鎖狀態(tài)n允許系統(tǒng)進(jìn)入死鎖狀態(tài)，然后恢復(fù)系統(tǒng)n忽略這個(gè)問(wèn)題，假裝系統(tǒng)中從未出現(xiàn)過(guò)死鎖。這個(gè)方法被大部分的操作系統(tǒng)采用，包括UNIXl設(shè)備虛擬化6.19n互斥：存在互斥資源，不能改變這個(gè)條件l現(xiàn)代操作系統(tǒng)中的虛擬化技術(shù)n占有并等待：必須保證進(jìn)程申請(qǐng)資源的時(shí)候沒(méi)有占有其他資源l靜態(tài)分配策略l要求進(jìn)程在執(zhí)行前一次性申請(qǐng)全部的資源，只有沒(méi)有占有資源時(shí)才可以分配資源）l利用率低，可能出現(xiàn)饑餓6.20n非搶占:l如果一個(gè)進(jìn)程的申請(qǐng)沒(méi)有實(shí)現(xiàn)，它要釋放所有占有的資源l先占的資源放入進(jìn)程等待資源列表中l(wèi)進(jìn)程在重新得到舊的資源的時(shí)

7、候可以重新開(kāi)始n循環(huán)等待：對(duì)所有的資源類型排序進(jìn)行總排序，并且要求進(jìn)程按照遞增順序申請(qǐng)資源6.22n一個(gè)簡(jiǎn)單而有效的模型要求每一個(gè)進(jìn)程聲明它所需要的資源的最大數(shù)n死鎖避免算法動(dòng)態(tài)檢查資源分配狀態(tài)以確保不會(huì)出現(xiàn)循環(huán)等待的情況n資源分配狀態(tài)定義為可用的與已分配的資源數(shù)，和進(jìn)程所需的最大資源量6.23n當(dāng)進(jìn)程申請(qǐng)一個(gè)有效的資源的時(shí)候，系統(tǒng)必須確定分配后是安全的n如果存在一個(gè)安全序列，系統(tǒng)處于安全態(tài)n進(jìn)程序列是安全的，如果每一個(gè)進(jìn)程Pi所申請(qǐng)的可以被滿足的資源數(shù)加上其他進(jìn)程所持有的該資源數(shù)小于系統(tǒng)總數(shù)l如果 Pi 需要的資源不能馬上獲得，那么Pi 等待直到所有的Pi-1進(jìn)程結(jié)束。l當(dāng)Pi-1 結(jié)束后，

8、 Pi獲得所需的資源，執(zhí)行、返回資源、結(jié)束。l當(dāng)Pi結(jié)束后， Pi+1獲得所需的資源執(zhí)行，依此類推。6.24n如果一個(gè)系統(tǒng)在安全狀態(tài)，就沒(méi)有死鎖n如果一個(gè)系統(tǒng)不是處于安全狀態(tài)，就有可能死鎖n避免 確保系統(tǒng)永遠(yuǎn)不會(huì)進(jìn)入死鎖狀態(tài)6.25n為什么系統(tǒng)處于不安全狀態(tài)，但不一定發(fā)生死鎖？6.26n單實(shí)例資源l資源分配圖法n多實(shí)例資源l銀行家算法6.27n需求邊 Pi Rj ： Pi 可能以后需要申請(qǐng)Rj資源，用虛線表示nPi 申請(qǐng)Rj資源，需求邊轉(zhuǎn)換為請(qǐng)求邊n請(qǐng)求邊在資源分配后轉(zhuǎn)換為分配邊n資源釋放后，分配邊轉(zhuǎn)換為需求邊6.28n假設(shè) Pi 申請(qǐng)資源 Rjn請(qǐng)求能滿足的前提是：把請(qǐng)求邊轉(zhuǎn)換為分配邊后不會(huì)

9、導(dǎo)致環(huán)存在6.29n多個(gè)實(shí)例n每一個(gè)進(jìn)程必須事先聲明使用的最大量n當(dāng)一個(gè)進(jìn)程請(qǐng)求資源，它可能要等待n當(dāng)一個(gè)進(jìn)程得到所有的資源，它必須在有限的時(shí)間釋放它們6.30nAvailable: 長(zhǎng)度為 m的向量。 如果availablej=k,那么資源Rj有k個(gè)實(shí)例有效nMax: n x m 矩陣。 如果Maxi,j=k,那么進(jìn)程Pi可以最多請(qǐng)求資源Rj的k個(gè)實(shí)例nAllocation: n x m 矩陣。 如果Allocationi,j=k,那么進(jìn)程Pj當(dāng)前分配了k個(gè)資源Rj的實(shí)例nNeed: n x m 矩陣。如果Need,j=k,那么進(jìn)程Pj還需要k個(gè)資源Rj的實(shí)例Need i,j = Mxi,j

10、 Allocation i,j.N為進(jìn)程的數(shù)目，為進(jìn)程的數(shù)目，M為資源類型的數(shù)目為資源類型的數(shù)目6.311.讓W(xué)ork和Finish作為長(zhǎng)度為m和n的向量初始化：Work := AvailableFinish i = false for i - 1,3, , n.2. 查找i(a) Finish i = false(b) Needi WorkIf no such i exists, go to step 4.3. Work := Work + AllocationiFinishi := truego to step 2.4. 如果對(duì)所有i的 Finish i = true, 則系統(tǒng)處在安全狀態(tài)

11、。6.32 Requesti =進(jìn)程 Pi 的資源請(qǐng)求向量. 如果Requesti m = k 則進(jìn)程 Pi 想要資源類型為Rjm的k個(gè)實(shí)例1. 如果 Requesti Needi 轉(zhuǎn) step 2. 否則報(bào)錯(cuò), 因?yàn)檫M(jìn)程請(qǐng)求超出了其聲明的最大值2. 如果 Requesti Available, 轉(zhuǎn) step 3. 否則 Pi 必須等待, 因?yàn)橘Y源不可用.3. 假設(shè)通過(guò)修改下列狀態(tài)來(lái)分配請(qǐng)求的資源給進(jìn)程Pi :Available := Available - Requesti;Allocationi := Allocationi + Requesti;Needi := Needi Reques

12、ti;如果系統(tǒng)安全 將資源分配給 Pi. 如果系統(tǒng)不安全 Pi 必須等待，恢復(fù)原有的資源分配狀態(tài)6.33n5個(gè)進(jìn)程P0到P4； 3個(gè)資源類型A(10個(gè)實(shí)例），B（5個(gè)實(shí)例），C（7個(gè)實(shí)例）n時(shí)刻Tn的快照：AllocationMaxAvailableA B CA B C A B CP00 1 07 5 3 3 3 2 P12 0 0 3 2 2 P23 0 2 9 0 2 P32 1 1 2 2 2 P40 0 24 3 3 系統(tǒng)處在安全的狀態(tài)，因?yàn)樾蛄邢到y(tǒng)處在安全的狀態(tài)，因?yàn)樾蛄?滿足了滿足了安全的標(biāo)準(zhǔn)安全的標(biāo)準(zhǔn)NeedA B C P07 4 3 P11 2 2 P26 0 0 P30 1

13、1 P44 3 1 6.34n檢查檢查Request Available（就是說(shuō)，（就是說(shuō)，(1,0,2) (3,3,2)為真為真AllocationNeedAvailableA B CA B CA B C P00 1 0 7 4 3 2 3 0P13 0 20 2 0 P23 0 2 6 0 0 P32 1 1 0 1 1P40 0 2 4 3 1 n執(zhí)行安全算法表明序列 滿足要求n思考：nP4的請(qǐng)求(3,3,0)是否可以通過(guò)？nP0的請(qǐng)求(0,2,0)是否可以通過(guò)？6.36n允許進(jìn)入死鎖狀態(tài)n檢測(cè)死鎖n恢復(fù)策略6.37n維護(hù)等待圖l節(jié)點(diǎn)是進(jìn)程lPi Pj表明Pi在等待Pjn定期調(diào)用算法來(lái)檢

14、查是否有環(huán)n一個(gè)檢查圖中是否有環(huán)的算法需要n2的操作來(lái)進(jìn)行，n為圖中的節(jié)點(diǎn)數(shù)6.38n:Available ：一個(gè)向量的長(zhǎng)度m代表每一種資源類型有效的數(shù)目nAllocation: 一個(gè)n x m 的矩陣定義了當(dāng)前分配的每一種資源類型的實(shí)例數(shù)目nRequest: 一個(gè)n x m 的矩陣表明了當(dāng)前的進(jìn)程請(qǐng)求。如果Requesti，j=k,那么進(jìn)程Pi請(qǐng)求k個(gè)資源Rj的實(shí)例6.391. 讓W(xué)ork和Finish作為長(zhǎng)度為m和n的向量初始化(a) Work := Available(b) For i = 1,2, , n, if Allocationi 0, then Finishi := false

15、;otherwise, Finishi := true.2. 找到滿足下列條件的下標(biāo)i(a) Finishi = false(b) Requesti Work如果沒(méi)有這樣的i存在，轉(zhuǎn)43. Work := Work + AllocationiFinishi := true轉(zhuǎn) 2.4.如果有一些i, 1 i n , Finishi = false, 則系統(tǒng)處在死鎖狀態(tài)。而且， 如果 Finishi = false, 則進(jìn)程 Pi 是死鎖的。算法需要算法需要m x n2 次操作來(lái)判斷是否系統(tǒng)處于死鎖狀態(tài)次操作來(lái)判斷是否系統(tǒng)處于死鎖狀態(tài)6.40n五個(gè)進(jìn)程Pn到P4,三個(gè)資源類型A（7個(gè)實(shí)例），B（2個(gè)實(shí)例）,C（6個(gè)實(shí)例）n時(shí)刻Tn的狀態(tài)AllocationRequestAvailableA B C A B C A B CP00 1 0 0 0 0 0 0 0P12 0 0 2 0 2P23 0 30 0 0 P32 1 1 1 0 0 P40 0 2 0 0 2n對(duì)所有i，序列 將導(dǎo)致Finishi = true。6.41nP2請(qǐng)求一個(gè)額外的C實(shí)例RequestA B C P00 0 0 P12 0 1P20 0 1P31 0 0 P40 0 2n系統(tǒng)的狀態(tài)？l可以歸還Pn所有的資源，但是資源不夠完成其他進(jìn)程的請(qǐng)求l死鎖存在，包括進(jìn)程P1,P2,P3和P46.42n何時(shí)及多長(zhǎng)時(shí)間的