第3章調(diào)度與死鎖

1、 本章介紹內(nèi)容：本章介紹內(nèi)容：按調(diào)度的層次按調(diào)度的層次 高級調(diào)度高級調(diào)度(High Scheduling)(High Scheduling) 低級調(diào)度低級調(diào)度(Low Level Scheduling)(Low Level Scheduling) 中級調(diào)度中級調(diào)度(Intermediate-Level Scheduling)(Intermediate-Level Scheduling)按按OSOS的類型的類型 批處理調(diào)度批處理調(diào)度 分時和實時調(diào)度分時和實時調(diào)度 多處理機(jī)調(diào)度多處理機(jī)調(diào)度3.1 處理機(jī)調(diào)度的基本概念處理機(jī)調(diào)度的基本概念 1.1. 高級調(diào)度高級調(diào)度 = = 作業(yè)調(diào)度作業(yè)調(diào)度( (接

2、納調(diào)度接納調(diào)度) ) 高級調(diào)度定義：高級調(diào)度定義： 決定把那些后備隊列中的作業(yè)調(diào)入內(nèi)決定把那些后備隊列中的作業(yè)調(diào)入內(nèi)存，并為其創(chuàng)建進(jìn)程，分配必要的資源，存，并為其創(chuàng)建進(jìn)程，分配必要的資源，最后將所創(chuàng)建的進(jìn)程掛在就緒隊列上，準(zhǔn)最后將所創(chuàng)建的進(jìn)程掛在就緒隊列上，準(zhǔn)備執(zhí)行。備執(zhí)行。 高級調(diào)度高級調(diào)度的任務(wù)：的任務(wù)： 接納多少個作業(yè)：接納多少個作業(yè)：取決于允許多少個作取決于允許多少個作業(yè)同時在內(nèi)存中運行業(yè)同時在內(nèi)存中運行 接納哪些作業(yè)：接納哪些作業(yè)：取決于所采用的調(diào)度算取決于所采用的調(diào)度算法法3.1 處理機(jī)調(diào)度的基本概念處理機(jī)調(diào)度的基本概念 應(yīng)用范圍：應(yīng)用范圍：3.1 處理機(jī)調(diào)度的基本概念處理機(jī)調(diào)度的

3、基本概念 低級調(diào)度定義：低級調(diào)度定義： 決定就緒隊列中哪個進(jìn)程先獲得處理機(jī)決定就緒隊列中哪個進(jìn)程先獲得處理機(jī)，然后再由分派程序執(zhí)行將處理機(jī)分配給進(jìn)，然后再由分派程序執(zhí)行將處理機(jī)分配給進(jìn)程的操作。程的操作。低級調(diào)度任務(wù)：低級調(diào)度任務(wù)： 處理機(jī)分配。處理機(jī)分配。應(yīng)用范圍：應(yīng)用范圍： 批處理系統(tǒng)、分時系統(tǒng)和實時系統(tǒng)批處理系統(tǒng)、分時系統(tǒng)和實時系統(tǒng)特點：特點： 進(jìn)程調(diào)度運行效率很高，典型情況是幾進(jìn)程調(diào)度運行效率很高，典型情況是幾十毫秒一次十毫秒一次 3.1 處理機(jī)調(diào)度的基本概念處理機(jī)調(diào)度的基本概念 3.1 處理機(jī)調(diào)度的基本概念處理機(jī)調(diào)度的基本概念 作用：作用： 按一定算法在內(nèi)存和外存之間進(jìn)行進(jìn)程對按一定

4、算法在內(nèi)存和外存之間進(jìn)行進(jìn)程對換。換。目的：目的： 緩解內(nèi)存緊張情況緩解內(nèi)存緊張情況, ,提高內(nèi)存利用率和系統(tǒng)提高內(nèi)存利用率和系統(tǒng)吞吐量。吞吐量。任務(wù)：任務(wù)： 是將內(nèi)存中處于阻塞狀態(tài)的某些進(jìn)程換至是將內(nèi)存中處于阻塞狀態(tài)的某些進(jìn)程換至外存，騰出內(nèi)存空間以便將外存上已具備執(zhí)外存，騰出內(nèi)存空間以便將外存上已具備執(zhí)行條件的進(jìn)程換入內(nèi)存。行條件的進(jìn)程換入內(nèi)存。3.1 處理機(jī)調(diào)度的基本概念處理機(jī)調(diào)度的基本概念 CPU交互用戶交互用戶時間片完時間片完進(jìn)程調(diào)度進(jìn)程調(diào)度等待事件等待事件就就 緒緒 隊隊 列列阻阻 塞塞 隊隊 列列事件出現(xiàn)事件出現(xiàn)進(jìn)程完成進(jìn)程完成圖圖 31 僅具有進(jìn)程調(diào)度的調(diào)度隊列模型僅具有進(jìn)程調(diào)

5、度的調(diào)度隊列模型3.1 處理機(jī)調(diào)度的基本概念處理機(jī)調(diào)度的基本概念 2 2、具有高級和低級調(diào)度的調(diào)度隊列模型、具有高級和低級調(diào)度的調(diào)度隊列模型3、同時具有三級調(diào)度的調(diào)度隊列模型、同時具有三級調(diào)度的調(diào)度隊列模型3.1 處理機(jī)調(diào)度的基本概念處理機(jī)調(diào)度的基本概念 CPU時間片完時間片完進(jìn)程調(diào)度進(jìn)程調(diào)度等待事件等待事件1就就 緒緒 隊隊 列列阻阻 塞塞 隊隊 列列圖圖 32 具有高、低級調(diào)度的調(diào)度隊列模型具有高、低級調(diào)度的調(diào)度隊列模型隊隊 列列后后 備備阻阻 塞塞 隊隊 列列阻阻 塞塞 隊隊 列列等待事件等待事件2等待事件等待事件n事件出現(xiàn)事件出現(xiàn)事件出現(xiàn)事件出現(xiàn)事件事件n出現(xiàn)出現(xiàn)作業(yè)作業(yè)調(diào)度調(diào)度進(jìn)程完

