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

1、6.21.死鎖問題死鎖問題2.死鎖系統(tǒng)模型死鎖系統(tǒng)模型3.死鎖預防死鎖預防4.死鎖避免死鎖避免5.死鎖檢測和恢復死鎖檢測和恢復6.46.5n只能一個方向通行n橋的每一個部分都可以看成資源n如果死鎖發(fā)生，它可以由一輛車返回而解決，搶占資源并回退n如果死鎖發(fā)生，可能很多車都不得不返回n有可能產生饑餓6.6n一組等待的進程，其中每一個進程都持有資源，并且等待著由這個組中其他進程所持有的資源n所有死鎖進程無法推進n原因l競爭互斥資源l進程推進不當n例如l系統(tǒng)有兩個磁帶設備l進程P1和P2各占有一個磁帶設備并且實際需要兩個磁帶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：一次只有一個進程可以使用一個資源：一次只有一個進程可以使用一個資源n占有并等待占有并等待：一個至少持有一個資源的進程等待獲得額外：一個至少持有一個資源的進程等待獲得額外的由其他進程所持有的資源的由其他進程所持有的資源n不可搶占不可搶占：一個資源只有當持有它的進程完

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

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

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

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

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

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

10、 Allocation i,j.N為進程的數目，為進程的數目，M為資源類型的數目為資源類型的數目6.311.讓Work和Finish作為長度為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. 如果對所有i的 Finish i = true, 則系統(tǒng)處在安全狀態(tài)

11、。6.32 Requesti =進程 Pi 的資源請求向量. 如果Requesti m = k 則進程 Pi 想要資源類型為Rjm的k個實例1. 如果 Requesti Needi 轉 step 2. 否則報錯, 因為進程請求超出了其聲明的最大值2. 如果 Requesti Available, 轉 step 3. 否則 Pi 必須等待, 因為資源不可用.3. 假設通過修改下列狀態(tài)來分配請求的資源給進程Pi :Available := Available - Requesti;Allocationi := Allocationi + Requesti;Needi := Needi Reques

12、ti;如果系統(tǒng)安全 將資源分配給 Pi. 如果系統(tǒng)不安全 Pi 必須等待，恢復原有的資源分配狀態(tài)6.33n5個進程P0到P4； 3個資源類型A(10個實例），B（5個實例），C（7個實例）n時刻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)，因為序列系統(tǒng)處在安全的狀態(tài)，因為序列 滿足了滿足了安全的標準安全的標準NeedA B C P07 4 3 P11 2 2 P26 0 0 P30 1

13、1 P44 3 1 6.34n檢查檢查Request Available（就是說，（就是說，(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的請求(3,3,0)是否可以通過？nP0的請求(0,2,0)是否可以通過？6.36n允許進入死鎖狀態(tài)n檢測死鎖n恢復策略6.37n維護等待圖l節(jié)點是進程lPi Pj表明Pi在等待Pjn定期調用算法來檢

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

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