中南大學(xué)操作系統(tǒng)第三講進程調(diào)度

1、2013-92 總總 目目 錄錄第第1章章 操作系統(tǒng)引論操作系統(tǒng)引論第第2章章 進程管理進程管理第第3章章 處理機調(diào)度與死鎖處理機調(diào)度與死鎖第第4章章 存儲器管理存儲器管理第第5章章 設(shè)備管理設(shè)備管理第第6章章 文件管理文件管理第第7章章 操作系統(tǒng)接口操作系統(tǒng)接口3第第3 3章章 處理機調(diào)度與死鎖處理機調(diào)度與死鎖3.1 處理機調(diào)度的基本概念處理機調(diào)度的基本概念3.2 調(diào)度算法調(diào)度算法第二次上機實驗第二次上機實驗 進程調(diào)度進程調(diào)度3.3 實時調(diào)度實時調(diào)度3.4 多處理機系統(tǒng)中的調(diào)度多處理機系統(tǒng)中的調(diào)度 ( (第三版刪第三版刪) )3.5 產(chǎn)生死鎖的原因和必要條件產(chǎn)生死鎖的原因和必要條件3.6 預(yù)

2、防和避免死鎖的方法預(yù)防和避免死鎖的方法3.7 死鎖的檢測和解除死鎖的檢測和解除第三次上機實驗第三次上機實驗 演示銀行家算法演示銀行家算法實時調(diào)度和多處理機調(diào)度，考研不要求。實時調(diào)度和多處理機調(diào)度，考研不要求。43.1 處理機調(diào)度的基本概念處理機調(diào)度的基本概念3.1.1 高級、中級和低級調(diào)度高級、中級和低級調(diào)度 1高級調(diào)度高級調(diào)度又稱作業(yè)調(diào)度或長調(diào)度又稱作業(yè)調(diào)度或長調(diào)度 用于決定把外存上后備隊列中哪些作業(yè)調(diào)入內(nèi)存，并用于決定把外存上后備隊列中哪些作業(yè)調(diào)入內(nèi)存，并為它們創(chuàng)建進程、分配必要的資源，然后將新創(chuàng)建的為它們創(chuàng)建進程、分配必要的資源，然后將新創(chuàng)建的進程插入到就緒隊列中，準(zhǔn)備運行進程插入到就緒

3、隊列中，準(zhǔn)備運行。定義定義每次作業(yè)調(diào)度，都需做以下兩個決定：每次作業(yè)調(diào)度，都需做以下兩個決定： 接納多少個作業(yè)接納多少個作業(yè)取決于多道程序度取決于多道程序度內(nèi)存中同時運行的內(nèi)存中同時運行的作業(yè)數(shù)目太多，會影作業(yè)數(shù)目太多，會影響系統(tǒng)的服務(wù)質(zhì)量。響系統(tǒng)的服務(wù)質(zhì)量。如，周轉(zhuǎn)時間長。如，周轉(zhuǎn)時間長。內(nèi)存中同時運行的內(nèi)存中同時運行的作業(yè)數(shù)目太少，會導(dǎo)作業(yè)數(shù)目太少，會導(dǎo)致系統(tǒng)資源利用率和致系統(tǒng)資源利用率和系統(tǒng)吞吐量低。系統(tǒng)吞吐量低。 接納哪些作業(yè)接納哪些作業(yè)取決于調(diào)度算法取決于調(diào)度算法53.1 處理機調(diào)度的基本概念處理機調(diào)度的基本概念2低級調(diào)度低級調(diào)度 又稱進程調(diào)度或短調(diào)度。是最基本的調(diào)度，又稱進程調(diào)度或

4、短調(diào)度。是最基本的調(diào)度，三種類型三種類型OS中，都必須配置此調(diào)度。中，都必須配置此調(diào)度。 定義定義用來決定就緒隊列中的哪個進程應(yīng)獲得處理機，然后再用來決定就緒隊列中的哪個進程應(yīng)獲得處理機，然后再由分派程序執(zhí)行把處理機分配給該進程的具體操作。由分派程序執(zhí)行把處理機分配給該進程的具體操作。 進程調(diào)度可采用下述兩種調(diào)度方式：進程調(diào)度可采用下述兩種調(diào)度方式： （1）非搶占方式）非搶占方式（2）搶占方式）搶占方式 一旦把處理機分配給某進程后，便讓一旦把處理機分配給某進程后，便讓它一直執(zhí)行，直到該進程完成或發(fā)生它一直執(zhí)行，直到該進程完成或發(fā)生某事件而被阻塞時，才把處理機分配某事件而被阻塞時，才把處理機分配

5、給其它進程，決不允許某進程搶占已給其它進程，決不允許某進程搶占已經(jīng)分配出去的處理機。經(jīng)分配出去的處理機。優(yōu)點：實現(xiàn)簡單，系統(tǒng)開銷小。優(yōu)點：實現(xiàn)簡單，系統(tǒng)開銷小。缺點：難于滿足緊急任務(wù)的要求。缺點：難于滿足緊急任務(wù)的要求。 允許調(diào)度程序根據(jù)某種原則，暫停某個允許調(diào)度程序根據(jù)某種原則，暫停某個正在執(zhí)行的進程，將已分配給該進程的正在執(zhí)行的進程，將已分配給該進程的處理機重新分配給另一進程。處理機重新分配給另一進程。 搶占原則有：搶占原則有： 優(yōu)先權(quán)原則；優(yōu)先權(quán)原則； 短作業(yè)優(yōu)先原則；短作業(yè)優(yōu)先原則； 時間片原則。時間片原則。 非搶占調(diào)度方式中，可能引起進程調(diào)非搶占調(diào)度方式中，可能引起進程調(diào)度的因素：度

6、的因素：（1 1）正在執(zhí)行的進程執(zhí)行完畢，或）正在執(zhí)行的進程執(zhí)行完畢，或因某事件不能繼續(xù)執(zhí)行因某事件不能繼續(xù)執(zhí)行（2 2）執(zhí)行中的進程提出）執(zhí)行中的進程提出I/OI/O請求請求（3 3）執(zhí)行了）執(zhí)行了waitblocksignalwaitblocksignal等原等原語語 63.1 處理機調(diào)度的基本概念處理機調(diào)度的基本概念n3. 中級調(diào)度中級調(diào)度 掛起和激活，存儲器管理中的對換功能。掛起和激活，存儲器管理中的對換功能。 主要目的：主要目的： 為了提高內(nèi)存的利用率和系統(tǒng)的吞吐量。為了提高內(nèi)存的利用率和系統(tǒng)的吞吐量。 主要介紹進程調(diào)主要介紹進程調(diào)度和作業(yè)調(diào)度。度和作業(yè)調(diào)度。三種調(diào)度相比較：三種調(diào)度

7、相比較：進程調(diào)度的運行頻率最高進程調(diào)度的運行頻率最高 作業(yè)調(diào)度頻率最低作業(yè)調(diào)度頻率最低 中級調(diào)度界于之間中級調(diào)度界于之間 73.1.2 調(diào)度隊列模型調(diào)度隊列模型三種類型的調(diào)度隊列模型：三種類型的調(diào)度隊列模型： 1. 僅有進程調(diào)度的調(diào)度隊列模型僅有進程調(diào)度的調(diào)度隊列模型 在在分時系統(tǒng)中，通常僅設(shè)置了進程中，通常僅設(shè)置了進程調(diào)度。常把就緒進程組織成調(diào)度。常把就緒進程組織成FIFO隊隊列形式。列形式。 阻塞隊列一阻塞隊列一般可能有多般可能有多個。個。就就 緒緒 隊隊 列列阻阻 塞塞 隊隊 列列交互用戶交互用戶進程調(diào)度進程調(diào)度CPU時間片完時間片完等待事件等待事件進程進程完成完成事件出現(xiàn)事件出現(xiàn)圖圖3

8、-1 僅具有進程調(diào)度的調(diào)度隊列模型僅具有進程調(diào)度的調(diào)度隊列模型83.1.2 調(diào)度隊列模型調(diào)度隊列模型2. 具有高級和低級調(diào)度的調(diào)度隊列模型具有高級和低級調(diào)度的調(diào)度隊列模型 批處理系統(tǒng)中批處理系統(tǒng)中的調(diào)度模型的調(diào)度模型 比第一種情況比第一種情況多了后備隊列多了后備隊列就就 緒緒 隊隊 列列阻阻 塞塞 隊隊 列列1 1作業(yè)作業(yè)調(diào)度調(diào)度進程調(diào)度進程調(diào)度CPU時間片完時間片完等待事件等待事件1 1進程進程完成完成圖圖3-2 具有高、低兩級調(diào)度的調(diào)度隊列模型具有高、低兩級調(diào)度的調(diào)度隊列模型阻阻 塞塞 隊隊 列列2 2等待事件等待事件2 2阻阻 塞塞 隊隊 列列n n等待事件等待事件n n事件事件1 1出