6、成進(jìn)程完成交互用戶交互用戶3.1 處理機(jī)調(diào)度的基本概念處理機(jī)調(diào)度的基本概念 CPU批量作業(yè)批量作業(yè)后備隊列后備隊列作業(yè)調(diào)度作業(yè)調(diào)度時間片完時間片完交互型作業(yè)交互型作業(yè)就緒隊列就緒隊列就緒，掛起隊列就緒，掛起隊列阻塞，掛起隊列阻塞，掛起隊列阻塞隊列阻塞隊列中級調(diào)度中級調(diào)度進(jìn)程調(diào)度進(jìn)程調(diào)度進(jìn)程完成進(jìn)程完成事件出現(xiàn)事件出現(xiàn)掛起掛起等待事件等待事件事件出現(xiàn)事件出現(xiàn)圖圖 3-3 具有三級調(diào)度時的調(diào)度隊列模型具有三級調(diào)度時的調(diào)度隊列模型3.1 處理機(jī)調(diào)度的基本概念處理機(jī)調(diào)度的基本概念 四、選擇調(diào)度方式和調(diào)度算法的若干準(zhǔn)則四、選擇調(diào)度方式和調(diào)度算法的若干準(zhǔn)則一、面向用戶的準(zhǔn)則一、面向用戶的準(zhǔn)則1 1、 周轉(zhuǎn)

7、時間短（評價批處理系統(tǒng)）周轉(zhuǎn)時間短（評價批處理系統(tǒng)） 周轉(zhuǎn)時間周轉(zhuǎn)時間(T)(T)：從作業(yè)提交開始到完成止的這段從作業(yè)提交開始到完成止的這段時間間隔。時間間隔。 包括包括： （1 1）作業(yè)在外存后備隊列上等待進(jìn)入內(nèi)存的時間；）作業(yè)在外存后備隊列上等待進(jìn)入內(nèi)存的時間； （2 2）在就緒隊列上等待獲得處理機(jī)的時間；）在就緒隊列上等待獲得處理機(jī)的時間； （3 3）在）在CPUCPU上的執(zhí)行時間上的執(zhí)行時間(T(Ts s) )； （4 4）等待）等待I/OI/O操作完成的時間。操作完成的時間。 平均周轉(zhuǎn)時間：平均周轉(zhuǎn)時間： nTTnii113.1 處理機(jī)調(diào)度的基本概念處理機(jī)調(diào)度的基本概念 2 2、響應(yīng)

8、時間快（評價分時系統(tǒng)）、響應(yīng)時間快（評價分時系統(tǒng)） 響應(yīng)時間：響應(yīng)時間：指從提交一個請求開始到首次指從提交一個請求開始到首次產(chǎn)生響應(yīng)為止（顯示出結(jié)果）的一段時間間隔產(chǎn)生響應(yīng)為止（顯示出結(jié)果）的一段時間間隔。平均帶權(quán)周轉(zhuǎn)時間：平均帶權(quán)周轉(zhuǎn)時間：nTsiTnWWniinii1111STTW 帶權(quán)周轉(zhuǎn)時間：帶權(quán)周轉(zhuǎn)時間：3.1 處理機(jī)調(diào)度的基本概念處理機(jī)調(diào)度的基本概念 3 3、截止時間的保證（評價實時系統(tǒng)）、截止時間的保證（評價實時系統(tǒng)） 截止時間：截止時間：某任務(wù)必須開始或完成的最某任務(wù)必須開始或完成的最遲時間。遲時間。4 4、優(yōu)先權(quán)準(zhǔn)則、優(yōu)先權(quán)準(zhǔn)則二、二、面向系統(tǒng)的準(zhǔn)則面向系統(tǒng)的準(zhǔn)則 1 1、系

9、統(tǒng)吞吐量高、系統(tǒng)吞吐量高 系統(tǒng)吞吐量是評價批處理系統(tǒng)性能的重要指標(biāo)系統(tǒng)吞吐量是評價批處理系統(tǒng)性能的重要指標(biāo)。是選擇批處理作業(yè)調(diào)度的重要準(zhǔn)則。是選擇批處理作業(yè)調(diào)度的重要準(zhǔn)則。 影響系統(tǒng)吞吐量的因素：影響系統(tǒng)吞吐量的因素：作業(yè)的平均長度、調(diào)作業(yè)的平均長度、調(diào)度方式和算法。度方式和算法。3.1 處理機(jī)調(diào)度的基本概念處理機(jī)調(diào)度的基本概念 單位時間內(nèi)單位時間內(nèi)系統(tǒng)所完成系統(tǒng)所完成的作業(yè)數(shù)量的作業(yè)數(shù)量2 2、處理機(jī)利用率好、處理機(jī)利用率好 對大、中型多用戶系統(tǒng)，處理機(jī)利用率是衡量對大、中型多用戶系統(tǒng)，處理機(jī)利用率是衡量系統(tǒng)性能的十分重要的指標(biāo)。系統(tǒng)性能的十分重要的指標(biāo)。 對單用戶微型機(jī)或某些實時系統(tǒng)，該準(zhǔn)

10、則并不對單用戶微型機(jī)或某些實時系統(tǒng)，該準(zhǔn)則并不重要。重要。 影響系統(tǒng)吞吐量的因素：影響系統(tǒng)吞吐量的因素：調(diào)度方式和算法調(diào)度方式和算法3 3、各類資源的平衡利用、各類資源的平衡利用 對大、中型系統(tǒng)重要。對微型機(jī)或某些實時系對大、中型系統(tǒng)重要。對微型機(jī)或某些實時系統(tǒng)，該準(zhǔn)則并不重要。統(tǒng)，該準(zhǔn)則并不重要。 影響系統(tǒng)吞吐量的因素：影響系統(tǒng)吞吐量的因素：調(diào)度方式和算法調(diào)度方式和算法 3.1 處理機(jī)調(diào)度的基本概念處理機(jī)調(diào)度的基本概念 3.2 調(diào)度算法調(diào)度算法 先來先服務(wù)調(diào)度算法先來先服務(wù)調(diào)度算法(FCFS)FCFSFCFS原理原理: :就緒隊列按進(jìn)入的先后次序排列，調(diào)度就緒隊列按進(jìn)入的先后次序排列，調(diào)度時

