1、 實用操作系統教程實用操作系統教程2本章內容本章內容3.1 3.1 三級調度體系三級調度體系3.2 3.2 進程調度目標和調度方式進程調度目標和調度方式3.3 3.3 調度算法的評價準則調度算法的評價準則3.4 3.4 典型進程調度算法典型進程調度算法3.5 3.5 線程調度算法線程調度算法3.6 3.6 實時調度算法實時調度算法3本章學習目標本章學習目標v理解三級調度的含義和比較；理解三級調度的含義和比較；v理解搶占式調度、非搶占式調度的區別與聯系；理解搶占式調度、非搶占式調度的區別與聯系；v了解調度算法的評價準則；了解調度算法的評價準則；v掌握常見調度算法及其比較；掌握常見調度算法及其比較

2、；v理解等待時間、周轉時間、加權周轉時間的含義，理解等待時間、周轉時間、加權周轉時間的含義，并會計算；并會計算；v了解實時調度和多處理機調度的特點了解實時調度和多處理機調度的特點43.1 3.1 三級調度體系三級調度體系3.1.1 高級調度高級調度1高級調度（高級調度（high-level scheduling）又稱作業調度）又稱作業調度或長程調度，它是根據某種算法將外存上處于后或長程調度，它是根據某種算法將外存上處于后備作業隊列中的若干作業調入內存，為作業分配備作業隊列中的若干作業調入內存，為作業分配所需資源并建立相應進程。所需資源并建立相應進程。2作業通常分成若干個既相對獨立又互相關聯的加

3、作業通常分成若干個既相對獨立又互相關聯的加工步驟，每個步驟稱為一個作業步。每個作業步工步驟，每個步驟稱為一個作業步。每個作業步可能對應一個或多個進程。可能對應一個或多個進程。53.1.1 3.1.1 高級調度高級調度v作業一般要經歷作業一般要經歷“提交提交”、“后備后備”、“執行執行”和和“完成完成”四個狀態。四個狀態。63.1.1 3.1.1 高級調度高級調度v高級調度決定允許哪些作業可進入內存，參與競高級調度決定允許哪些作業可進入內存，參與競爭爭CPUCPU和系統其他資源，將一個或一批作業從后和系統其他資源，將一個或一批作業從后備狀態變為運行狀態。備狀態變為運行狀態。73.1.1 3.1.

4、1 高級調度高級調度v在多道批處理系統中，為了管理和調度作業，系統在多道批處理系統中，為了管理和調度作業，系統為每個作業設置了一個作業控制塊為每個作業設置了一個作業控制塊(JCB)(JCB)，它記錄作，它記錄作業的相關信息。業的相關信息。83.1.1 3.1.1 高級調度高級調度9重點回顧重點回顧v 管程由四部分組成：管程由四部分組成：管程的名稱管程的名稱局部于管程內部的共享數據結構說明局部于管程內部的共享數據結構說明對該數據結構進行操作的一組過程對該數據結構進行操作的一組過程對管程內部共享數據設置初始值的語句對管程內部共享數據設置初始值的語句v 高級進程通信機制可分為：高級進程通信機制可分為

5、：共享存儲器系統共享存儲器系統 消息傳遞系統消息傳遞系統 管道通信管道通信10重點回顧重點回顧v 線程線程在引入線程之后，進程作為資源分配的基本在引入線程之后，進程作為資源分配的基本單位，而線程作為獨立調度和運行的基本單單位，而線程作為獨立調度和運行的基本單位位v 高級調度（高級調度（high-level schedulinghigh-level scheduling）又稱作業調度或長程調度，它是根據某種算又稱作業調度或長程調度，它是根據某種算法將外存上處于后備作業隊列中的若干作業法將外存上處于后備作業隊列中的若干作業調入內存，為作業分配所需資源并建立相應調入內存，為作業分配所需資源并建立相應

6、進程。進程。113.1.2 3.1.2 中級調度中級調度v中級調度中級調度(middle-level scheduling)(middle-level scheduling)又稱內存調度，又稱內存調度，它是進程在內存和外存之間的對換。它是進程在內存和外存之間的對換。v具有中級調度的系統中，進程除了具有三個基本具有中級調度的系統中，進程除了具有三個基本狀態外，還具有靜止就緒和靜止阻塞兩個狀態。狀態外，還具有靜止就緒和靜止阻塞兩個狀態。123.1.3 3.1.3 低級調度低級調度v 低級調度低級調度（low-level schedulinglow-level scheduling）又稱進程調度、短