9、現(xiàn)出現(xiàn)事件事件2 2出現(xiàn)出現(xiàn)事件事件n n出現(xiàn)出現(xiàn)后備隊列后備隊列93.1.2 調(diào)度隊列模型調(diào)度隊列模型3. 同時具有三級調(diào)度的調(diào)度隊列模型同時具有三級調(diào)度的調(diào)度隊列模型 具有掛起狀具有掛起狀態(tài)的系統(tǒng)。態(tài)的系統(tǒng)。 103.1.3 選擇調(diào)度方式和調(diào)度算法的若干準(zhǔn)則選擇調(diào)度方式和調(diào)度算法的若干準(zhǔn)則1面向用戶的準(zhǔn)則面向用戶的準(zhǔn)則 （1）周轉(zhuǎn)時間短。）周轉(zhuǎn)時間短。 評價評價批處理系統(tǒng)批處理系統(tǒng)的準(zhǔn)則之一的準(zhǔn)則之一周轉(zhuǎn)時間周轉(zhuǎn)時間 是指從作業(yè)被提交給系統(tǒng)開始，到作業(yè)完是指從作業(yè)被提交給系統(tǒng)開始，到作業(yè)完成這段時間間隔。成這段時間間隔。平均周轉(zhuǎn)時間平均周轉(zhuǎn)時間 舉例說明舉例說明（2）響應(yīng)時間快）響應(yīng)時間快

10、 評價評價分時系統(tǒng)分時系統(tǒng)的準(zhǔn)則之一的準(zhǔn)則之一響應(yīng)時間響應(yīng)時間 是從用戶通過鍵盤提交一個請求開始，到是從用戶通過鍵盤提交一個請求開始，到系統(tǒng)首次產(chǎn)生響應(yīng)為止的時間。系統(tǒng)首次產(chǎn)生響應(yīng)為止的時間。 11在批處理、分時和實時系統(tǒng)中選擇調(diào)度在批處理、分時和實時系統(tǒng)中選擇調(diào)度算法時，都可以遵循優(yōu)先權(quán)準(zhǔn)則，以便算法時，都可以遵循優(yōu)先權(quán)準(zhǔn)則，以便讓某些緊急的作業(yè)能得到及時處理。在讓某些緊急的作業(yè)能得到及時處理。在要求嚴(yán)格的場合，往往還須選擇搶占式要求嚴(yán)格的場合，往往還須選擇搶占式調(diào)度方式調(diào)度方式 （4）優(yōu)先權(quán)準(zhǔn)則）優(yōu)先權(quán)準(zhǔn)則 截止時間截止時間 是指某任務(wù)必須開始執(zhí)行的最遲時間，是指某任務(wù)必須開始執(zhí)行的最遲時

11、間，或必須完成的最遲時間。或必須完成的最遲時間。 （3）截止時間的保證）截止時間的保證 評價評價實時系統(tǒng)實時系統(tǒng)的準(zhǔn)則之一的準(zhǔn)則之一123.1.3 選擇調(diào)度方式和調(diào)度算法的若干準(zhǔn)則選擇調(diào)度方式和調(diào)度算法的若干準(zhǔn)則2. 面向系統(tǒng)的準(zhǔn)則面向系統(tǒng)的準(zhǔn)則 （1）系統(tǒng)吞吐量高）系統(tǒng)吞吐量高（2）處理機利用率好）處理機利用率好 （3）各類資源的均衡利用）各類資源的均衡利用 吞吐量吞吐量 單位時間內(nèi)系統(tǒng)單位時間內(nèi)系統(tǒng)所完成的作業(yè)數(shù)所完成的作業(yè)數(shù) 調(diào)度方式和算法對處理機的調(diào)度方式和算法對處理機的利用率起著十分重要的作用利用率起著十分重要的作用 對于單用戶微機或某些實對于單用戶微機或某些實時系統(tǒng)，該準(zhǔn)則并不重要

12、時系統(tǒng)，該準(zhǔn)則并不重要 133.2 調(diào)度算法調(diào)度算法3.2.1 先來先服務(wù)調(diào)度算法先來先服務(wù)調(diào)度算法3.2.2 短作業(yè)短作業(yè)(進程進程)優(yōu)先調(diào)度算法優(yōu)先調(diào)度算法3.2.3 高優(yōu)先權(quán)優(yōu)先調(diào)度算法高優(yōu)先權(quán)優(yōu)先調(diào)度算法 3.2.4 高響應(yīng)比優(yōu)先調(diào)度算法高響應(yīng)比優(yōu)先調(diào)度算法3.2.5 基于時間片的輪轉(zhuǎn)調(diào)度算法基于時間片的輪轉(zhuǎn)調(diào)度算法 143.2.1 先來先服務(wù)調(diào)度算法先來先服務(wù)調(diào)度算法 FCFS調(diào)度算法是一種最簡單的調(diào)度算法。調(diào)度算法是一種最簡單的調(diào)度算法。既可用于既可用于作業(yè)調(diào)度作業(yè)調(diào)度，也可用于，也可用于進程調(diào)度進程調(diào)度。用于作業(yè)用于作業(yè)調(diào)度中：調(diào)度中： 從后備隊列作業(yè)中，選擇一個或幾個最先從后備

13、隊列作業(yè)中，選擇一個或幾個最先進入該隊列的作業(yè)，將它們調(diào)入內(nèi)存，為進入該隊列的作業(yè)，將它們調(diào)入內(nèi)存，為它們分配資源、創(chuàng)建進程，然后放入進程它們分配資源、創(chuàng)建進程，然后放入進程就緒隊列。就緒隊列。 用于進程用于進程調(diào)度時：調(diào)度時： 從就緒隊列中，選擇一個最先進入該隊列從就緒隊列中，選擇一個最先進入該隊列的進程，為之分配處理機，使之投入運行。的進程，為之分配處理機，使之投入運行。該進程一直運行到完成或發(fā)生某事件而阻該進程一直運行到完成或發(fā)生某事件而阻塞后，才放棄處理機。塞后，才放棄處理機。非搶占式非搶占式 15【例【例3-1】設(shè)在單道系統(tǒng)中用設(shè)在單道系統(tǒng)中用FCFSFCFS算法調(diào)度如下作業(yè)，請完算

14、法調(diào)度如下作業(yè)，請完成下表。成下表。進程名進程名 ABCDE平平 均均 到達(dá)時間到達(dá)時間 9:00 9:10 9:30 10:00 10:15 服務(wù)時間服務(wù)時間 30分鐘分鐘 1小時小時 10分鐘分鐘 50分鐘分鐘 20分鐘分鐘 完成時間完成時間 周轉(zhuǎn)時間周轉(zhuǎn)時間 帶權(quán)周帶權(quán)周轉(zhuǎn)時間轉(zhuǎn)時間 80分鐘分鐘 9:30 30分鐘分鐘10:30 70分鐘分鐘 10:40 11:30 90分鐘分鐘 11:50 95分鐘分鐘 11.3371.84.7573分鐘分鐘 3.176FCFS算法比較有利于長作業(yè)（進程），不利于短作業(yè)（進程）。算法比較有利于長作業(yè)（進程），不利于短作業(yè)（進程）。有利于有利于CPU繁

15、忙型作業(yè)（進程），不利于繁忙型作業(yè)（進程），不利于I/O繁忙型作業(yè)（進程）繁忙型作業(yè)（進程）因非搶占式因非搶占式 CPU繁忙型作業(yè)繁忙型作業(yè)需要大量的需要大量的CPU時間進行計時間進行計算，而很少請求算，而很少請求I/O。如，科學(xué)計算。如，科學(xué)計算I/O繁忙型作業(yè)繁忙型作業(yè)是指是指CPU進行處理時，需頻進行處理時，需頻繁地請求繁地請求I/O。如，大多數(shù)事務(wù)處理。如，大多數(shù)事務(wù)處理 163.2.2 短作業(yè)短作業(yè)( (進程進程) )優(yōu)先調(diào)度算法優(yōu)先調(diào)度算法 短作業(yè)優(yōu)先（短作業(yè)優(yōu)先（SJF）調(diào)度算法）調(diào)度算法 從后備隊從后備隊列中選擇一個或幾個估計運行時間最短的作列中選擇一個或幾個估計運行時間最短的