11、，選則隊首進(jìn)程投入運行。時，選則隊首進(jìn)程投入運行。調(diào)度算法調(diào)度算法: : 指根據(jù)系統(tǒng)的資源分配策略所規(guī)定的資指根據(jù)系統(tǒng)的資源分配策略所規(guī)定的資源分配算法。源分配算法。3.2 調(diào)度算法調(diào)度算法 先來先服務(wù)調(diào)度算法先來先服務(wù)調(diào)度算法(FCFS)進(jìn)程名進(jìn)程名到達(dá)時間到達(dá)時間服務(wù)時間服務(wù)時間開始執(zhí)行開始執(zhí)行時時 間間完成時間完成時間周轉(zhuǎn)時間周轉(zhuǎn)時間帶權(quán)周轉(zhuǎn)帶權(quán)周轉(zhuǎn)時時 間間 A B C D 0 1 2 3 1 100 1 100 0 1 101 102 1 101 102 202 1 100 100 199 1 1 100 1.99不同進(jìn)程的周轉(zhuǎn)時間及帶權(quán)周轉(zhuǎn)時間不同進(jìn)程的周轉(zhuǎn)時間及帶權(quán)周轉(zhuǎn)時間 作作

12、調(diào)調(diào) 業(yè)業(yè) 度度 調(diào)調(diào) 算算 度度 法法進(jìn)進(jìn) 程程 名名A B C D E平均平均到到 達(dá)達(dá) 時時 間間 0 1 2 3 4服服 務(wù)務(wù) 時時 間間 4 3 5 2 4 FCFS （a） 完完 成成 時時 間間 4 7 12 14 18周周 轉(zhuǎn)轉(zhuǎn) 時時 間間 4 6 10 11 14 9帶權(quán)周轉(zhuǎn)時間帶權(quán)周轉(zhuǎn)時間 1 2 25.5 3.5 2.8 SJF (b)完完 成成 時時 間間 4 9 18 6 13周周 轉(zhuǎn)轉(zhuǎn) 時時 間間 4 8 16 3 9 8帶權(quán)周轉(zhuǎn)時間帶權(quán)周轉(zhuǎn)時間 1 2.67 3.1 1.5 2.25 2.1圖圖 3-4 FCFS 和和SJF調(diào)度算法的性能調(diào)度算法的性能3.2 調(diào)度

13、算法調(diào)度算法 短作業(yè)短作業(yè)(進(jìn)程進(jìn)程)優(yōu)先調(diào)度算法優(yōu)先調(diào)度算法3.2 調(diào)度算法調(diào)度算法 優(yōu)先權(quán)調(diào)度算法優(yōu)先權(quán)調(diào)度算法基本思想基本思想: :為作業(yè)或進(jìn)程設(shè)置優(yōu)先級為作業(yè)或進(jìn)程設(shè)置優(yōu)先級, ,調(diào)度調(diào)度時按優(yōu)先級的高低進(jìn)行調(diào)度。時按優(yōu)先級的高低進(jìn)行調(diào)度。應(yīng)用范圍應(yīng)用范圍: :用于批處理系統(tǒng)中的作業(yè)調(diào)度用于批處理系統(tǒng)中的作業(yè)調(diào)度算法、多種操作系統(tǒng)及實時系統(tǒng)中的進(jìn)程算法、多種操作系統(tǒng)及實時系統(tǒng)中的進(jìn)程調(diào)度算法。調(diào)度算法。作業(yè)調(diào)度：作業(yè)調(diào)度：從后備隊列中選擇若干個優(yōu)先從后備隊列中選擇若干個優(yōu)先權(quán)最高的作業(yè)調(diào)入內(nèi)存。權(quán)最高的作業(yè)調(diào)入內(nèi)存。進(jìn)程調(diào)度：進(jìn)程調(diào)度：是把處理機(jī)分配給就緒隊列中是把處理機(jī)分配給就緒隊列

14、中具有最高優(yōu)先權(quán)的進(jìn)程。具有最高優(yōu)先權(quán)的進(jìn)程。1 1、 算法的兩種方式算法的兩種方式3.2 調(diào)度算法調(diào)度算法 優(yōu)先權(quán)調(diào)度算法優(yōu)先權(quán)調(diào)度算法(1)(1)非搶占式優(yōu)先權(quán)算法非搶占式優(yōu)先權(quán)算法：處理機(jī)分配給就緒：處理機(jī)分配給就緒隊列優(yōu)先權(quán)最高的進(jìn)程。隊列優(yōu)先權(quán)最高的進(jìn)程。應(yīng)用范圍：應(yīng)用范圍：批處理系統(tǒng)、實時性要求不嚴(yán)的批處理系統(tǒng)、實時性要求不嚴(yán)的實時系統(tǒng)。實時系統(tǒng)。(2)(2)搶占式優(yōu)先權(quán)調(diào)度算法：搶占式優(yōu)先權(quán)調(diào)度算法：出現(xiàn)另一個優(yōu)先出現(xiàn)另一個優(yōu)先權(quán)更高的進(jìn)程時停止原來執(zhí)行進(jìn)程，把處理權(quán)更高的進(jìn)程時停止原來執(zhí)行進(jìn)程，把處理機(jī)分配給新出現(xiàn)的優(yōu)先權(quán)最高的進(jìn)程。機(jī)分配給新出現(xiàn)的優(yōu)先權(quán)最高的進(jìn)程。應(yīng)用范圍：

15、應(yīng)用范圍：實時性要求比較嚴(yán)格的實時系統(tǒng)實時性要求比較嚴(yán)格的實時系統(tǒng)、對性能要求較高的批處理和分時系統(tǒng)中。、對性能要求較高的批處理和分時系統(tǒng)中。2 2、確定進(jìn)程優(yōu)先權(quán)的方法、確定進(jìn)程優(yōu)先權(quán)的方法 對于最高優(yōu)先權(quán)算法，關(guān)鍵在于采用何對于最高優(yōu)先權(quán)算法，關(guān)鍵在于采用何種優(yōu)先權(quán)（靜態(tài)優(yōu)先權(quán)或動態(tài)優(yōu)先權(quán)）、以種優(yōu)先權(quán)（靜態(tài)優(yōu)先權(quán)或動態(tài)優(yōu)先權(quán)）、以及如何確定進(jìn)程的優(yōu)先權(quán)。及如何確定進(jìn)程的優(yōu)先權(quán)。(1) (1) 靜態(tài)優(yōu)先權(quán)靜態(tài)優(yōu)先權(quán) 在創(chuàng)建進(jìn)程時確定、在整個運行期間不改變。在創(chuàng)建進(jìn)程時確定、在整個運行期間不改變。 優(yōu)先權(quán)大小用優(yōu)先數(shù)表示。優(yōu)先權(quán)大小用優(yōu)先數(shù)表示。 進(jìn)程類型進(jìn)程類型 進(jìn)程對資源的需求進(jìn)程對資源

