1,2019年9月6日星期五,北京交通大學計算機學院,操作系統(tǒng)（A）,北京交通大學計算機學院 何永忠 副教授,第三章：處理機調度與死鎖,2,2019年9月6日星期五,北京交通大學計算機學院,第三章 處理機調度與死鎖,3.1 高級、中級與低級調度 3.2 調度隊列模型 3.3 調度方式與算法選擇準則 3.4 調度算法 3.5 死鎖產生及處理策略 3.6 死鎖避免與銀行家算法,3,2019年9月6日星期五,北京交通大學計算機學院,3.5 死鎖產生及處理策略,3.5.1 死鎖的基本概念 3.5.2 死鎖產生的原因 3.5.3 死鎖產生的必要條件 3.5.4 處理死鎖的基本方法 3.5.5 死鎖的預防 3.5.6 死鎖的檢測與解除,哲學家進餐問題回顧,0,3,2,1,4,0,4,3,2,1,死鎖的基本概念,5,2019年9月6日星期五,北京交通大學計算機學院,死鎖的基本概念,哲學家進餐問題死鎖分析 哲學家都拿起左手的筷子 都申請右手的筷子無法滿足阻塞等待無外界干預所有的哲學家都永遠阻塞等待 死鎖（Deadlock） 在多道程序系統(tǒng)中，并發(fā)執(zhí)行的多個進程因爭奪資源而造成的一種若無外力作用有關進程都將永遠不能向前推進的僵持狀態(tài)或僵局 在多道程序系統(tǒng)中，一組進程中的每一個進程都無限等待被同組的另外一個進程所占有且永遠不會釋放的資源的狀態(tài)。,6,2019年9月6日星期五,北京交通大學計算機學院,死鎖的相關概念辨析,餓死（Starvation） 資源不被一個進程永久占用的情況下，系統(tǒng)不能保證某個進程等待該資源的時間上界，從而使得該進程長時間等待該資源而無法在規(guī)定的時間完成 例如：短進程優(yōu)先調度算法，不斷有更短的進程到達時，長進程將永久等待而餓死。 活鎖（Livelock） 除了進程狀態(tài)可能在不斷改變外，與死鎖類似沒有一個進程能向前執(zhí)行。 例如：哲學家都拿起左手的筷子，試圖拿起右手的筷子不成，等待一段時間后都放下筷子又同時拿起左手的筷子。,7,2019年9月6日星期五,北京交通大學計算機學院,死鎖的后果,進程永遠無法完成 進程占有的資源永遠無法釋放 你遇到過死鎖嗎？ 我的程序怎么不響應我的操作了？ 一個程序怎么一直不能完成？ 一個進程調用winrar解壓文件時發(fā)生死鎖,8,2019年9月6日星期五,北京交通大學計算機學院,3.5 死鎖產生及處理策略,3.5.1 死鎖的基本概念 3.5.2 死鎖產生的原因 3.5.3 死鎖產生的必要條件 3.5.4 處理死鎖的基本方法 3.5.5 死鎖的預防 3.5.6 死鎖的檢測與解除,9,2019年9月6日星期五,北京交通大學計算機學院,死鎖產生原因之一：競爭資源,I/O設備共享時的死鎖情況 （A）競爭非剝奪性資源,非剝奪性資源：例如打印機。一旦分配不能隨時強行收回。 可剝奪資源：例如CPU。分配后可隨時收回。,10,2019年9月6日星期五,北京交通大學計算機學院,死鎖產生原因之一：競爭資源,進程間通信時的死鎖情況 （ B ）競爭臨時性資源,P1,P3,S1,S3,P2,S2,永久資源：例如打印機。始終存在的可重復使用的資源。 臨時性資源：例如進程產生的消息。由一個進程產生，被另一個進程臨時使用的資源。 P1: request S3; release S1; P2: request S1; release S2; P3: request S2; release S3;,11,2019年9月6日星期五,北京交通大學計算機學院,死鎖產生原因之二：進程推進次序非法,P1Request(R1),P1Request(R2),P1Release(R1),P1Release(R2),P2Request(R2),P2Request(R1),P2Release(R2),P2Release(R1),1,2,3,4,12,2019年9月6日星期五,北京交通大學計算機學院,3.5 死鎖產生及處理策略,3.5.1 死鎖的基本概念 3.5.2 死鎖產生的原因 3.5.3 死鎖產生的必要條件 3.5.4 處理死鎖的基本方法 3.5.5 死鎖的預防 3.5.6 死鎖的檢測與解除,13,2019年9月6日星期五,北京交通大學計算機學院,產生死鎖的必要條件,互斥條件 資源排它性使用，其他進程必須等待 請求和保持條件 請求資源未果進程雖阻塞但保持占有資源不放 不剝奪條件 進程已獲資源未使用完之前不能被剝奪 環(huán)路等待條件 進程-資源環(huán)形鏈 P0R1 P1 R2 P2 Pn Rn P0,14,2019年9月6日星期五,北京交通大學計算機學院,3.5 死鎖產生及處理策略,3.5.1 死鎖的基本概念 3.5.2 死鎖產生的原因 3.5.3 死鎖產生的必要條件 3.5.4 處理死鎖的基本方法 3.5.5 死鎖的預防 3.5.6 死鎖的檢測與解除,15,2019年9月6日星期五,北京交通大學計算機學院,處理死鎖的基本方法,預防死鎖 避免死鎖 檢測死鎖 解除死鎖,16,2019年9月6日星期五,北京交通大學計算機學院,3.5 死鎖產生及處理策略,3.5.1 死鎖的基本概念 3.5.2 死鎖產生的原因 3.5.3 死鎖產生的必要條件 3.5.4 處理死鎖的基本方法 3.5.5 死鎖的預防與避免 3.5.6 死鎖的檢測與解除,17,2019年9月6日星期五,北京交通大學計算機學院,預防死鎖與避免死鎖,如何防止死鎖的發(fā)生？ 思路：死鎖的原因包括競爭資源和推進次序非法兩個方面。 競爭資源的環(huán)節(jié)：用戶進程提出申請，系統(tǒng)批準分配資源。 推進次序：調度次序,18,2019年9月6日星期五,北京交通大學計算機學院,預防死鎖,預防死鎖：設置對用戶申請資源環(huán)節(jié)的限制，如果可以破壞產生死鎖的4個必要條件之一，就可以防止死鎖的發(fā)生。 互斥條件：是資源本身固有的，必須遵守該條件。,19,2019年9月6日星期五,北京交通大學計算機學院,死鎖的預防策略之一,一次性申請全部資源 系統(tǒng)要求所有進程在開始運行之前，都必須一次性地申請其在整個運行過程所需的全部資源。 原子操作，只有當每個要求都滿足時才進行一次性分配，否則等待。例如AND信號量實現(xiàn)哲學家進餐問題。 Swait (chi, ch(i+1) % 5) 摒棄“請求和保持”條件。,20,2019年9月6日星期五,北京交通大學計算機學院,死鎖的預防策略之一,一次性申請全部資源 優(yōu)點： 簡單、安全且易于實現(xiàn) 缺點： 資源浪費：全部資源一次申請，可能部分資源在很晚才會用到。 進程延遲：如果一個將來才用的資源被其他進程占有，本進程也無法執(zhí)行。,21,2019年9月6日星期五,北京交通大學計算機學院,死鎖的預防策略之二,申請失敗則釋放所有資源 進程在需要資源時才提出請求，且得不到滿足時應釋放其已占有資源 摒棄“請求保持”與“不剝奪”條件（主動放棄資源） 優(yōu)點：？資源利用率提高？ 缺點： 實現(xiàn)復雜，代價很大：如何保證已經完成的部分工作不失效 性能下降：反復地申請與釋放資源、進程周轉時間延長、系統(tǒng)吞吐量降低、系統(tǒng)開銷增加,22,2019年9月6日星期五,北京交通大學計算機學院,死鎖的預防策略之三,按升序申請資源 所有資源按類型進行線性排隊，所有進程對資源的請求按資源序號遞增次序提出 例如：打印機R1，磁帶機R2, 掃描儀R3 。 P1: request R1; request R2; P2: request R1; request R2； P3: request R2; request R1; request R3；？ 摒棄“環(huán)路等待”條件,能證明嗎？,23,2019年9月6日星期五,北京交通大學計算機學院,死鎖的預防策略之三,資源排序法 優(yōu)點：資源不是一次申請好，也不需要放棄已有資源，因此比前兩種方法的資源利用率、系統(tǒng)吞吐量更好 缺點： 資源浪費不可避免：編號小的后使用。 增加新設備如何編號？臨時性資源如何編號？如果是常用設備編號小些更好，但原有的設備必須重新編號。 編程者負擔重，給程序員增加了過多限制,24,2019年9月6日星期五,北京交通大學計算機學院,預防死鎖法的特點,預防死鎖：設置對用戶申請資源環(huán)節(jié)的限制，從而破壞產生死鎖必要條件 靜態(tài)性 進程執(zhí)行過程中都必須滿足相同限制條件 獨立性 與當前的系統(tǒng)中其他進程的情況無關 缺點小結：對用戶不透明，限制嚴格，資源利用率低,25,2019年9月6日星期五,北京交通大學計算機學院,第三章 處理機調度與死鎖,3.1 高級、中級與低級調度 3.2 調度隊列模型 3.3 調度方式與算法選擇準則 3.4 調度算法 3.5 死鎖產生及處理策略 3.6 死鎖避免與銀行家算法,26,2019年9月6日星期五,北京交通大學計算機學院,死鎖避免,基本思想 允許進程任意申請資源，對用戶不做任何限制 操作系統(tǒng)在進行資源分配之前，應首先進行必要的檢查，且僅當確認此次分配不會導致系統(tǒng)進入死鎖狀態(tài)時才可分配，否則予以拒絕。 例如：根據車流情況確定紅綠燈時間，提高了道路通行率。,27,2019年9月6日星期五,北京交通大學計算機學院,死鎖避免,一個簡單的方法 分配資源前，操作系統(tǒng)檢查：當把該資源分配給申請的進程后該狀態(tài)是否存在死鎖 如果不死鎖就分配，否則拒絕。,28,2019年9月6日星期五,北京交通大學計算機學院,死鎖避免,不可行，不能一定阻止死鎖發(fā)生。 兩個進程 P1: request R1; request R2; P2: request R2; request R1;,29,2019年9月6日星期五,北京交通大學計算機學院,死鎖產生原因之二：進程推進次序非法,P1Request(R1),P1Request(R2),P1Release(R1),P1Release(R2),P2Request(R2),P2Request(R1),P2Release(R2),P2Release(R1),1,2,3,4,可分配嗎？,死鎖了嗎？,30,2019年9月6日星期五,北京交通大學計算機學院,死鎖避免,結論：即使在分配資源后的下一狀態(tài)沒有死鎖，但是死鎖可能已經不可避免，即在將來的某個狀態(tài)一定會進入死鎖。,31,2019年9月6日星期五,北京交通大學計算機學院,死鎖避免,迷宮游戲（不準走回頭路）,32,2019年9月6日星期五,北京交通大學計算機學院,死鎖避免,因此，在決定是否分配資源時，需要有一定的預見性。 需要找到這樣一個狀態(tài)，不論之后進程并發(fā)執(zhí)行次序如何、資源申請情況如何，都不會發(fā)生“一定進入死鎖” 的狀態(tài)。 對迷宮來說，就是前方一定存在一條通向出口的道路。 這種狀態(tài)就是一種安全狀態(tài)。,33,2019年9月6日星期五,北京交通大學計算機學院,死鎖避免,難點： 假如系統(tǒng)完全不知道進程之后的申請資源的情況，是很難確定當前是否是安全狀態(tài)的。如同迷宮，身處迷宮中的人無法判斷當前是否已經進入了一個死胡同。 我們假設： 系統(tǒng)知道每個進程可以申請各類資源的最大數目。那么，進程在之后的執(zhí)行中申請資源數目就受到這個最大數的限制。,34,2019年9月6日星期五,北京交通大學計算機學院,死鎖避免基本概念,安全狀態(tài) 指系統(tǒng)可按某種進程序列（稱之為安全分配序列）來順序地為每個進程Pi分配其所需資源滿足該進程對資源的最大需求，完成并釋放資源，最終使每個進程均能順利完成。 不安全狀態(tài) 系統(tǒng)無法找到一個安全分配序列的系統(tǒng)狀態(tài),35,2019年9月6日星期五,北京交通大學計算機學院,安全狀態(tài)及向不安全狀態(tài)的轉換,T0時刻存在安全分配序列 若在T0時刻應進程請求將所剩磁帶機中的1臺分配給P3，則系統(tǒng)進入不安全狀態(tài),36,2019年9月6日星期五,北京交通大學計算機學院,死鎖避免基本概念,死鎖與安全狀態(tài)的關系 在安全狀態(tài)下，一定沒有死鎖 如果死鎖，則一定不是安全狀態(tài),37,2019年9月6日星期五,北京交通大學計算機學院,死鎖避免算法（銀行家算法）,檢查初始狀態(tài)是否安全狀態(tài) 每個進程的資源申請最大數都不超過系統(tǒng)資源數。 每次進程申請資源，操作系統(tǒng)收到申請后分配資源前都進行檢查 假設分配后進入安全狀態(tài)，就分配。 假設分配后進入不安全狀態(tài)，就不予分配。 該算法能保證系統(tǒng)始終不會死鎖嗎？,38,2019年9月6日星期五,北京交通大學計算機學院,死鎖避免算法正確性,用數學歸納法證明 1）i=0 時系統(tǒng)初始狀態(tài)是安全的 2）i=k系統(tǒng)是安全的，證明（在進程全部完成前）下一個狀態(tài)i=k+1是安全的。 THEN 系統(tǒng)不可能發(fā)生死鎖。,39,2019年9月6日星期五,北京交通大學計算機學院,死鎖避免算法正確性,1）i=0成立。 2）i=k系統(tǒng)是安全的，證明系統(tǒng)在進程全部完成前一定轉移到第k+1狀態(tài)是安全狀態(tài) 首先證明在進程沒有全部完成前，第k+1步中一定存在一個安全狀態(tài)。因為i=k狀態(tài)是安全的，即存在一個安全序列，所以在進程沒有全部完成前，只要按該安全序列的順序分配資源一次資源，可轉換到的第k+1狀態(tài)是安全狀態(tài)。 又因為每次分配資源都檢查，假設分配后進入不安全狀態(tài)，就不予分配（狀態(tài)不變）；只有安全時才分配資源。 所以系統(tǒng)一定轉移到狀態(tài)k+1,且是安全狀態(tài)。,40,2019年9月6日星期五,北京交通大學計算機學院,銀行家算法,如何判定當前狀態(tài)是否安全 當前可用資源是否可以滿足某個未完成進程的剩余需求（最大需求-已分配）？ 如果有多個進程都滿足，任選其一 將該進程已分配資源釋放，將該進程標識為已完成。 重復上述步驟，如果所有進程都可以完成，當前狀態(tài)是安全的；否則不安全。,41,2019年9月6日星期五,北京交通大學計算機學院,銀行家算法之數據結構,可利用資源向量/請求向量m Availablej=k表示系統(tǒng)現(xiàn)有k個Rj類資源 Requestij=k表示進程Pi請求k個Rj類資源 最大需求矩陣/分配矩陣/需求矩陣n,m Maxi,j=k表示進程Pi最多需要k個Rj類資源 Allocationi,j=k表示進程Pi已有k個Rj類資源 Needi,j=k表示進程Pi尚需k個Rj類資源 工作向量 m / Finish布爾向量 n Workj=k表示系統(tǒng)“可”提供k個Rj類資源 Finishi 表示進程Pi可否擁有足夠資源完成運行,42,2019年9月6日星期五,北京交通大學計算機學院,銀行家算法之主體算法,1 進程Pi發(fā)出資源請求Requesti 2 若非RequestiNeedi，出錯返回 3 若非Requesti Available，則應使Pi等待并返回 4 系統(tǒng)試探性地滿足Pi請求，并作以下修改： Available = Available Requesti Allocationi = Allocationi + Requesti Needi = Needi Requesti 5 系統(tǒng)調用安全性算法進行資源分配檢查，若安全則執(zhí)行分配，否則恢復試探分配前狀態(tài)，并使Pi等待,43,2019年9月6日星期五,北京交通大學計算機學院,銀行家算法之安全性子算法,1 令Work = Available， Finish=FALSE 2 從進程集合中查找一個滿足Finishi=FALSE且 Needi = Work 的進程Pi 。若找到，則可假定Pi能獲得所需資源并順利執(zhí)行，故有： Work = Work + Allocationi Finishi = True 然后重復執(zhí)行第2步；否則轉至第3步執(zhí)行 3 如果Finish=TRUE，則表示系統(tǒng)處于安全狀態(tài)；否則系統(tǒng)處于不安全狀態(tài),44,2019年9月6日星期五,北京交通大學計算機學院,銀行家算法應用舉例之一A(待續(xù)),系統(tǒng)資源總量 AvailableA,B,C = 10, 5, 7 T0時刻 AvailableA,B,C = 3, 3, 2 安全分配序列 ?,45,2019年9月6日星期五,北京交通大學計算機學院,銀行家算法應用舉例之一B(待續(xù)),系統(tǒng)資源總量 AvailableA,B,C = 10, 5, 7 T0時刻 AvailableA,B,C = 3, 3, 2 安全分配序列 ?,46,2019年9月6日星期五,北京交通大學計算機學院,銀行家算法應用舉例之一C(待續(xù)),系統(tǒng)資源總量 AvailableA,B,C = 10, 5, 7 T0時刻 AvailableA,B,C = 3, 3, 2 安全分配序列 ?,47,2019年9月6日星期五,北京交通大學計算機學院,銀行家算法應用舉例之一D(待續(xù)),系統(tǒng)資源總量 AvailableA,B,C = 10, 5, 7 T0時刻 AvailableA,B,C = 3, 3, 2 安全分配序列 ?,48,2019年9月6日星期五,北京交通大學計算機學院,銀行家算法應用舉例之一E(待續(xù)),系統(tǒng)資源總量 AvailableA,B,C = 10, 5, 7 T0時刻 AvailableA,B,C = 3, 3, 2 安全分配序列 ?,49,2019年9月6日星期五,北京交通大學計算機學院,銀行家算法應用舉例之一F(待續(xù)),系統(tǒng)資源總量 AvailableA,B,C = 10, 5, 7 T0時刻 AvailableA,B,C = 3, 3, 2 安全分配序列,50,2019年9月6日星期五,北京交通大學計算機學院,銀行家算法應用舉例之二A(待續(xù)),T1時刻 AvailableA,B,C = 3, 3, 2=2, 3, 0 進程P1發(fā)出資源請求Request1(1,0,2) Need1(1,2,2) 安全分配序列 ?,3 0 2,0 2 0,51,2019年9月6日星期五,北京交通大學計算機學院,銀行家算法應用舉例之二B(待續(xù)),進程P1發(fā)出資源請求Request1(1,0,2)2, 3, 0 安全分配序列 ?,52,2019年9月6日星期五,北京交通大學計算機學院,銀行家算法應用舉例之二C(待續(xù)),進程P1發(fā)出資源請求Request1(1,0,2)2, 3, 0 安全分配序列 ?,53,2019年9月6日星期五,北京交通大學計算機學院,銀行家算法應用舉例之二D(待續(xù)),進程P1發(fā)出資源請求Request1(1,0,2)2, 3, 0 安全分配序列 ?,54,2019年9月6日星期五,北京交通大學計算機學院,銀行家算法應用舉例之二E(待續(xù)),進程P1發(fā)出資源請求Request1(1,0,2)2, 3, 0 安全分配序列 ?,55,2019年9月6日星期五,北京交通大學計算機學院,銀行家算法應用舉例之二F(待續(xù)),進程P1發(fā)出資源請求Request1(1,0,2)2, 3, 0 安全分配序列,56,2019年9月6日星期五,北京交通大學計算機學院,銀行家算法應用舉例之三(待續(xù)),T2時刻 AvailableA,B,C = 2, 3, 0 進程P4發(fā)出資源請求Request4(3,3,0) Available(2,3,0)，故讓P4等待,57,2019年9月6日星期五,北京交通大學計算機學院,銀行家算法應用舉例之四(續(xù)完),T3時刻 AvailableA,B,C = 2, 3, 0 =2, 1, 0 進程P0發(fā)出資源請求Request0(0,2,0) Need0(7,4,3) 嘗試分配，則系統(tǒng)進入不安全狀態(tài),0 3 0,7 2 3,58,2019年9月6日星期五,北京交通大學計算機學院,銀行家算法,在一個安全狀態(tài)下：存在一個安全序列或者多個安全序列。 如果在計算是否存在安全序列時，如果有兩個（或者多個）進程的最大資源需求都可以滿足，那么任意選擇一個不會導致不同的判定結果。,59,2019年9月6日星期五,北京交通大學計算機學院,3.5 死鎖產生及處理策略,3.5.1 死鎖的基本概念 3.5.2 死鎖產生的原因 3.5.3 死鎖產生的必要條件 3.5.4 處理死鎖的基本方法 3.5.5 死鎖的預防 3.5.6 死鎖的檢測與解除,60,2019年9月6日星期五,北京交通大學計算機學院,資源分配圖RAG,G=(PR, E) 資源請求邊 e = 資源分配邊 e = ,61,2019年9月6日星期五,北京交通大學計算機學院,資源分配圖RAG轉換規(guī)則,申請資源時：之前沒有未決申請；可以一次申請一種資源的多個單位；增加一個或者多個申請邊。 獲取資源時：如果申請的資源空閑，申請邊改為占有邊。 釋放資源時：之前沒有未決申請；可以釋放部分單位；刪除占有邊。,62,2019年9月6日星期五,北京交通大學計算機學院,資源分配圖RAG轉換舉例,p1,p1,p1,Request,Acquisition,Release,63,2019年9月6日星期五,北京交通大學計算機學院,死鎖檢測,死鎖：進程子集合中的所有進程都不能執(zhí)行。 一種思路：檢查RAG是否存在環(huán)來判定是否死鎖？ 如何判定有向圖存在環(huán)？ 該方法正確嗎？,64,2019年9月6日星期五,北京交通大學計算機學院,死鎖定理,系統(tǒng)狀態(tài)S為死鎖狀態(tài)的充要條件是當且僅當該狀態(tài)下的資源