7、程調度，）又稱進程調度、短程調度，它決定哪個就緒態進程獲得處理機，即選擇某個進程從就它決定哪個就緒態進程獲得處理機，即選擇某個進程從就緒態變為執行態。執行低級調度的原因多是處于執行態的緒態變為執行態。執行低級調度的原因多是處于執行態的進程由于某種原因放棄或被剝奪處理機。進程由于某種原因放棄或被剝奪處理機。v 低級調度是三級調度中的低級調度是三級調度中的最終調度最終調度，又稱底層調度。在這，又稱底層調度。在這級調度中真正實現了處理機的分配，級調度中真正實現了處理機的分配，它是系統不可缺少的它是系統不可缺少的最基本調度最基本調度。133.1.3 3.1.3 低級調度低級調度v進程調度的功能主要包括

8、以下兩部分：進程調度的功能主要包括以下兩部分： 選擇就緒進程選擇就緒進程 進程切換進程切換143.1.4 3.1.4 三級調度關系三級調度關系v分級調度系統中，各級調度分別在不同的調度時分級調度系統中，各級調度分別在不同的調度時機進行。對于一個用戶作業來說，通常要經歷高機進行。對于一個用戶作業來說，通常要經歷高級調度、中級調度和低級調度才能完成整個作業級調度、中級調度和低級調度才能完成整個作業程序的運行。程序的運行。153.1.4 3.1.4 三級調度關系三級調度關系163.2 3.2 進程進程調度目標和調度方式調度目標和調度方式3.2.1 3.2.1 進程調度目標進程調度目標（1 1）公平性

9、）公平性（2 2）高效率）高效率（3 3）低響應時間）低響應時間（4 4）高吞吐量）高吞吐量（5 5）特殊應用要求）特殊應用要求173.2.1 3.2.1 進程調度目標進程調度目標（1 1）多道批處理操作系統）多道批處理操作系統 多道批處理系統強調高效利用系統資源和高作業吞吐多道批處理系統強調高效利用系統資源和高作業吞吐量。進程提交給處理機后就不再與外部進行交互，系統量。進程提交給處理機后就不再與外部進行交互，系統按照調度策略安排它們運行，直到諸進程完成為止。按照調度策略安排它們運行，直到諸進程完成為止。（2 2）分時操作系統）分時操作系統 分時系統更關心多個用戶的公平性和及時響應性，它分時系

10、統更關心多個用戶的公平性和及時響應性，它不允許某個進程長時間占用處理機。分時系統多采用時不允許某個進程長時間占用處理機。分時系統多采用時間片輪轉調度算法或在其基礎上改進的其他調度算法。間片輪轉調度算法或在其基礎上改進的其他調度算法。但處理機在各個進程之間頻繁切換會增加系統時空開銷，但處理機在各個進程之間頻繁切換會增加系統時空開銷，延長各個進程在系統中的存在時間。分時系統最關注的延長各個進程在系統中的存在時間。分時系統最關注的是交互性和各進程的均衡性，對進程的執行效率和系統是交互性和各進程的均衡性，對進程的執行效率和系統開銷往往要求并不苛刻。開銷往往要求并不苛刻。183.2.1 3.2.1 進程

11、調度目標進程調度目標（3 3）實時操作系統）實時操作系統 實時操作系統必須保證實時進程的請求得到及時實時操作系統必須保證實時進程的請求得到及時響應，往往不考慮處理機的使用效率。實時系統響應，往往不考慮處理機的使用效率。實時系統采取的調度算法和其他類型系統采取的調度算法采取的調度算法和其他類型系統采取的調度算法相比有很大不同，其調度算法的最大特點是可搶相比有很大不同，其調度算法的最大特點是可搶占性。占性。（4 4）通用操作系統）通用操作系統 通用操作系統中，對進程調度沒有特殊限制和要通用操作系統中，對進程調度沒有特殊限制和要求，選擇進程調度算法時主要追求處理機使用的求，選擇進程調度算法時主要追求

12、處理機使用的公平性以及各類資源使用的均衡性公平性以及各類資源使用的均衡性193.2.2 3.2.2 進程調度方式進程調度方式v進程調度有兩種基本方式：進程調度有兩種基本方式：非搶占方式非搶占方式和和搶占搶占方式方式。（1）非搶占方式（）非搶占方式（Nonpreemptive）v進程一旦獲得處理機執行，其他進程就不能中斷它的執進程一旦獲得處理機執行，其他進程就不能中斷它的執行，即使當前等待進程中出現了優先級更高的請求進程行，即使當前等待進程中出現了優先級更高的請求進程也不允許該進程搶占處理機。直到執行態進程完成或發也不允許該進程搶占處理機。直到執行態進程完成或發生某個事件主動放棄處理機，才能調度