16、的需求 用戶要求的優(yōu)先級用戶要求的優(yōu)先級3.2 調(diào)度算法調(diào)度算法 優(yōu)先權(quán)調(diào)度算法優(yōu)先權(quán)調(diào)度算法特點：特點： 算法簡單易行，系統(tǒng)開銷小，不夠算法簡單易行，系統(tǒng)開銷小，不夠 精確精確。用于要求不太高的系統(tǒng)。用于要求不太高的系統(tǒng)。3.2 調(diào)度算法調(diào)度算法 優(yōu)先權(quán)調(diào)度算法優(yōu)先權(quán)調(diào)度算法 (2) (2) 動態(tài)優(yōu)先權(quán)動態(tài)優(yōu)先權(quán)基于某種原則，進(jìn)程創(chuàng)建時賦予的優(yōu)先權(quán)可基于某種原則，進(jìn)程創(chuàng)建時賦予的優(yōu)先權(quán)可以隨時間而改變，以便獲得更好的調(diào)度性。以隨時間而改變，以便獲得更好的調(diào)度性。 如如: :進(jìn)程隨等待時間的增加，優(yōu)先權(quán)以速進(jìn)程隨等待時間的增加，優(yōu)先權(quán)以速率率a a增加。增加。3.2 調(diào)度算法調(diào)度算法 高響應(yīng)比

17、優(yōu)先高響應(yīng)比優(yōu)先(HRRN)調(diào)度算法調(diào)度算法 短作業(yè)優(yōu)先算法短作業(yè)優(yōu)先算法 + + 動態(tài)優(yōu)先權(quán)調(diào)度算法動態(tài)優(yōu)先權(quán)調(diào)度算法(1) (1) 算法描述算法描述 等待時間等待時間 + + 要求服務(wù)時間要求服務(wù)時間 響應(yīng)時間響應(yīng)時間優(yōu)先權(quán)優(yōu)先權(quán)= - = - = Rp= - = - = Rp 要求服務(wù)時間要求服務(wù)時間 要求服務(wù)時間要求服務(wù)時間(2) (2) 特點特點如果作業(yè)的等待時間相同，則要求服務(wù)的如果作業(yè)的等待時間相同，則要求服務(wù)的時間愈短，其優(yōu)先權(quán)愈高，因而該算法有利時間愈短，其優(yōu)先權(quán)愈高，因而該算法有利于短作業(yè)；于短作業(yè)；當(dāng)要求服務(wù)的時間相同時，作業(yè)的優(yōu)先權(quán)當(dāng)要求服務(wù)的時間相同時，作業(yè)的優(yōu)先權(quán)決

18、定于等待時間，因而是實現(xiàn)了先來先服務(wù)決定于等待時間，因而是實現(xiàn)了先來先服務(wù)（FCFSFCFS）；）；對于長作業(yè)，當(dāng)其等待時間足夠長時，其對于長作業(yè)，當(dāng)其等待時間足夠長時，其優(yōu)先權(quán)便可升到很高，從而也可獲得處理機(jī)優(yōu)先權(quán)便可升到很高，從而也可獲得處理機(jī) 調(diào)度之前都需先進(jìn)行響應(yīng)比的計算，增加調(diào)度之前都需先進(jìn)行響應(yīng)比的計算，增加了系統(tǒng)的開銷。了系統(tǒng)的開銷。3.2 調(diào)度算法調(diào)度算法 高響應(yīng)比優(yōu)先調(diào)度算法高響應(yīng)比優(yōu)先調(diào)度算法3.2 調(diào)度算法調(diào)度算法 時間片輪轉(zhuǎn)時間片輪轉(zhuǎn)(RR)調(diào)度算法調(diào)度算法t 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 (a)q=1(b)q=

19、4ABCDEAAAACDEBBCDEBCECE圖圖 3-5 q=1 和和 q=4 時進(jìn)程運行情況時進(jìn)程運行情況 作作時時 業(yè)業(yè) 間間 情情 片片 況況 進(jìn)進(jìn) 程程 名名A B C D E平均平均到到 達(dá)達(dá) 時時 間間 0 1 2 3 4服服 務(wù)務(wù) 時時 間間 4 3 4 2 4 RR q=1 完完 成成 時時 間間 15 12 16 9 17周周 轉(zhuǎn)轉(zhuǎn) 時時 間間 15 11 14 6 13 11.8帶權(quán)周轉(zhuǎn)時間帶權(quán)周轉(zhuǎn)時間 3.75 3.67 3.5 3 3.33 3.46 RR q=4完完 成成 時時 間間 4 7 1113 17周周 轉(zhuǎn)轉(zhuǎn) 時時 間間 4 6 910 13 8.4帶權(quán)周轉(zhuǎn)

20、時間帶權(quán)周轉(zhuǎn)時間 1 22.25 53.33 2.5圖圖 3-6 q=1 和和 q=4 時的周轉(zhuǎn)時間時的周轉(zhuǎn)時間3.2 調(diào)度算法調(diào)度算法 多級反饋隊列調(diào)度算法多級反饋隊列調(diào)度算法 基本思想：基本思想： 設(shè)置了多個就緒隊列，并賦予各隊設(shè)置了多個就緒隊列，并賦予各隊列不同的優(yōu)先權(quán)。第一個隊列的優(yōu)先權(quán)列不同的優(yōu)先權(quán)。第一個隊列的優(yōu)先權(quán)最高，其余隊列的優(yōu)先權(quán)逐個降低。最高，其余隊列的優(yōu)先權(quán)逐個降低。1 1、調(diào)度算法、調(diào)度算法（1 1）設(shè)置多個就緒隊列，并為各個隊列賦予）設(shè)置多個就緒隊列，并為各個隊列賦予不同的優(yōu)先權(quán)。不同的優(yōu)先權(quán)。（2 2）賦予各個隊列中進(jìn)程執(zhí)行時間片的大小）賦予各個隊列中進(jìn)程執(zhí)行時間

