第3章處理機調度與死鎖處理機調度相關基本概念常用調度算法實時調度產生死鎖的原因和必要條件預防死鎖的方法死鎖的檢測與解除12/3/20221山東農業大學計算機系第3章處理機調度與死鎖處理機調度相關基本概念12/3/20關于死鎖多道程序系統借助并發執行改善資源利用率，提高系統吞吐量，但可能發生一種危險——死鎖。死鎖（Deadlock）：指多個進程在運行過程中，因爭奪資源而造成的一種僵局。當進程處于這種狀態時，若無外力作用，它們都將無法再向前推進。12/3/20222山東農業大學計算機系關于死鎖多道程序系統借助并發執行改善資源利用率，提高系統吞吐找原因分析形成條件根據分析，找出處理死鎖的方法四、產生死鎖的原因和必要條件12/3/20223山東農業大學計算機系找原因分析形成條件根據分析，找出處理死鎖的方法四、產生死鎖的例：使用信號量造成死鎖的典型 P1 P2wait（D） wait（E）wait（E） wait（D）signal（D） signal（E）signal（E） signal（D） 死鎖發生：雙方都擁有部分資源，同時在請求對方已占有的資源。請求推進的次序與對非剝奪性資源的爭用都是造成死鎖的原因。12/3/20224山東農業大學計算機系例：使用信號量造成死鎖的典型12/3/20224山東農業大學產生死鎖的原因可歸結為如下兩點：競爭資源。系統中供多個進程共享的資源如打印機、公用隊列等的數目不滿足需要時，會引起資源競爭而產生死鎖。進程間推進順序非法。進程在運行過程中，請求和釋放資源的順序不當，同樣會導致死鎖。12/3/20225山東農業大學計算機系產生死鎖的原因可歸結為如下兩點：12/3/20225山東農業1、競爭資源引起進程死鎖可把系統中的資源分為兩類：可剝奪和非剝奪性資源可剝奪性資源：分配給進程后可以被高優先級的進程剝奪。如CPU和主存。不可剝奪性資源：分配給進程后只能在進程用完后釋放。如磁帶機、打印機等。永久性資源和臨時性資源永久性：打印機?？身樞蛑貜褪褂门R時性：進程產生被其他進程短暫使用的資源，如數據資源：“生產者/消費者”算法中的信號量。。它可能引起死鎖。12/3/20226山東農業大學計算機系1、競爭資源引起進程死鎖可把系統中的資源分為兩類：12/3/2、進程推進順序不當引起死鎖進程在運行中具有異步性特征，多個進程按向前推進的順序有兩種情況：推進順序合法推進順序非法12/3/20227山東農業大學計算機系2、進程推進順序不當引起死鎖進程在運行中具有異步性特征，多個3、產生死鎖的必要條件形成死鎖的四個必要條件（四個條件都具備就會死鎖，缺一就不會死鎖）12/3/20228山東農業大學計算機系3、產生死鎖的必要條件形成死鎖的四個必要條件（四個條件都具互斥條件：進程對所分配到的資源進行排他性使用請求和保持條件：進程已經保持了至少一個資源，又提出新的資源請求，而新請求資源被其他進程占有只能造成自身進程阻塞，但對自己已獲得的其他資源保持不放，必然影響其他進程。不剝奪條件：進程已獲得的資源未使用完之前不能被剝奪，只能在使用完時由自己釋放。環路等待條件破壞這4個條件即是處理死鎖的方法12/3/20229山東農業大學計算機系互斥條件：進程對所分配到的資源進行排他性使用破壞這4個條件1如哲學家就餐問題的一種寫法，wait（mutex）wait（left）wait（right）signal(mutex)signal(left)signal(left)會死鎖么？12/3/202210山東農業大學計算機系如哲學家就餐問題的一種寫法，會死鎖么？12/3/202214、處理死鎖的基本方法事先預防：預防死鎖設置限制條件，破壞四個必要條件的一個或幾個，預防發生死鎖。較易實現。限制條件的嚴格也會導致系統資源利用率和系統吞吐量降低。避免死鎖不須事先限制，破壞四個必要條件，而是在資源的動態分配過程中，用某種方法去防止系統進入不安全狀態，從而避免發生死鎖。這種事先加以較弱限制的方法，實現上有一定難度，但可獲較高的資源利用率及系統吞吐量，目前在較完善的系統中，常用此方法來避免發生死鎖。12/3/202211山東農業大學計算機系4、處理死鎖的基本方法12/3/202211山東農業大學計算事后處理：檢測死鎖。允許系統運行過程中發生死鎖，但通過系統檢測機構可及時的檢測出，能精確確定與死鎖有關的進程和資源；然后采取適當的措施，從系統中將已發生的死鎖清除掉。解除死鎖。與死鎖檢測配套的一種措施。常用的實施方法：撤銷或掛起一些進程，以便回收一些資源并將他們分配給已阻塞進程，使之轉為就緒以繼續運行。死鎖的檢測與解除措施，有可能使系統獲得較好的資源利用率和吞吐量（死鎖幾率不一定很高），但在實現上難度也最大。12/3/202212山東農業大學計算機系事后處理：12/3/202212山東農業大學計算機系第3章處理機調度與死鎖處理機調度相關基本概念常用調度算法實時調度產生死鎖的原因和必要條件預防死鎖的方法死鎖的檢測與解除12/3/202213山東農業大學計算機系第3章處理機調度與死鎖處理機調度相關基本概念12/3/20五、預防死鎖的方法預防死鎖資源的排他性無法更改，故在其他3個條件上入手摒棄“請求和保持”條件：所有進程開始運行前，必須一次性的申請其在整個運行過程所需的全部資源（AND）。算法簡單、易于實現且很安全。但缺點是資源浪費嚴重、或進程延遲運行。摒棄“不剝奪”條件：允許進程先運行，但當提出的新要求不被滿足時必須釋放它已保持的所有資源，待以后需要時再重新申請。實現比較復雜且付出很大代價?？赡軙斐汕肮ΡM棄，反復申請和釋放等情況。12/3/202214山東農業大學計算機系五、預防死鎖的方法預防死鎖12/3/202214山東農業大學摒棄“環路等待”條件有序設置資源：將所有資源按類型進行線性排隊，賦予不同序號。所有進程對資源的請求必須嚴格按照資源序號遞增的次序提出，這樣在所形成的資源分配圖中，不可能會出現環路。與前兩種策略比較，資源利用率和系統吞吐量都有較明顯的改善。但也存在嚴重問題：資源編號限制新設備的增加；應用中的使用設備順序與規定的順序并不協調；限制了用戶編程自由。12/3/202215山東農業大學計算機系摒棄“環路等待”條件12/3/202215山東農業大學計算機2.避免死鎖上述方法限制條件都太強；造成一定的應用不便。采用避免死鎖的方法則是只施加較弱限制條件，從而獲得令人滿意的系統性能。名詞：安全狀態：系統能按某種進程順序為每個進程分配所需資源，直至滿足每個進程對資源的最大需求，并能順利完成。不安全狀態：系統無法找到一種使多個進程能夠順利分配資源執行完的安全序列。12/3/202216山東農業大學計算機系2.避免死鎖上述方法限制條件都太強；造成一定的應用不便。采用*安全狀態、安全序列舉例假定三個進程A、B和C，共有12臺磁帶機。假設t0時刻，磁帶機資源分配情況如下表所示，此時系統是否處于安全狀態？進程最大需求已分配還需可用A10553B422C927是安全的，因為存在一個安全序列B,A,C只要系統按此進程序列分配資源，就能使每個進程都順利完成。12/3/202217山東農業大學計算機系*安全狀態、安全序列舉例假定三個進程A、B和C，共有12臺*由安全狀態向不安全狀態的轉換每次資源分配時，都應分析判斷資源分配圖，看該次操作后是否有安全序列。若沒有，說明該操作會使系統進入不安全狀態。只要使系統始終處于安全狀態，便可避免發生死鎖。不是所有的不安全狀態都是死鎖狀態。12/3/202218山東農業大學計算機系*由安全狀態向不安全狀態的轉換每次資源分配時，都應分析判斷3.銀行家算法避免死鎖 最有代表性的避免死鎖的算法，是Dijkstra的銀行家算法。由于該算法能用于銀行系統現金貸款的發放而得名。 【思路描述】：隨時對系統中的所有資源信息進行統計，包括每種資源的數量、已分配給各進程的數量；每當進程提出某種資源請求時判斷該請求分配后是否安全，如果安全才分配。對每個資源請求的處理都要保證系統始終從一個安全狀態到另一個安全狀態。12/3/202219山東農業大學計算機系3.銀行家算法避免死鎖12/3/202219山東農業大學計銀行家算法應用之例假定系統中有五個進程{P0,P1,P2,P3,P4}和三類資源{A,B,C}，各種資源的數量分別為10、5、7，在T0時刻的資源分配情況如圖所示。431002433P4011211222P3600302902P2122200322P1332743010753P0AvailableABCNeedABCAllocationABCMaxABC資源情況進程12/3/202220山東農業大學計算機系銀行家算法應用之例假定系統中有五個進程{P0,P1,P計算舉例：當前T0時刻是否安全？利用安全性算法在下表找一個安全序列{P1,P3,P4,P2,P0}，故是安全的。（最后檢查應是資源釋放完后又回到10、5、7）431002433P4011211222P3600302902P2122200322P1332743010753P0AvailableABCNeedABCAllocationABCMaxABC資源情況進程5327437451047105712/3/202221山東農業大學計算機系計算舉例：當前T0時刻是否安全？43找安全序列的計算過程表True10570107431047P0True1047302600745P2True745002431743P4True743211011532P3True532200122332P1FinishWork+AllocationABCAllocationABCNeedABCWorkABC資源情況進程12/3/202222山東農業大學計算機系找安全序列的計算過程表True105（1）T0時刻的初始狀態是安全的；（2）下面出現P1請求資源的操作，具體請求向量為Request1(1,0,2)，利用銀行家算法進行檢查該操作是否是安全可行的：1）兩個基本判斷 Request1(1,0,2)<=Need1(1,2,2) Request1(1,0,2)<=Available1(3,3,2)2）先假設為P1分配資源，并修改Available,Allocation1和Need1向量。12/3/202223山東農業大學計算機系（1）T0時刻的初始狀態是安全的；12/3/202223山東3）Request1(1,0,2)后新的資源狀態表下再判斷新資源狀態是否是安全的。找到一個安全序列{P1,P3,P4,P0,P2}，因此系統是安全的，該請求是安全的，可將假設真正實施，將P1所申請的資源分配給它。True1057302600755P2True755010743745P0True745002431743P4True743211011532P3True532302020230P1FinishWork+AllocationABCAllocationABCNeedABCWorkABC資源情況進程200+102122—102332—10212/3/202224山東農業大學計算機系3）Request1(1,0,2)后新的資源狀態表下再判斷問：P4發出請求向量Request4(3,3,0)，可否分配資源？1）Request4(3,3,0)<=Need4(4,3,1);2）Request4(3,3,0)<=Available(2,3,0),P4等待問：P0發出請求向量Request0(0,2,0)，可否分配資源？1）Request0(0,2,0)<=Need0(7,4,3);2）Request0(0,2,0)<=Available(2,3,0)；3）系統暫時先假定可為P0分配資源，并修改有關數據，見下表：431002P4011211P3600302P2020302P1210723030P0AvailableABCNeedABCAllocationABC資源情況進程Available(2,1,0)不能滿足任何finish=false進程的需求，如果分配會使系統進入不安全狀態，所以不能分配資源。如果把P0發出的請求向量改為Request0(0,1,0),系統是否能將資源分配給它，大家考慮。73322002012/3/202225山東農業大學計算機系問：P4發出請求向量Request4(3,3,0)，可否分配算法實現說明算法實現:首先：需要的一些數據結構再次：算法過程核心：安全性判斷算法12/3/202226山東農業大學計算機系算法實現說明算法實現:12/3/202226山東農業大學計算1）銀行家算法中的數據結構（1）各類可利用資源的數量向量Available：（i1，i2，…，im），含m個元素，每個元素代表一類可利用的資源數目。動態變化的，初始值是系統配置的該類資源的全部數目，值隨資源的分配與回收而動態的改變。實現：一維數組。Available【j】=K，表示系統中Rj類資源現有可用數量為K個。m類資源，n個并發進程對其產生需求12/3/202227山東農業大學計算機系1）銀行家算法中的數據結構m類資源，n個并發進程對其產生需（2）每個進程對每類資源的需求最大需求、已獲得的、還需要的最大需求矩陣Maxn*m，系統中n個進程中每個進程分別對m類資源的最大需求。取值：根據進程需求賦初始值。實現：二維數組。Max【i，j】=K，表示進程i需要Rj類資源的最大數目為K。12/3/202228山東農業大學計算機系（2）每個進程對每類資源的需求12/3/202228山東農業已分配矩陣Allocation。n*m，定義系統中每一進程已獲得的每類資源數量。Allocation【i，j】=K，表示進程i當前已分得Rj類資源數為K。還需求的矩陣Need。n*m，表示每一進程尚需的各類資源數。Need【i，j】=K，表示進程i還需要Rj類資源K個，方能完成任務。上述三個矩陣存在關系： Max【i，j】=Allocation【i，j】+Need【i，j】每次，給進程i分配資源的動作，影響上述數據結構的取值： Available【】，Allocation【i，】，Need【i，】12/3/202229山東農業大學計算機系已分配矩陣Allocation。12/3/202229山東農2）避免死鎖的算法過程（銀行家算法）當前資源分配狀態如何？構建資源分配表判斷向下運行過程中，各進程對資源的需求是否安全。

在當前資源分配狀態基礎上，分析進程的實際請求Requesti【j】=k。表示進程Pi需要K個Rj類型的資源。進程MAXABCAllocationABCNeedABCAvailableABCP0753232521432P1542221321P2211100111資源情況Request0（2，2，1）12/3/202230山東農業大學計算機系2）避免死鎖的算法過程（銀行家算法）當前資源分配狀態如何？構算法過程：

就是對各進程的Request向量及資源數量進行一系列判斷及值操作。進程Pi發出資源請求后，系統按下述步驟進行檢查：首先是兩個基本判斷：（1）IFRequesti[j]<=Need[i,j] THEN轉向步驟2； ELSE認為出錯，所需資源數超過宣布的最大值（自我矛盾)（2）IFRequesti[j]<=Available[j] THEN轉向步驟3； ELSE表示尚無足夠資源，Pi需等待（現實不滿足）12/3/202231山東農業大學計算機系算法過程：