13、其他進程獲得處生某個事件主動放棄處理機，才能調度其他進程獲得處理機執行。理機執行。v這種調度方式的優點是實現簡單、系統開銷小，適用于這種調度方式的優點是實現簡單、系統開銷小，適用于大多數批處理系統。但它難以滿足實時任務的要求，在大多數批處理系統。但它難以滿足實時任務的要求，在要求比較嚴格的實時操作系統中，一般不宜采用此類調要求比較嚴格的實時操作系統中，一般不宜采用此類調度方式。度方式。 203.2.2 3.2.2 進程調度方式進程調度方式（2 2）搶占方式（）搶占方式（PreemptivePreemptive） 搶占式調度是指在進程并發執行中，如果就緒進程中搶占式調度是指在進程并發執行中，如果

14、就緒進程中某個進程優先級比當前運行進程的優先級還高，無論某個進程優先級比當前運行進程的優先級還高，無論當前正在運行的進程是否結束，允許高優先級進程搶當前正在運行的進程是否結束，允許高優先級進程搶占當前運行進程的處理機并立即執行。占當前運行進程的處理機并立即執行。 搶占式調度可確保高優先級進程立即獲得處理機。搶占式調度可確保高優先級進程立即獲得處理機。搶占式調度在實際系統中具有重要意義。搶占式調度在實際系統中具有重要意義。213.2.2 3.2.2 進程調度方式進程調度方式支持搶占式調度的系統中，一般的搶占原則如下：支持搶占式調度的系統中，一般的搶占原則如下：優先權原則優先權原則 就緒的高優先權

15、進程有權搶占低優先權進程的就緒的高優先權進程有權搶占低優先權進程的CPUCPU。 短作業優先原則短作業優先原則 就緒的短作業有權搶占長作業的就緒的短作業有權搶占長作業的CPUCPU。 時間片原則時間片原則 一個時間片用完后，系統重新進行進程調度一個時間片用完后，系統重新進行進程調度223.3 3.3 調度算法的評價準則調度算法的評價準則(1) (1) 作業周轉時間作業周轉時間 所謂作業周轉時間是指從作業被提交給系統開始，所謂作業周轉時間是指從作業被提交給系統開始，到作業完成為止的這段時間間隔。到作業完成為止的這段時間間隔。平均周轉時間：平均周轉時間： 平均帶權周轉時間平均帶權周轉時間：niiT

16、nT11niSiiTTnW11233.3.1 3.3.1 面向用戶的評價準則面向用戶的評價準則(2) (2) 響應時間響應時間 響應時間是指從進程輸入第一個請求到系統給響應時間是指從進程輸入第一個請求到系統給出首次響應的時間間隔。用戶請求的響應時間出首次響應的時間間隔。用戶請求的響應時間越短，用戶的滿意度越高。越短，用戶的滿意度越高。 響應時間通常由三部分時間組成：進程請求傳響應時間通常由三部分時間組成：進程請求傳送到處理機的時間、處理機對請求信息進行處送到處理機的時間、處理機對請求信息進行處理的時間、響應信息回送到顯示器顯示的時間。理的時間、響應信息回送到顯示器顯示的時間。243.3.1 3

17、.3.1 面向用戶的評價準則面向用戶的評價準則(3)(3)截止時間截止時間 截止時間是指用戶或其他系統對運行進程可容忍的最截止時間是指用戶或其他系統對運行進程可容忍的最大延遲時間。在實時系統中，通常用該準則衡量一個大延遲時間。在實時系統中，通常用該準則衡量一個調度算法是否合格。在實際系統評價中，主要考核的調度算法是否合格。在實際系統評價中，主要考核的是開始截止時間和完成截止時間。是開始截止時間和完成截止時間。(4) (4) 優先權準則優先權準則 在批處理、分時和實時系統中選擇調度算法時，為保在批處理、分時和實時系統中選擇調度算法時，為保證某些緊急作業得到及時處理，必須遵循優先權準則。證某些緊急

