1、第三章 處理機調度與死鎖 主要內容n3.1 處理機調度的層次 n3.2 調度隊列模型和調度準則n3.3 調度算法n3.4 實時調度n3.5 產生死鎖的原因和必要條件 n3.6 預防死鎖的方法 n3.7 死鎖的檢測與解除 3.1 處理機調度的層次n3.1.1 高級調度n3.1.2 低級調度n3.1.3 中級調度3.1.1 高級調度n作業調度、長程調度n功能n基本概念作業、作業步、作業流、作業控制塊（JCB）n作業調度決定接納多少個作業決定接納哪些作業3.1.1 高級調度n思考：分時系統中是否需要高級調度？3.1.2 低級調度n進程調度、短程調度最基本的一種調度，三種類型的OS都必須配置n功能保存

2、處理機的現場信息按某種算法選取進程把處理器分配給進程3.1.2 低級調度n進程調度中的三個基本機制排隊器分派器（分派程序）上下文切換機制3.1.2 低級調度n進程調度方式非搶占方式(Non-preemptive Model)搶占方式(Preemptive Model)3.1.2 低級調度n非搶占方式(Non-preemptive Model)正在執行的進程執行完畢， 或因發生某事件而不能再繼續執行;執行中的進程因提出I/O請求而暫停執行；在進程通信或同步過程中執行了某種原語操作，如P操作(wait操作)、Block原語、Wakeup原語等。優缺點優缺點3.1.2 低級調度n搶占方式(Preem

3、ptive Model)優先權原則短作業（進程）優先原則時間片原則3.1.3 中級調度n中程調度主要目的是為了提高內存利用率和系統吞吐量n基本思想主要內容n3.1 處理機調度的層次 n3.2 調度隊列模型和調度準則n3.3 調度算法n3.4 實時調度n3.5 產生死鎖的原因和必要條件 n3.6 預防死鎖的方法 n3.7 死鎖的檢測與解除 3.2 調度隊列模型和調度準則n3.2.1 調度隊列模型n3.2.2 選擇調度方式和調度算法的若干準則3.2.1 調度隊列模型n僅有進程調度的調度隊列模型n具有高級和低級調度的調度隊列模型n同時具有三級調度的調度隊列模型 3.2.1 調度隊列模型n僅有進程調度

4、的調度隊列模型就 緒隊 列阻 塞隊列進程調度CPU進程完成等待事件交互用戶事件出現時間片完3.2.1 調度隊列模型n具有高級和低級調度的調度隊列模型就 緒隊列進程調度CPU進程完成等待事件1作業調度事件1出現時間片完等待事件2事件2出現等待事件n事件n出現后備 隊列1.就緒隊列的形式2.設置多個阻塞隊列3.2.1 調度隊列模型n同時具有三級調度的調度隊列模型就緒隊列進程調度CPU就緒，掛起隊列中級調度阻塞，掛起隊列阻塞隊列等待事件進程完成時間片完作業調度交互型作業后備隊列批量作業掛起事件出現事件出現3.2.2 選擇調度方式和調度算法的若干準則n面向用戶的準則周轉時間短響應時間快截止時間的保證優

5、先權準則n面向系統的準則系統吞吐量高處理機利用率高各類資源的平衡利用3.2.2 選擇調度方式和調度算法的若干準則n周轉時間短定義，組成部分平均周轉時間作業的周轉時間T與系統為它提供服務的時間TS之比，即W=T/TS，稱為帶權周轉時間，平均帶權周轉時間可表示為:iiiTnT11niSiiTTnW113.2.2 選擇調度方式和調度算法的若干準則n響應時間快分時系統從用戶通過鍵盤提交一個請求開始，直至系統首次產生響應為止的時間，或者說，直到屏幕上顯示出結果為止的一段時間n截止時間的保證：實時系統n優先權準則3.2.2 選擇調度方式和調度算法的若干準則n面向系統的準則面向系統的準則系統吞吐量高。n單位

6、時間內系統所完成的作業數處理機利用率好。 各類資源的平衡利用。主要內容n3.1 處理機調度的層次 n3.2 調度隊列模型和調度準則n3.3 調度算法n3.4 實時調度n3.5 產生死鎖的原因和必要條件 n3.6 預防死鎖的方法 n3.7 死鎖的檢測與解除 3.3 調度算法n3.3.1 先來先服務和短作業（進程）優先調度算法n3.3.2高優先權優先調度算法n3.3.3 基于時間片的輪轉調度算法3.3.1 先來先服務和短作業（進程）優先調度算法n先來先服務調度算法進程名到達時間服務時間開始執行時間完成時間周轉時間帶權周轉時間A01B1100C21D310001111101100 110110210