16、作業(yè)，將它調(diào)入內(nèi)存運行。業(yè)，將它調(diào)入內(nèi)存運行。短進程優(yōu)先（短進程優(yōu)先（SPF）調(diào)度算法）調(diào)度算法從就緒隊從就緒隊列中選擇一個估計運行時間最短的進程，將列中選擇一個估計運行時間最短的進程，將處理機分配給它，使它立即執(zhí)行并一直到完處理機分配給它，使它立即執(zhí)行并一直到完成，或發(fā)生某事件而被阻塞放棄處理機時，成，或發(fā)生某事件而被阻塞放棄處理機時，再重新調(diào)度。再重新調(diào)度。( (非搶占式非搶占式) ) 17【例例3-2】 設(shè)在單道系統(tǒng)中用設(shè)在單道系統(tǒng)中用SJF算法調(diào)度如下作業(yè)，請完算法調(diào)度如下作業(yè)，請完成下表。成下表。進程名進程名 ABCDE平平 均均 到達(dá)時間到達(dá)時間 9:00 9:10 9:30 10

17、:00 10:15 服務(wù)時間服務(wù)時間 30分鐘分鐘 1小時小時 10分鐘分鐘 50分鐘分鐘 20分鐘分鐘 完成時間完成時間 周轉(zhuǎn)時間周轉(zhuǎn)時間 帶權(quán)周轉(zhuǎn)帶權(quán)周轉(zhuǎn)時間時間9:3010:409:4011:5011:0030分鐘分鐘90分鐘分鐘10分鐘分鐘110分鐘分鐘45分鐘分鐘57分鐘分鐘11.512.22.251.5918SJF調(diào)度算法的優(yōu)點調(diào)度算法的優(yōu)點：SJF調(diào)度算法的缺點調(diào)度算法的缺點： n該算法對長作業(yè)不利該算法對長作業(yè)不利長作業(yè)可能長期不被長作業(yè)可能長期不被調(diào)度，甚至調(diào)度，甚至“餓死餓死”。n未考慮作業(yè)的緊迫性，不能保證緊迫作業(yè)（進未考慮作業(yè)的緊迫性，不能保證緊迫作業(yè)（進程）會被及時調(diào)

18、度。程）會被及時調(diào)度。 n由于作業(yè)（進程）的長短只是根據(jù)用戶所提供由于作業(yè)（進程）的長短只是根據(jù)用戶所提供的估計時間而定的，致使該算法不一定能真正的估計時間而定的，致使該算法不一定能真正做到短作業(yè)優(yōu)先調(diào)度。做到短作業(yè)優(yōu)先調(diào)度。 當(dāng)多個作業(yè)同時到達(dá)時，當(dāng)多個作業(yè)同時到達(dá)時，SJF算法可使平均周轉(zhuǎn)時算法可使平均周轉(zhuǎn)時間最短。間最短。193.2.3 高優(yōu)先權(quán)優(yōu)先調(diào)度算法高優(yōu)先權(quán)優(yōu)先調(diào)度算法 引入的目的：引入的目的：為了照顧緊迫型作業(yè)，使之在進入系統(tǒng)后便獲得優(yōu)先處理。為了照顧緊迫型作業(yè)，使之在進入系統(tǒng)后便獲得優(yōu)先處理。 優(yōu)先權(quán)作業(yè)調(diào)度優(yōu)先權(quán)作業(yè)調(diào)度 系統(tǒng)從后備中選擇一個或幾個優(yōu)先權(quán)系統(tǒng)從后備中選擇一個

19、或幾個優(yōu)先權(quán)最高的作業(yè)，將它調(diào)入內(nèi)存運行。最高的作業(yè)，將它調(diào)入內(nèi)存運行。 優(yōu)先權(quán)進程調(diào)度優(yōu)先權(quán)進程調(diào)度 系統(tǒng)將處理機分配給就緒隊列中一個系統(tǒng)將處理機分配給就緒隊列中一個優(yōu)先權(quán)最高的進程。優(yōu)先權(quán)最高的進程。 適用范圍：適用范圍： 批處理系統(tǒng)的作業(yè)調(diào)度批處理系統(tǒng)的作業(yè)調(diào)度 多種操作系統(tǒng)的進程調(diào)度多種操作系統(tǒng)的進程調(diào)度 還適用于實時系統(tǒng)還適用于實時系統(tǒng) 201優(yōu)先權(quán)進程調(diào)度算法的類型優(yōu)先權(quán)進程調(diào)度算法的類型 非搶占式優(yōu)先權(quán)算法非搶占式優(yōu)先權(quán)算法 搶占式優(yōu)先權(quán)算法搶占式優(yōu)先權(quán)算法 非搶占式優(yōu)先權(quán)算法非搶占式優(yōu)先權(quán)算法 系統(tǒng)一旦把處理機分配給就緒隊列中優(yōu)先權(quán)最高的進程后，系統(tǒng)一旦把處理機分配給就緒隊列中

20、優(yōu)先權(quán)最高的進程后，該進程便一直執(zhí)行下去，直到完成，或因發(fā)生某事件使該進該進程便一直執(zhí)行下去，直到完成，或因發(fā)生某事件使該進程放棄處理機時，系統(tǒng)方可再將處理機重新分配給另一個優(yōu)程放棄處理機時，系統(tǒng)方可再將處理機重新分配給另一個優(yōu)先權(quán)最高的進程。先權(quán)最高的進程。 搶占式優(yōu)先權(quán)算法搶占式優(yōu)先權(quán)算法 系統(tǒng)把處理機分配給就緒隊列中優(yōu)先權(quán)最高的進程，使之執(zhí)系統(tǒng)把處理機分配給就緒隊列中優(yōu)先權(quán)最高的進程，使之執(zhí)行，但在其執(zhí)行期間，只要出現(xiàn)了另一個優(yōu)先權(quán)更高的進程，行，但在其執(zhí)行期間，只要出現(xiàn)了另一個優(yōu)先權(quán)更高的進程，系統(tǒng)就立即停止當(dāng)前進程的執(zhí)行，重新將處理機分配給新的系統(tǒng)就立即停止當(dāng)前進程的執(zhí)行，重新將處理

21、機分配給新的優(yōu)先權(quán)最高的進程。優(yōu)先權(quán)最高的進程。 它能更好地滿足緊迫作業(yè)的要求。常用于實時系統(tǒng)中，以它能更好地滿足緊迫作業(yè)的要求。常用于實時系統(tǒng)中，以及對實時性能要求較高的批處理系統(tǒng)和分時系統(tǒng)中。及對實時性能要求較高的批處理系統(tǒng)和分時系統(tǒng)中。 212優(yōu)先權(quán)的類型優(yōu)先權(quán)的類型 靜態(tài)優(yōu)先權(quán)靜態(tài)優(yōu)先權(quán) 動態(tài)優(yōu)先權(quán)動態(tài)優(yōu)先權(quán) 1）靜態(tài)優(yōu)先權(quán)靜態(tài)優(yōu)先權(quán) 靜態(tài)優(yōu)先權(quán)靜態(tài)優(yōu)先權(quán)它是在創(chuàng)建進程時確定的，且在進程整個運它是在創(chuàng)建進程時確定的，且在進程整個運行期間保持不變。行期間保持不變。優(yōu)先權(quán)一般用某一范圍內(nèi)的一個整數(shù)來表示。優(yōu)先權(quán)一般用某一范圍內(nèi)的一個整數(shù)來表示。有的系統(tǒng)用有的系統(tǒng)用“0”表示最高優(yōu)先權(quán)，數(shù)值

22、越大，優(yōu)先權(quán)越低；表示最高優(yōu)先權(quán)，數(shù)值越大，優(yōu)先權(quán)越低；有的系統(tǒng)恰恰相反。有的系統(tǒng)恰恰相反。 確定優(yōu)先權(quán)的依據(jù)確定優(yōu)先權(quán)的依據(jù)：常有三方面常有三方面 進程類型進程類型 系統(tǒng)進程（如接收進程、對換進程、磁盤系統(tǒng)進程（如接收進程、對換進程、磁盤I/OI/O進程等）的進程等）的優(yōu)先權(quán)高于一般用戶進程的優(yōu)先權(quán)。優(yōu)先權(quán)高于一般用戶進程的優(yōu)先權(quán)。進程對資源的需求進程對資源的需求 如進程的估計執(zhí)行時間及內(nèi)存需求量的多少，對如進程的估計執(zhí)行時間及內(nèi)存需求量的多少，對這些要求少的進程賦予較高的優(yōu)先權(quán)。這些要求少的進程賦予較高的優(yōu)先權(quán)。 用戶要求用戶要求 這是由用戶進程的緊迫程度和用戶所付費用的多少來確定這是由用