18、作業得到及時處理，必須遵循優先權準則。因此，系統對不同進程設立優先級，高優先級進程優因此，系統對不同進程設立優先級，高優先級進程優先獲得處理機的使用權先獲得處理機的使用權。253.3.2 3.3.2 面向面向系統的評價準則系統的評價準則v對計算機系統而言，在保證用戶請求被高效處理的基礎對計算機系統而言，在保證用戶請求被高效處理的基礎上，盡量使計算機系統中的各類資源得到充分利用。上，盡量使計算機系統中的各類資源得到充分利用。 面向系統的調度指標有：面向系統的調度指標有： (1) (1) 系統吞吐量系統吞吐量 (2) (2) 處理機利用率處理機利用率 (3) (3) 各類資源均衡利用各類資源均衡利

19、用 (4) (4) 調度算法實現準則調度算法實現準則263.4 3.4 典型進程調度算法典型進程調度算法3.4.1 3.4.1 先來先服務調度算法先來先服務調度算法3.4.2 3.4.2 短作業短作業（進程）優先調度算法（進程）優先調度算法3.4.4 3.4.4 時間片輪轉調度算法時間片輪轉調度算法3.4.5 3.4.5 優先級優先級調度算法調度算法3.4.6 3.4.6 高響應比優先高響應比優先調度算法調度算法3.4.7 3.4.7 多級多級反饋隊列調度算法反饋隊列調度算法重點重點273.4.1 先來先服務調度算法先來先服務調度算法vFCFS( First Come First Servic

20、e)算法按照進程就算法按照進程就緒的先后順序調度進程，越早到達的進程，越先緒的先后順序調度進程，越早到達的進程，越先執行。執行。FCFS算法的優缺點：算法的優缺點： 有利于長進程，不利于短進程，排在長進程后有利于長進程，不利于短進程，排在長進程后邊的短進程往往等待的時間較長，導致其周轉時邊的短進程往往等待的時間較長，導致其周轉時間過長，沒有體現出短進程優先原則。間過長，沒有體現出短進程優先原則。 有利于處理機繁忙的進程，不利于輸入輸出繁有利于處理機繁忙的進程，不利于輸入輸出繁忙的進程。忙的進程。 算法簡單，易于實現，系統開銷小。算法簡單，易于實現，系統開銷小。283.4.2 3.4.2 短作業

21、短作業（進程）優先調度算法（進程）優先調度算法又稱為又稱為“短進程優先短進程優先”SPN(Shortest Process SPN(Shortest Process Next)Next)；這是對；這是對FCFSFCFS算法的改進，其目標是算法的改進，其目標是減少平均周轉時間。減少平均周轉時間。其思想是：對其思想是：對預計執行時間預計執行時間短的作業（進短的作業（進程）優先分派處理機。通常后來的短作業程）優先分派處理機。通常后來的短作業不搶先不搶先正在執行的作業。正在執行的作業。29SJ(P)FSJ(P)F的特點的特點v優點：優點： 比比FCFSFCFS改善改善平均周轉時間平均周轉時間和和平均帶

22、權周轉時間平均帶權周轉時間，縮短作業的等待時間；，縮短作業的等待時間； 提高系統的提高系統的吞吐量吞吐量；v缺點：缺點： 對長作業非常不利對長作業非常不利，可能長時間得不到執行；，可能長時間得不到執行； 未能依據作業的未能依據作業的緊迫程度緊迫程度來劃分執行的優先級；來劃分執行的優先級； 難以準確估計作業（進程）的執行時間難以準確估計作業（進程）的執行時間，從而影，從而影響調度性能。響調度性能。303.4.4 3.4.4 時間片輪轉調度算法時間片輪轉調度算法v時間片輪轉算法（時間片輪轉算法（RRRR，Round RobinRound Robin）依據公平服）依據公平服務的原則，將處理機的運行時

23、間劃分成等長的時間務的原則，將處理機的運行時間劃分成等長的時間片，輪轉式分配給各個就緒進程使用。片，輪轉式分配給各個就緒進程使用。v采用此算法的系統中，所有就緒進程按照先來先服采用此算法的系統中，所有就緒進程按照先來先服務的原則排成一個隊列，每次調度時將處理機分派務的原則排成一個隊列，每次調度時將處理機分派給隊首進程。如果進程在一個時間片內沒執行完，給隊首進程。如果進程在一個時間片內沒執行完，那么調度程序強行將該進程中止，進程由執行態變那么調度程序強行將該進程中止，進程由執行態變為就緒態并把處理機分配給下一個就緒進程。該算為就緒態并把處理機分配給下一個就緒進程。該算法能保證就緒隊列中的所有進程