7、0 1001022021991.99有利于長作業，不利于短作業最短作業優先調度(Shortest-Job-First, SJR)n將每個進程與其下一個CPU區間段相關聯。當CPU為可用時，它會賦給具有最短后續CPU區間的進程。如果兩個進程具有同樣長度的CPU區間，那么可以使用FCFS調度來處理。n兩種方式非搶占式搶占式nSJF是最佳的：對于給定的一組進程，SJF算法的平均等待時間最小。非搶占式SJF的實例搶占式SJF的實例確定下一CPU區間的長度n只能估計CPU區間的長度，無法精確計算n下一CPU區間的長度通常可預測為以前CPU區間的測量長度的指數平均下一個CPU區間長度的預測指數平均計算的實

8、例3.3.2 高優先權優先調度算法n優先權調度算法的類型非搶占式優先權算法搶占式優先權調度算法n優先權類型靜態優先權n進程類型n進程對資源的需求n用戶要求n缺點及解決辦法饑餓與老化動態優先權n高響應比優先調度算法要求服務時間等待時間要求服務時間要求服務時間等待時間優先權1要求服務時間響應時間要求服務時間要求服務時間等待時間優先權等待時間相同時？要求服務時間相同時？等待時間變長時？3.3.3 基于時間片的輪轉調度算法n基本原理n時間片大小的確定n圖3-5、3-6Example of RR with Time Q = 20Process Burst TimeP153 P2 17 P368 P4 2

9、4nThe Gantt chart is: P1P2P3P4P1P3P4P1P3P302037577797117121 134154 162n多級反饋隊列調度算法性能：終端型作業用戶。 短批處理作業用戶。 長批處理作業用戶。作業nP114:167n對于下面一組進程，假設在0時刻以ABCDE的順序到達進程服務時間優先級A103B11C23D14E521、畫圖演示進程使用FCFS、SJF、非搶占優先級、時間片輪轉法(RR=1)算法調度時進程的執行過程2、每個進程在每種調度算法下的周轉時間和平均周轉時間？3、每個進程在每種調度算法下的等待時間？主要內容n3.1 處理機調度的層次 n3.2 調度隊列模

10、型和調度準則n3.3 調度算法n3.4 實時調度n3.5 產生死鎖的原因和必要條件 n3.6 預防死鎖的方法 n3.7 死鎖的檢測與解除 3.4 實時調度n3.4.1 實現實時調度的基本條件n3.4.2 實時調度算法的分類n3.4.3 常用的幾種實時調度算法3.4.1 實現實時調度的基本條件n提供必要的信息n系統處理能力強n采用搶占式調度機制n具有快速切換機制n必要的信息就緒時間開始截止時間和完成截止時間處理時間資源要求優先級n系統處理能力強若處理機的處理能力不夠強，則有可能因處理機忙不過來而使某些實時任務不能得到及時處理， 從而導致發生難以預料的后果。假定系統中有m個周期性的硬實時任務，它們

11、的處理時間可表示為Ci，周期時間表示為Pi，則在單處理機情況下，必須滿足下面的限制條件：miiiPC113.4.2 實時調度算法的分類n非搶占式調度算法一些小實時系統或要求不太嚴格的實時系統非搶占式輪轉調度算法非搶占式優先調度算法n搶占式調度算法基于時鐘終端的搶占式優先權調度算法立即搶占的優先權調度算法(a) 非搶占輪轉調度當前進程實時進程實時進程請求調度實時進程槍占當前進程，并立即執行(d) 立即搶占的優先權調度調度時間進程 1進程 2實時進程要求調度進程 n實時進程調度實時進程運行(b) 非搶占優先權調度當前進程實時進程實時進程請求調度當前進程運行完成調度時間當前進程實時進程請求調度時鐘中