就是對各進程的Request向量及資源數量進行一如果上面兩步判斷都通過了，進入實質的資源分析（3）系統試探著把資源分配給進程Pi，并修改相應數據結構的值（假設性操作）：Available【j】 =Allocation【i,j】=Need【i,j】=（4）系統執行安全性算法，判斷新的資源分配狀態是否是安全的。 即：找一個安全序列，使這些進程按順序執行完）如果能夠找到，則將假設操作真正實施完成資源分配。Available【j】-Requesti【j】;Allocation【i,j】+Requesti【j】;Need【i,j】 -Requesti【j】;請求前的資源分配狀態新的資源分配狀態安全性算法12/3/202232山東農業大學計算機系如果上面兩步判斷都通過了，進入實質的資源分析Availabl3）安全性算法（1）需要一些記錄信息的數據結構，設置兩個向量：工作向量work算法開始時work=Available;系統找安全序列的過程需要不斷判斷和修改當前資源數量，不能直接修改原始數據記錄Aailable。標志向量Finish表示每個進程是否有足夠的資源使之運行完成。開始時所以進程都設置初值Finish[i]:=false;找安全序列的過程相當于使所有Finish[i]:=true。12/3/202233山東農業大學計算機系3）安全性算法（1）需要一些記錄信息的數據結構，設置兩個向量（2）找安全序列的過程 從Finish[i]=false的進程集合中找一個進程 IFNeed[i,j]<=work[j] THEN執行步驟a; ELSE執行步驟b; a）假設Pi獲得資源順利執行完，釋放出分配給它的資源，修改相應的值：work【j】=work【i】+Allocation【i，j】;Finish【i】=true;gotostep（2）;//返回去繼續找下一個進程。 b）當算法不再在（2）、a）步間循環找進程，到達本步時，若所有Finish[i]=true都滿足，則表示所有進程都按某個順序執行完了，系統處于安全狀態；否則，系統當前所處的資源分配狀態是不安全狀態。12/3/202234山東農業大學計算機系（2）找安全序列的過程12/3/202234山東農業大學計算第3章處理機調度與死鎖處理機調度相關基本概念常用調度算法實時調度產生死鎖的原因和必要條件預防死鎖的方法死鎖的檢測與解除12/3/202235山東農業大學計算機系第3章處理機調度與死鎖處理機調度相關基本概念12/3/20六、死鎖的檢測與解除當系統為進程分配資源時，若未采取任何限制性措施，則系統必須提供檢測和解除死鎖的手段，為此系統必須：保存有關資源的請求和分配信息；提供一種算法，以利用這些信息來檢測系統是否已進入死鎖狀態。12/3/202236山東農業大學計算機系六、死鎖的檢測與解除當系統為進程分配資源時，若未采取任何限制1、資源分配圖系統死鎖可利用資源分配圖來描述。圓圈表示進程方框表示一類資源，其中的一個點代表一個該類資源請求邊由進程指向方框中的資源分配邊則由方框中的一個點即資源。r1r2P2P112/3/202237山東農業大學計算機系1、資源分配圖系統死鎖可利用資源分配圖來描述。P2P112/2、死鎖定理利用資源分配圖簡化法來檢測死鎖。簡化方法如下： 1.在資源分配圖中找出一個既不阻塞又非獨立的進程結點Pi，在順利的情況下運行完畢，釋放其占有的全部資源。 2.由于釋放了資源，這樣能使其它被阻塞的進程獲得資源繼續運行。消去了Pi的邊。 3.經過一系列簡化后，若能消去圖中所有邊，使結點都孤立，稱該圖是可完全簡化的。S狀態為死鎖狀態的充分條件是當且僅當S狀態的資源分配圖是不可完全簡化的。<死鎖定理>12/3/202238山東農業大學計算機系2、死鎖定理利用資源分配圖簡化法來檢測死鎖。12/3/202例：根據死鎖定理判斷如下所示的資源分配圖是否存在死鎖?！稹稹稹餚1P2P3R1R2R3P1P3P2○○R1R2圖1圖212/3/202239山東農業大學計算機系例：根據死鎖定理判斷如下所示的資源分配圖是否存在死鎖。○○○3、死鎖的解除當發現進程死鎖時，便應立即把它們從死鎖狀態中解脫出來。常采用的方法是：剝奪資源。從其他進程剝奪足夠數量的資源給死鎖進程以解除死鎖狀態。撤銷進程。最簡單的是讓全部進程都死掉；溫和一點的是按照某種順序逐個撤銷進程，直至有足夠的資源可用，使死鎖狀態消除為止。12/3/202240山東農業大學計算機系3、死鎖的解除當發現進程死鎖時，便應立即把它們從死鎖狀態中本章基礎要點若要使當前運行進程總是優先級最高的進程，則應選擇：可搶占優先級調度算法。在分時系統中，進程調度經常采用：時間片輪轉調度算法。可引起進程調度的原因：進程運行結束進入阻塞狀態時間片用完有更高優先級的進程進入就緒隊列12/3/202241山東農業大學計算機系本章基礎要點若要使當前運行進程總是優先級最高的進程，則應選擇本章基礎要點進程調度采用時間片輪轉法時，時間片過大，就會使輪轉法轉化為：先來先服務調度算法。進程的調度方式有兩種：可搶占和非搶占方式死鎖產生的四個必要條件是：互斥、占有且等待、不剝奪和環路等待。在有m個進程的系統中出現死鎖時，死鎖進程的個數k滿足條件：2≤k≤m12/3/202242山東農業大學計算機系本章基礎要點進程調度采用時間片輪轉法時，時間片過大，就會使輪本章基礎要點不讓死鎖發生的策略可分為靜態和動態兩種，死鎖避免屬于：動態策略。在進程資源圖中，資源Rj分配給進程Pi應表示為：（Rj，Pi）。預先靜態分配法可以破壞：10：3*3+1資源的按序分配策略可以破壞：環路等待條件。某系統中有3個并發進程，都需要同類資源4個，該系統絕對不會發生死鎖的最少資源個數是：占有且等待條件。9：？12/3/202243山東農業大學計算機系本章基礎要點不讓死鎖發生的策略可分為靜態和動態兩種，死鎖避免設系統中僅有一類獨占資源，進程一次只能申請一個資源，系統中有多個進程競爭該類資源。試判斷下述哪些情況會發生死鎖？為什么？平均分到每個進程maxneed-1個后，能否有執行序列資源數為4，進程數為3，每個進程最多需要2個資源；資源數為6，進程數為2，每個進程最多需要4個資源；資源數為8，進程數為3，每個進程最多需要3個資源；資源數為20，進程數為8，每個進程最多需要2個資源；12/3/202244山東農業大學計算機系設系統中僅有一類獨占資源，進程一次只能申請一個資源，系統中有勿眼高手低練習中檢查知識細節的掌握12/3/202245山東農業大學計算機系勿眼高手低12/3/202245山東農業大學計算機系第3章處理機調度與死鎖處理機調度相關基本概念常用調度算法實時調度產生死鎖的原因和必要條件預防死鎖的方法死鎖的檢測與解除12/3/202246山東農業大學計算機系第3章處理機調度與死鎖處理機調度相關基本概念12/3/20關于死鎖多道程序系統借助并發執行改善資源利用率，提高系統吞吐量，但可能發生一種危險——死鎖。死鎖（Deadlock）：指多個進程在運行過程中，因爭奪資源而造成的一種僵局。當進程處于這種狀態時，若無外力作用，它們都將無法再向前推進。12/3/202247山東農業大學計算機系關于死鎖多道程序系統借助并發執行改善資源利用率，提高系統吞吐找原因分析形成條件根據分析，找出處理死鎖的方法四、產生死鎖的原因和必要條件12/3/202248山東農業大學計算機系找原因分析形成條件根據分析，找出處理死鎖的方法四、產生死鎖的例：使用信號量造成死鎖的典型 P1 P2wait（D） wait（E）wait（E） wait（D）signal（D） signal（E）signal（E） signal（D） 死鎖發生：雙方都擁有部分資源，同時在請求對方已占有的資源。請求推進的次序與對非剝奪性資源的爭用都是造成死鎖的原因。12/3/202249山東農業大學計算機系例：使用信號量造成死鎖的典型12/3/20224山東農業大學產生死鎖的原因可歸結為如下兩點：競爭資源。系統中供多個進程共享的資源如打印機、公用隊列等的數目不滿足需要時，會引起資源競爭而產生死鎖。進程間推進順序非法。進程在運行過程中，請求和釋放資源的順序不當，同樣會導致死鎖。12/3/202250山東農業大學計算機系產生死鎖的原因可歸結為如下兩點：12/3/20225山東農業1、競爭資源引起進程死鎖可把系統中的資源分為兩類：可剝奪和非剝奪性資源可剝奪性資源：分配給進程后可以被高優先級的進程剝奪。如CPU和主存。不可剝奪性資源：分配給進程后只能在進程用完后釋放。如磁帶機、打印機等。永久性資源和臨時性資源永久性：打印機?？身樞蛑貜褪褂门R時性：進程產生被其他進程短暫使用的資源，如數據資源：“生產者/消費者”算法中的信號量。。它可能引起死鎖。12/3/202251山東農業大學計算機系1、競爭資源引起進程死鎖可把系統中的資源分為兩類：12/3/2、進程推進順序不當引起死鎖進程在運行中具有異步性特征，多個進程按向前推進的順序有兩種情況：推進順序合法推進順序非法12/3/202252山東農業大學計算機系2、進程推進順序不當引起死鎖進程在運行中具有異步性特征，多個3、產生死鎖的必要條件形成死鎖的四個必要條件（四個條件都具備就會死鎖，缺一就不會死鎖）12/3/202253山東農業大學計算機系3、產生死鎖的必要條件形成死鎖的四個必要條件（四個條件都具互斥條件：進程對所分配到的資源進行排他性使用請求和保持條件：進程已經保持了至少一個資源，又提出新的資源請求，而新請求資源被其他進程占有只能造成自身進程阻塞，但對自己已獲得的其他資源保持不放，必然影響其他進程。不剝奪條件：進程已獲得的資源未使用完之前不能被剝奪，只能在使用完時由自己釋放。環路等待條件破壞這4個條件即是處理死鎖的方法12/3/202254山東農業大學計算機系互斥條件：進程對所分配到的資源進行排他性使用破壞這4個條件1如哲學家就餐問題的一種寫法，wait（mutex）wait（left）wait（right）signal(mutex)signal(left)signal(left)會死鎖么？12/3/202255山東農業大學計算機系如哲學家就餐問題的一種寫法，會死鎖么？12/3/202214、處理死鎖的基本方法事先預防：預防死鎖設置限制條件，破壞四個必要條件的一個或幾個，預防發生死鎖。較易實現。限制條件的嚴格也會導致系統資源利用率和系統吞吐量降低。避免死鎖不須事先限制，破壞四個必要條件，而是在資源的動態分配過程中，用某種方法去防止系統進入不安全狀態，從而避免發生死鎖。這種事先加以較弱限制的方法，實現上有一定難度，但可獲較高的資源利用率及系統吞吐量，目前在較完善的系統中，常用此方法來避免發生死鎖。12/3/202256山東農業大學計算機系4、處理死鎖的基本方法12/3/202211山東農業大學計算事后處理：檢測死鎖。允許系統運行過程中發生死鎖，但通過系統檢測機構可及時的檢測出，能精確確定與死鎖有關的進程和資源；然后采取適當的措施，從系統中將已發生的死鎖清除掉。解除死鎖。與死鎖檢測配套的一種措施。常用的實施方法：撤銷或掛起一些進程，以便回收一些資源并將他們分配給已阻塞進程，使之轉為就緒以繼續運行。死鎖的檢測與解除措施，有可能使系統獲得較好的資源利用率和吞吐量（死鎖幾率不一定很高），但在實現上難度也最大。12/3/202257山東農業大學計算機系事后處理：12/3/202212山東農業大學計算機系第3章處理機調度與死鎖處理機調度相關基本概念常用調度算法實時調度產生死鎖的原因和必要條件預防死鎖的方法死鎖的檢測與解除12/3/202258山東農業大學計算機系第3章處理機調度與死鎖處理機調度相關基本概念12/3/20五、預防死鎖的方法預防死鎖資源的排他性無法更改，故在其他3個條件上入手摒棄“請求和保持”條件：所有進程開始運行前，必須一次性的申請其在整個運行過程所需的全部資源（AND）。算法簡單、易于實現且很安全。但缺點是資源浪費嚴重、或進程延遲運行。摒棄“不剝奪”條件：允許進程先運行，但當提出的新要求不被滿足時必須釋放它已保持的所有資源，待以后需要時再重新申請。實現比較復雜且付出很大代價?？赡軙斐汕肮ΡM棄，反復申請和釋放等情況。12/3/202259山東農業大學計算機系五、預防死鎖的方法預防死鎖12/3/202214山東農業大學摒棄“環路等待”條件有序設置資源：將所有資源按類型進行線性排隊，賦予不同序號。所有進程對資源的請求必須嚴格按照資源序號遞增的次序提出，這樣在所形成的資源分配圖中，不可能會出現環路。與前兩種策略比較，資源利用率和系統吞吐量都有較明顯的改善。但也存在嚴重問題：資源編號限制新設備的增加；應用中的使用設備順序與規定的順序并不協調；限制了用戶編程自由。12/3/202260山東農業大學計算機系摒棄“環路等待”條件12/3/202215山東農業大學計算機2.避免死鎖上述方法限制條件都太強；造成一定的應用不便。采用避免死鎖的方法則是只施加較弱限制條件，從而獲得令人滿意的系統性能。名詞：安全狀態：系統能按某種進程順序為每個進程分配所需資源，直至滿足每個進程對資源的最大需求，并能順利完成。不安全狀態：系統無法找到一種使多個進程能夠順利分配資源執行完的安全序列。12/3/202261山東農業大學計算機系2.避免死鎖上述方法限制條件都太強；造成一定的應用不便。采用*安全狀態、安全序列舉例假定三個進程A、B和C，共有12臺磁帶機。假設t0時刻，磁帶機資源分配情況如下表所示，此時系統是否處于安全狀態？進程最大需求已分配還需可用A10553B422C927是安全的，因為存在一個安全序列B,A,C只要系統按此進程序列分配資源，就能使每個進程都順利完成。12/3/202262山東農業大學計算機系*安全狀態、安全序列舉例假定三個進程A、B和C，共有12臺*由安全狀態向不安全狀態的轉換每次資源分配時，都應分析判斷資源分配圖，看該次操作后是否有安全序列。若沒有，說明該操作會使系統進入不安全狀態。只要使系統始終處于安全狀態，便可避免發生死鎖。不是所有的不安全狀態都是死鎖狀態。12/3/202263山東農業大學計算機系*由安全狀態向不安全狀態的轉換每次資源分配時，都應分析判斷3.銀行家算法避免死鎖 最有代表性的避免死鎖的算法，是Dijkstra的銀行家算法。由于該算法能用于銀行系統現金貸款的發放而得名。 【思路描述】：隨時對系統中的所有資源信息進行統計，包括每種資源的數量、已分配給各進程的數量；每當進程提出某種資源請求時判斷該請求分配后是否安全，如果安全才分配。對每個資源請求的處理都要保證系統始終從一個安全狀態到另一個安全狀態。12/3/202264山東農業大學計算機系3.銀行家算法避免死鎖12/3/202219山東農業大學計銀行家算法應用之例假定系統中有五個進程{P0,P1,P2,P3,P4}和三類資源{A,B,C}，各種資源的數量分別為10、5、7，在T0時刻的資源分配情況如圖所示。431002433P4011211222P3600302902P2122200322P1332743010753P0AvailableABCNeedABCAllocationABCMaxABC資源情況進程12/3/202265山東農業大學計算機系銀行家算法應用之例假定系統中有五個進程{P0,P1,P計算舉例：當前T0時刻是否安全？利用安全性算法在下表找一個安全序列{P1,P3,P4,P2,P0}，故是安全的。（最后檢查應是資源釋放完后又回到10、5、7）431002433P4011211222P3600302902P2122200322P1332743010753P0AvailableABCNeedABCAllocationABCMaxABC資源情況進程5327437451047105712/3/202266山東農業大學計算機系計算舉例：當前T0時刻是否安全？43找安全序列的計算過程表True10570107431047P0True1047302600745P2True745002431743P4True743211011532P3True532200122332P1FinishWork+AllocationABCAllocationABCNeedABCWorkABC資源情況進程12/3/202267山東農業大學計算機系找安全序列的計算過程表True105（1）T0時刻的初始狀態是安全的；（2）下面出現P1請求資源的操作，具體請求向量為Request1(1,0,2)，利用銀行家算法進行檢查該操作是否是安全可行的：1）兩個基本判斷 Request1(1,0,2)<=Need1(1,2,2) Request1(1,0,2)<=Available1(3,3,2)2）先假設為P1分配資源，并修改Available,Allocation1和Need1向量。12/3/202268山東農業大學計算機系（1）T0時刻的初始狀態是安全的；12/3/202223山東3）Request1(1,0,2)后新的資源狀態表下再判斷新資源狀態是否是安全的。找到一個安全序列{P1,P3,P4,P0,P2}，因此系統是安全的，該請求是安全的，可將假設真正實施，將P1所申請的資源分配給它。True1057302600755P2True755010743745P0True745002431743P4True743211011532P3True532302020230P1FinishWork+AllocationABCAllocationABCNeedABCWorkABC資源情況進程200+102122—102332—10212/3/202269山東農業大學計算機系3）Request1(1,0,2)后新的資源狀態表下再判斷問：P4發出請求向量Request4(3,3,0)，可否分配資源？1）Request4(3,3,0)<=Need4(4,3,1);2）Request4(3,3,0)<=Available(2,3,0),P4等待問：P0發出請求向量Request0(0,2,0)，可否分配資源？1）Request0(0,2,0)<=Need0(7,4,3);2）Request0(0,2,0)<=Available(2,3,0)；3）系統暫時先假定可為P0分配資源，并修改有關數據，見下表：431002P4011211P3600302P2020302P1210723030P0AvailableABCNeedABCAllocationABC資源情況進程Available(2,1,0)不能滿足任何finish=false進程的需求，如果分配會使系統進入不安全狀態，所以不能分配資源。如果把P0發出的請求向量改為Request0(0,1,0),系統是否能將資源分配給它，大家考慮。73322002012/3/202270山東農業大學計算機系問：P4發出請求向量Request4(3,3,0)，可否分配算法實現說明算法實現:首先：需要的一些數據結構再次：算法過程核心：安全性判斷算法12/3/202271山東農業大學計算機系算法實現說明算法實現:12/3/202226山東農業大學計算1）銀行家算法中的數據結構（1）各類可利用資源的數量向量Available：（i1，i2，…，im），含m個元素，每個元素代表一類可利用的資源數目。動態變化的，初始值是系統配置的該類資源的全部數目，值隨資源的分配與回收而動態的改變。實現：一維數組。Available【j】=K，表示系統中Rj類資源現有可用數量為K個。m類資源，n個并發進程對其產生需求12/3/202272山東農業大學計算機系1）銀行家算法中的數據結構m類資源，n個并發進程對其產生需（2）每個進程對每類資源的需求最大需求、已獲得的、還需要的最大需求矩陣Maxn*m，系統中n個進程中每個進程分別對m類資源的最大需求。取值：根據進程需求賦初始值。實現：二維數組。Max【i，j】=K，表示進程i需要Rj類資源的最大數目為K。12/3/202273山東農業大學計算機系（2）每個進程對每類資源的需求12/3/202228山東農業已分配矩陣Allocation。n*m，定義系統中每一進程已獲得的每類資源數量。Allocation【i，j】=K，表示進程i當前已分得Rj類資源數為K。還需求的矩陣Need。n*m，表示每一進程尚需的各類資源數。Need【i，j】=K，表示進程i還需要Rj類資源K個，方能完成任務。上述三個矩陣存在關系： Max【i，j】=Allocation【i，j】+Need【i，j】每次，給進程i分配資源的動作，影響上述數據結構的取值： Available【】，Allocation【i，】，Need【i，】12/3/202274山東農業大學計算機系已分配矩陣Allocation。12/3/202229山東農2）避免死鎖的算法過程（銀行家算法）當前資源分配狀態如何？構建資源分配表判斷向下運行過程中，各進程對資源的需求是否安全。