24、在一給定的時間段法能保證就緒隊列中的所有進程在一給定的時間段內均能獲得處理機運行。內均能獲得處理機運行。31v時間片輪轉法的原理見圖所示。時間片輪轉法的原理見圖所示。圖 輪轉法調度323.4.5 3.4.5 優先級優先級調度算法調度算法v 優先級調度算法（優先級調度算法（Priority SchedulingPriority Scheduling）為每個進程賦予一個整）為每個進程賦予一個整數，表示其優先級。就緒進程按照優先級的大小順序排隊，調數，表示其優先級。就緒進程按照優先級的大小順序排隊，調度程序選擇優先級最高的進程獲得度程序選擇優先級最高的進程獲得CPUCPU。該算法常被用于批處。該算法

25、常被用于批處理系統中。理系統中。1 1優先權調度算法的類型優先權調度算法的類型v 為了照顧緊迫型作業，使之在進入系統后便獲得優先處理，引為了照顧緊迫型作業，使之在進入系統后便獲得優先處理，引入了最高優先權優先入了最高優先權優先(FPF)(FPF)調度算法。調度算法。v 此算法常被用于此算法常被用于批處理系統批處理系統中，作為中，作為作業調度作業調度算法，也作為多算法，也作為多種操作系統中的種操作系統中的進程調度進程調度算法，還可用于算法，還可用于實時系統實時系統中。中。v 當把該算法用于作業調度時，系統將從后備隊列中選擇若干個當把該算法用于作業調度時，系統將從后備隊列中選擇若干個優先權最高優先

26、權最高的作業裝入內存。的作業裝入內存。v 當用于進程調度時，該算法是把處理機分配給就緒隊列中優先當用于進程調度時，該算法是把處理機分配給就緒隊列中優先權最高的進程，這時，又可進一步把該算法分成如下兩種。權最高的進程，這時，又可進一步把該算法分成如下兩種。331 1優先優先級級調度算法的類型調度算法的類型1) 1) 非搶占式優先權算法非搶占式優先權算法v 系統一旦把處理機分配給就緒隊列中優先權最高的進程后系統一旦把處理機分配給就緒隊列中優先權最高的進程后，該，該進程便一直執行下去，直至完成進程便一直執行下去，直至完成；或因發生某事件使；或因發生某事件使該進程放棄處理機時，系統方可再將處理機重新分

27、配給另該進程放棄處理機時，系統方可再將處理機重新分配給另一優先權最高的進程。一優先權最高的進程。v 這種調度算法主要用于批處理系統中；也可用于某些對實這種調度算法主要用于批處理系統中；也可用于某些對實時性要求不嚴的實時系統中。時性要求不嚴的實時系統中。 2) 2) 搶占式優先權調度算法搶占式優先權調度算法v 系統同樣是把處理機分配給優先權最高的進程，使之執行系統同樣是把處理機分配給優先權最高的進程，使之執行。但在其執行期間，只要又出現了另一個。但在其執行期間，只要又出現了另一個其優先權更其優先權更高的高的進程，進程調度程序就進程，進程調度程序就立即停止立即停止當前進程當前進程( (原優先權最高

28、的原優先權最高的進程進程) )的執行，重新將處理機分配給新到的優先權最高的進的執行，重新將處理機分配給新到的優先權最高的進程。程。v 顯然，這種搶占式的優先權調度算法能更好地滿足緊迫作顯然，這種搶占式的優先權調度算法能更好地滿足緊迫作業的要求，故而常用于要求比較嚴格的實時系統中，以及業的要求，故而常用于要求比較嚴格的實時系統中，以及對性能要求較高的批處理和分時系統中。對性能要求較高的批處理和分時系統中。 342 2優先優先級級的類型的類型v對于最高優先權優先調度算法，其關鍵在于：它對于最高優先權優先調度算法，其關鍵在于：它是使用是使用靜態優先權靜態優先權，還是用，還是用動態優先權動態優先權，以

29、及如，以及如何確定進程的優先權。何確定進程的優先權。1) 1) 靜態優先權靜態優先權v靜態優先權是在靜態優先權是在創建進程時確定創建進程時確定的，且在進程的的，且在進程的整個運行期間整個運行期間保持不變保持不變。一般地，優先權是利用。一般地，優先權是利用某一范圍內的一個整數來表示的。某一范圍內的一個整數來表示的。v確定進程優先權的依據有如下三個方面：確定進程優先權的依據有如下三個方面：(1) (1) 進程類型。進程類型。(2) (2) 進程對資源的需求。進程對資源的需求。(3) (3) 用戶要求。用戶要求。352優先級級的類型2) 2) 動態優先動態優先級級v動態優先權是指在創建進程時所賦予的

