1、第第5章章 處理器調度處理器調度引言引言51 三級調度的概念三級調度的概念52 作業調度作業調度53 進程調度進程調度54 常用的調度算法常用的調度算法55 實例分析：實例分析：unix進程調度進程調度引言引言 處理器是計算機系統中一個十分重要的資源。隨著多道程序設計技術出現，處理器的管理也日趨復雜。對于不同類型的操作系統，處理器的管理方法各不相同。不同的處理器管理方法將為用戶提供不同性能的操作系統。因此，根據操作系統目標的不同，處理器的管理策略是不盡相同的。 本章將以處理器管理為核心，討論與處理器調度有關的概念，并介紹常用的調度算法。51 三級調度的概念三級調度的概念 在多道程序系統中，一個

2、作業被提交后，并不一定能立即執行，必須經過處理器調度，方可為其創建進程，分配內存，從而進入執行狀態，稱為作業調度或高級調度。而作業的執行歸結為進程的調度，又稱為低級調度。在比較完善的系統中，為了提高內存的利用率，往往還設置了對換調度，即中級調度。 511 作業的狀態及其轉換作業的狀態及其轉換 作業是用戶在一次解題或一個事務處理過程中要求計算機系統所做的工作的集合。 作業由用戶程序、所需的數據及作業說明書三部分組成。 計算機系統完成一個作業過程中所做的一項相對獨立的工作稱為一個作業步。 在多道程序系統中，一個作業在它的生命期內要經歷提交、后備、運行和完成四個主要的階段。 511 作業的狀態及其轉

3、換作業的狀態及其轉換 n提交狀態：提交狀態：當用戶將自己的作業提交給操作員，操作員通過某種輸入方式將用戶提交的作業輸入到外存上時，稱此階段為作業處于提交狀態。作業輸入方式通常有5種：u聯機輸入方式：聯機輸入方式：該方式大多用在交互式系統中，用戶和系統通過交互式會話來輸入作業。在聯機方式中，外圍設備直接和主機相連接，一臺主機可連接一臺或多臺外圍設備。u脫機輸入方式：脫機輸入方式：脫機輸入方式利用低檔i/o處理器作為外圍處理器進行輸入處理，提高了主機的資源利用率。 511 作業的狀態及其轉換作業的狀態及其轉換 u聯機輸入方式：聯機輸入方式：該方式大多用在交互式系統中，用戶和系統通過交互式會話來輸入

4、作業。在聯機方式中，外圍設備直接和主機相連接，一臺主機可連接一臺或多臺外圍設備。u脫機輸入方式：脫機輸入方式：脫機輸入方式利用低檔i/o處理器作為外圍處理器進行輸入處理，提高了主機的資源利用率。 511 作業的狀態及其轉換作業的狀態及其轉換 u直接耦合方式：直接耦合方式：該方式是把主機和外圍低檔機通過一個公用的大容量外存直接耦合起來，從而省去了在脫機輸入時依靠人工干預來傳遞給后援存儲器的過程。u spooling系統：系統：在spooling系統中，多臺外圍設備通過通道或dma器件將主機與外存連接起來，作業的輸入過程由主機中的操作系統控制。 u網絡輸入方式：網絡輸入方式：該方式以上述幾種輸入方

5、式為基礎。當用戶需要把在網絡中某一臺主機上輸入的信息傳遞到同一網絡中的另一臺主機上進行操作或執行時，就構成了網絡輸入方式。 511 作業的狀態及其轉換作業的狀態及其轉換 n后備狀態：后備狀態：當操作系統為輸入并存放在外存輸入井上的作業建立一個作業控制塊（jcb，job control block）之后，作業就進入了后備狀態。作業從建立jcb到被作業調度程序選中運行，所處的狀態叫做后備狀態。n運行狀態：運行狀態：作業調度程序從處于后備狀態的作業隊列中按一定的算法選中一個作業調入內存，并為之建立相應的進程后，由于此時的作業已具有獨立運行的資格，如果處理器空閑，便可立即開始執行，稱此時的作業進入了運