23、戶進程的緊迫程度和用戶所付費用的多少來確定優(yōu)先權(quán)的。優(yōu)先權(quán)的。 靜態(tài)優(yōu)先權(quán)的優(yōu)缺點：靜態(tài)優(yōu)先權(quán)的優(yōu)缺點：優(yōu)點優(yōu)點：簡單易行，系統(tǒng)開銷小。：簡單易行，系統(tǒng)開銷小。 缺點缺點：優(yōu)先權(quán)低的作業(yè)（進程）可能：優(yōu)先權(quán)低的作業(yè)（進程）可能長期得不到調(diào)度。長期得不到調(diào)度。 222）動態(tài)優(yōu)先權(quán)動態(tài)優(yōu)先權(quán) 動態(tài)優(yōu)先權(quán)動態(tài)優(yōu)先權(quán)在創(chuàng)建進程時所賦予的優(yōu)先權(quán)，是在創(chuàng)建進程時所賦予的優(yōu)先權(quán)，是可以隨進程得推進，或隨其等待時間的增加而改變可以隨進程得推進，或隨其等待時間的增加而改變的，以便獲得更好的調(diào)度性。的，以便獲得更好的調(diào)度性。 例如：例如： n在就緒隊列中的進程，隨其等待時間的增長，其在就緒隊列中的進程，隨其等待時

24、間的增長，其優(yōu)先權(quán)以速率優(yōu)先權(quán)以速率提高；提高； n在采用搶占式優(yōu)先權(quán)調(diào)度算法時，如果再規(guī)定當(dāng)在采用搶占式優(yōu)先權(quán)調(diào)度算法時，如果再規(guī)定當(dāng)前執(zhí)行進程以速率前執(zhí)行進程以速率下降，則可防止一個長作業(yè)下降，則可防止一個長作業(yè)長期壟斷處理機。長期壟斷處理機。 23UNIX采用計算的方法動態(tài)改變進程的優(yōu)先數(shù)。在采用計算的方法動態(tài)改變進程的優(yōu)先數(shù)。在UNIX System V版本中，進程優(yōu)先數(shù)版本中，進程優(yōu)先數(shù)p_pri的算式如下：的算式如下：p_pri=p_cpu/2+PUSER+p_nice+NZERO其中，其中，PUSER和和NZERO是偏置常數(shù)，分別為是偏置常數(shù)，分別為25和和20。p_cpu和和p

25、_nice是基本進程控制塊中的兩個項，分別表示進是基本進程控制塊中的兩個項，分別表示進程使用處理器的情況和用戶自己設(shè)置的計算優(yōu)先數(shù)的偏置程使用處理器的情況和用戶自己設(shè)置的計算優(yōu)先數(shù)的偏置量。量。系統(tǒng)對正在占用系統(tǒng)對正在占用CPU的進程每隔一個時鐘周期的進程每隔一個時鐘周期(20ms)對其對其p_cpu加加1。這使得占用處理器時間長的進程的。這使得占用處理器時間長的進程的p_cpu值增大，值增大，其優(yōu)先數(shù)也增大，優(yōu)先權(quán)就相應(yīng)降低。其優(yōu)先數(shù)也增大，優(yōu)先權(quán)就相應(yīng)降低。系統(tǒng)每隔系統(tǒng)每隔1s對所有進程執(zhí)行對所有進程執(zhí)行p_cpu/2，這使就緒進程優(yōu)先級，這使就緒進程優(yōu)先級提高。提高。p_nice的值允許

26、用戶根據(jù)任務(wù)的輕重緩急程度來設(shè)置，其值的值允許用戶根據(jù)任務(wù)的輕重緩急程度來設(shè)置，其值在在039之間。一旦一個進程的之間。一旦一個進程的p_nice設(shè)置后，此后用戶只設(shè)置后，此后用戶只能使其值增加。能使其值增加。24【例例3-3】設(shè)有一個最多可有兩道作業(yè)同時裝入內(nèi)存執(zhí)設(shè)有一個最多可有兩道作業(yè)同時裝入內(nèi)存執(zhí)行的批處理系統(tǒng)，作業(yè)調(diào)度采用最短作業(yè)優(yōu)先調(diào)度算行的批處理系統(tǒng)，作業(yè)調(diào)度采用最短作業(yè)優(yōu)先調(diào)度算法，進程調(diào)度采用搶占式靜態(tài)優(yōu)先權(quán)調(diào)度算法，今有法，進程調(diào)度采用搶占式靜態(tài)優(yōu)先權(quán)調(diào)度算法，今有如下純計算型作業(yè)序列（表中所列進程優(yōu)先數(shù)中，數(shù)如下純計算型作業(yè)序列（表中所列進程優(yōu)先數(shù)中，數(shù)值越小優(yōu)先權(quán)越高）：

27、值越小優(yōu)先權(quán)越高）： (1)(1)列出所有作業(yè)進入內(nèi)存時間及結(jié)束時間。列出所有作業(yè)進入內(nèi)存時間及結(jié)束時間。 (2)(2)計算平均周轉(zhuǎn)時間。計算平均周轉(zhuǎn)時間。 作業(yè)名作業(yè)名到達(dá)時間到達(dá)時間估計運行時間估計運行時間進程優(yōu)先數(shù)進程優(yōu)先數(shù)J110:1020分鐘分鐘5J210:2030分鐘分鐘3J310:3025分鐘分鐘4J410:5020分鐘分鐘625作業(yè)名作業(yè)名提交時間提交時間進入時間進入時間結(jié)束時間結(jié)束時間周轉(zhuǎn)時間周轉(zhuǎn)時間J110：10J210：20J310：30J410：50平均周轉(zhuǎn)時間平均周轉(zhuǎn)時間=(50+30+55+55)4=47.5(分鐘分鐘)作業(yè)名作業(yè)名到達(dá)時間到達(dá)時間估計運行時間估計運

28、行時間進程優(yōu)先數(shù)進程優(yōu)先數(shù)J110:1020分鐘分鐘5J210:2030分鐘分鐘3J310:3025分鐘分鐘4J410:5020分鐘分鐘610:1011:0050分鐘分鐘10:2010:5030分鐘分鐘11:0011:2555分鐘分鐘10:5011:4555分鐘分鐘263.2.4 高響應(yīng)比優(yōu)先調(diào)度算法高響應(yīng)比優(yōu)先調(diào)度算法 響應(yīng)比響應(yīng)比( (等待時間等待時間+ +要求服務(wù)時間要求服務(wù)時間)/)/要求服務(wù)時間要求服務(wù)時間（實際上響應(yīng)比是動態(tài)優(yōu)先權(quán)）（實際上響應(yīng)比是動態(tài)優(yōu)先權(quán)） 高響應(yīng)比優(yōu)先調(diào)度算法高響應(yīng)比優(yōu)先調(diào)度算法 每次要進行作業(yè)調(diào)度時，系統(tǒng)每次要進行作業(yè)調(diào)度時，系統(tǒng)首先計算后備隊列中各作業(yè)的首

29、先計算后備隊列中各作業(yè)的響應(yīng)比，然后選擇一個或若干響應(yīng)比，然后選擇一個或若干個響應(yīng)比最高的作業(yè)調(diào)入內(nèi)存?zhèn)€響應(yīng)比最高的作業(yè)調(diào)入內(nèi)存執(zhí)行。執(zhí)行。 該算法綜合了該算法綜合了FCFS和和SJF算法的算法的優(yōu)點優(yōu)點既考慮公平性，又既考慮公平性，又考慮平均周轉(zhuǎn)時間考慮平均周轉(zhuǎn)時間缺點缺點是會增加系統(tǒng)開銷是會增加系統(tǒng)開銷每次調(diào)度都要計算響應(yīng)比。每次調(diào)度都要計算響應(yīng)比。 優(yōu)先權(quán)優(yōu)先權(quán)( (等待時間等待時間+ +要求服務(wù)時間要求服務(wù)時間)/)/要求服務(wù)時間要求服務(wù)時間2724下列進程調(diào)度算法中，綜合考慮進程等待時間下列進程調(diào)度算法中，綜合考慮進程等待時間和執(zhí)行時間的是和執(zhí)行時間的是_。(2009(2009全國考

30、研第全國考研第2424題題) )A時間片輪轉(zhuǎn)調(diào)度算法時間片輪轉(zhuǎn)調(diào)度算法B短進程優(yōu)先調(diào)度算法短進程優(yōu)先調(diào)度算法C先來先服務(wù)調(diào)度算法先來先服務(wù)調(diào)度算法D高響應(yīng)比優(yōu)先調(diào)度算法高響應(yīng)比優(yōu)先調(diào)度算法28【例例3-4】設(shè)有一個最多可有兩道作業(yè)同時裝入內(nèi)存執(zhí)設(shè)有一個最多可有兩道作業(yè)同時裝入內(nèi)存執(zhí)行的批處理系統(tǒng)，作業(yè)調(diào)度采用行的批處理系統(tǒng)，作業(yè)調(diào)度采用高響應(yīng)比優(yōu)先高響應(yīng)比優(yōu)先調(diào)度算調(diào)度算法，進程調(diào)度采用搶占式靜態(tài)優(yōu)先權(quán)調(diào)度算法，今有法，進程調(diào)度采用搶占式靜態(tài)優(yōu)先權(quán)調(diào)度算法，今有如下純計算型作業(yè)序列（假設(shè)表中所列進程優(yōu)先數(shù)中，如下純計算型作業(yè)序列（假設(shè)表中所列進程優(yōu)先數(shù)中，數(shù)值越小優(yōu)先權(quán)越高）：數(shù)值越小優(yōu)先權(quán)越