30、優先動態優先權是指在創建進程時所賦予的優先權，是權，是可以可以隨進程的推進或隨其等待時間的隨進程的推進或隨其等待時間的增加而增加而改變改變的，以便獲得更好的調度性能。的，以便獲得更好的調度性能。363.4.6 3.4.6 高響應比優先高響應比優先調度算法調度算法最高響應比作業優先算法是對最高響應比作業優先算法是對FCFS方式和方式和SJF方式方式的一種綜合平衡。響應比的一種綜合平衡。響應比R定義為系統對作業的響定義為系統對作業的響應時間與作業要求運行時間的比值。應時間與作業要求運行時間的比值。一個作業或進程的響應比一個作業或進程的響應比R HRRF調度程序開始調度時，首先計算各個后備作調度程序

31、開始調度時，首先計算各個后備作業或各個就緒進程的響應比業或各個就緒進程的響應比 ,然后選擇然后選擇 值最大的作值最大的作業或進程。業或進程。需運行時間需運行時間需運行時間需運行時間等待時間等待時間需運行時間需運行時間響應時間響應時間/R需需運運行行時時間間等等待待時時間間1R37舉例舉例例：假定在一個處理機上執行以下五個作業：例：假定在一個處理機上執行以下五個作業： 作業號作業號 A B C D E 到達時間到達時間 0 1 2 3 4 運行時間運行時間 4 3 5 2 4 優先數優先數 1 4 2 5 3(優先數越大代優先數越大代表優先級越高表優先級越高)分別采用分別采用FCFS、SJF、R

32、R（時間片（時間片1），），HRRF (響應比高者優先響應比高者優先)和和四種調度算法時，試做：四種調度算法時，試做：（1） 計算每個作業的周轉時間和帶權周轉時間計算每個作業的周轉時間和帶權周轉時間 ；（2） 計算平均周轉時間和平均帶權周轉時間。計算平均周轉時間和平均帶權周轉時間。382.11.518342.25913 6 3.11618 2.6789 4 SJF帶權周轉時間帶權周轉時間周轉時間周轉時間完成時間完成時間2.83.55.5221帶權周轉時間帶權周轉時間914111064周轉時間周轉時間18 14 12 7 4 完成時間完成時間FCFSFCFS42534運行時間運行時間43210到

33、達時間到達時間平均平均EDCBA作業號作業號39圖圖3-5 qq=1和和qq=4時的進程運行情況時的進程運行情況 ABED(b) qq =4(a) qq =112345678910 11 1213 14 151617t18C4 3 5 2 4ACBDABAECECEC403.2911.63.251317 4811 3.21618 3910 31212 帶權周轉時間帶權周轉時間周轉時間周轉時間完成時間完成時間RRRR42534運行時間運行時間43210到達時間到達時間平均平均EDCBA作業號作業號2.388.43.51418 369 2.41214 267 144 帶權周轉時間帶權周轉時間周轉時

34、間周轉時間完成時間完成時間HRRF41帶權周轉時間帶權周轉時間周轉時間周轉時間完成時間完成時間優先級優先級42534運行時間運行時間43210到達時間到達時間平均平均EDCBA作業號作業號2.25913 1.536 3.21618 2.6789 144 作業號作業號 A B C D E到達時間到達時間 0 1 2 3 4運行時間運行時間 4 3 5 2 4優先數優先數 1 4 2 5 3(優優先數越大代表優先級越高先數越大代表優先級越高)423.4.7 3.4.7 多級多級反饋隊列調度算法反饋隊列調度算法v 多級反饋隊列調度算法（多級反饋隊列調度算法（MFQMFQ，Multilevel Fee

35、dback QueueMultilevel Feedback Queue）是綜合時間片輪轉調度算法和優先級調度算法并加以改進而是綜合時間片輪轉調度算法和優先級調度算法并加以改進而得到的算法。得到的算法。433.4.7 3.4.7 多級多級反饋隊列調度算法反饋隊列調度算法443.4.7 3.4.7 多級多級反饋隊列調度算法反饋隊列調度算法v 多級反饋隊列調度算法的優點：多級反饋隊列調度算法的優點： 保證了短進程的優先，可讓終端型用戶滿意。短進程需要保證了短進程的優先，可讓終端型用戶滿意。短進程需要的服務時間少，在前幾級就緒隊列中就能夠完成。的服務時間少，在前幾級就緒隊列中就能夠完成。 滿足輸入輸