6、行狀態。n完成狀態：完成狀態：當作業（進程）運行正常完成或異常結束時，便自我終止（正常完成），或被迫終止（異常終止），此時作業便進入完成狀態。 511 作業的狀態及其轉換作業的狀態及其轉換 n作業狀態及其轉換如下圖所示：作業狀態及其轉換如下圖所示：提交狀態提交狀態后備狀態后備狀態完成狀態完成狀態運行狀態運行狀態512 調度的層次調度的層次 n高級調度：高級調度：高級調度又稱作業調度。作業調度程序決定把哪些后備隊列中的作業調入內存，并為其創建進程，分配必要的資源，最后將所創建的進程插入就緒隊列，以使該作業的進程獲得競爭處理器的權利。在批處理系統中或者是操作系統中的批處理部分都配有作業調度。n中級

7、調度：中級調度：中級調度又稱交換調度，它的主要功能是按一定的算法在內存和外存之間進行進程對換，其目的是為了使內存緊張的情況得以緩解。交換調度的主要工作是將內存中處于阻塞狀態的某些進程換至外存，騰出內存空間以便將外存上已具備運行條件的進程換入內存，準備運行。進程在其整個生命期間可能要經歷多次換進換出，在分時系統中常采用交換調度。 512 調度的層次調度的層次 n低級調度：低級調度：低級調度又稱進程調度。其主要任務是按照某種策略和方法選取一個處于就緒狀態的進程占用處理器。它決定就緒隊列中哪個進程先獲得處理器，然后再由分派程序執行將處理器分配給進程的操作。 513 調度模型調度模型 從上述操作系統的

8、調度類型可知，雖然操作系統的調度機制不盡相同，有的操作系統僅設有低級調度，有的操作系統則擁有高級調度和低級調度，有的操作系統三級調度一應俱全。但是操作系統中的任何一種調度都涉及進程隊列，因此根據操作系統的不同性能，一般有三種相應的調度隊列模型。 512 調度的層次調度的層次 n一級調度隊列模型：一級調度隊列模型：一級調度模型僅設置了進程調度。在這種調度模型中，用戶輸入的命令和數據都直接送入內存。操作系統會為每一個作業建立一個或多個進程，并將它們插入就緒隊列，然后按照時間片輪轉方式進行調度。一級調度隊列模型如下圖所示： 512 調度的層次調度的層次 就緒隊列就緒隊列阻塞隊列阻塞隊列進程調度進程調

9、度時間片完時間片完事件發生事件發生等待事件等待事件交互用戶交互用戶進程完成進程完成512 調度的層次調度的層次 n二級調度隊列模型：二級調度隊列模型：在二級調度隊列中，不僅有進程調度，還有作業調度。作業調度從外存中選擇一批作業調入內存，為其創建進程并送入就緒隊列。同時，當操作系統任務較多時，阻塞隊列有可能很長。為了提高執行效率，通常設置若干個阻塞隊列，不同隊列對應于引起進程阻塞的不同原因。二級調度隊列模型如下圖所示：512 調度的層次調度的層次 ：后備作業隊列等待事件2阻塞隊列2就緒隊列事件1發生等待事件1阻塞隊列1時間片完事件2發生等待事件n阻塞隊列n事件n發生作業調度進程調度：512 調度

10、的層次調度的層次 n三級調度隊列模型：三級調度隊列模型：三級調度隊列模型同時擁有作業調度，交換調度和進程調度。在引入交換調度之后，可以把處于靜止就緒和靜止阻塞的進程從內存交換到外存上，以使內存緊張的狀況得以緩解。三級調度隊列模型如下圖所示： 512 調度的層次調度的層次 交換調度(外存)進程完成后備作業隊列就緒隊列靜止就緒隊列時間片完等待事件阻塞隊列n事件發生作業調度靜止阻塞隊列進程調度52 作業調度作業調度 只有批處理系統才必須具有作業調度。在分時系統和實時系統中都沒有作業調度的概念。因為在分時系統中，由于要進行人機交互，系統必須能及時響應，為此應把用戶從終端輸入的作業直接送入內存而不是建立