31、高）： (1)(1)列出所有作業(yè)進入內(nèi)存時間及結(jié)束時間。列出所有作業(yè)進入內(nèi)存時間及結(jié)束時間。 (2)(2)計算平均周轉(zhuǎn)時間。計算平均周轉(zhuǎn)時間。 作業(yè)名作業(yè)名到達(dá)時間到達(dá)時間估計運行時間估計運行時間進程優(yōu)先數(shù)進程優(yōu)先數(shù)J110:1020分鐘分鐘5J210:2030分鐘分鐘3J310:3025分鐘分鐘4J410:5020分鐘分鐘629J1CPU10:1010:20J210:5010:50 J3響應(yīng)比高，響應(yīng)比高，J3調(diào)入內(nèi)存并執(zhí)行。調(diào)入內(nèi)存并執(zhí)行。11:15J311:15 J4調(diào)入內(nèi)存，調(diào)入內(nèi)存，J1恢復(fù)執(zhí)行。恢復(fù)執(zhí)行。J111:25J411:4510:10 只有只有J1一個作業(yè)，調(diào)入內(nèi)存執(zhí)行。一

32、個作業(yè)，調(diào)入內(nèi)存執(zhí)行。10:20 J2到達(dá)，調(diào)入內(nèi)存，因其優(yōu)先級高，到達(dá)，調(diào)入內(nèi)存，因其優(yōu)先級高，J2執(zhí)行。執(zhí)行。30J1J2J3J1J4CPU10:1010:2010:5011:1511:2511:45作業(yè)名作業(yè)名 到達(dá)時間到達(dá)時間 調(diào)入時間調(diào)入時間結(jié)束時間結(jié)束時間周轉(zhuǎn)時間周轉(zhuǎn)時間J110:1010:1011:2575分鐘分鐘J210:2010:2010:5030分鐘分鐘J310:3010:5011:1545分鐘分鐘J410:5011:1511:4555分鐘分鐘平均周轉(zhuǎn)時間平均周轉(zhuǎn)時間=(75+30+45+55)/4=51.25(分鐘分鐘)313.2.5 基于時間片的輪轉(zhuǎn)調(diào)度算法基于時間片的

33、輪轉(zhuǎn)調(diào)度算法 用于進程調(diào)度。用于進程調(diào)度。早期，分時系統(tǒng)采用的是早期，分時系統(tǒng)采用的是簡單的時間片輪轉(zhuǎn)法簡單的時間片輪轉(zhuǎn)法； 9090年代后，廣泛采用年代后，廣泛采用多級反饋隊列調(diào)度算法多級反饋隊列調(diào)度算法。 1時間片輪轉(zhuǎn)法時間片輪轉(zhuǎn)法 n系統(tǒng)把就緒隊列中的所有進程，按先來先服務(wù)的系統(tǒng)把就緒隊列中的所有進程，按先來先服務(wù)的原則，排成一個隊列；原則，排成一個隊列； n每次調(diào)度時，把每次調(diào)度時，把CPU分配給隊首進程，并讓它執(zhí)分配給隊首進程，并讓它執(zhí)行一個時間片；行一個時間片； n每當(dāng)執(zhí)行的時間片用完，調(diào)度程序便停止該進程每當(dāng)執(zhí)行的時間片用完，調(diào)度程序便停止該進程的執(zhí)行，將其送入就緒隊列尾部；然后

34、進行下一的執(zhí)行，將其送入就緒隊列尾部；然后進行下一次進程調(diào)度。次進程調(diào)度。 時間片的大?。簬讜r間片的大?。簬譵s幾百幾百ms。 32【例例3-5】設(shè)有一個最多可有兩道作業(yè)同時裝入內(nèi)存執(zhí)設(shè)有一個最多可有兩道作業(yè)同時裝入內(nèi)存執(zhí)行的批處理系統(tǒng)，作業(yè)調(diào)度采用行的批處理系統(tǒng)，作業(yè)調(diào)度采用高響應(yīng)比優(yōu)先高響應(yīng)比優(yōu)先調(diào)度算調(diào)度算法，進程調(diào)度采用時間片輪轉(zhuǎn)調(diào)度算法法，進程調(diào)度采用時間片輪轉(zhuǎn)調(diào)度算法( (假設(shè)時間片為假設(shè)時間片為100ms) )，今有如下純計算型作業(yè)序列：，今有如下純計算型作業(yè)序列： (1)(1)列出所有作業(yè)進入內(nèi)存時間及結(jié)束時間。列出所有作業(yè)進入內(nèi)存時間及結(jié)束時間。 (2)(2)計算平均周轉(zhuǎn)時間

35、。計算平均周轉(zhuǎn)時間。 作業(yè)名作業(yè)名到達(dá)時間到達(dá)時間估計運行時間估計運行時間J110:1020分鐘分鐘J210:2030分鐘分鐘J310:3025分鐘分鐘J410:5020分鐘分鐘33先在草稿上分析如下：先在草稿上分析如下：10:10J1到達(dá)，調(diào)入內(nèi)存執(zhí)行到達(dá)，調(diào)入內(nèi)存執(zhí)行10:20J2到達(dá)，調(diào)入內(nèi)存與到達(dá)，調(diào)入內(nèi)存與J1一起均分一起均分CPU運行。運行。J1已運行已運行10分鐘，還需與分鐘，還需與J2一起運行一起運行20分鐘分鐘10:30J3到達(dá)，不調(diào)入內(nèi)存到達(dá)，不調(diào)入內(nèi)存10:40J1結(jié)束，結(jié)束，J3調(diào)入內(nèi)存與調(diào)入內(nèi)存與J2一起均分一起均分CPU運行。運行。J2已運行已運行10分鐘，還需與分

36、鐘，還需與J3一起運行一起運行40分鐘分鐘10:50J4到達(dá)，不調(diào)入內(nèi)存到達(dá)，不調(diào)入內(nèi)存11:20J2結(jié)束，結(jié)束，J4調(diào)入內(nèi)存與調(diào)入內(nèi)存與J3一起均分一起均分CPU運行。運行。J3已運行已運行20分鐘，還需與分鐘，還需與J4一起運行一起運行10分鐘分鐘11:30J3結(jié)束，結(jié)束，J4還需單獨運行還需單獨運行15分鐘分鐘11:45J4結(jié)束結(jié)束34作業(yè)名作業(yè)名調(diào)入時間調(diào)入時間結(jié)束時間結(jié)束時間周轉(zhuǎn)時間周轉(zhuǎn)時間J110:1010:4030分鐘分鐘J210:2011:2060分鐘分鐘J310:4011:3060分鐘分鐘J411:2011:4555分鐘分鐘(2)平均周轉(zhuǎn)時間平均周轉(zhuǎn)時間=(30+60+60+

37、55)/4=51.25(分鐘分鐘)解：解：(1)各作業(yè)進入內(nèi)存時間及結(jié)束時間如下表所示。各作業(yè)進入內(nèi)存時間及結(jié)束時間如下表所示。352多級反饋隊列調(diào)度算法多級反饋隊列調(diào)度算法 不必事先知道不必事先知道各進程所需的各進程所需的執(zhí)行時間，而執(zhí)行時間，而且還可以滿足且還可以滿足各種類型進程各種類型進程的需要。的需要。 目前被公認(rèn)的一目前被公認(rèn)的一種較好的進程調(diào)種較好的進程調(diào)度算法。度算法。 CPU完成完成就緒隊列就緒隊列1S1時間片用完時間片用完CPU完成完成就緒隊列就緒隊列2S2時間片用完時間片用完CPU完成完成就緒隊列就緒隊列3S3時間片用完時間片用完CPU完成完成就緒隊列就緒隊列nSn時間片用