36、出型進程的要求。輸入輸出型進程經常需要等滿足輸入輸出型進程的要求。輸入輸出型進程經常需要等待輸入輸出設備而阻塞，但阻塞的進程仍然處在較高優先級待輸入輸出設備而阻塞，但阻塞的進程仍然處在較高優先級隊列中。隊列中。 照顧了計算型長進程的執行。對于計算型的長進程，由于照顧了計算型長進程的執行。對于計算型的長進程，由于其執行時間長，往往要不斷的向優先級低的調度隊列轉換。其執行時間長，往往要不斷的向優先級低的調度隊列轉換。但是該算法中，優先級越低的調度隊列其執行的時間片越長但是該算法中，優先級越低的調度隊列其執行的時間片越長，這可以有效地減少長進程的調度次數，保證長進程能夠較，這可以有效地減少長進程的調

37、度次數，保證長進程能夠較快執行完畢。快執行完畢。 系統開銷小。由于不需要動態計算時間片和優先級，進程系統開銷小。由于不需要動態計算時間片和優先級，進程的優先級和時間片等于他所在調度隊列的優先級和時間片的優先級和時間片等于他所在調度隊列的優先級和時間片45典型調度算法比較典型調度算法比較46重點回顧重點回顧v中級調度中級調度(middle-level scheduling)(middle-level scheduling)又稱內存調度，又稱內存調度，它是進程在內存和外存之間的對換。它是進程在內存和外存之間的對換。v低級調度低級調度（low-level schedulinglow-level sc

38、heduling）又稱進程調度、）又稱進程調度、短程調度，它決定哪個就緒態進程獲得處理機，短程調度，它決定哪個就緒態進程獲得處理機，即選擇某個進程從就緒態變為執行態。執行低級即選擇某個進程從就緒態變為執行態。執行低級調度的原因多是處于執行態的進程由于某種原因調度的原因多是處于執行態的進程由于某種原因放棄或被剝奪處理機。放棄或被剝奪處理機。47重點回顧重點回顧典型進程調度算法典型進程調度算法 先來先服務調度算法先來先服務調度算法 短作業短作業（進程）優先調度算法（進程）優先調度算法 時間片輪轉調度算法時間片輪轉調度算法 優先級優先級調度算法調度算法 高響應比優先高響應比優先調度算法調度算法 多級

39、多級反饋隊列調度算法反饋隊列調度算法483.5 3.5 線程調度算法線程調度算法3 3.5.1 .5.1 用戶級線程調度用戶級線程調度 用戶級線程是在用戶態下創建的，系統內核并不知道線程的存在用戶級線程是在用戶態下創建的，系統內核并不知道線程的存在。此時系統內核和只支持進程的系統內核一樣，只為進程服務，。此時系統內核和只支持進程的系統內核一樣，只為進程服務，從就緒進程隊列中選中一個進程并分配給它一個從就緒進程隊列中選中一個進程并分配給它一個CPUCPU時間片。時間片。493.5.2 3.5.2 核心核心級線程調度級線程調度 在核心支持線程技術的系統中，內核直接調度線程。線程調度時在核心支持線程

40、技術的系統中，內核直接調度線程。線程調度時，內核不考慮該線程屬于哪個進程。被選中的線程獲得一個時間，內核不考慮該線程屬于哪個進程。被選中的線程獲得一個時間片，如果執行時間超過此時間片，該線程被系統強制掛起。如線片，如果執行時間超過此時間片，該線程被系統強制掛起。如線程在給定時間片內阻塞，處于內核的線程調度程序調度另一線程程在給定時間片內阻塞，處于內核的線程調度程序調度另一線程運行。后者和前者可能同屬于一個進程，也可能屬于不同進程。運行。后者和前者可能同屬于一個進程，也可能屬于不同進程。503 3.6 .6 實時調度算法實時調度算法v 實時系統是一種時間起主導作用的系統，對時間有著嚴格的要求實時

