1、1第四章、處理機調度第四章、處理機調度4.1分級調度分級調度4.2作業調度作業調度4.3進程調度進程調度4.4調度算法調度算法4.6實時系統調度算法實時系統調度算法24.1、分級調度、分級調度一、調度的層次：一、調度的層次：1、作業調度（宏觀、高級）、作業調度（宏觀、高級）2、交換調度（中級）、交換調度（中級）3、進程調度（微觀、低級）、進程調度（微觀、低級）4、線程調度、線程調度3二、狀態轉換圖：二、狀態轉換圖：44.2、作業調度、作業調度一、作業狀態：一、作業狀態：1、收容（后備）狀態：、收容（后備）狀態：輸入外存、建立輸入外存、建立JCB、進入后備隊列、進入后備隊列：把：把JCB用表格或

2、指針組成的隊列，按優先級大小或用表格或指針組成的隊列，按優先級大小或作業到達系統的時間順序排列。作業到達系統的時間順序排列。2、執行狀態：、執行狀態：獲得所需資源、調入內存、創建進程獲得所需資源、調入內存、創建進程3、完成狀態：、完成狀態：正常正常/異常結束、結果輸出、回收資源、釋放異常結束、結果輸出、回收資源、釋放JCB5二、作業調度二、作業調度按一定調度規則，從后備作業隊列中選擇一個或多個作業進入按一定調度規則，從后備作業隊列中選擇一個或多個作業進入“執行狀態執行狀態”；作業執行完畢后，回收資源。；作業執行完畢后，回收資源。1、考慮因素：、考慮因素：1）系統目標：）系統目標：2）作業優先級

3、：）作業優先級：3）資源均衡使用：）資源均衡使用：4）公平合理：）公平合理：5）指標衡量：）指標衡量： （平均）周轉時間、（平均）帶權周轉時間（平均）周轉時間、（平均）帶權周轉時間2、調度算法：、調度算法：1）先來先服務調度算法（）先來先服務調度算法（FCFS：First Come First Serve）2）最短作業優先算法（）最短作業優先算法（SJF：Shortest Job First)3）響應比高者優先算法（）響應比高者優先算法（HRN：Highest Response_ratio Next)4）優先級高者優先算法）優先級高者優先算法63、調度步驟、調度步驟調度算法選擇一個作業調度算法

4、選擇一個作業是否獲得所需資源（是否獲得所需資源（CPU除外）除外）分配要求資源分配要求資源為其創建進程為其創建進程進程調度（獲得進程調度（獲得CPU）回收占用資源回收占用資源計算費用計算費用撤消進程及撤消進程及JCB調度下一個作業調度下一個作業74.3、進程調度、進程調度一、進程狀態及其轉換一、進程狀態及其轉換1、就緒狀態、就緒狀態ready：已獲得除：已獲得除CPU之外的所有必要資源。之外的所有必要資源。2、執行狀態、執行狀態excute：占有：占有CPU正在執行。正在執行。3、等待（阻塞）狀態、等待（阻塞）狀態blocked：因某事件（請求：因某事件（請求I/O）而暫停執行，處）而暫停執行

5、，處于等待執行的狀態。于等待執行的狀態。8二、進程調度的功能二、進程調度的功能1、記錄系統中所有進程的狀態：、記錄系統中所有進程的狀態：PCB2、在就緒隊列中選擇占有處理機的進程：、在就緒隊列中選擇占有處理機的進程：調度算法調度算法3、進行新老進程的、進行新老進程的上下文切換上下文切換：1）是否允許進行上下文切換？）是否允許進行上下文切換？2）保存當前進程上下文；）保存當前進程上下文；3）在就緒隊列中選擇占有處理機的進程；）在就緒隊列中選擇占有處理機的進程；4）裝配所選進程的上下文。）裝配所選進程的上下文。9進程控制塊進程控制塊PCB基本內容基本內容現行狀態現行狀態進程標識符進程標識符現場保護