38、完時間片用完新進程就緒新進程就緒(時間片時間片：S1S2S3Sn)優(yōu)先級：優(yōu)先級：S1S2S3S1S2S3SnSn) )圖圖3-4 3-4 多級反饋隊列調(diào)度算法多級反饋隊列調(diào)度算法阻塞進程阻塞進程I/O完成完成 或或等待的事件發(fā)等待的事件發(fā)生生CPU運行態(tài)運行態(tài)363. 多級反饋隊列調(diào)度算法的性能多級反饋隊列調(diào)度算法的性能多級反饋隊列調(diào)度算法具有較好的性能，能很好地多級反饋隊列調(diào)度算法具有較好的性能，能很好地滿足各種類型用戶的需要。滿足各種類型用戶的需要。(1)終端型作業(yè)用戶。交互型作業(yè)通常較小，系統(tǒng)只終端型作業(yè)用戶。交互型作業(yè)通常較小，系統(tǒng)只要能使這些作業(yè)要能使這些作業(yè)(進程進程)在第一隊列

39、所規(guī)定的時間在第一隊列所規(guī)定的時間片內(nèi)完成，便可使終端型作業(yè)片內(nèi)完成，便可使終端型作業(yè) 用戶感到滿意。用戶感到滿意。(2)短批處理作業(yè)用戶。如果僅在第一隊列中執(zhí)行一短批處理作業(yè)用戶。如果僅在第一隊列中執(zhí)行一個時間片即可完成，便可獲得終端型用戶一樣的個時間片即可完成，便可獲得終端型用戶一樣的響應(yīng)時間。對于稍長的作業(yè)，通常也只需在第二響應(yīng)時間。對于稍長的作業(yè)，通常也只需在第二或第三隊列各執(zhí)行一個時間片即可完成，其周轉(zhuǎn)或第三隊列各執(zhí)行一個時間片即可完成，其周轉(zhuǎn)時間仍然較短。時間仍然較短。(3)長批處理作業(yè)用戶。將依次在第長批處理作業(yè)用戶。將依次在第1, 2, , n個隊列個隊列中運行，然后再按輪轉(zhuǎn)方

40、式運行，用戶不必?fù)?dān)心中運行，然后再按輪轉(zhuǎn)方式運行，用戶不必?fù)?dān)心其作業(yè)長期得不到服務(wù)。其作業(yè)長期得不到服務(wù)。37演示進程調(diào)度算法演示進程調(diào)度算法進程調(diào)度實驗一進程調(diào)度實驗一383.3 實時調(diào)度實時調(diào)度 由于在實時系統(tǒng)中都存在著若干個實時由于在實時系統(tǒng)中都存在著若干個實時進程或任務(wù)，它們用來反應(yīng)或控制某個進程或任務(wù)，它們用來反應(yīng)或控制某個( (些些) )外部事件，往往帶有某種程度的緊迫性，因外部事件，往往帶有某種程度的緊迫性，因而對實時系統(tǒng)的調(diào)度提出了某些特殊要求，而對實時系統(tǒng)的調(diào)度提出了某些特殊要求，前面介紹的多種調(diào)度算法，并不能滿足實時前面介紹的多種調(diào)度算法，并不能滿足實時系統(tǒng)對調(diào)度的要求，為

41、此需引入一種新的調(diào)系統(tǒng)對調(diào)度的要求，為此需引入一種新的調(diào)度，即度，即實時調(diào)度實時調(diào)度。跳過實時調(diào)度和多處理機調(diào)度跳過實時調(diào)度和多處理機調(diào)度393.3.1 實現(xiàn)實時調(diào)度的基本條件實現(xiàn)實時調(diào)度的基本條件 在實時系統(tǒng)中，硬實時任務(wù)在實時系統(tǒng)中，硬實時任務(wù)(存在著必須滿足的時間限制存在著必須滿足的時間限制)和和軟實時任務(wù)軟實時任務(wù)(偶爾超過時間限制是可以容忍的偶爾超過時間限制是可以容忍的)都聯(lián)系著一個截止都聯(lián)系著一個截止時間。為了保證系統(tǒng)能正常工作，實時調(diào)度必須滿足實時任務(wù)對時間。為了保證系統(tǒng)能正常工作，實時調(diào)度必須滿足實時任務(wù)對截止時間的要求，為此，實現(xiàn)實時調(diào)度應(yīng)具備下述幾個條件：截止時間的要求，為

42、此，實現(xiàn)實時調(diào)度應(yīng)具備下述幾個條件：1提供必要的信息提供必要的信息系統(tǒng)應(yīng)向調(diào)度程序提供有關(guān)任務(wù)的下述信息：系統(tǒng)應(yīng)向調(diào)度程序提供有關(guān)任務(wù)的下述信息：(1)(1)就緒時間就緒時間。這是該任務(wù)成為就緒狀態(tài)的起始時間。這是該任務(wù)成為就緒狀態(tài)的起始時間(2)(2)開始截止時間和完成截止時間開始截止時間和完成截止時間。對于典型的實時應(yīng)用，。對于典型的實時應(yīng)用，只需知道開始截止時間，或者知道完成截止時間。只需知道開始截止時間，或者知道完成截止時間。(3)(3)處理時間處理時間。一個任務(wù)從開始執(zhí)行直至完成所需的時間。一個任務(wù)從開始執(zhí)行直至完成所需的時間。在某些情況下，該時間也是系統(tǒng)提供的。在某些情況下，該時間

43、也是系統(tǒng)提供的。(4)(4)資源要求資源要求。(5)(5)優(yōu)先級優(yōu)先級。若某任務(wù)的開始截止時間已經(jīng)錯過，就會引起。若某任務(wù)的開始截止時間已經(jīng)錯過，就會引起故障，則應(yīng)賦予該任務(wù)故障，則應(yīng)賦予該任務(wù)“絕對絕對”優(yōu)先級；如果對系統(tǒng)的繼優(yōu)先級；如果對系統(tǒng)的繼續(xù)運行無重大影響，則可賦予續(xù)運行無重大影響，則可賦予“相對相對”優(yōu)先級，供調(diào)度參優(yōu)先級，供調(diào)度參考?？肌?02系統(tǒng)處理能力強系統(tǒng)處理能力強 若處理機的處理能力不強，則有可能因處理機忙若處理機的處理能力不強，則有可能因處理機忙不過來而使某些實時任務(wù)不能得到及時處理，從而導(dǎo)不過來而使某些實時任務(wù)不能得到及時處理，從而導(dǎo)致發(fā)生難于預(yù)料的后果。致發(fā)生難于預(yù)

44、料的后果。 假定系統(tǒng)中有假定系統(tǒng)中有m個周期性硬實時任務(wù)，它們的處個周期性硬實時任務(wù)，它們的處理時間為理時間為Ci，周期時間為，周期時間為Pi，則在單處理機情況下，則在單處理機情況下，必須滿足下面的限制條件：必須滿足下面的限制條件：1.22111mmmiiiPCPCPCPC系統(tǒng)才是可調(diào)度的。系統(tǒng)才是可調(diào)度的。41例如例如 設(shè)系統(tǒng)中有設(shè)系統(tǒng)中有6個硬實時任務(wù)，它們的周期都是個硬實時任務(wù)，它們的周期都是50ms，而每次的處理時間都是，而每次的處理時間都是10ms，此時不能滿，此時不能滿足上式，因而系統(tǒng)是不可調(diào)度的。足上式，因而系統(tǒng)是不可調(diào)度的。又例如又例如 一個實時系統(tǒng)中有一個實時系統(tǒng)中有3個實時

45、事件流，其周期分別個實時事件流，其周期分別為為100ms、200ms和和500ms，每次的處理時間分別，每次的處理時間分別為為50ms、30ms和和100ms，則因為，則因為0.5+0.15+0.21故系統(tǒng)是可調(diào)度的。如果加入周期為故系統(tǒng)是可調(diào)度的。如果加入周期為1秒的第秒的第4個任務(wù)，個任務(wù)，則只要其處理時間不超過則只要其處理時間不超過150ms，系統(tǒng)仍是可調(diào)度，系統(tǒng)仍是可調(diào)度的。的。 當(dāng)然，上述運算的隱含條件是進行切換的時間足當(dāng)然，上述運算的隱含條件是進行切換的時間足夠小，可以忽略。夠小，可以忽略。42設(shè)實時任務(wù)設(shè)實時任務(wù)A、B、C，周期分別為，周期分別為100ms、200ms、500ms