41、系統是一種時間起主導作用的系統，對時間有著嚴格的要求。在實時系統中，每一個實時任務都有一個時間約束要求。實時。在實時系統中，每一個實時任務都有一個時間約束要求。實時調度（調度（real-time schedulingreal-time scheduling）的目標就是合理地安排這些任務的執）的目標就是合理地安排這些任務的執行次序，使之滿足各個實時任務的時間約束要求。行次序，使之滿足各個實時任務的時間約束要求。v 通常，一個特定任務與一個截止時間相關聯。截止時間包括：開通常，一個特定任務與一個截止時間相關聯。截止時間包括：開始截止時間（任務在某時間以前，必須開始執行）和完成截止時始截止時間（任務

42、在某時間以前，必須開始執行）和完成截止時間（任務在某時間以前必須完成）間（任務在某時間以前必須完成）v 實時調度策略主要考慮如何使硬實時任務在規定的截止時間內完實時調度策略主要考慮如何使硬實時任務在規定的截止時間內完成（或開始）。同時，盡可能使軟實時任務也能在規定的截止時成（或開始）。同時，盡可能使軟實時任務也能在規定的截止時間內完成（或開始）。公平性和最短平均響應時間等準則不再顯間內完成（或開始）。公平性和最短平均響應時間等準則不再顯得重要。大多數現代操作系統都無法實現直接依據任務截止時間得重要。大多數現代操作系統都無法實現直接依據任務截止時間進行調度，它們一般通過提高響應速度，保證任務在其

43、截止時間進行調度，它們一般通過提高響應速度，保證任務在其截止時間內完成。內完成。513.6.1 3.6.1 實時調度目標和所需必要信息實時調度目標和所需必要信息v 一般情況下，實時系統中可能同時有多個周期性任務并發執行，一般情況下，實時系統中可能同時有多個周期性任務并發執行，形成任務流，這些實時任務都要求系統做出實時響應。系統能否形成任務流，這些實時任務都要求系統做出實時響應。系統能否對它們全部予以處理，取決于每個任務要求的處理時間和該任務對它們全部予以處理，取決于每個任務要求的處理時間和該任務出現的周期。例如，系統中有出現的周期。例如，系統中有n n個周期性任務，其中任務出現的個周期性任務，

44、其中任務出現的周期為周期為Pi,Pi,處理所需的處理所需的CPUCPU時間為時間為CiCi，那么系統能處理這個任務流，那么系統能處理這個任務流的條件是：的條件是：niPiCi11523.6.2 3.6.2 搶占調度和快速切換機制搶占調度和快速切換機制v 在要求嚴格的實時系統中，如硬實時系統，允許一個優先權高的在要求嚴格的實時系統中，如硬實時系統，允許一個優先權高的實時任務搶占優先權低的實時任務，從而滿足實時任務對截止時實時任務搶占優先權低的實時任務，從而滿足實時任務對截止時間的要求。如果一個實時任務不搶占就能夠滿足自己的截止時間間的要求。如果一個實時任務不搶占就能夠滿足自己的截止時間要求，則不

45、宜采取搶占調度，因為搶占調度系統開銷較大。要求，則不宜采取搶占調度，因為搶占調度系統開銷較大。v 在實際應用中，系統判斷能否滿足截止時間要求并不是一件容易在實際應用中，系統判斷能否滿足截止時間要求并不是一件容易的事。如系統小，需處理的任務較少，則容易判斷能否滿足截止的事。如系統小，需處理的任務較少，則容易判斷能否滿足截止時間要求；如系統較大，則很難判斷能否滿足其截止時間要求。時間要求；如系統較大，則很難判斷能否滿足其截止時間要求。v 快速切換機制可以實現對實時任務的快速切換。快速切換機制常快速切換機制可以實現對實時任務的快速切換。快速切換機制常用硬件裝置實現快速中斷機構，做到盡量不漏掉實時任務

46、的中斷用硬件裝置實現快速中斷機構，做到盡量不漏掉實時任務的中斷。在軟件實現上，可通過提高分派程序對任務切換的速度來提高。在軟件實現上，可通過提高分派程序對任務切換的速度來提高系統的性能。系統的性能。533.6.3 3.6.3 典型實時調度算法典型實時調度算法1最早截止時間優先調度算法（最早截止時間優先調度算法（EDF, Earliest Deadline First） 最早截止時間優先調度算法中根據實時任務的開始截止時間最早截止時間優先調度算法中根據實時任務的開始截止時間確定任務的優先級，截止時間越早，其優先級越高。調度程確定任務的優先級，截止時間越早，其優先級越高。調度程序把所有可以運行的進程按照其截止時間先后順序放在一個序把所有可以運行的進程按