12、斷到來時調度時間(c) 基于時鐘中斷搶占的優先權搶占調度調度時間實時進程圖 3-6 實時進程調度 3.4.3 常用的幾種實時調度算法n最早截止時間優先算法EDF (Earliest Deadline First)非搶占式調度方式用于非周期實時任務搶占式調度方式用于周期實時任務n最低松弛度優先算法LLF (Least Laxity First)問題描述n有兩個周期性任務，任務A的周期時間為20ms，每個周期處理時間為10ms；任務B的周期時間為50ms，每個周期處理時間為25ms。兩個任務的到達時間，最后期限和執行時間如下圖：B2最后期限A1A3A5A4A2B1B2A1最后期限A2最后期限A3最

13、后期限A4最后期限A5最后期限B1最后期限0 10 20 30 40 50 60 70 80 90 100 時間t/ms1. 非搶占式調度方式用于非周期實時任務圖 3-7 EDF算法用于非搶占調度方式 1342開始截止時間任務執行任務到達12341342t搶占式調度方式用于周期實時任務2. 最低松弛度優先即最低松弛度優先即LLF(Least Laxity First)算法算法 A1A2A3A4A5A6A7A820406080100120140160B1B2B3t0松弛度松弛度=必須完成時間必須完成時間-其本身的運行時間其本身的運行時間-當前時間當前時間過橋的實例主要內容n3.1 處理機調度的層

14、次 n3.2 調度隊列模型和調度準則n3.3 調度算法n3.4 實時調度n3.5 產生死鎖的原因和必要條件 n3.6 預防死鎖的方法 n3.7 死鎖的檢測與解除 n死鎖死鎖指多個進程在運行過程中因爭奪資源而造成的指多個進程在運行過程中因爭奪資源而造成的一種僵局。一種僵局。是是OS的一種隨機故障，是指兩個或兩個以上的一種隨機故障，是指兩個或兩個以上的進程都無限制的地等待永遠不會出現的事件的進程都無限制的地等待永遠不會出現的事件而發生的狀態。而發生的狀態。3.5.1 產生死鎖的原因產生死鎖的原因 (1) 競爭資源。競爭資源。 (2) 進程間推進順序非法。進程間推進順序非法。 1. 競爭資源引起進程

15、死鎖競爭資源引起進程死鎖 1) 可剝奪和非剝奪性資源：內存VS打印機 2) 競爭非剝奪性資源 ：3) 競爭臨時性資源 ：消息、緩沖區等圖 3-12 I/O設備共享時的死鎖情況 R1R2P1P2圖 3-13 進程之間通信時的死鎖 S2P1S3P3S1P22. 進程推進順序不當引起死鎖進程推進順序不當引起死鎖 1) 進程推進順序合法 圖 3-14 進程推進順序對死鎖的影響 P2Rel(R1)P2Rel(R2)P2Req(R1)P2Req(R2)P1Req(R1)P1Req(R2)P1Rel(R1)P1Rel(R2)D3.5.2 產生死鎖的必要條件產生死鎖的必要條件 (1) 互斥條件 (2) 請求和

16、保持條件 (3) 不剝奪條件 (4) 環路等待條件 3.5.3 處理死鎖的基本方法處理死鎖的基本方法(1) 預防死鎖。 (2) 避免死鎖。 (3) 檢測死鎖。 (4) 解除死鎖。 主要內容n3.1 處理機調度的層次 n3.2 調度隊列模型和調度準則n3.3 調度算法n3.4 實時調度n3.5 產生死鎖的原因和必要條件 n3.6 預防死鎖的方法 n3.7 死鎖的檢測與解除 3.6 預防死鎖的方法n3.6.1 預防死鎖n3.6.2 系統安全狀態n3.6.3 銀行家算法3.6.1 預防死鎖n產生死鎖的必要條件？n預防死鎖摒棄“請求和保持”條件 摒棄“不剝奪”條件 摒棄“環路等待”條件3.6.2 系統

17、安全狀態n安全狀態系統能按某種進程順序(P1, P2, ，Pn)來為每個進程Pi分配其所需資源，直至滿足每個進程對資源的最大需求，使每個進程都可順利地完成，并且稱P1, P2, , Pn序列為安全序列如果系統無法找到這樣一個安全序列，則稱系統處于不安全狀態。安全、不安全、死鎖狀態空間避免死鎖的實質在于：系統在資源分配時，如何使系統不進入安全狀態安全狀態之例安全狀態之例n系統當前是否為安全狀態？n若P3又請求1臺磁帶機，并且分配給它，系統是否仍然處于安全狀態？進 程 最 大 需 求 已 分 配 可 用 P1P2P310495223系統可能會由安全狀態系統可能會由安全狀態進入不安全狀態進入不安全狀