6、區現場保護區程序與數據地址程序與數據地址互斥和同步機構互斥和同步機構進程通信機構進程通信機構進程優先數進程優先數資源清單資源清單家族關系家族關系鏈接字鏈接字進程上下文進程上下文 進程執行活動過程的靜態描述，是進程執行所依賴的環境。進程執行活動過程的靜態描述，是進程執行所依賴的環境。 當系統調度新進程占有處理機時，新老進程的上下文發生轉換。當系統調度新進程占有處理機時，新老進程的上下文發生轉換。1111三、進程調度的方式三、進程調度的方式1、非剝奪方式：、非剝奪方式：不允許強行剝奪當前執行進程的不允許強行剝奪當前執行進程的CPU，直至其運，直至其運行完畢或時間片用完或因某時間而阻塞。行完畢或時間

7、片用完或因某時間而阻塞。優點：設計簡單，系統開銷小。優點：設計簡單，系統開銷小。缺點：系統性能惡化；緊急任務不能及時處理；不利缺點：系統性能惡化；緊急任務不能及時處理；不利于短作業。于短作業。2、可剝奪方式：、可剝奪方式：可以根據某原則剝奪正在運行程序的可以根據某原則剝奪正在運行程序的CPU，分配，分配給另進程。給另進程。剝奪原則剝奪原則: 1）優先權原則）優先權原則2）短進程優先原則）短進程優先原則3）時間片原則）時間片原則12四、進程調度的時機四、進程調度的時機1、正在執行的進程執行完畢；、正在執行的進程執行完畢；2、進程調用阻塞原語將自己阻塞；、進程調用阻塞原語將自己阻塞；3、調用、調用

8、P原語而阻塞，調用原語而阻塞，調用V原語喚醒一等待進程；原語喚醒一等待進程；4、執行進程提出、執行進程提出I/O請求而阻塞；請求而阻塞；5、分時系統中時間片用完；、分時系統中時間片用完；6、執行系統調用后有系統程序返回用戶程序，調度新進程；、執行系統調用后有系統程序返回用戶程序，調度新進程；7、就緒隊列中某進程優先級高于當前執行進程優先級。、就緒隊列中某進程優先級高于當前執行進程優先級。13UNIX SystemV進程調度的時機進程調度的時機1、當前進程自己調用、當前進程自己調用sleep,wait進入睡眠狀態；進入睡眠狀態；2、當前進程從系統態返回用戶態時，優先級低、當前進程從系統態返回用戶

9、態時，優先級低于其他就緒進程，或調度標志被置位；于其他就緒進程，或調度標志被置位；3、當前進程時間片用完，且優先級低于其他就、當前進程時間片用完，且優先級低于其他就緒進程；緒進程；4、當前進程調用、當前進程調用exit自我終止。自我終止。14五、進程調度的實現五、進程調度的實現 確定引起調度的因素確定引起調度的因素 調度算法的選擇設計調度算法的選擇設計 就就 緒緒 隊隊 列列 的的 組組 織織決定哪個進程獲得決定哪個進程獲得CPU分派程序完成分派程序完成CPU分配分配15六、線程調度六、線程調度 線程控制塊線程控制塊TCB的內容的內容1、線程的狀態；、線程的狀態；2、CPU現場信息：現場信息：

10、PC、PSW、通用寄存器、堆棧指針、通用寄存器、堆棧指針164.4、調度算法、調度算法1、先來先服務調度算法、先來先服務調度算法（FCFS：First Come First Serve）2、最短作業（、最短作業（CPU運行期）優先算法運行期）優先算法（SJF：Shortest Job First)3、響應比高者優先算法、響應比高者優先算法（HRN：Highest Response_ratio Next)4、優先級高者優先算法、優先級高者優先算法5、輪轉法、輪轉法（round robin）6、多級反饋輪轉法（、多級反饋輪轉法（ round robin with multiple feedback

11、）作業調度：作業調度：1、2、3、4進程調度：進程調度：1、2、4、5、617 1、先來先服務調度算法先來先服務調度算法原則：原則：按照作業到達系統或進程進入就緒隊列的先后順序來按照作業到達系統或進程進入就緒隊列的先后順序來選擇。選擇。缺點：缺點：提高了平均的作業周轉時間，不利于短作業。提高了平均的作業周轉時間，不利于短作業。例：有四個作業幾乎同時到達，進入系統的先后順序及運行時間依次是：例：有四個作業幾乎同時到達，進入系統的先后順序及運行時間依次是：1# 2分鐘、分鐘、2 # 60分鐘、分鐘、3# 4分鐘、分鐘、4# 10 分鐘分鐘按此順序調度運行后每個作業的周轉時間和運行時間之比分別是：按