21、片的大小也各不相同優(yōu)先權(quán)愈高，時間片愈小。也各不相同優(yōu)先權(quán)愈高，時間片愈小。（3 3）新進(jìn)程進(jìn)入內(nèi)存后，放在第一隊列未尾）新進(jìn)程進(jìn)入內(nèi)存后，放在第一隊列未尾，先來先服務(wù)；一個時間片內(nèi)運行不完，則，先來先服務(wù)；一個時間片內(nèi)運行不完，則轉(zhuǎn)下一隊列。轉(zhuǎn)下一隊列。（4 4）按隊列順序運行）按隊列順序運行 , ,最后一個隊列按時間最后一個隊列按時間片輪轉(zhuǎn)，其余按片輪轉(zhuǎn)，其余按FCFSFCFS運行。運行。3.2 調(diào)度算法調(diào)度算法 多級反饋隊列多級反饋隊列(MFQ)調(diào)度算法調(diào)度算法 FCFS時間片時間片輪轉(zhuǎn)輪轉(zhuǎn)時間片：時間片：S1S2S3Sn圖圖 3-7 多級反饋隊列調(diào)度算法多級反饋隊列調(diào)度算法對列優(yōu)先權(quán)對

22、列優(yōu)先權(quán)底底高高2 2、性能、性能注意：注意： 該算法具有較好的性能，能較好地滿足該算法具有較好的性能，能較好地滿足各種類型用戶的需要。各種類型用戶的需要。 終端型用戶終端型用戶 短批處理作業(yè)用戶短批處理作業(yè)用戶 長批處理作業(yè)用戶長批處理作業(yè)用戶3.2 調(diào)度算法調(diào)度算法 多級反饋隊列調(diào)度算法多級反饋隊列調(diào)度算法 w w 至今至今, ,在系統(tǒng)中用于等待和執(zhí)行所花在系統(tǒng)中用于等待和執(zhí)行所花費的時間。費的時間。e e 至今為此在至今為此在CPUCPU上執(zhí)行用去的時間。上執(zhí)行用去的時間。s s 進(jìn)程所需的總體運行時間（包括進(jìn)程所需的總體運行時間（包括e e） 幾種常用調(diào)度算法的比較幾種常用調(diào)度算法的比

23、較3.2 調(diào)度算法調(diào)度算法 算法比較項目FCFS先來先服務(wù)RR時間片輪轉(zhuǎn)SJF短作業(yè)優(yōu)先優(yōu)先權(quán)HRRF高響應(yīng)比優(yōu)先MFQ多級反饋選擇依據(jù)maxw常量mins見正文max(w+s)/s)見正文調(diào)度方式非搶占式搶占式（按時間片）非搶占式搶占式（進(jìn)程到達(dá)時）非搶占式搶占式（按時間片）吞吐量不突出如果時間片太小，可能很低高高高不突出響應(yīng)時間可能很高，特別在進(jìn)程執(zhí)行時間有很大變化時對于短進(jìn)程提供良好的響應(yīng)時間對于短作業(yè)（進(jìn)程）提供良好的響應(yīng)時間提供良好的響應(yīng)時間提供良好的響應(yīng)時間不突出開銷最小低可能高可能高可能高可能高對進(jìn)程的影響不利于短作業(yè)（進(jìn)程）和I/O繁忙型作業(yè)（進(jìn)程）公平對待不利于長作業(yè)（進(jìn)程）

24、不利于長進(jìn)程良好的均衡可能偏愛I/O繁忙型作業(yè)（進(jìn)程）“饑餓”問題無無可能可能無可能圖圖3-8 幾種常用調(diào)度算法的比較幾種常用調(diào)度算法的比較3.3 實時調(diào)度實時調(diào)度 實時進(jìn)程或任務(wù)往往帶有某種程度的緊迫實時進(jìn)程或任務(wù)往往帶有某種程度的緊迫性，因而對實時系統(tǒng)中的調(diào)度提出了某些特殊性，因而對實時系統(tǒng)中的調(diào)度提出了某些特殊的要求。的要求。一、實現(xiàn)實時調(diào)度的基本條件一、實現(xiàn)實時調(diào)度的基本條件 提供必要的調(diào)度信息提供必要的調(diào)度信息就緒時間就緒時間截止時間截止時間處理時間處理時間資源要求資源要求優(yōu)先級優(yōu)先級 系統(tǒng)處理能力強(qiáng)系統(tǒng)處理能力強(qiáng) 調(diào)度方式搶占調(diào)度方式調(diào)度方式搶占調(diào)度方式 具有快速切換機(jī)制具有快速切

25、換機(jī)制3.3 實時調(diào)度實時調(diào)度 二、實時調(diào)度算法的類型二、實時調(diào)度算法的類型n按實時任務(wù)性質(zhì)劃分按實時任務(wù)性質(zhì)劃分 硬實時調(diào)度算法與軟實時調(diào)度算法硬實時調(diào)度算法與軟實時調(diào)度算法n按調(diào)度方式劃分按調(diào)度方式劃分 搶占與非搶占調(diào)度算法搶占與非搶占調(diào)度算法n按調(diào)度時間劃分按調(diào)度時間劃分 靜態(tài)調(diào)度算法與動態(tài)調(diào)度算法靜態(tài)調(diào)度算法與動態(tài)調(diào)度算法n多處理機(jī)環(huán)境多處理機(jī)環(huán)境 集中式與分布式集中式與分布式3.3 實時調(diào)度實時調(diào)度 三、按調(diào)度方式劃分的實時調(diào)度算法（三、按調(diào)度方式劃分的實時調(diào)度算法（算法算法） 非搶占方式非搶占方式: : 非搶占輪轉(zhuǎn)調(diào)度算法非搶占輪轉(zhuǎn)調(diào)度算法 、非搶占優(yōu)先調(diào)度算法、非搶占優(yōu)先調(diào)度算法