11、在外存上，因此，不再需要專門用于把作業從外存調入內存的作業調度過程。對于實時系統中的實時任務，因為通常對其響應的時間更為嚴格，故也不需要作業調度。 521 作業調度的功能作業調度的功能 作業調度主要是完成作業從后備狀態到運行狀態的轉變，以及從運行狀態到完成狀態的轉變。其主要功能如下：n記錄系統中各作業的狀況記錄系統中各作業的狀況 ：作業調度程序要能挑選出一個作業投入運行，并且在運行中對其進行管理。它必須掌握作業在各個狀態，包括運行階段的有關情況。為此，系統為每個作業建立一個作業控制塊jcb（job control block）來記錄這些有關信息。jcb的主要內容包括作業名、作業類型、資源要求、

12、當前狀態、資源使用情況以及該作業的優先級等。與系統感知進程存在時要通過進程控制塊pcb一樣，系統通過jcb而感知作業的存在。 521 作業調度的功能作業調度的功能 n從后備隊列中挑選出一部分作業投入執行從后備隊列中挑選出一部分作業投入執行 ：作業調度程序根據選定的調度算法，從后備作業隊列中挑選出若干作業去投入運行。 n為被選中的作業做好運行前的準備工作為被選中的作業做好運行前的準備工作 ：作業調度程序為選中的作業建立相應的進程，并為這些進程分配它們所需要的全部資源，如分配給它們內存、外存、外設等。n在作業運行結束時做善后處理工作在作業運行結束時做善后處理工作 ：善后處理主要是輸出作業管理信息，

13、例如執行時間等。再就是回收該作業所占用的資源，撤消與該作業有關的全部進程和該作業的作業控制塊等。522 作業調度的目標與性能衡量作業調度的目標與性能衡量 n面向系統的準則面向系統的準則 ：不同的操作系統有不同的要求，為了滿足系統功能的要求，在設計操作系統時，應遵循一些準則，最重要的有以下幾點：u吞吐量大吞吐量大 ：這是用來評價批處理系統的重要指標。吞吐量是單位時間內完成的作業數，它與批處理作業的平均長度有著密切關系。但作業調度的方式和算法，對吞吐量的大小也將產生較大的影響。u cpu利用率高利用率高 ：對于大中型多用戶系統，由于cpu價格十分昂貴，所以cpu的利用率成為衡量大中型系統性能的十分

14、重要的指標。而調度方式和算法，對cpu的利用率起著十分重要的作用。 522 作業調度的目標與性能衡量作業調度的目標與性能衡量 u各類資源的平衡利用各類資源的平衡利用 ：在大中型系統中，有效地利用各類資源（如cpu、內存、外存和i/o設備等），也是一個重要指標。對于微機和某些實時系統，該準則也不那么重要。522 作業調度的目標與性能衡量作業調度的目標與性能衡量 n面向用戶的準則面向用戶的準則 ：為了滿足用戶對操作系統的要求，應滿足如下準則：u周轉時間短周轉時間短 ：周轉時間是評價批處理系統的一個重要性能指標。作業周轉時間是指從作業提交給系統開始，到作業完成為止的時間間隔。p平均周轉時間：平均周轉