12、此順序調度運行后每個作業的周轉時間和運行時間之比分別是：1#：2/22#：62/603#：66/44#：76/10平均周轉時間平均周轉時間=（2+62+66+76）/4 = 51.5應用：應用：不用于分時和實時系統，常結合其他調度策略使用，不用于分時和實時系統，常結合其他調度策略使用，而不作為主要的調度策略，而不作為主要的調度策略，182、最短作業（、最短作業（CPU運行期）優先算法運行期）優先算法原則：原則：從作業后備隊列（進程就緒隊列）中挑選所需運行從作業后備隊列（進程就緒隊列）中挑選所需運行時間（下一個時間（下一個CPU運行期）最短的作業進入內存運行。運行期）最短的作業進入內存運行。缺點

13、：缺點：利于短作業（進程），不利于長作業（進程），且利于短作業（進程），不利于長作業（進程），且作業（進程）運行時間要能估計。作業（進程）運行時間要能估計。前例：前例：1# 2分鐘、分鐘、2 # 60分鐘、分鐘、3# 4分鐘、分鐘、4# 10 分鐘分鐘按最短作業優先順序調度運行后，周轉時間和運行時間之比分別是：按最短作業優先順序調度運行后，周轉時間和運行時間之比分別是：1#：2/23#：6/4 4#：18/102#：78/60平均周轉時間平均周轉時間=（2+6+18+78）/4 = 26應用：應用：不適用于分時系統。不適用于分時系統。193、響應比高者優先算法、響應比高者優先算法響應比響應比R

14、=（作業等待時間（作業等待時間W+作業要求運行時間作業要求運行時間T）/ T = 1 + W / T原則：原則：響應比高者得到優先調度。響應比高者得到優先調度。特點：特點：考慮了來到先后和運行時間長短，折衷，開考慮了來到先后和運行時間長短，折衷，開銷大。銷大。204、優先級高者優先算法、優先級高者優先算法原則：原則：按照進程的優先級大小來調度，高優先級進按照進程的優先級大小來調度，高優先級進程得到優先處理。程得到優先處理。關鍵：關鍵：以什么原則確定進程的優先級？以什么原則確定進程的優先級？1）靜態優先級：）靜態優先級：進程創建時確定，運行期間不變。進程創建時確定，運行期間不變。確定依據：確定依

15、據：進程類型、進程對資源的要求、用戶要求的優先級進程類型、進程對資源的要求、用戶要求的優先級特點：特點：簡單易行，但不精確，各進程特性可能動態變化。簡單易行，但不精確，各進程特性可能動態變化。212）動態優先級）動態優先級：進程的優先級可以隨時間而變化。進程的優先級可以隨時間而變化。變化依據：變化依據：進程占有進程占有CPU時間的長短時間的長短就緒進程等待就緒進程等待CPU的長短的長短優點：優點：調度性能好：優先級相同的進程先進的優先，優先級低調度性能好：優先級相同的進程先進的優先，優先級低的經一段時間的等待而運行，防止大進程壟斷運行。的經一段時間的等待而運行，防止大進程壟斷運行。225、輪轉

16、法、輪轉法（round robin）原理：原理：把就緒進程按先進先出原則排成隊列，隊首進程執把就緒進程按先進先出原則排成隊列，隊首進程執行一個時間片后釋放行一個時間片后釋放CPU ，排到就緒隊列末尾，把，排到就緒隊列末尾，把CPU分給新的隊首進程，以此類推。分給新的隊首進程，以此類推。23優點：優點：各進程可以在一段時間內及時得到響應。各進程可以在一段時間內及時得到響應。關鍵：關鍵：時間片長度的選取時間片長度的選取: q = R / Nmax缺點：缺點：所有進程一視同仁，不區分急緩、長短。所有進程一視同仁，不區分急緩、長短。改進：改進：1）可變時間片輪轉法）可變時間片輪轉法2）多級反饋輪轉法）