46、，處理時間分別為處理時間分別為50ms、30ms、100ms，又設(shè)它們同時開始計，又設(shè)它們同時開始計時，則設(shè)想可有如下調(diào)度順序時，則設(shè)想可有如下調(diào)度順序(假設(shè)優(yōu)先級順序為假設(shè)優(yōu)先級順序為A、B、C)：ABCt(ms)100200300400500600700800900100011000思考思考：考慮加入一個周期為：考慮加入一個周期為1秒，處理時間為秒，處理時間為150ms的實的實時任務(wù)后的情況。時任務(wù)后的情況。43提高系統(tǒng)的可調(diào)度性的解決方法是提高系統(tǒng)的處理提高系統(tǒng)的可調(diào)度性的解決方法是提高系統(tǒng)的處理能力，其途徑有二：能力，其途徑有二：NPCmiii1 上述限制條件并未考慮任務(wù)的切換時間，包

47、括上述限制條件并未考慮任務(wù)的切換時間，包括執(zhí)行調(diào)度算法和進程任務(wù)切換，以及消息的傳遞時間執(zhí)行調(diào)度算法和進程任務(wù)切換，以及消息的傳遞時間等開銷，因此，當(dāng)利用上述限制條件來確定系統(tǒng)是否等開銷，因此，當(dāng)利用上述限制條件來確定系統(tǒng)是否可調(diào)度時，還應(yīng)適當(dāng)?shù)亓粲杏嗟亍？烧{(diào)度時，還應(yīng)適當(dāng)?shù)亓粲杏嗟?。n 仍采用單處理機系統(tǒng)，但需提高其處理能力，以仍采用單處理機系統(tǒng)，但需提高其處理能力，以顯著減少對每一個任務(wù)的處理時間；顯著減少對每一個任務(wù)的處理時間；n 采用多處理機系統(tǒng)，假設(shè)系統(tǒng)中處理機數(shù)為采用多處理機系統(tǒng)，假設(shè)系統(tǒng)中處理機數(shù)為N，則應(yīng)將上述限制條件改為：則應(yīng)將上述限制條件改為：443采用搶占式調(diào)度機制采用搶

48、占式調(diào)度機制 含有硬實時任務(wù)的實時系統(tǒng)中，廣泛采用搶占機含有硬實時任務(wù)的實時系統(tǒng)中，廣泛采用搶占機制。這樣可滿足硬實時任務(wù)對截止時間的要求，但這制。這樣可滿足硬實時任務(wù)對截止時間的要求，但這種調(diào)度機制比較復(fù)雜。種調(diào)度機制比較復(fù)雜。 對于一些小的實時系統(tǒng)，如果能預(yù)知任務(wù)的開始對于一些小的實時系統(tǒng)，如果能預(yù)知任務(wù)的開始截止時間，則對實時任務(wù)的調(diào)度可采用非搶占調(diào)度機截止時間，則對實時任務(wù)的調(diào)度可采用非搶占調(diào)度機制以簡化調(diào)度程序和對任務(wù)調(diào)度所花費的系統(tǒng)開銷。制以簡化調(diào)度程序和對任務(wù)調(diào)度所花費的系統(tǒng)開銷。但在設(shè)計這種調(diào)度機制時，應(yīng)使所有的實時任務(wù)都比但在設(shè)計這種調(diào)度機制時，應(yīng)使所有的實時任務(wù)都比較小，并

49、在執(zhí)行完關(guān)鍵性程序和臨界區(qū)后，能及時地較小，并在執(zhí)行完關(guān)鍵性程序和臨界區(qū)后，能及時地把自己阻塞起來，以便釋放處理機，供調(diào)度程序去調(diào)把自己阻塞起來，以便釋放處理機，供調(diào)度程序去調(diào)度那種開始截止時間即將到達(dá)的任務(wù)。度那種開始截止時間即將到達(dá)的任務(wù)。454具有快速切換機制具有快速切換機制 為了保證要求較高的硬實時任務(wù)能及時運行，為了保證要求較高的硬實時任務(wù)能及時運行，在實時系統(tǒng)中還應(yīng)具有快速切換機制，以保證能進在實時系統(tǒng)中還應(yīng)具有快速切換機制，以保證能進行任務(wù)的快速切換。該機制應(yīng)具有下述兩方面的能行任務(wù)的快速切換。該機制應(yīng)具有下述兩方面的能力：力：n對外部中斷的快速響應(yīng)能力。要求系統(tǒng)具有快對外部中斷

50、的快速響應(yīng)能力。要求系統(tǒng)具有快速硬件中斷機構(gòu)，還應(yīng)使禁止中斷的時間間隔速硬件中斷機構(gòu)，還應(yīng)使禁止中斷的時間間隔盡量短，以免耽誤其它緊迫任務(wù)。盡量短，以免耽誤其它緊迫任務(wù)。n快速的任務(wù)分派能力。在完成任務(wù)調(diào)度后，便快速的任務(wù)分派能力。在完成任務(wù)調(diào)度后，便應(yīng)進行任務(wù)切換。為了提高分派程序進行任務(wù)應(yīng)進行任務(wù)切換。為了提高分派程序進行任務(wù)切換時的速度，應(yīng)使系統(tǒng)中的每個運行功能單切換時的速度，應(yīng)使系統(tǒng)中的每個運行功能單位適當(dāng)?shù)男?，以減少任務(wù)切換的時間開銷。位適當(dāng)?shù)男?，以減少任務(wù)切換的時間開銷。463.3.2 實時調(diào)度算法的分類實時調(diào)度算法的分類n按實時任務(wù)性質(zhì)不同來劃分：按實時任務(wù)性質(zhì)不同來劃分：n硬實

51、時調(diào)度算法硬實時調(diào)度算法n軟實時調(diào)度算法軟實時調(diào)度算法n按調(diào)度方式的不同按調(diào)度方式的不同n非搶占調(diào)度算法非搶占調(diào)度算法n搶占調(diào)度算法搶占調(diào)度算法n因調(diào)度程序調(diào)度時間的不同因調(diào)度程序調(diào)度時間的不同n靜態(tài)調(diào)度算法靜態(tài)調(diào)度算法進程執(zhí)行前，調(diào)度程序便已經(jīng)決定進程執(zhí)行前，調(diào)度程序便已經(jīng)決定了個進程間的執(zhí)行順序了個進程間的執(zhí)行順序n動態(tài)調(diào)度算法動態(tài)調(diào)度算法n多處理機環(huán)境下多處理機環(huán)境下n集中式調(diào)度集中式調(diào)度n分布式調(diào)度分布式調(diào)度47下面討論按調(diào)度方式的不同對調(diào)度算法進行分類：下面討論按調(diào)度方式的不同對調(diào)度算法進行分類：1非搶占式調(diào)度算法非搶占式調(diào)度算法 算法比較簡單，易于實現(xiàn)，故在一些小型實時算法比較簡單

52、，易于實現(xiàn)，故在一些小型實時系統(tǒng)或要求不太嚴(yán)格的實時控制系統(tǒng)中，經(jīng)常采用系統(tǒng)或要求不太嚴(yán)格的實時控制系統(tǒng)中，經(jīng)常采用之。又可分成兩種：之。又可分成兩種： 非搶占式輪轉(zhuǎn)調(diào)度算法非搶占式輪轉(zhuǎn)調(diào)度算法。常用于工業(yè)生產(chǎn)的群控。常用于工業(yè)生產(chǎn)的群控系統(tǒng)中系統(tǒng)中,可用于要求不太嚴(yán)格的實時控制系統(tǒng)中。可用于要求不太嚴(yán)格的實時控制系統(tǒng)中。 非搶占式優(yōu)先調(diào)度算法非搶占式優(yōu)先調(diào)度算法。如果系統(tǒng)中存在要求較。如果系統(tǒng)中存在要求較為嚴(yán)格的任務(wù)為嚴(yán)格的任務(wù)( (響應(yīng)時間為數(shù)百毫秒響應(yīng)時間為數(shù)百毫秒) )，可采用此，可采用此算法?？捎糜谟幸欢ㄒ蟮膶崟r控制系統(tǒng)中。算法。可用于有一定要求的實時控制系統(tǒng)中。48進程進程1 進

53、程進程2 進程進程n 實時進程實時進程實時進程請求調(diào)度實時進程請求調(diào)度調(diào)度實時進程運行調(diào)度實時進程運行調(diào)度時間調(diào)度時間(a) 非搶占輪轉(zhuǎn)調(diào)度非搶占輪轉(zhuǎn)調(diào)度 當(dāng)前進程當(dāng)前進程 實時進程實時進程實時進程請求調(diào)度實時進程請求調(diào)度當(dāng)前進程運行當(dāng)前進程運行完成或阻塞完成或阻塞調(diào)度時間調(diào)度時間(b) 非搶占優(yōu)先權(quán)調(diào)度非搶占優(yōu)先權(quán)調(diào)度圖圖3-6 實時進程調(diào)度實時進程調(diào)度( (非搶占式非搶占式) )492搶占式調(diào)度算法搶占式調(diào)度算法 在要求較嚴(yán)格在要求較嚴(yán)格( (響應(yīng)時間為數(shù)十毫秒以下響應(yīng)時間為數(shù)十毫秒以下) )的實的實時系統(tǒng)中采用，可根據(jù)搶占發(fā)生時間的不同進而分時系統(tǒng)中采用，可根據(jù)搶占發(fā)生時間的不同進而分成