15、時間：計算機系統為使大多數用戶對周轉時間感到滿意，引入了平均周轉時間t的評價指標。對于有n個作業的系統，平均周轉時間可描述為：)(1111ininiiitstentnt522 作業調度的目標與性能衡量作業調度的目標與性能衡量 式中，n是系統中的作業個數，ti是第i個作業的周轉時間，tei是作業的完成時間，tsi是作業的提交時間。p平均帶權周轉時間：周轉時間沒有考慮作業的運行時間，不能準確反映作業周轉時間與作業運行時間的關系。為此引入了平均帶權周轉時間。一個作業的帶權周轉時間定義為作業的周轉時間與系統為它提供的實際服務時間之比，即w=ti/tri。 n個作業的平均帶權周轉時間為： 式中，tri是

16、系統為作業i提供的實際服務時間。niiitrtnw11522 作業調度的目標與性能衡量作業調度的目標與性能衡量 u響應時間快響應時間快 ：響應時間是評價分時系統的性能指標。它是從用戶通過鍵盤提交一個請求開始，直至系統首次產生響應為止的時間，或者說直到屏幕顯示結果為止的時間。u截止時間的保證：截止時間的保證：在實時系統中，截止時間是衡量系統性能好壞的重要指標。截止時間是指某任務必須完成的最遲時間。對于嚴格的實時系統，其調度方式和調度算法必須保證這一點，否則將可能引起難以預料的后果。u優先權準則：優先權準則：在批處理、分時、實時和多模式系統中，都可使用優先權準則，以便讓那些緊急的作業得到及時的處理

17、。在要求較嚴格的場合，往往還需要選擇搶占調度方式，才能保證緊急作業得到及時的處理。53 進程調度進程調度 進程調度的任務是控制、協調多個進程對處理器的競爭，即按照一定的調度算法從就緒隊列中選中一個進程，并把處理器的使用權交給被選中的進程。操作系統為了對進程進行有效的監控，需要維護一些與進程相關的數據結構，記錄所有進程的運行情況，并在進程讓出處理器或調度程序剝奪運行狀態進程占用處理器時，選擇適當的進程分派處理器，完成上下文的切換。我們把操作系統內核中完 成 這 些 功 能 的 部 分 稱 為 進 程 調 度 程 序（scheduler），它所使用的算法稱為調度算法（scheduling algo

18、rithm）。53 進程調度進程調度 進程調度的任務是控制、協調多個進程對處理器的競爭，即按照一定的調度算法從就緒隊列中選中一個進程，并把處理器的使用權交給被選中的進程。操作系統為了對進程進行有效的監控，需要維護一些與進程相關的數據結構，記錄所有進程的運行情況，并在進程讓出處理器或調度程序剝奪運行狀態進程占用處理器時，選擇適當的進程分派處理器，完成上下文的切換。我們把操作系統內核中完 成 這 些 功 能 的 部 分 稱 為 進 程 調 度 程 序（scheduler），它所使用的算法稱為調度算法（scheduling algorithm）。53 1 進程調度的功能進程調度的功能 n進程調度的功

19、能進程調度的功能 ：作為進程調度的準備，進程管理模塊必須將系統中各進程的執行情況和狀態特征記錄在各進程的pcb中，作為管理進程的依據。 n選擇占有處理器的進程選擇占有處理器的進程 ：進程調度的主要功能是按照一定的策略選擇一個處于就緒狀態的進程，使其獲得處理器運行。根據不同的系統設計目標，有各種各樣的選擇策略 。n進行進程上下文的切換進行進程上下文的切換 ：進程的上下文是進程執行活動全過程的靜態描述。一個進程的上下文包括進程的狀態、有關變量和數據結構的值、機器寄存器的值和pcb以及有關程序、數據等。一個進程的執行是在進程的上下文中執行的。當正在運行的進程由于某種原因要讓出處理器時，系統要做進程上

20、下文切換，以使另一個進程得以運行。 53 2 進程調度方式進程調度方式 n非剝奪調度方式非剝奪調度方式 ：調度程序一旦把處理器分配給某進程，該進程就將一直運行下去，只有當進程完成或發生其事件而阻塞時，系統才把處理器分配給另一進程的調度方式稱為非剝奪調度，也稱非搶占方式（nonpreemptive scheduling）方式。在此調度方式下，系統不得以任何理由剝奪現行進程所占用的處理器。該調度方式的優點是簡單、系統開銷小，但卻可能導致系統性能的惡化，表現為：u當一個緊急任務到達時，不能立即投入運行，以至于延誤時機；u若干個后到的短作業，需要等待先到的長作業運行完畢后才能運行，致使短作業的周轉時間

21、較長。 53 2 進程調度方式進程調度方式 n剝奪調度方式剝奪調度方式 ：進程的另一種調度方式是剝奪調度方式，或稱搶占方式（preemptive scheduling），這是指進程正在運行時，系統可根據某種原則，剝奪已分配給它的處理器，并將處理器再分配給其他進程的一種調度方式。剝奪的原則有： u優先權原則。優先權高的進程可以剝奪優先權低的進程的運行； u短進程優先原則。短進程到達后可以剝奪長進程的運行； u時間片原則。一個時間片運行完后重新調度。 53 3 進程調度的時機進程調度的時機 進程調度發生的時機，與引起進程調度的原因以及進程調度的方式有關。引起進程調度的原因有以下幾類：u正在執行的進

22、程執行完畢或由于某種錯誤而異常中止。u執行中的進程自己調用阻塞原語將自己阻塞起來而進入等待狀態（如等待某一事件而事件未發生或調用了wait原語而資源不足等）。u分時系統中的時間片用完。u在執行完系統調用等系統程序后返回用戶進程時，這時可看作系統進程運行完畢，從而可選擇一新的用戶進程執行。53 3 進程調度的時機進程調度的時機 u在基于優先級調度的策略時，就緒隊列中的某進程的優先級變得高于當前運行進程的優先級，從而也將引發進程調度。 以上14條是在剝奪和不可剝奪情況下引起進程調度的原因，而第5條是在剝奪情況下引起調度的原因。54 常用的調度算法常用的調度算法 調度算法是指：根據系統的資源分配策略

23、所規定的資源分配算法。對于不同的系統和系統目標，通常采用不同的調度算法。目前存在著多種調度算法，有的算法適用于作業調度，有的算法適用于進程調度，但也有些調度算法，既可用于作業調度，也可用于進程調度。54 1 先來先服務調度算法先來先服務調度算法 n實現方法：實現方法：先來先服務fcfs（first come first serve， fcfs）調度算法是一種最簡單的調度算法。其基本思想是：將用戶作業或就緒進程按提交或變為就緒狀態的先后次序排成隊列，調度時總是選擇隊首作業或進程投入運行。該算法既可用于作業調度，也可用于進程調度。n優缺點：優缺點：雖然fcfs調度算法易于實現，表面上也公平，但服務

24、質量不佳，對短作業用戶不公平 。n使用場合：使用場合：fcfs算法很少作為進程調度的主調度算法，但常作為一種輔助調度算法。 54 1 先來先服務調度算法先來先服務調度算法 【例5-1】假設有五道作業，它們的進入時間和運行時間由下表給出： 作業號進入時間運行時間104213326432544在不剝奪方式的單道環境下，采用fcfs調度算法，試說明它們的調度順序，并計算在該種調度算法下的平均周轉時間和平均帶權周轉時間。54 1 先來先服務調度算法先來先服務調度算法 解：采用fcfs調度算法，調度順序是1，2，3，4，5五道作業的執行時間、完成時間和周轉時間如下表所示：作業號進入時間 運行時間 開始執

25、行時間完成時間 周轉時間10404421347632671311432131512544151915平均周轉時間t（4+6+11+12+15）/ 5=9.8小時平均帶權周轉時間w=(4/4+6/3+11/6+12/2+15/4) / 5=2.9254 2 短作業（進程）優先調度算法短作業（進程）優先調度算法 n實現方法：實現方法：sjf調度算法是從后備隊列中選擇一個或若干個估計運行時間最短的作業，將它們調入內存運行。該調度算法可以照顧到實際上在所有作業中占很大比例的短作業，使它們能比長作業優先執行。n優缺點：優缺點：這種算法能有效地降低作業的平均周轉時間，提高系統的吞吐量，但是，它們存在著不容

26、忽視的缺點：u該算法對長作業不利。由于系統狀態是動態的，如果不斷地有短作業進入，則可能導致長作業長時間得不到響應；u該算法未考慮作業的緊迫程度； 54 2 短作業（進程）優先調度算法短作業（進程）優先調度算法 u由于作業（進程）的長短只是根據用戶所提供的估計運行時間而定，而用戶又可能會有意或無意地縮短其作業的估計執行時間，致使該算法不一定能真正做到短作業優先調度。 54 2 短作業（進程）優先調度算法短作業（進程）優先調度算法 【例5-2】仍采用例5-1的題目，在不剝奪方式的單道環境下，采用sjf調度算法，試說明它們的調度順序，并計算在該種調度算法下的平均周轉時間和平均帶權周轉時間。 作業號進

27、入時間運行時間10421332643254454 2 短作業（進程）優先調度算法短作業（進程）優先調度算法解：采用sjf調度算法，調度順序是1，4，2，5，3五道作業的執行時間、完成時間和周轉時間如下表所示：作業號進入時間 運行時間 開始執行時間完成時間 周轉時間1040444324632136985449139326131917平均周轉時間t（4+3+8+9+17）/ 5=8.2小時平均帶權周轉時間w=(4/4+3/2+8/3+9/4+17/6) / 5=2.0554 3 時間片輪轉調度算法時間片輪轉調度算法 n實現方法：實現方法：時間片輪轉法rr（round robin）是將cpu的處理時

28、間分成固定大小的時間片，且采用剝奪調度方式。在簡單輪轉法中，系統將所有就緒進程按先進先出規則排成一個環形隊列，把cpu分配給隊首進程，并規定它執行一個時間片。當時間片用完時，系統剝奪該進程的運行并將它送到就緒隊列末尾，重新把處理器分配給就緒隊列中新的隊首進程。54 3 時間片輪轉調度算法時間片輪轉調度算法 【例5-3】假設有五道作業，它們的進入時間和運行時間由下表給出： 作業號進入時間運行時間a04b12c25d33e43畫出當時間片分別為q=1和q=4時的調度圖，并計算該種調度算法時的平均周轉時間和平均帶權周轉時間。54 3 時間片輪轉調度算法時間片輪轉調度算法 時刻運行進程 排隊進程時刻運

29、行進程 排隊進程01a910daec12ba1011aecd23acb1112ecd34cbda1213cde45bdaec1314dec56daec1415ec67aecd1516c78ecda1617c89cdae解：當時間片q=1時，列出下表，找出運行序列： 54 3 時間片輪轉調度算法時間片輪轉調度算法 根據上表，畫出調度圖如下圖所示： abcde0123456789111012 13 14 15 16 17 54 3 時間片輪轉調度算法時間片輪轉調度算法 從上圖得出的五道作業的完成時間和周轉時間如下表所示： 作業號進入時間運行時間完成時間周轉時間a041111b1254c251715

30、d331411e431511平均周轉時間t（11+4+15+11+11）/ 5=10.4 平均帶權周轉時間w=(11/4+4/2+15/5+11/3+11/3) / 5=3.0254 3 時間片輪轉調度算法時間片輪轉調度算法 當時間片q=4時，調度圖如下圖所示：abcde0123456789111012 13 14 15 16 17 54 3 時間片輪轉調度算法時間片輪轉調度算法 如果一個作業的時間片沒有用完，剩余時間可由下一個作業使用。從上圖得出的五道作業的完成時間和周轉時間如下表所示： 作業號進入時間運行時間完成時間周轉時間a0444b1265c25119d331411e431713平均周

31、轉時間t（4+5+9+11+13）/ 5=8.4 平均帶權周轉時間w=(4/4+5/2+9/5+11/3+13/3) / 5=2.66 54 4 高優先權優先調度算法高優先權優先調度算法 n實現方法：實現方法：為了使緊急的作業得到優先調度，在許多系統中，每個作業或進程都被指定一個優先級，調度程序總是選擇相應隊列中具有最高優先權的作業或進程，這就是高優先權優先（first priority first，fpf）調度算法。n優先權確定方法：優先權確定方法：u靜態優先權：靜態優先權：靜態優先權是在創建進程時確定的，在整個運行期間不再改變。基于靜態優先權的調度算法實現簡單，系統開銷小。但由于靜態優先權

32、一旦確定之后，直到運行結束為止始終保持不變，從而使優先級低的進程長時間得不到調度。 54 4 高優先權優先調度算法高優先權優先調度算法 u動態優先權：動態優先權：動態優先權是基于某種原則，使進程的優先權隨時間而改變，例如在就緒隊列中的進程，其優先權以速度a增加，若再令正在執行進程的優先權以速度b下降，便可防止一個長作業長期壟斷處理器這種情況的發生。n優先數與優先級的關系優先數與優先級的關系；在unix和許多其他的系統中，優先級數值越大，表示的進程優先權越低；而在某些系統中的用法則剛好相反，如windows，大數值表示高優先級。 54 4 高優先權優先調度算法高優先權優先調度算法 【例5-4】假

33、設有五道作業，它們的進入時間、運行時間和靜態優先數由下表給出：作業號進入時間運行時間優先數10462134326243255443假定優先數越高，優先級越低，系統采用靜態fpf調度算法，且不可剝奪，試計算采用該調度算法時的平均周轉時間和平均帶權周轉時間。 54 4 高優先權優先調度算法高優先權優先調度算法 解：解：采用靜態fpf調度算法，調度順序是1，3，5，2，4。五道作業的執行時間、完成時間和周轉時間如下表所示：作業號進入時間運行時間開始執行時間完成時間周轉時間1040443264108544101410213141716432171916平均周轉時間t（4+8+10+16+16）/ 5=

34、10.8小時平均帶權周轉時間w=(4/4+8/6+10/4+16/3+16/2) / 5=3.63 54 5 最高響應比優先調度算法最高響應比優先調度算法 n響應比計算公式：響應比計算公式：最高響應比優先（highest response_ratio next，hrn）調度算法是fcfs和sjf的一種折衷。hrn調度算法同時考慮每個作業的等待時間和估計的運行時間。設響應比為r，則作業p的響應比為：twttwrp1式中，w為作業的等待時間，t為作業的估計運行時間。 54 5 最高響應比優先調度算法最高響應比優先調度算法 n算法思想：算法思想：在當前進程完成或被阻塞時，選擇rp值最大的就緒進程投入

35、運行。n優點：優點：即考慮了作業的等待時間，又照顧了短作業。 54 5 最高響應比優先調度算法最高響應比優先調度算法 【例5-4】假設有五道作業，它們的進入時間、運行時間由下表給出：系統采用hrn調度算法，試計算采用該調度算法時的平均周轉時間和平均帶權周轉時間。作業號進入時間運行時間106214324431543 54 5 最高響應比優先調度算法最高響應比優先調度算法 解：解：采用hrn調度算法，應在每次調度時計算各作業的響應比，選擇響應比高的作業進入運行狀態。 在時刻0，由于只有作業1，因此調度作業1投入運行，作業1運行到時刻6結束，在時刻6時進行調度； 在時刻6，計算各作業的響應比為： 作

36、業2的響應比：r2=1+（6-1）/4=2.25 作業3的響應比：r3=1+（6-2）/4=2 作業4的響應比：r4=1+（6-3）/1=4 作業5的響應比：r5=1+（6-4）/3=1.67 選擇作業4投入運行，作業4運行到時刻7時結束，在時刻7時進行調度； 54 5 最高響應比優先調度算法最高響應比優先調度算法 在時刻7，計算各作業的響應比為： 作業2的響應比：r2=1+（7-1）/4=2.5 作業3的響應比：r3=1+（7-2）/4=2.25 作業5的響應比：r5=1+（7-4）/3=2 選擇作業2投入運行，作業2運行到時刻11時結束，在時刻11時進行調度； 作業3的響應比：r3=1+（

37、11-2）/4=3.25 作業5的響應比：r5=1+（11-4）/3=3.33 選擇作業5投入運行，作業5運行到時刻14時結束，在時刻14時進行調度； 在時刻14，只有作業3等待運行，因此五道作業的調度順序是1，4，2，5，3。 54 5 最高響應比優先調度算法最高響應比優先調度算法 五道作業的執行時間、完成時間和周轉時間如下表所示：作業號進入時間運行時間（小時）開始執行時間完成時間周轉時間10606643167421471110543111410324141816平均周轉時間t（6+4+10+10+16）/ 5=9.2小時平均帶權周轉時間w=(6/6+4/1+10/4+10/3+16/4)

38、/ 5=2.97 546 多級隊列調度算法多級隊列調度算法 多級隊列調度算法（multiple-level queue，mq）的基本思想是引入多個就緒隊列，通過各隊列的區別對待，達到一個綜合的調度目標。在多級隊列調度算法中，根據作業或進程的性質或類型的不同，將就緒隊列再分成若干個子隊列，每個作業固定歸入一個隊列，例如，系統進程、用戶交互進程、批處理進程等不同隊列。不同隊列可有不同的優先級、時間片長度、調度策略等。 547 多級反饋隊列調度算法多級反饋隊列調度算法 多級反饋隊列（round robin with multiple feedback，rrmf）調度算法是時間片輪轉算法和優先級調度算法的綜合和發展。在多級反饋隊列調度算法中，通常設置