18、態3.6.3 銀行家算法避免避免死鎖n由于該算法能用于銀行系統現金貸款的發放而得名操作系統看作是銀行家，操作系統管理的資源相當于銀行家管理的資金，進程向操作系統請求分配資源相當于用戶向銀行家貸款。 n當一個顧客對資金的最大需求量不超過銀行家現有的資金時就可接納該顧客; n顧客可以分期貸款,但貸款的總數不能超過最大需求量; n當銀行家現有的資金不能滿足顧客尚需的貸款數額時,對顧客的貸款可推遲支付,但總能使顧客在有限的時間里得到貸款; n當顧客得到所需的全部資金后,一定能在有限的時間里歸還所有的資金. 數據結構n可利用資源向量Available。這是一個含有m個元素的數組，其中的每一個元素代表一類

19、可利用的資源數目，其初始值是系統中所配置的該類全部可用資源的數目，其數值隨該類資源的分配和回收而動態地改變。如果Availablej=K，則表示系統中現有Rj類資源K個。n最大需求矩陣Max。這是一個nm的矩陣，它定義了系統中n個進程中的每一個進程對m類資源的最大需求。如果Maxi,j=K，則表示進程i需要Rj類資源的最大數目為K。n分配矩陣Allocation。這也是一個nm的矩陣，它定義了系統中每一類資源當前已分配給每一進程的資源數。如果Allocationi,j=K，則表示進程i當前已分得Rj類資源的數目為K。n需求矩陣Need。這也是一個nm的矩陣，用以表示每一個進程尚需的各類資源數。

20、如果Needi,j=K，則表示進程i還需要Rj類資源K個，方能完成其任務Needi,j=Maxi,j-Allocationi,j 銀行家算法銀行家算法n設Requesti是進程Pi的請求向量，如果Requestij=K，表示進程Pi需要K個Rj類型的資源。如果RequestijNeedi,j，便轉向步驟2；否則認為出錯，因為它所需要的資源數已超過它所宣布的最大值。如果RequestijAvailablej，便轉向步驟(3)；否則， 表示尚無足夠資源，Pi須等待。 系統試探著把資源分配給進程Pi，并修改下面數據結構：n Availablej =Availablej-Requestij;n All

21、ocationi,j =Allocationi,j+Requestij;n Needi,j =Needi,j-Requestij;系統執行安全性算法，檢查此次資源分配后，系統是否處于安全狀態。若安全，才正式將資源分配給進程Pi，以完成本次分配；否則， 將本次的試探分配作廢，恢復原來的資源分配狀態，讓進程Pi等待。 安全性算法安全性算法 (1) 設置兩個向量： 工作向量Work: 它表示系統可提供給進程繼續運行所需的各類資源數目，它含有m個元素，在執行安全算法開始時，Work =Available; Finish: 它表示系統是否有足夠的資源分配給進程，使之運行完成。開始時先做Finishi =

22、false; 當有足夠資源分配給進程時， 再令Finishi =true。 (2) 從進程集合中找到一個能滿足下述條件的進程： Finishi=false; Needi,jWorkj； 若找到， 執行步驟(3)， 否則，執行步驟(4)。 (3) 當進程Pi獲得資源后，可順利執行，直至完成，并釋放出分配給它的資源，故應執行： Workj =Worki+Allocationi,j; Finishi =true; go to step 2; (4) 如果所有進程的Finishi=true都滿足， 則表示系統處于安全狀態；否則，系統處于不安全狀態。 實例實例nT0時刻的安全性？nP1發出請求向量Req

23、uest1(1，0，2)，是否可以滿足？nP4發出請求向量Request4(3，3，0) ，是否可以滿足？nP0發出請求向量Requst0(0，2，0) ，是否可以滿足？作業n18、19、22主要內容n3.1 處理機調度的層次 n3.2 調度隊列模型和調度準則n3.3 調度算法n3.4 實時調度n3.5 產生死鎖的原因和必要條件 n3.6 預防死鎖的方法 n3.7 死鎖的檢測與解除 3.7 死鎖的檢測與解除死鎖的檢測與解除n3.7.1 死鎖的檢測死鎖的檢測n3.7.2 死鎖的解除死鎖的解除3.7.1 死鎖的檢測死鎖的檢測n1.資源分配圖資源分配圖(Resource Allocation Graph