26、 搶占方式搶占方式: : 1 1、基于時鐘中斷的搶占式優(yōu)先權(quán)調(diào)度算、基于時鐘中斷的搶占式優(yōu)先權(quán)調(diào)度算法法 2 2立即搶占立即搶占(Immediate Preemption)(Immediate Preemption)的的優(yōu)先權(quán)調(diào)度算法優(yōu)先權(quán)調(diào)度算法3.3 實時調(diào)度實時調(diào)度 調(diào)度算法調(diào)度算法調(diào)度方式調(diào)度方式響應(yīng)時間響應(yīng)時間應(yīng)用范圍應(yīng)用范圍非搶占輪轉(zhuǎn)非搶占輪轉(zhuǎn)非搶占非搶占數(shù)秒數(shù)秒-數(shù)十秒數(shù)十秒實時要求不嚴(yán)實時要求不嚴(yán)格的控制系統(tǒng)格的控制系統(tǒng)非搶占優(yōu)先權(quán)非搶占優(yōu)先權(quán)非搶占非搶占數(shù)秒數(shù)秒-數(shù)百毫數(shù)百毫秒秒有實時要求的有實時要求的控制系統(tǒng)控制系統(tǒng)基于時鐘中斷搶基于時鐘中斷搶占優(yōu)先權(quán)占優(yōu)先權(quán)搶占搶占數(shù)豪秒