17、多級反饋輪轉法246、多級反饋輪轉法、多級反饋輪轉法原理：原理：設多個就緒隊列，設多個就緒隊列，賦予不同的優先級，賦予不同的優先級，先對高優先級隊列中先對高優先級隊列中的進程輪轉，隊列空的進程輪轉，隊列空時再對低優先級隊列時再對低優先級隊列輪轉；若在某級隊列輪轉；若在某級隊列中輪轉時，有新進程中輪轉時，有新進程進入更高優先級的隊進入更高優先級的隊列，將重新調度，把列，將重新調度，把CPU分給新進程。分給新進程。25注意：注意：1、隊列時間片隨優先級的由高到低而由小到大；、隊列時間片隨優先級的由高到低而由小到大；2、不同類型作業的優先級設置：、不同類型作業的優先級設置： 交互型作業交互型作業 優

18、先級高優先級高 批處理作業批處理作業 優先級低優先級低 提高系統吞吐量，降低平均等待時間提高系統吞吐量，降低平均等待時間 提高提高I/O設備利用率，及時響應交互用戶設備利用率，及時響應交互用戶3、各隊列采取時間片輪轉法，最低優先級隊列可以、各隊列采取時間片輪轉法，最低優先級隊列可以采取其他調度法；采取其他調度法；優點：優點：較好滿足各種用戶的要求。較好滿足各種用戶的要求。26例：例：在一個批處理系統中，有一個作業序列，其到達時在一個批處理系統中，有一個作業序列，其到達時間及估計運行時間表如下。系統間及估計運行時間表如下。系統只允許有兩個作業進程只允許有兩個作業進程。系統采用系統采用最短作業優先

19、的作業調度最短作業優先的作業調度算法，算法，進程調度采用進程調度采用最高優先級優先的搶占式最高優先級優先的搶占式調度算法（優先數越小，優先調度算法（優先數越小，優先級越高）。級越高）。1）列出各作業的執行時間段；）列出各作業的執行時間段；2）計算這批作業的平均周轉時間。）計算這批作業的平均周轉時間。作業作業到達時刻到達時刻估計運行時間估計運行時間優先數優先數110：00405210：20303310：30504410：5020627分析分析兩個層次調度（競爭）兩個層次調度（競爭）1、作業調度作業調度進入內存的競爭進入內存的競爭策略：策略：最短作業優先最短作業優先調度調度2、進程調度進程調度擁有

20、擁有CPU的競爭的競爭策略：策略：最高優先級優先最高優先級優先搶占式調度搶占式調度28過程分析過程分析10:00 J1運行運行10:20 J1余余20分，分，J2到，需到，需30分，分， J2 優先級高，優先級高，J2運行運行，J1 就緒等待就緒等待10:30 J3到，需到，需50分，分，J1余余20分，分， J2余余20分繼續運行分繼續運行10:50 J2結束結束，J4到，需到，需20分，分，J4進入，進入， J4優先級低于優先級低于J1，J1重新運行重新運行11:10 J1結束結束，J3進入，優先級高于進入，優先級高于J4，J3運行運行12:00 J3結束結束, J4運行運行12:20 J

21、4結束結束29平均周轉時間：平均周轉時間：280 / 4 = 70作業作業到達時刻到達時刻結束時刻結束時刻周轉時間周轉時間J110:0011:1070J210:2010:5030J310:3012:0090J410:5012:2090304.6 、實時系統調度算法、實時系統調度算法一、實時系統特點：一、實時系統特點： 1、有限等待時間、有限等待時間2、有限響應時間、有限響應時間3、用戶控制、用戶控制4、可靠性高、可靠性高5、系統出錯處理能力強、系統出錯處理能力強31二、實時系統設計要求：二、實時系統設計要求：1、很快的進程或線程切換速度；、很快的進程或線程切換速度；2、快速的外部中斷響應能力；、快速的外部中斷響應能力；3、基于優先級的隨時搶先式調度策略：、基于優先級的隨時搶先式調度策略：1）優先級）優先級+時間片輪轉調度策略時間片輪轉調度策略2）基于優先級的非搶先式調度策略）基于優先級的非搶先式調度策略3）基于優先級的固定點搶先式調度策略）基于優先級的固定點搶先式調度策略4）基于優先級的隨時搶先式調度策略）基于優先級的隨時搶先式調度策略主要主要32三、實時調度算法三、實時調度算法1、靜態表格驅動類、靜態表格驅動類