在當前資源分配狀態基礎上，分析進程的實際請求Requesti【j】=k。表示進程Pi需要K個Rj類型的資源。進程MAXABCAllocationABCNeedABCAvailableABCP0753232521432P1542221321P2211100111資源情況Request0（2，2，1）12/3/202275山東農業大學計算機系2）避免死鎖的算法過程（銀行家算法）當前資源分配狀態如何？構算法過程：

就是對各進程的Request向量及資源數量進行一系列判斷及值操作。進程Pi發出資源請求后，系統按下述步驟進行檢查：首先是兩個基本判斷：（1）IFRequesti[j]<=Need[i,j] THEN轉向步驟2； ELSE認為出錯，所需資源數超過宣布的最大值（自我矛盾)（2）IFRequesti[j]<=Available[j] THEN轉向步驟3； ELSE表示尚無足夠資源，Pi需等待（現實不滿足）12/3/202276山東農業大學計算機系算法過程：

就是對各進程的Request向量及資源數量進行一如果上面兩步判斷都通過了，進入實質的資源分析（3）系統試探著把資源分配給進程Pi，并修改相應數據結構的值（假設性操作）：Available【j】 =Allocation【i,j】=Need【i,j】=（4）系統執行安全性算法，判斷新的資源分配狀態是否是安全的。 即：找一個安全序列，使這些進程按順序執行完）如果能夠找到，則將假設操作真正實施完成資源分配。Available【j】-Requesti【j】;Allocation【i,j】+Requesti【j】;Need【i,j】 -Requesti【j】;請求前的資源分配狀態新的資源分配狀態安全性算法12/3/202277山東農業大學計算機系如果上面兩步判斷都通過了，進入實質的資源分析Availabl3）安全性算法（1）需要一些記錄信息的數據結構，設置兩個向量：工作向量work算法開始時work=Available;系統找安全序列的過程需要不斷判斷和修改當前資源數量，不能直接修改原始數據記錄Aailable。標志向量Finish表示每個進程是否有足夠的資源使之運行完成。開始時所以進程都設置初值Finish[i]:=false;找安全序列的過程相當于使所有Finish[i]:=true。12/3/202278山東農業大學計算機系3）安全性算法（1）需要一些記錄信息的數據結構，設置兩個向量（2）找安全序列的過程 從Finish[i]=false的進程集合中找一個進程 IFNeed[i,j]<=work[j] THEN執行步驟a; ELSE執行步驟b; a）假設Pi獲得資源順利執行完，釋放出分配給它的資源，修改相應