54、以下兩種算法：成以下兩種算法： 基于時鐘中斷的搶占式優(yōu)先權(quán)調(diào)度算法基于時鐘中斷的搶占式優(yōu)先權(quán)調(diào)度算法。在某。在某實時任務(wù)到達(dá)后，如果任務(wù)的優(yōu)先級高于當(dāng)前實時任務(wù)到達(dá)后，如果任務(wù)的優(yōu)先級高于當(dāng)前任務(wù)的優(yōu)先級，這時并不立即搶占當(dāng)前任務(wù)的任務(wù)的優(yōu)先級，這時并不立即搶占當(dāng)前任務(wù)的處理機，而是等到時鐘中斷到來時，調(diào)度程序處理機，而是等到時鐘中斷到來時，調(diào)度程序才剝奪當(dāng)前任務(wù)執(zhí)行，將處理機分配給新到的才剝奪當(dāng)前任務(wù)執(zhí)行，將處理機分配給新到的高優(yōu)先權(quán)任務(wù)。這種調(diào)度算法能獲得較好的響高優(yōu)先權(quán)任務(wù)。這種調(diào)度算法能獲得較好的響應(yīng)效果，其調(diào)度延時可降到幾十毫秒到幾毫秒。應(yīng)效果，其調(diào)度延時可降到幾十毫秒到幾毫秒。因此

55、，此算法可用于大多數(shù)的實時系統(tǒng)。因此，此算法可用于大多數(shù)的實時系統(tǒng)。50立即搶占的優(yōu)先權(quán)調(diào)度算法。這種調(diào)度策立即搶占的優(yōu)先權(quán)調(diào)度算法。這種調(diào)度策略要求操作系統(tǒng)具有快速響應(yīng)外部中斷事略要求操作系統(tǒng)具有快速響應(yīng)外部中斷事件的能力。一旦出現(xiàn)外部中斷，只要當(dāng)前件的能力。一旦出現(xiàn)外部中斷，只要當(dāng)前任務(wù)未處于臨界區(qū)，便可立即剝奪當(dāng)前任任務(wù)未處于臨界區(qū)，便可立即剝奪當(dāng)前任務(wù)的執(zhí)行，把處理機分配給請求中斷的緊務(wù)的執(zhí)行，把處理機分配給請求中斷的緊迫任務(wù)。這種算法能獲得非?？斓捻憫?yīng)，迫任務(wù)。這種算法能獲得非常快的響應(yīng)，可把調(diào)度延遲時間降低到幾毫秒至可把調(diào)度延遲時間降低到幾毫秒至100微秒，微秒，甚至更低。甚至更低

56、。51 當(dāng)前進程當(dāng)前進程 實時進程實時進程實時進程請求調(diào)度實時進程請求調(diào)度時鐘中斷到來時時鐘中斷到來時調(diào)度時間調(diào)度時間(c) 基于時鐘中斷搶占的優(yōu)先權(quán)調(diào)度基于時鐘中斷搶占的優(yōu)先權(quán)調(diào)度 當(dāng)前進程當(dāng)前進程 實時進程實時進程實時進程請求調(diào)度實時進程請求調(diào)度實時進程搶占當(dāng)前實時進程搶占當(dāng)前進程，并立即執(zhí)行進程，并立即執(zhí)行調(diào)度時間調(diào)度時間(d) 立即搶占的優(yōu)先權(quán)調(diào)度立即搶占的優(yōu)先權(quán)調(diào)度圖圖3-6 實時進程調(diào)度實時進程調(diào)度( (搶占式搶占式) )523.3.3 常用的幾種實時調(diào)度算法常用的幾種實時調(diào)度算法1最早截止時間優(yōu)先算法最早截止時間優(yōu)先算法 即即EDF(Earliest Deadling First

57、)算法算法u 根據(jù)任務(wù)的根據(jù)任務(wù)的開始截止時間開始截止時間來確定任務(wù)的優(yōu)先級。來確定任務(wù)的優(yōu)先級。截止時間愈早，其優(yōu)先級愈高。截止時間愈早，其優(yōu)先級愈高。u 實時任務(wù)就緒隊列按各任務(wù)的截止時間的早晚實時任務(wù)就緒隊列按各任務(wù)的截止時間的早晚排序。排序。u 可用于搶占式調(diào)度，也可用于非搶占式調(diào)度?？捎糜趽屨际秸{(diào)度，也可用于非搶占式調(diào)度。53 1 3 4 2開始截開始截止時間止時間任務(wù)執(zhí)行任務(wù)執(zhí)行任務(wù)到達(dá)任務(wù)到達(dá)12 341342t圖圖3-7 EDF算法用于非搶占調(diào)度方式算法用于非搶占調(diào)度方式設(shè)有設(shè)有4 4個非周期任務(wù)，它們先后到達(dá)。系統(tǒng)首先調(diào)度任務(wù)個非周期任務(wù)，它們先后到達(dá)。系統(tǒng)首先調(diào)度任務(wù)1 1

58、執(zhí)執(zhí)行，在任務(wù)行，在任務(wù)1 1執(zhí)行期間，任務(wù)執(zhí)行期間，任務(wù)2 2、3 3又先后到達(dá)。由于任務(wù)又先后到達(dá)。由于任務(wù)3 3的的開始截止時間早于任務(wù)開始截止時間早于任務(wù)2 2，故系統(tǒng)在任務(wù)，故系統(tǒng)在任務(wù)1 1后將調(diào)度任務(wù)后將調(diào)度任務(wù)3 3執(zhí)執(zhí)行。任務(wù)行。任務(wù)3 3執(zhí)行時，又到達(dá)任務(wù)執(zhí)行時，又到達(dá)任務(wù)4 4，其開始截止時間早于任務(wù)，其開始截止時間早于任務(wù)2 2，故任務(wù)，故任務(wù)3 3執(zhí)行完后，系統(tǒng)又調(diào)度任務(wù)執(zhí)行完后，系統(tǒng)又調(diào)度任務(wù)4 4執(zhí)行，最后才調(diào)度執(zhí)行，最后才調(diào)度任務(wù)任務(wù)2 2執(zhí)行。執(zhí)行。542最低松弛度優(yōu)先算法最低松弛度優(yōu)先算法 即即LLF(Least Laxity First)算法算法u 根據(jù)根

59、據(jù)任務(wù)緊急任務(wù)緊急( (或松弛或松弛) )的程度的程度來確定任務(wù)的優(yōu)來確定任務(wù)的優(yōu)先級。任務(wù)緊急程度愈高，其優(yōu)先級愈高。先級。任務(wù)緊急程度愈高，其優(yōu)先級愈高。u 實現(xiàn)該算法要求系統(tǒng)中有一個按松弛度排序的實現(xiàn)該算法要求系統(tǒng)中有一個按松弛度排序的實時任務(wù)就緒隊列，松弛度最低的任務(wù)排在隊實時任務(wù)就緒隊列，松弛度最低的任務(wù)排在隊列的最前面。列的最前面。u 主要用于可搶占式調(diào)度方式中。主要用于可搶占式調(diào)度方式中。例：例：松弛度的計算松弛度的計算一個任務(wù)在一個任務(wù)在200ms200ms之前必須完成，它本身需要運行之前必須完成，它本身需要運行100ms100ms，則該任務(wù)的緊急程度，則該任務(wù)的緊急程度( (

60、松弛程度松弛程度) )為為100ms100ms。55利用利用LLF算法進行調(diào)度的例子算法進行調(diào)度的例子在一個實時系統(tǒng)中，有在一個實時系統(tǒng)中，有2個周期性實時任務(wù)個周期性實時任務(wù)A和和B，任務(wù)，任務(wù)A要求要求每每20ms執(zhí)行一次，執(zhí)行時間為執(zhí)行一次，執(zhí)行時間為10ms；任務(wù)；任務(wù)B要求每要求每50ms執(zhí)執(zhí)行一次，執(zhí)行時間為行一次，執(zhí)行時間為25ms。由此可知任務(wù)。由此可知任務(wù)A和任務(wù)和任務(wù)B每次必每次必須完成的時間分別為：須完成的時間分別為：A1、A2、A3和和B1、B2、B3，見圖，見圖3-8。為保證不遺漏任何一次截止時間，應(yīng)采用最低松弛優(yōu)先。為保證不遺漏任何一次截止時間，應(yīng)采用最低松弛優(yōu)先的