27、數(shù)豪秒-數(shù)十?dāng)?shù)十毫秒毫秒多數(shù)實時要求多數(shù)實時要求較嚴(yán)格的實時較嚴(yán)格的實時系統(tǒng)系統(tǒng)立即搶占優(yōu)先權(quán)立即搶占優(yōu)先權(quán)搶占搶占100微秒微秒-數(shù)豪秒數(shù)豪秒實時要求嚴(yán)格實時要求嚴(yán)格的實時系統(tǒng)的實時系統(tǒng)各種實時調(diào)度算法對比各種實時調(diào)度算法對比三、常用實時調(diào)度算法三、常用實時調(diào)度算法 最早截止時間優(yōu)先最早截止時間優(yōu)先( (EDFEDF Earliest Deadline First)算法算法 按截止時間來確定任務(wù)的優(yōu)先級。按截止時間來確定任務(wù)的優(yōu)先級。 最低松弛度優(yōu)先算法最低松弛度優(yōu)先算法( (LLFLLF) ) 按任務(wù)的緊急（或松弛）程度確定任務(wù)按任務(wù)的緊急（或松弛）程度確定任務(wù)的優(yōu)先級。的優(yōu)先級。 調(diào)度時

28、選擇松弛度最小的先執(zhí)行。調(diào)度時選擇松弛度最小的先執(zhí)行。 松弛度松弛度= =必須完成時間必須完成時間- -本身運行時間本身運行時間- -當(dāng)當(dāng)前時間前時間 3.3 實時調(diào)度實時調(diào)度 （a）非搶占式輪轉(zhuǎn)調(diào)）非搶占式輪轉(zhuǎn)調(diào)度度實時進(jìn)程請求調(diào)度實時進(jìn)程請求調(diào)度調(diào)度實時進(jìn)程運行調(diào)度實時進(jìn)程運行實時進(jìn)程實時進(jìn)程進(jìn)程進(jìn)程1進(jìn)程進(jìn)程2進(jìn)程進(jìn)程n調(diào)度時間調(diào)度時間(b）優(yōu)先權(quán)非搶占調(diào)度優(yōu)先權(quán)非搶占調(diào)度實時進(jìn)程請求調(diào)度實時進(jìn)程請求調(diào)度調(diào)度實時進(jìn)程運行調(diào)度實時進(jìn)程運行調(diào)度時間調(diào)度時間當(dāng)前進(jìn)程當(dāng)前進(jìn)程實時進(jìn)程實時進(jìn)程（c）基于時鐘中斷搶）基于時鐘中斷搶占優(yōu)先權(quán)調(diào)度占優(yōu)先權(quán)調(diào)度實時進(jìn)程請求調(diào)度實時進(jìn)程請求調(diào)度調(diào)度實時進(jìn)程運

29、行調(diào)度實時進(jìn)程運行當(dāng)前進(jìn)程當(dāng)前進(jìn)程實時進(jìn)程實時進(jìn)程調(diào)度時間調(diào)度時間（d）立即搶占的優(yōu)立即搶占的優(yōu)先權(quán)調(diào)度先權(quán)調(diào)度實時進(jìn)程請求調(diào)度實時進(jìn)程請求調(diào)度實時進(jìn)程搶占當(dāng)前進(jìn)程，實時進(jìn)程搶占當(dāng)前進(jìn)程，并立即執(zhí)行并立即執(zhí)行當(dāng)前進(jìn)程當(dāng)前進(jìn)程實時進(jìn)程實時進(jìn)程調(diào)度時間調(diào)度時間圖圖 3-9 實時進(jìn)程調(diào)度實時進(jìn)程調(diào)度圖圖 3-10EDF算法用于非搶占調(diào)度方式算法用于非搶占調(diào)度方式開始截止時間開始截止時間執(zhí)行任務(wù)執(zhí)行任務(wù)任務(wù)到達(dá)任務(wù)到達(dá)1 342t12 343.3 實時調(diào)度實時調(diào)度 1342圖圖 3-11 利用利用LLF算法進(jìn)行調(diào)度的情況算法進(jìn)行調(diào)度的情況0 10 20 30 40 50 60 70 80 90 100

30、 110 120 130 140 150 160A1 A2 A3 A4 A5 A6 A7 A8B1B2B3B 的一個周期的一個周期A 的一個周期的一個周期0 10 30 40 45 55 70 80 90 100 110 130 140B1(20)B1(5)B2(15)B2(10)B3(20)A1 A2 A3 A4 A5 A6 A7 B 的第一個周期的第一個周期B 的第二個周期的第二個周期B 的第三個周期的第三個周期完成截止時間完成截止時間3.4 多處理機(jī)調(diào)度多處理機(jī)調(diào)度 一、進(jìn)程分配一、進(jìn)程分配 在多處理機(jī)系統(tǒng)在多處理機(jī)系統(tǒng)(MPS)(MPS)中，進(jìn)程的中，進(jìn)程的分配與系統(tǒng)結(jié)構(gòu)（同構(gòu)系統(tǒng)、異

31、構(gòu)系統(tǒng)分配與系統(tǒng)結(jié)構(gòu)（同構(gòu)系統(tǒng)、異構(gòu)系統(tǒng)）有關(guān)。此外，還與）有關(guān)。此外，還與OSOS的工作模式密切的工作模式密切相關(guān)。相關(guān)。v同構(gòu)系統(tǒng)同構(gòu)系統(tǒng)v異構(gòu)系統(tǒng)異構(gòu)系統(tǒng) 3.4 多處理機(jī)調(diào)度多處理機(jī)調(diào)度 3.4 多處理機(jī)調(diào)度多處理機(jī)調(diào)度 動態(tài)分配：動態(tài)分配： 在系統(tǒng)中設(shè)置一個公共就緒隊列，系統(tǒng)中在系統(tǒng)中設(shè)置一個公共就緒隊列，系統(tǒng)中的所有就緒進(jìn)程都放在該隊列中。分配處理機(jī)的所有就緒進(jìn)程都放在該隊列中。分配處理機(jī)時，對一進(jìn)程而言，可隨機(jī)分配到任意一臺處時，對一進(jìn)程而言，可隨機(jī)分配到任意一臺處理機(jī)上。理機(jī)上。 特點：特點：系統(tǒng)中的進(jìn)程可以在任意一個處理機(jī)系統(tǒng)中的進(jìn)程可以在任意一個處理機(jī)上運行。上運行。 優(yōu)點

32、：優(yōu)點：消除了處理機(jī)忙閑不均的現(xiàn)象消除了處理機(jī)忙閑不均的現(xiàn)象 缺點：缺點：增大進(jìn)程調(diào)度的開銷增大進(jìn)程調(diào)度的開銷、非對稱多處理機(jī)系統(tǒng)（異構(gòu)型）中的進(jìn)程、非對稱多處理機(jī)系統(tǒng)（異構(gòu)型）中的進(jìn)程分配分配 OSOS大多采用主從（大多采用主從（Master/SlaveMaster/Slave）式）式OSOS，即，即OSOS的核心駐留在主機(jī)上的核心駐留在主機(jī)上(Master)(Master)，而從機(jī)，而從機(jī)(Slave)(Slave)只是執(zhí)行用戶程序，進(jìn)程調(diào)度只由主只是執(zhí)行用戶程序，進(jìn)程調(diào)度只由主機(jī)執(zhí)行。機(jī)執(zhí)行。 優(yōu)點：優(yōu)點：主機(jī)獨自處理，同步問題簡單。主機(jī)獨自處理，同步問題簡單。 缺點：缺點：主機(jī)一旦故障

33、，會使整個系統(tǒng)癱瘓。主機(jī)一旦故障，會使整個系統(tǒng)癱瘓。主機(jī)太忙，形成系統(tǒng)瓶頸。主機(jī)太忙，形成系統(tǒng)瓶頸。3.4 多處理機(jī)調(diào)度多處理機(jī)調(diào)度3.4 多處理機(jī)調(diào)度多處理機(jī)調(diào)度 二、進(jìn)（線）程調(diào)度方式二、進(jìn)（線）程調(diào)度方式 1 1、自調(diào)度方式：、自調(diào)度方式： 系統(tǒng)中有一個公共的線程或進(jìn)程隊列，系統(tǒng)中有一個公共的線程或進(jìn)程隊列，所有的處理機(jī)在空閑時，都可自己從該隊列所有的處理機(jī)在空閑時，都可自己從該隊列中取出一個進(jìn)程或線程運行。中取出一個進(jìn)程或線程運行。 優(yōu)點：優(yōu)點： （1 1）只要就緒隊列不空，就不會出現(xiàn)處理只要就緒隊列不空，就不會出現(xiàn)處理機(jī)空閑。機(jī)空閑。 （2 2） 系統(tǒng)中沒有集中調(diào)度機(jī)制，處理機(jī)可系統(tǒng)

34、中沒有集中調(diào)度機(jī)制，處理機(jī)可以利用以利用OSOS的調(diào)度程序選擇一個線程。的調(diào)度程序選擇一個線程。 （3 3）對就緒隊列可按單處理機(jī)采用的各種）對就緒隊列可按單處理機(jī)采用的各種方式組織，調(diào)度算法也可沿用單處理機(jī)用的算法。方式組織，調(diào)度算法也可沿用單處理機(jī)用的算法。3.4 多處理機(jī)調(diào)度多處理機(jī)調(diào)度缺點：缺點： （1 1）瓶頸問題）瓶頸問題 （2 2）低效性）低效性 （3 3）線程切換頻繁）線程切換頻繁有代表性的三種自調(diào)度算法：有代表性的三種自調(diào)度算法： 1 1、FCFSFCFS 2 2最高優(yōu)先權(quán)優(yōu)先的算法最高優(yōu)先權(quán)優(yōu)先的算法 3 3、搶占式最高優(yōu)先權(quán)優(yōu)先算法、搶占式最高優(yōu)先權(quán)優(yōu)先算法3.4 多處理

35、機(jī)調(diào)度多處理機(jī)調(diào)度特點：特點： （1 1）減少線程的切換，改善系統(tǒng)性能。）減少線程的切換，改善系統(tǒng)性能。 （2 2）顯著減少調(diào)度頻率，從而減少了系統(tǒng)開銷。）顯著減少調(diào)度頻率，從而減少了系統(tǒng)開銷。成組調(diào)度的處理機(jī)時間分配方式：成組調(diào)度的處理機(jī)時間分配方式： 1 1、面向所有的應(yīng)用程序平均分配處理機(jī)時間、面向所有的應(yīng)用程序平均分配處理機(jī)時間 2 2、面向所有的線程平均分配處理機(jī)時間、面向所有的線程平均分配處理機(jī)時間2 2、成組調(diào)度：、成組調(diào)度： 系統(tǒng)將一組相關(guān)的進(jìn)程或線程同時分配到一組系統(tǒng)將一組相關(guān)的進(jìn)程或線程同時分配到一組處理機(jī)上運行，在應(yīng)用程序未結(jié)束之前，處理機(jī)專處理機(jī)上運行，在應(yīng)用程序未結(jié)束

36、之前，處理機(jī)專用于處理這組線程。用于處理這組線程。3.4 多處理機(jī)調(diào)度多處理機(jī)調(diào)度3 3、專用處理機(jī)分配方式：、專用處理機(jī)分配方式： 它是將同屬于一個應(yīng)用程序的一組線程，它是將同屬于一個應(yīng)用程序的一組線程，分配到一組處理機(jī)上運行，每個線程一個處理分配到一組處理機(jī)上運行，每個線程一個處理機(jī)。在應(yīng)用程序未結(jié)束前，處理機(jī)專用于處理機(jī)。在應(yīng)用程序未結(jié)束前，處理機(jī)專用于處理這組線程。這組線程。特點：特點： 處理機(jī)浪費嚴(yán)重。處理機(jī)浪費嚴(yán)重。應(yīng)用范圍：應(yīng)用范圍： 用于并發(fā)程度相當(dāng)高的多處理機(jī)環(huán)境。用于并發(fā)程度相當(dāng)高的多處理機(jī)環(huán)境。 進(jìn)程進(jìn)程P2打印機(jī)打印機(jī)R1磁帶機(jī)磁帶機(jī)R2進(jìn)程進(jìn)程P13.5 產(chǎn)生死鎖的原

37、因和必要條件產(chǎn)生死鎖的原因和必要條件 產(chǎn)生死鎖的原因產(chǎn)生死鎖的原因3.5 產(chǎn)生死鎖的原因和必要條件產(chǎn)生死鎖的原因和必要條件 產(chǎn)生死鎖的原因產(chǎn)生死鎖的原因進(jìn)程進(jìn)程P1進(jìn)程進(jìn)程P2消息消息S3消息消息S1進(jìn)程進(jìn)程P3死死鎖鎖消息消息S2 P1Req(R1) P1Req(R2) P1Rel(R1) P1Rel(R2) P2Req(R1)P2Req(R2)P2Rel(R1)P2Rel(R2)3.5 產(chǎn)生死鎖的原因和必要條件產(chǎn)生死鎖的原因和必要條件 產(chǎn)生死鎖的原因產(chǎn)生死鎖的原因 在發(fā)生死鎖時，必然存在一個進(jìn)程在發(fā)生死鎖時，必然存在一個進(jìn)程 - - 資源的環(huán)行鏈。即資源的環(huán)行鏈。即進(jìn)程集合進(jìn)程集合 P0,

38、P1, P0,P1, PnPn 對資源的請求成環(huán)狀：對資源的請求成環(huán)狀：P0 P1 P2 P0 P1 P2 PnPn P0 P0綜上所述可以看出，在同時具備下列四個必要條件時，就會產(chǎn)生死鎖綜上所述可以看出，在同時具備下列四個必要條件時，就會產(chǎn)生死鎖3.5 產(chǎn)生死鎖的原因和必要條件產(chǎn)生死鎖的原因和必要條件 產(chǎn)生死鎖的必要條件產(chǎn)生死鎖的必要條件3.5 產(chǎn)生死鎖的原因和必要條件產(chǎn)生死鎖的原因和必要條件 處理死鎖的基本方法處理死鎖的基本方法3.6 預(yù)防死鎖的方法預(yù)防死鎖的方法預(yù)防死鎖預(yù)防死鎖3.6 預(yù)防死鎖的方法預(yù)防死鎖的方法預(yù)防死鎖預(yù)防死鎖3.6 預(yù)防死鎖的方法預(yù)防死鎖的方法系統(tǒng)系統(tǒng)死鎖死鎖避免避免

39、死鎖的實質(zhì)：死鎖的實質(zhì)：如何使系統(tǒng)不進(jìn)入如何使系統(tǒng)不進(jìn)入不不安全狀態(tài)。安全狀態(tài)。3.6 預(yù)防死鎖的方法預(yù)防死鎖的方法系統(tǒng)系統(tǒng)死鎖死鎖3.6 預(yù)防死鎖的方法預(yù)防死鎖的方法銀行家算法避免死鎖銀行家算法避免死鎖3.6 預(yù)防死鎖的方法預(yù)防死鎖的方法銀行家算法避免死鎖銀行家算法避免死鎖3.6 預(yù)防死鎖的方法預(yù)防死鎖的方法銀行家算法避免死鎖銀行家算法避免死鎖出出 錯錯N等等 待待NRequest i,j= Needi,jRequesti,j = AvailablejY系統(tǒng)把要求的資源試探分配給進(jìn)程系統(tǒng)把要求的資源試探分配給進(jìn)程PiAvailablej := Availablej Requesti,j;Al

40、location i,j:= Allocationi,j+ Request i,j;Needi,j :=Needi,j Requesti,jY系統(tǒng)執(zhí)行系統(tǒng)執(zhí)行安全性算法安全性算法分配資源給進(jìn)程分配資源給進(jìn)程試探分配作廢試探分配作廢3.6 預(yù)防死鎖的方法預(yù)防死鎖的方法銀行家算法避免死鎖銀行家算法避免死鎖3.6 預(yù)防死鎖的方法預(yù)防死鎖的方法銀行家算法避免死鎖銀行家算法避免死鎖3.7 死鎖的檢測與解除死鎖的檢測與解除 死鎖的檢測死鎖的檢測進(jìn)程進(jìn)程P1R1R2進(jìn)程進(jìn)程P2進(jìn)程進(jìn)程P2進(jìn)程進(jìn)程P1R1 R23.7 死鎖的檢測與解除死鎖的檢測與解除 死鎖的檢測死鎖的檢測3.7 死鎖的檢測與解除死鎖的檢測與解除 死鎖的檢測死鎖的檢測3.7 死鎖的檢測與解除死鎖的檢測與解除 死鎖的檢測死鎖的檢測3.8 死鎖的檢測和解除死鎖的檢測和解除 死鎖的解除死鎖的解除3.7 死鎖的檢測與解除死鎖的檢測與解除 死鎖的解除死鎖的解除方法方法資源分配資源分配策略策略方案方案優(yōu)點優(yōu)點缺點缺點預(yù)防預(yù)防保守的保守的一次分配全一次分配全部資源部資源l對執(zhí)行一連串活動對執(zhí)行一連串活動的進(jìn)程非常有效的進(jìn)程非常有效l不需剝奪不需剝奪l低效低效l延遲進(jìn)程初始化延遲進(jìn)程初始化l必須知道進(jìn)程將來的資必須知道進(jìn)程將來的資源請求源請求剝奪剝奪用于狀態(tài)易保存和用于狀態(tài)易保存