第3章 處理機(jī)調(diào)試與死鎖

1、1第第3 3章章 處理機(jī)調(diào)度與死鎖處理機(jī)調(diào)度與死鎖3.1 3.1 處理機(jī)調(diào)度的基本概念處理機(jī)調(diào)度的基本概念3.2 3.2 調(diào)度算法調(diào)度算法3.3 3.3 實(shí)時(shí)調(diào)度實(shí)時(shí)調(diào)度 3.4 3.4 產(chǎn)生死鎖的原因和必要條件產(chǎn)生死鎖的原因和必要條件3.5 3.5 預(yù)防和避免死鎖的方法預(yù)防和避免死鎖的方法3.6 3.6 死鎖的檢測(cè)和解除死鎖的檢測(cè)和解除23.1 處理機(jī)調(diào)度的基本概念處理機(jī)調(diào)度的基本概念3.1.1 高級(jí)、中級(jí)和低級(jí)調(diào)度高級(jí)、中級(jí)和低級(jí)調(diào)度 1高級(jí)調(diào)度高級(jí)調(diào)度又稱(chēng)作業(yè)調(diào)度或長(zhǎng)調(diào)度又稱(chēng)作業(yè)調(diào)度或長(zhǎng)調(diào)度 用于決定把外存上后備隊(duì)列中哪些作業(yè)調(diào)入內(nèi)存，并用于決定把外存上后備隊(duì)列中哪些作業(yè)調(diào)入內(nèi)存，并為它

2、們創(chuàng)建進(jìn)程、分配必要的資源，然后將新創(chuàng)建的為它們創(chuàng)建進(jìn)程、分配必要的資源，然后將新創(chuàng)建的進(jìn)程插入到就緒隊(duì)列中，準(zhǔn)備運(yùn)行進(jìn)程插入到就緒隊(duì)列中，準(zhǔn)備運(yùn)行。定義定義每次作業(yè)調(diào)度，都需做以下兩個(gè)決定：每次作業(yè)調(diào)度，都需做以下兩個(gè)決定： 接納多少個(gè)作業(yè)接納多少個(gè)作業(yè)取決于多道程序度取決于多道程序度內(nèi)存中同時(shí)運(yùn)行的內(nèi)存中同時(shí)運(yùn)行的作業(yè)數(shù)目太多，會(huì)影作業(yè)數(shù)目太多，會(huì)影響系統(tǒng)的服務(wù)質(zhì)量。響系統(tǒng)的服務(wù)質(zhì)量。如，周轉(zhuǎn)時(shí)間長(zhǎng)。如，周轉(zhuǎn)時(shí)間長(zhǎng)。內(nèi)存中同時(shí)運(yùn)行的內(nèi)存中同時(shí)運(yùn)行的作業(yè)數(shù)目太少，會(huì)導(dǎo)作業(yè)數(shù)目太少，會(huì)導(dǎo)致系統(tǒng)資源利用率和致系統(tǒng)資源利用率和系統(tǒng)吞吐量低。系統(tǒng)吞吐量低。 接納哪些作業(yè)接納哪些作業(yè)取決于調(diào)度算法取決

3、于調(diào)度算法33.1 處理機(jī)調(diào)度的基本概念處理機(jī)調(diào)度的基本概念2低級(jí)調(diào)度低級(jí)調(diào)度 又稱(chēng)進(jìn)程調(diào)度或短調(diào)度。是最基本的調(diào)度，又稱(chēng)進(jìn)程調(diào)度或短調(diào)度。是最基本的調(diào)度，三種類(lèi)型三種類(lèi)型OS中，都必須配置此調(diào)度。中，都必須配置此調(diào)度。 定義定義用來(lái)決定就緒隊(duì)列中的哪個(gè)進(jìn)程應(yīng)獲得處理機(jī)，然后再用來(lái)決定就緒隊(duì)列中的哪個(gè)進(jìn)程應(yīng)獲得處理機(jī)，然后再由分派程序執(zhí)行把處理機(jī)分配給該進(jìn)程的具體操作。由分派程序執(zhí)行把處理機(jī)分配給該進(jìn)程的具體操作。 進(jìn)程調(diào)度可采用下述兩種調(diào)度方式：進(jìn)程調(diào)度可采用下述兩種調(diào)度方式： （1）非搶占方式）非搶占方式（2）搶占方式）搶占方式 一旦把處理機(jī)分配給某進(jìn)程后，便讓一旦把處理機(jī)分配給某進(jìn)程后，

4、便讓它一直執(zhí)行，直到該進(jìn)程完成或發(fā)生它一直執(zhí)行，直到該進(jìn)程完成或發(fā)生某事件而被阻塞時(shí)，才把處理機(jī)分配某事件而被阻塞時(shí)，才把處理機(jī)分配給其它進(jìn)程，決不允許某進(jìn)程搶占已給其它進(jìn)程，決不允許某進(jìn)程搶占已經(jīng)分配出去的處理機(jī)。經(jīng)分配出去的處理機(jī)。優(yōu)點(diǎn)：實(shí)現(xiàn)簡(jiǎn)單，系統(tǒng)開(kāi)銷(xiāo)小。優(yōu)點(diǎn)：實(shí)現(xiàn)簡(jiǎn)單，系統(tǒng)開(kāi)銷(xiāo)小。缺點(diǎn)：難于滿(mǎn)足緊急任務(wù)的要求。缺點(diǎn)：難于滿(mǎn)足緊急任務(wù)的要求。 允許調(diào)度程序根據(jù)某種原則，暫停某個(gè)允許調(diào)度程序根據(jù)某種原則，暫停某個(gè)正在執(zhí)行的進(jìn)程，將已分配給該進(jìn)程的正在執(zhí)行的進(jìn)程，將已分配給該進(jìn)程的處理機(jī)重新分配給另一進(jìn)程。處理機(jī)重新分配給另一進(jìn)程。 搶占原則有：搶占原則有： 優(yōu)先權(quán)原則；優(yōu)先權(quán)原則； 短作

5、業(yè)優(yōu)先原則；短作業(yè)優(yōu)先原則； 時(shí)間片原則。時(shí)間片原則。 43.1 處理機(jī)調(diào)度的基本概念處理機(jī)調(diào)度的基本概念n3. 中級(jí)調(diào)度中級(jí)調(diào)度 掛起和激活，存儲(chǔ)器管理中的對(duì)換功能。掛起和激活，存儲(chǔ)器管理中的對(duì)換功能。 主要目的：主要目的： 為了提高內(nèi)存的利用率和系統(tǒng)的吞吐量。為了提高內(nèi)存的利用率和系統(tǒng)的吞吐量。 主要介紹進(jìn)程調(diào)主要介紹進(jìn)程調(diào)度和作業(yè)調(diào)度。度和作業(yè)調(diào)度。三種調(diào)度相比較：三種調(diào)度相比較：進(jìn)程調(diào)度的運(yùn)行頻率最高進(jìn)程調(diào)度的運(yùn)行頻率最高 作業(yè)調(diào)度頻率最低作業(yè)調(diào)度頻率最低 中級(jí)調(diào)度界于之間中級(jí)調(diào)度界于之間 53.1.2 調(diào)度隊(duì)列模型調(diào)度隊(duì)列模型三種類(lèi)型的調(diào)度隊(duì)列模型：三種類(lèi)型的調(diào)度隊(duì)列模型： 1. 僅

6、有進(jìn)程調(diào)度的調(diào)度隊(duì)列模型僅有進(jìn)程調(diào)度的調(diào)度隊(duì)列模型 在在分時(shí)系統(tǒng)中，通常僅設(shè)置了進(jìn)程中，通常僅設(shè)置了進(jìn)程調(diào)度。常把就緒進(jìn)程組織成調(diào)度。常把就緒進(jìn)程組織成FIFO隊(duì)隊(duì)列形式。列形式。 阻塞隊(duì)列一阻塞隊(duì)列一般可能有多般可能有多個(gè)。個(gè)。就就 緒緒 隊(duì)隊(duì) 列列阻阻 塞塞 隊(duì)隊(duì) 列列交互用戶(hù)交互用戶(hù)進(jìn)程調(diào)度進(jìn)程調(diào)度CPU時(shí)間片完時(shí)間片完等待事件等待事件進(jìn)程進(jìn)程完成完成事件出現(xiàn)事件出現(xiàn)圖圖3-1 僅具有進(jìn)程調(diào)度的調(diào)度隊(duì)列模型僅具有進(jìn)程調(diào)度的調(diào)度隊(duì)列模型63.1.2 調(diào)度隊(duì)列模型調(diào)度隊(duì)列模型2. 具有高級(jí)和低級(jí)調(diào)度的調(diào)度隊(duì)列模型具有高級(jí)和低級(jí)調(diào)度的調(diào)度隊(duì)列模型 批處理系統(tǒng)中批處理系統(tǒng)中的調(diào)度模型的調(diào)度模型

7、比第一種情況比第一種情況多了后備隊(duì)列多了后備隊(duì)列就就 緒緒 隊(duì)隊(duì) 列列阻阻 塞塞 隊(duì)隊(duì) 列列1 1作業(yè)作業(yè)調(diào)度調(diào)度進(jìn)程調(diào)度進(jìn)程調(diào)度CPU時(shí)間片完時(shí)間片完等待事件等待事件1 1進(jìn)程進(jìn)程完成完成圖圖3-2 具有高、低兩級(jí)調(diào)度的調(diào)度隊(duì)列模型具有高、低兩級(jí)調(diào)度的調(diào)度隊(duì)列模型阻阻 塞塞 隊(duì)隊(duì) 列列2 2等待事件等待事件2 2阻阻 塞塞 隊(duì)隊(duì) 列列n n等待事件等待事件n n事件事件1 1出現(xiàn)出現(xiàn)事件事件2 2出現(xiàn)出現(xiàn)事件事件n n出現(xiàn)出現(xiàn)后備隊(duì)列后備隊(duì)列73.1.2 調(diào)度隊(duì)列模型調(diào)度隊(duì)列模型3. 同時(shí)具有三級(jí)調(diào)度的調(diào)度隊(duì)列模型同時(shí)具有三級(jí)調(diào)度的調(diào)度隊(duì)列模型 具有掛起狀具有掛起狀態(tài)的系統(tǒng)。態(tài)的系統(tǒng)。 83

8、.1.3 選擇調(diào)度方式和調(diào)度算法的若干準(zhǔn)則選擇調(diào)度方式和調(diào)度算法的若干準(zhǔn)則1面向用戶(hù)的準(zhǔn)則面向用戶(hù)的準(zhǔn)則 （1）周轉(zhuǎn)時(shí)間短。）周轉(zhuǎn)時(shí)間短。 評(píng)價(jià)評(píng)價(jià)批處理系統(tǒng)批處理系統(tǒng)的準(zhǔn)則之一的準(zhǔn)則之一周轉(zhuǎn)時(shí)間周轉(zhuǎn)時(shí)間 是指從作業(yè)被提交給系統(tǒng)開(kāi)始，到作業(yè)完是指從作業(yè)被提交給系統(tǒng)開(kāi)始，到作業(yè)完成這段時(shí)間間隔。成這段時(shí)間間隔。平均周轉(zhuǎn)時(shí)間平均周轉(zhuǎn)時(shí)間 舉例說(shuō)明舉例說(shuō)明（2）響應(yīng)時(shí)間快）響應(yīng)時(shí)間快 評(píng)價(jià)評(píng)價(jià)分時(shí)系統(tǒng)分時(shí)系統(tǒng)的準(zhǔn)則之一的準(zhǔn)則之一響應(yīng)時(shí)間響應(yīng)時(shí)間 是從用戶(hù)通過(guò)鍵盤(pán)提交一個(gè)請(qǐng)求開(kāi)始，到是從用戶(hù)通過(guò)鍵盤(pán)提交一個(gè)請(qǐng)求開(kāi)始，到系統(tǒng)首次產(chǎn)生響應(yīng)為止的時(shí)間。系統(tǒng)首次產(chǎn)生響應(yīng)為止的時(shí)間。 9在批處理、分時(shí)和實(shí)時(shí)系統(tǒng)

9、中選擇調(diào)度在批處理、分時(shí)和實(shí)時(shí)系統(tǒng)中選擇調(diào)度算法時(shí)，都可以遵循優(yōu)先權(quán)準(zhǔn)則，以便算法時(shí)，都可以遵循優(yōu)先權(quán)準(zhǔn)則，以便讓某些緊急的作業(yè)能得到及時(shí)處理。在讓某些緊急的作業(yè)能得到及時(shí)處理。在要求嚴(yán)格的場(chǎng)合，往往還須選擇搶占式要求嚴(yán)格的場(chǎng)合，往往還須選擇搶占式調(diào)度方式調(diào)度方式 （4）優(yōu)先權(quán)準(zhǔn)則）優(yōu)先權(quán)準(zhǔn)則 截止時(shí)間截止時(shí)間 是指某任務(wù)必須開(kāi)始執(zhí)行的最遲時(shí)間，是指某任務(wù)必須開(kāi)始執(zhí)行的最遲時(shí)間，或必須完成的最遲時(shí)間?；虮仨毻瓿傻淖钸t時(shí)間。 （3）截止時(shí)間的保證）截止時(shí)間的保證 評(píng)價(jià)評(píng)價(jià)實(shí)時(shí)系統(tǒng)實(shí)時(shí)系統(tǒng)的準(zhǔn)則之一的準(zhǔn)則之一103.1.3 選擇調(diào)度方式和調(diào)度算法的若干準(zhǔn)則選擇調(diào)度方式和調(diào)度算法的若干準(zhǔn)則2. 面向

10、系統(tǒng)的準(zhǔn)則面向系統(tǒng)的準(zhǔn)則 （1）系統(tǒng)吞吐量高）系統(tǒng)吞吐量高（2）處理機(jī)利用率好）處理機(jī)利用率好 （3）各類(lèi)資源的均衡利用）各類(lèi)資源的均衡利用 吞吐量吞吐量 單位時(shí)間內(nèi)系統(tǒng)單位時(shí)間內(nèi)系統(tǒng)所完成的作業(yè)數(shù)所完成的作業(yè)數(shù) 調(diào)度方式和算法對(duì)處理機(jī)的調(diào)度方式和算法對(duì)處理機(jī)的利用率起著十分重要的作用利用率起著十分重要的作用 對(duì)于單用戶(hù)微機(jī)或某些實(shí)對(duì)于單用戶(hù)微機(jī)或某些實(shí)時(shí)系統(tǒng)，該準(zhǔn)則并不重要時(shí)系統(tǒng)，該準(zhǔn)則并不重要 113.2 調(diào)度算法調(diào)度算法3.2.1 先來(lái)先服務(wù)調(diào)度算法先來(lái)先服務(wù)調(diào)度算法3.2.2 短作業(yè)短作業(yè)(進(jìn)程進(jìn)程)優(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.

11、4 高響應(yīng)比優(yōu)先調(diào)度算法高響應(yīng)比優(yōu)先調(diào)度算法3.2.5 基于時(shí)間片的輪轉(zhuǎn)調(diào)度算法基于時(shí)間片的輪轉(zhuǎn)調(diào)度算法 123.2.1 先來(lái)先服務(wù)調(diào)度算法先來(lái)先服務(wù)調(diào)度算法 FCFS調(diào)度算法是一種最簡(jiǎn)單的調(diào)度算法。調(diào)度算法是一種最簡(jiǎn)單的調(diào)度算法。既可用于既可用于作業(yè)調(diào)度作業(yè)調(diào)度，也可用于，也可用于進(jìn)程調(diào)度進(jìn)程調(diào)度。用于作業(yè)用于作業(yè)調(diào)度中：調(diào)度中： 從后備隊(duì)列作業(yè)中，選擇一個(gè)或幾個(gè)最先從后備隊(duì)列作業(yè)中，選擇一個(gè)或幾個(gè)最先進(jìn)入該隊(duì)列的作業(yè)，將它們調(diào)入內(nèi)存，為進(jìn)入該隊(duì)列的作業(yè)，將它們調(diào)入內(nèi)存，為它們分配資源、創(chuàng)建進(jìn)程，然后放入進(jìn)程它們分配資源、創(chuàng)建進(jìn)程，然后放入進(jìn)程就緒隊(duì)列。就緒隊(duì)列。 用于進(jìn)程用于進(jìn)程調(diào)度時(shí)：調(diào)

12、度時(shí)： 從就緒隊(duì)列中，選擇一個(gè)最先進(jìn)入該隊(duì)列從就緒隊(duì)列中，選擇一個(gè)最先進(jìn)入該隊(duì)列的進(jìn)程，為之分配處理機(jī)，使之投入運(yùn)行。的進(jìn)程，為之分配處理機(jī)，使之投入運(yùn)行。該進(jìn)程一直運(yùn)行到完成或發(fā)生某事件而阻該進(jìn)程一直運(yùn)行到完成或發(fā)生某事件而阻塞后，才放棄處理機(jī)。塞后，才放棄處理機(jī)。非搶占式非搶占式 13【例例3-1】設(shè)在單道系統(tǒng)中用設(shè)在單道系統(tǒng)中用FCFSFCFS算法調(diào)度如下作業(yè)，請(qǐng)完算法調(diào)度如下作業(yè)，請(qǐng)完成下表。成下表。進(jìn)程名進(jìn)程名 ABCDE平平 均均 到達(dá)時(shí)間到達(dá)時(shí)間 9:00 9:10 9:30 10:00 10:15 服務(wù)時(shí)間服務(wù)時(shí)間 30分鐘分鐘 1小時(shí)小時(shí) 10分鐘分鐘 50分鐘分鐘 20分鐘

13、分鐘 完成時(shí)間完成時(shí)間 周轉(zhuǎn)時(shí)間周轉(zhuǎn)時(shí)間 帶權(quán)周帶權(quán)周轉(zhuǎn)時(shí)間轉(zhuǎn)時(shí)間 80分鐘分鐘 9:30 30分鐘分鐘10:30 70分鐘分鐘 10:40 11:30 90分鐘分鐘 11:50 95分鐘分鐘 11.3371.84.7573分鐘分鐘 3.176FCFS算法比較有利于長(zhǎng)作業(yè)（進(jìn)程），不利于短作業(yè)（進(jìn)程）。算法比較有利于長(zhǎng)作業(yè)（進(jìn)程），不利于短作業(yè)（進(jìn)程）。有利于有利于CPU繁忙型作業(yè)（進(jìn)程），不利于繁忙型作業(yè)（進(jìn)程），不利于I/O繁忙型作業(yè)（進(jìn)程）繁忙型作業(yè)（進(jìn)程）因非搶占式因非搶占式 CPU繁忙型作業(yè)繁忙型作業(yè)需要大量的需要大量的CPU時(shí)間進(jìn)行計(jì)時(shí)間進(jìn)行計(jì)算，而很少請(qǐng)求算，而很少請(qǐng)求I/O。如

14、，科學(xué)計(jì)算。如，科學(xué)計(jì)算I/O繁忙型作業(yè)繁忙型作業(yè)是指是指CPU進(jìn)行處理時(shí)，需頻進(jìn)行處理時(shí)，需頻繁地請(qǐng)求繁地請(qǐng)求I/O。如，大多數(shù)事務(wù)處理。如，大多數(shù)事務(wù)處理 143.2.2 短作業(yè)短作業(yè)( (進(jìn)程進(jìn)程) )優(yōu)先調(diào)度算法優(yōu)先調(diào)度算法 短作業(yè)優(yōu)先（短作業(yè)優(yōu)先（SJF）調(diào)度算法）調(diào)度算法 從后備隊(duì)從后備隊(duì)列中選擇一個(gè)或幾個(gè)估計(jì)運(yùn)行時(shí)間最短的作列中選擇一個(gè)或幾個(gè)估計(jì)運(yùn)行時(shí)間最短的作業(yè)，將它調(diào)入內(nèi)存運(yùn)行。業(yè)，將它調(diào)入內(nèi)存運(yùn)行。短進(jìn)程優(yōu)先（短進(jìn)程優(yōu)先（SPF）調(diào)度算法）調(diào)度算法從就緒隊(duì)從就緒隊(duì)列中選擇一個(gè)估計(jì)運(yùn)行時(shí)間最短的作業(yè)，將列中選擇一個(gè)估計(jì)運(yùn)行時(shí)間最短的作業(yè)，將處理機(jī)分配給它，使它立即執(zhí)行并一直到

15、完處理機(jī)分配給它，使它立即執(zhí)行并一直到完成，或發(fā)生某事件而被阻塞放棄處理機(jī)時(shí)，成，或發(fā)生某事件而被阻塞放棄處理機(jī)時(shí)，再重新調(diào)度。再重新調(diào)度。( (非搶占式非搶占式) ) 15【例例3-2】 設(shè)在單道系統(tǒng)中用設(shè)在單道系統(tǒng)中用SJF算法調(diào)度如下作業(yè)，請(qǐng)完算法調(diào)度如下作業(yè)，請(qǐng)完成下表。成下表。進(jìn)程名進(jìn)程名 ABCDE平平 均均 到達(dá)時(shí)間到達(dá)時(shí)間 9:00 9:10 9:30 10:00 10:15 服務(wù)時(shí)間服務(wù)時(shí)間 30分鐘分鐘 1小時(shí)小時(shí) 10分鐘分鐘 50分鐘分鐘 20分鐘分鐘 完成時(shí)間完成時(shí)間 周轉(zhuǎn)時(shí)間周轉(zhuǎn)時(shí)間 在黑板上畫(huà)此表格，請(qǐng)學(xué)生填表。在黑板上畫(huà)此表格，請(qǐng)學(xué)生填表。16SJF調(diào)度算法的優(yōu)

16、點(diǎn)調(diào)度算法的優(yōu)點(diǎn)：SJF調(diào)度算法的缺點(diǎn)調(diào)度算法的缺點(diǎn)： n該算法對(duì)長(zhǎng)作業(yè)不利該算法對(duì)長(zhǎng)作業(yè)不利長(zhǎng)作業(yè)可能長(zhǎng)期不被長(zhǎng)作業(yè)可能長(zhǎng)期不被調(diào)度，甚至調(diào)度，甚至“餓死餓死”。n未考慮作業(yè)的緊迫性，不能保證緊迫作業(yè)（進(jìn)未考慮作業(yè)的緊迫性，不能保證緊迫作業(yè)（進(jìn)程）會(huì)被及時(shí)調(diào)度。程）會(huì)被及時(shí)調(diào)度。 n由于作業(yè)（進(jìn)程）的長(zhǎng)短只是根據(jù)用戶(hù)所提供由于作業(yè)（進(jìn)程）的長(zhǎng)短只是根據(jù)用戶(hù)所提供的估計(jì)時(shí)間而定的，致使該算法不一定能真正的估計(jì)時(shí)間而定的，致使該算法不一定能真正做到短作業(yè)優(yōu)先調(diào)度。做到短作業(yè)優(yōu)先調(diào)度。 當(dāng)多個(gè)作業(yè)同時(shí)到達(dá)時(shí)，當(dāng)多個(gè)作業(yè)同時(shí)到達(dá)時(shí)，SJF算法可使平均周轉(zhuǎn)時(shí)算法可使平均周轉(zhuǎn)時(shí)間最短。間最短。173.2

17、.3 高優(yōu)先權(quán)優(yōu)先調(diào)度算法高優(yōu)先權(quán)優(yōu)先調(diào)度算法 引入的目的：引入的目的：為了照顧緊迫型作業(yè)，使之在進(jìn)入系統(tǒng)后便獲得優(yōu)先處理。為了照顧緊迫型作業(yè)，使之在進(jìn)入系統(tǒng)后便獲得優(yōu)先處理。 優(yōu)先權(quán)作業(yè)調(diào)度優(yōu)先權(quán)作業(yè)調(diào)度 系統(tǒng)從后備中選擇一個(gè)或幾個(gè)優(yōu)先權(quán)系統(tǒng)從后備中選擇一個(gè)或幾個(gè)優(yōu)先權(quán)最高的作業(yè)，將它調(diào)入內(nèi)存運(yùn)行。最高的作業(yè)，將它調(diào)入內(nèi)存運(yùn)行。 優(yōu)先權(quán)進(jìn)程調(diào)度優(yōu)先權(quán)進(jìn)程調(diào)度 系統(tǒng)將處理機(jī)分配給就緒隊(duì)列中一個(gè)系統(tǒng)將處理機(jī)分配給就緒隊(duì)列中一個(gè)優(yōu)先權(quán)最高的進(jìn)程。優(yōu)先權(quán)最高的進(jìn)程。 適用范圍：適用范圍： 批處理系統(tǒng)的作業(yè)調(diào)度批處理系統(tǒng)的作業(yè)調(diào)度 多種操作系統(tǒng)的進(jìn)程調(diào)度多種操作系統(tǒng)的進(jìn)程調(diào)度 還適用于實(shí)時(shí)系統(tǒng)還適用于

18、實(shí)時(shí)系統(tǒng) 181優(yōu)先權(quán)進(jìn)程調(diào)度算法的類(lèi)型優(yōu)先權(quán)進(jìn)程調(diào)度算法的類(lèi)型 非搶占式優(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)一旦把處理機(jī)分配給就緒隊(duì)列中優(yōu)先權(quán)最高的進(jìn)程后，系統(tǒng)一旦把處理機(jī)分配給就緒隊(duì)列中優(yōu)先權(quán)最高的進(jìn)程后，該進(jìn)程便一直執(zhí)行下去，直到完成，或因發(fā)生某事件使該進(jìn)該進(jìn)程便一直執(zhí)行下去，直到完成，或因發(fā)生某事件使該進(jìn)程放棄處理機(jī)時(shí)，系統(tǒng)方可再將處理機(jī)重新分配給另一個(gè)優(yōu)程放棄處理機(jī)時(shí)，系統(tǒng)方可再將處理機(jī)重新分配給另一個(gè)優(yōu)先權(quán)最高的進(jìn)程。先權(quán)最高的進(jìn)程。 搶占式優(yōu)先權(quán)算法搶占式優(yōu)先權(quán)算法 系統(tǒng)把處理機(jī)分配給就緒隊(duì)列中優(yōu)先權(quán)最高的進(jìn)程

19、，使之執(zhí)系統(tǒng)把處理機(jī)分配給就緒隊(duì)列中優(yōu)先權(quán)最高的進(jìn)程，使之執(zhí)行，但在其執(zhí)行期間，只要出現(xiàn)了另一個(gè)優(yōu)先權(quán)更高的進(jìn)程，行，但在其執(zhí)行期間，只要出現(xiàn)了另一個(gè)優(yōu)先權(quán)更高的進(jìn)程，系統(tǒng)就立即停止當(dāng)前進(jìn)程的執(zhí)行，重新將處理機(jī)分配給新的系統(tǒng)就立即停止當(dāng)前進(jìn)程的執(zhí)行，重新將處理機(jī)分配給新的優(yōu)先權(quán)最高的進(jìn)程。優(yōu)先權(quán)最高的進(jìn)程。 它能更好地滿(mǎn)足緊迫作業(yè)的要求。常用于實(shí)時(shí)系統(tǒng)中，以它能更好地滿(mǎn)足緊迫作業(yè)的要求。常用于實(shí)時(shí)系統(tǒng)中，以及對(duì)實(shí)時(shí)性能要求較高的批處理系統(tǒng)和分時(shí)系統(tǒng)中。及對(duì)實(shí)時(shí)性能要求較高的批處理系統(tǒng)和分時(shí)系統(tǒng)中。 192優(yōu)先權(quán)的類(lèi)型優(yōu)先權(quán)的類(lèi)型 靜態(tài)優(yōu)先權(quán)靜態(tài)優(yōu)先權(quán) 動(dòng)態(tài)優(yōu)先權(quán)動(dòng)態(tài)優(yōu)先權(quán) 1）靜態(tài)優(yōu)先權(quán)靜態(tài)優(yōu)

20、先權(quán) 靜態(tài)優(yōu)先權(quán)靜態(tài)優(yōu)先權(quán)它是在創(chuàng)建進(jìn)程時(shí)確定的，且在進(jìn)程整個(gè)運(yùn)它是在創(chuàng)建進(jìn)程時(shí)確定的，且在進(jìn)程整個(gè)運(yùn)行期間保持不變。行期間保持不變。優(yōu)先權(quán)一般用某一范圍內(nèi)的一個(gè)整數(shù)來(lái)表示。優(yōu)先權(quán)一般用某一范圍內(nèi)的一個(gè)整數(shù)來(lái)表示。有的系統(tǒng)用有的系統(tǒng)用“0”表示最高優(yōu)先權(quán)，數(shù)值越大，優(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ù)：常有三方面常有三方面 進(jìn)程類(lèi)型進(jìn)程類(lèi)型 系統(tǒng)進(jìn)程（如接收進(jìn)程、對(duì)換進(jìn)程、磁盤(pán)系統(tǒng)進(jìn)程（如接收進(jìn)程、對(duì)換進(jìn)程、磁盤(pán)I/OI/O進(jìn)程等）的進(jìn)程等）的優(yōu)先權(quán)高于一般用戶(hù)進(jìn)程的優(yōu)先權(quán)。優(yōu)先權(quán)高于一般用戶(hù)進(jìn)程的優(yōu)先權(quán)。進(jìn)程

21、對(duì)資源的需求進(jìn)程對(duì)資源的需求 如進(jìn)程的估計(jì)執(zhí)行時(shí)間及內(nèi)存需求量的多少，對(duì)如進(jìn)程的估計(jì)執(zhí)行時(shí)間及內(nèi)存需求量的多少，對(duì)這些要求少的進(jìn)程賦予較高的優(yōu)先權(quán)。這些要求少的進(jìn)程賦予較高的優(yōu)先權(quán)。 用戶(hù)要求用戶(hù)要求 這是由用戶(hù)進(jìn)程的緊迫程度和用戶(hù)所付費(fèi)用的多少來(lái)確定這是由用戶(hù)進(jìn)程的緊迫程度和用戶(hù)所付費(fèi)用的多少來(lái)確定優(yōu)先權(quán)的。優(yōu)先權(quán)的。 靜態(tài)優(yōu)先權(quán)的優(yōu)缺點(diǎn)：靜態(tài)優(yōu)先權(quán)的優(yōu)缺點(diǎn)：優(yōu)點(diǎn)優(yōu)點(diǎn)：簡(jiǎn)單易行，系統(tǒng)開(kāi)銷(xiāo)小。：簡(jiǎn)單易行，系統(tǒng)開(kāi)銷(xiāo)小。 缺點(diǎn)缺點(diǎn)：優(yōu)先權(quán)低的作業(yè)（進(jìn)程）可能：優(yōu)先權(quán)低的作業(yè)（進(jìn)程）可能長(zhǎng)期得不到調(diào)度。長(zhǎng)期得不到調(diào)度。 202）動(dòng)態(tài)優(yōu)先權(quán)動(dòng)態(tài)優(yōu)先權(quán) 動(dòng)態(tài)優(yōu)先權(quán)動(dòng)態(tài)優(yōu)先權(quán)在創(chuàng)建進(jìn)程時(shí)所賦予的優(yōu)先權(quán)，是

22、在創(chuàng)建進(jìn)程時(shí)所賦予的優(yōu)先權(quán)，是可以隨進(jìn)程得推進(jìn)，或隨其等待時(shí)間的增加而改變可以隨進(jìn)程得推進(jìn)，或隨其等待時(shí)間的增加而改變的，以便獲得更好的調(diào)度性。的，以便獲得更好的調(diào)度性。 例如：例如： n在就緒隊(duì)列中的進(jìn)程，隨其等待時(shí)間的增長(zhǎng)，其在就緒隊(duì)列中的進(jìn)程，隨其等待時(shí)間的增長(zhǎng)，其優(yōu)先權(quán)以速率優(yōu)先權(quán)以速率提高；提高； n在采用搶占式優(yōu)先權(quán)調(diào)度算法時(shí)，如果再規(guī)定當(dāng)在采用搶占式優(yōu)先權(quán)調(diào)度算法時(shí)，如果再規(guī)定當(dāng)前執(zhí)行進(jìn)程以速率前執(zhí)行進(jìn)程以速率下降，則可防止一個(gè)長(zhǎng)作業(yè)下降，則可防止一個(gè)長(zhǎng)作業(yè)長(zhǎng)期壟斷處理機(jī)。長(zhǎng)期壟斷處理機(jī)。 21UNIX采用計(jì)算的方法動(dòng)態(tài)改變進(jìn)程的優(yōu)先數(shù)。在采用計(jì)算的方法動(dòng)態(tài)改變進(jìn)程的優(yōu)先數(shù)。在U

23、NIX System V版本中，進(jìn)程優(yōu)先數(shù)版本中，進(jìn)程優(yōu)先數(shù)p_pri的算式如下：的算式如下：p_pri=p_cpu/2+PUSER+p_nice+NZERO其中，其中，PUSER和和NZERO是偏置常數(shù)，分別為是偏置常數(shù)，分別為25和和20。p_cpu和和p_nice是基本進(jìn)程控制塊中的兩個(gè)項(xiàng)，分別表示進(jìn)是基本進(jìn)程控制塊中的兩個(gè)項(xiàng)，分別表示進(jìn)程使用處理器的情況和用戶(hù)自己設(shè)置的計(jì)算優(yōu)先數(shù)的偏置程使用處理器的情況和用戶(hù)自己設(shè)置的計(jì)算優(yōu)先數(shù)的偏置量。量。系統(tǒng)對(duì)正在占用系統(tǒng)對(duì)正在占用CPU的進(jìn)程每隔一個(gè)時(shí)鐘周期的進(jìn)程每隔一個(gè)時(shí)鐘周期(20ms)對(duì)其對(duì)其p_cpu加加1。這使得占用處理器時(shí)間長(zhǎng)的進(jìn)程的

24、。這使得占用處理器時(shí)間長(zhǎng)的進(jìn)程的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對(duì)所有進(jìn)程執(zhí)行對(duì)所有進(jìn)程執(zhí)行p_cpu/2，這使就緒進(jìn)程優(yōu)先級(jí)，這使就緒進(jìn)程優(yōu)先級(jí)提高。提高。p_nice的值允許用戶(hù)根據(jù)任務(wù)的輕重緩急程度來(lái)設(shè)置，其值的值允許用戶(hù)根據(jù)任務(wù)的輕重緩急程度來(lái)設(shè)置，其值在在039之間。一旦一個(gè)進(jìn)程的之間。一旦一個(gè)進(jìn)程的p_nice設(shè)置后，此后用戶(hù)只設(shè)置后，此后用戶(hù)只能使其值增加。能使其值增加。22【例例3-3】設(shè)有一個(gè)最多可有兩道作業(yè)同時(shí)裝入內(nèi)存執(zhí)設(shè)有一個(gè)最多可有兩道作業(yè)同時(shí)裝入內(nèi)存執(zhí)行的批處理系統(tǒng)，作業(yè)調(diào)度采用最短作業(yè)

25、優(yōu)先調(diào)度算行的批處理系統(tǒng)，作業(yè)調(diào)度采用最短作業(yè)優(yōu)先調(diào)度算法，進(jìn)程調(diào)度采用搶占式靜態(tài)優(yōu)先權(quán)調(diào)度算法，今有法，進(jìn)程調(diào)度采用搶占式靜態(tài)優(yōu)先權(quán)調(diào)度算法，今有如下純計(jì)算型作業(yè)序列（表中所列進(jìn)程優(yōu)先數(shù)中，數(shù)如下純計(jì)算型作業(yè)序列（表中所列進(jìn)程優(yōu)先數(shù)中，數(shù)值越小優(yōu)先權(quán)越高）：值越小優(yōu)先權(quán)越高）： (1)(1)列出所有作業(yè)進(jìn)入內(nèi)存時(shí)間及結(jié)束時(shí)間。列出所有作業(yè)進(jìn)入內(nèi)存時(shí)間及結(jié)束時(shí)間。 (2)(2)計(jì)算平均周轉(zhuǎn)時(shí)間。計(jì)算平均周轉(zhuǎn)時(shí)間。 作業(yè)名作業(yè)名到達(dá)時(shí)間到達(dá)時(shí)間估計(jì)運(yùn)行時(shí)間估計(jì)運(yùn)行時(shí)間進(jìn)程優(yōu)先數(shù)進(jìn)程優(yōu)先數(shù)J110:1020分鐘分鐘5J210:2030分鐘分鐘3J310:3025分鐘分鐘4J410:5020分鐘分鐘

26、623作業(yè)名作業(yè)名提交時(shí)間提交時(shí)間進(jìn)入時(shí)間進(jìn)入時(shí)間結(jié)束時(shí)間結(jié)束時(shí)間周轉(zhuǎn)時(shí)間周轉(zhuǎn)時(shí)間J110:1010:1011:0050分鐘分鐘J210:2010:2010:5030分鐘分鐘J310:3011:0011:2555分鐘分鐘J410:5010:5011:4555分鐘分鐘平均周轉(zhuǎn)時(shí)間平均周轉(zhuǎn)時(shí)間=(50+30+55+55)4=47.5(分鐘分鐘)243.2.4 高響應(yīng)比優(yōu)先調(diào)度算法高響應(yīng)比優(yōu)先調(diào)度算法 響應(yīng)比響應(yīng)比( (等待時(shí)間等待時(shí)間+ +要求服務(wù)時(shí)間要求服務(wù)時(shí)間)/)/要求服務(wù)時(shí)間要求服務(wù)時(shí)間（實(shí)際上響應(yīng)比是動(dòng)態(tài)優(yōu)先權(quán)）（實(shí)際上響應(yīng)比是動(dòng)態(tài)優(yōu)先權(quán)） 高響應(yīng)比優(yōu)先調(diào)度算法高響應(yīng)比優(yōu)先調(diào)度算法 每次

27、要進(jìn)行作業(yè)調(diào)度時(shí)，系統(tǒng)每次要進(jìn)行作業(yè)調(diào)度時(shí)，系統(tǒng)首先計(jì)算后備隊(duì)列中各作業(yè)的首先計(jì)算后備隊(duì)列中各作業(yè)的響應(yīng)比，然后選擇一個(gè)或若干響應(yīng)比，然后選擇一個(gè)或若干個(gè)響應(yīng)比最高的作業(yè)調(diào)入內(nèi)存?zhèn)€響應(yīng)比最高的作業(yè)調(diào)入內(nèi)存執(zhí)行。執(zhí)行。 該算法綜合了該算法綜合了FCFS和和SJF算法的算法的優(yōu)點(diǎn)優(yōu)點(diǎn)既考慮公平性，又既考慮公平性，又考慮平均周轉(zhuǎn)時(shí)間考慮平均周轉(zhuǎn)時(shí)間缺點(diǎn)缺點(diǎn)是會(huì)增加系統(tǒng)開(kāi)銷(xiāo)是會(huì)增加系統(tǒng)開(kāi)銷(xiāo)每次調(diào)度都要計(jì)算響應(yīng)比。每次調(diào)度都要計(jì)算響應(yīng)比。 2524下列進(jìn)程調(diào)度算法中，綜合考慮進(jìn)程等待時(shí)間下列進(jìn)程調(diào)度算法中，綜合考慮進(jìn)程等待時(shí)間和執(zhí)行時(shí)間的是和執(zhí)行時(shí)間的是_。(2009(2009全國(guó)考研第全國(guó)考研第242

28、4題題) )A時(shí)間片輪轉(zhuǎn)調(diào)度算法時(shí)間片輪轉(zhuǎn)調(diào)度算法B短進(jìn)程優(yōu)先調(diào)度算法短進(jìn)程優(yōu)先調(diào)度算法C先來(lái)先服務(wù)調(diào)度算法先來(lái)先服務(wù)調(diào)度算法D高響應(yīng)比優(yōu)先調(diào)度算法高響應(yīng)比優(yōu)先調(diào)度算法26【例例3-4】設(shè)有一個(gè)最多可有兩道作業(yè)同時(shí)裝入內(nèi)存執(zhí)設(shè)有一個(gè)最多可有兩道作業(yè)同時(shí)裝入內(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)度算法，進(jìn)程調(diào)度采用搶占式靜態(tài)優(yōu)先權(quán)調(diào)度算法，今有法，進(jìn)程調(diào)度采用搶占式靜態(tài)優(yōu)先權(quán)調(diào)度算法，今有如下純計(jì)算型作業(yè)序列（假設(shè)表中所列進(jìn)程優(yōu)先數(shù)中，如下純計(jì)算型作業(yè)序列（假設(shè)表中所列進(jìn)程優(yōu)先數(shù)中，數(shù)值越小優(yōu)先權(quán)越高）：數(shù)值越小優(yōu)先權(quán)越高）： (1)(1)

29、列出所有作業(yè)進(jìn)入內(nèi)存時(shí)間及結(jié)束時(shí)間。列出所有作業(yè)進(jìn)入內(nèi)存時(shí)間及結(jié)束時(shí)間。 (2)(2)計(jì)算平均周轉(zhuǎn)時(shí)間。計(jì)算平均周轉(zhuǎn)時(shí)間。 作業(yè)名作業(yè)名到達(dá)時(shí)間到達(dá)時(shí)間估計(jì)運(yùn)行時(shí)間估計(jì)運(yùn)行時(shí)間進(jìn)程優(yōu)先數(shù)進(jìn)程優(yōu)先數(shù)J110:1020分鐘分鐘5J210:2030分鐘分鐘3J310:3025分鐘分鐘4J410:5020分鐘分鐘627J1CPU10: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一個(gè)作業(yè)，調(diào)入內(nèi)存執(zhí)行。一個(gè)作業(yè)，調(diào)入內(nèi)存執(zhí)行

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

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

32、送入就緒隊(duì)列尾部；然后進(jìn)行下一次進(jìn)程調(diào)度。次進(jìn)程調(diào)度。 時(shí)間片的大?。簬讜r(shí)間片的大?。簬譵s幾百幾百ms。 302多級(jí)反饋隊(duì)列調(diào)度算法多級(jí)反饋隊(duì)列調(diào)度算法 不必事先知道不必事先知道各進(jìn)程所需的各進(jìn)程所需的執(zhí)行時(shí)間，而執(zhí)行時(shí)間，而且還可以滿(mǎn)足且還可以滿(mǎn)足各種類(lèi)型進(jìn)程各種類(lèi)型進(jìn)程的需要。的需要。 目前被公認(rèn)的一目前被公認(rèn)的一種較好的進(jìn)程調(diào)種較好的進(jìn)程調(diào)度算法。度算法。 CPU完成完成就緒隊(duì)列就緒隊(duì)列1S1時(shí)間片用完時(shí)間片用完CPU完成完成就緒隊(duì)列就緒隊(duì)列2S2時(shí)間片用完時(shí)間片用完CPU完成完成就緒隊(duì)列就緒隊(duì)列3S3時(shí)間片用完時(shí)間片用完CPU完成完成就緒隊(duì)列就緒隊(duì)列nSn時(shí)間片用完時(shí)間片用完新進(jìn)程就

33、緒新進(jìn)程就緒(時(shí)間片時(shí)間片：S1S2S3Sn)圖圖3-4 3-4 多級(jí)反饋隊(duì)列調(diào)度算法多級(jí)反饋隊(duì)列調(diào)度算法阻塞進(jìn)程阻塞進(jìn)程I/O完成完成 或或等待的事件發(fā)等待的事件發(fā)生生CPU運(yùn)行態(tài)運(yùn)行態(tài)313. 多級(jí)反饋隊(duì)列調(diào)度算法的性能多級(jí)反饋隊(duì)列調(diào)度算法的性能多級(jí)反饋隊(duì)列調(diào)度算法具有較好的性能，能很好地多級(jí)反饋隊(duì)列調(diào)度算法具有較好的性能，能很好地滿(mǎn)足各種類(lèi)型用戶(hù)的需要。滿(mǎn)足各種類(lèi)型用戶(hù)的需要。(1)終端型作業(yè)用戶(hù)。交互型作業(yè)通常較小，系統(tǒng)只終端型作業(yè)用戶(hù)。交互型作業(yè)通常較小，系統(tǒng)只要能使這些作業(yè)要能使這些作業(yè)(進(jìn)程進(jìn)程)在第一隊(duì)列所規(guī)定的時(shí)間在第一隊(duì)列所規(guī)定的時(shí)間片內(nèi)完成，便可使終端型作業(yè)片內(nèi)完成，便可

34、使終端型作業(yè) 用戶(hù)感到滿(mǎn)意。用戶(hù)感到滿(mǎn)意。(2)短批處理作業(yè)用戶(hù)。如果僅在第一隊(duì)列中執(zhí)行一短批處理作業(yè)用戶(hù)。如果僅在第一隊(duì)列中執(zhí)行一個(gè)時(shí)間片即可完成，便可獲得終端型用戶(hù)一樣的個(gè)時(shí)間片即可完成，便可獲得終端型用戶(hù)一樣的響應(yīng)時(shí)間。對(duì)于稍長(zhǎng)的作業(yè)，通常也只需在第二響應(yīng)時(shí)間。對(duì)于稍長(zhǎng)的作業(yè)，通常也只需在第二或第三隊(duì)列各執(zhí)行一個(gè)時(shí)間片即可完成，其周轉(zhuǎn)或第三隊(duì)列各執(zhí)行一個(gè)時(shí)間片即可完成，其周轉(zhuǎn)時(shí)間仍然較短。時(shí)間仍然較短。(3)長(zhǎng)批處理作業(yè)用戶(hù)。將依次在第長(zhǎng)批處理作業(yè)用戶(hù)。將依次在第1, 2, , n個(gè)隊(duì)列個(gè)隊(duì)列中運(yùn)行，然后再按輪轉(zhuǎn)方式運(yùn)行，用戶(hù)不必?fù)?dān)心中運(yùn)行，然后再按輪轉(zhuǎn)方式運(yùn)行，用戶(hù)不必?fù)?dān)心其作業(yè)長(zhǎng)期得

35、不到服務(wù)。其作業(yè)長(zhǎng)期得不到服務(wù)。32【例例3-5】設(shè)有一個(gè)最多可有兩道作業(yè)同時(shí)裝入內(nèi)存執(zhí)設(shè)有一個(gè)最多可有兩道作業(yè)同時(shí)裝入內(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)度算法，進(jìn)程調(diào)度采用時(shí)間片輪轉(zhuǎn)調(diào)度算法法，進(jìn)程調(diào)度采用時(shí)間片輪轉(zhuǎn)調(diào)度算法( (假設(shè)時(shí)間片為假設(shè)時(shí)間片為100ms) )，今有如下純計(jì)算型作業(yè)序列：，今有如下純計(jì)算型作業(yè)序列： (1)(1)列出所有作業(yè)進(jìn)入內(nèi)存時(shí)間及結(jié)束時(shí)間。列出所有作業(yè)進(jìn)入內(nèi)存時(shí)間及結(jié)束時(shí)間。 (2)(2)計(jì)算平均周轉(zhuǎn)時(shí)間。計(jì)算平均周轉(zhuǎn)時(shí)間。 作業(yè)名作業(yè)名到達(dá)時(shí)間到達(dá)時(shí)間估計(jì)運(yùn)行時(shí)間估計(jì)運(yùn)行時(shí)間J110:1020分鐘

36、分鐘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運(yùn)行。運(yùn)行。J1已運(yùn)行已運(yùn)行10分鐘，還需與分鐘，還需與J2一起運(yùn)行一起運(yùn)行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運(yùn)行。運(yùn)行。J2已運(yùn)行已運(yùn)行10分鐘，還需與分鐘，還需與J3一起運(yùn)行一起運(yùn)行40分鐘分鐘10:50J4到達(dá)，不調(diào)入內(nèi)存到達(dá)，不調(diào)入內(nèi)存11:2

37、0J2結(jié)束，結(jié)束，J4調(diào)入內(nèi)存與調(diào)入內(nèi)存與J3一起均分一起均分CPU運(yùn)行。運(yùn)行。J3已運(yùn)行已運(yùn)行20分鐘，還需與分鐘，還需與J4一起運(yùn)行一起運(yùn)行10分鐘分鐘11:30J3結(jié)束，結(jié)束，J4還需單獨(dú)運(yùn)行還需單獨(dú)運(yùn)行15分鐘分鐘11:45J4結(jié)束結(jié)束34作業(yè)名作業(yè)名調(diào)入時(shí)間調(diào)入時(shí)間結(jié)束時(shí)間結(jié)束時(shí)間周轉(zhuǎn)時(shí)間周轉(zhuǎn)時(shí)間J110:1010:4030分鐘分鐘J210:2011:2060分鐘分鐘J310:4011:3060分鐘分鐘J411:2011:4555分鐘分鐘(2)平均周轉(zhuǎn)時(shí)間平均周轉(zhuǎn)時(shí)間=(30+60+60+55)/4=51.25(分鐘分鐘)解：解：(1)各各作業(yè)進(jìn)入內(nèi)存時(shí)間及結(jié)束時(shí)間如下表所示。作業(yè)進(jìn)

38、入內(nèi)存時(shí)間及結(jié)束時(shí)間如下表所示。351下列各項(xiàng)中，不是進(jìn)程調(diào)度時(shí)機(jī)的是下列各項(xiàng)中，不是進(jìn)程調(diào)度時(shí)機(jī)的是 。A. 現(xiàn)運(yùn)行的進(jìn)程正常結(jié)束或異常結(jié)束現(xiàn)運(yùn)行的進(jìn)程正常結(jié)束或異常結(jié)束B(niǎo). 現(xiàn)運(yùn)行的進(jìn)程從運(yùn)行態(tài)進(jìn)入就緒態(tài)現(xiàn)運(yùn)行的進(jìn)程從運(yùn)行態(tài)進(jìn)入就緒態(tài)C. 現(xiàn)運(yùn)行的進(jìn)程從運(yùn)行態(tài)進(jìn)入等待態(tài)現(xiàn)運(yùn)行的進(jìn)程從運(yùn)行態(tài)進(jìn)入等待態(tài)D. 現(xiàn)運(yùn)行的進(jìn)程從等待態(tài)進(jìn)入就緒態(tài)現(xiàn)運(yùn)行的進(jìn)程從等待態(tài)進(jìn)入就緒態(tài)2采用時(shí)間片輪轉(zhuǎn)調(diào)度算法主要是為了采用時(shí)間片輪轉(zhuǎn)調(diào)度算法主要是為了 。A.多個(gè)終端都能得到系統(tǒng)的及時(shí)響應(yīng)多個(gè)終端都能得到系統(tǒng)的及時(shí)響應(yīng)B.先來(lái)先服務(wù)先來(lái)先服務(wù)C.優(yōu)先權(quán)高的進(jìn)程及時(shí)得到調(diào)度優(yōu)先權(quán)高的進(jìn)程及時(shí)得到調(diào)度D.需要需要CP

39、U時(shí)間最短的進(jìn)程先做時(shí)間最短的進(jìn)程先做練習(xí)題練習(xí)題363在單處理器的多進(jìn)程系統(tǒng)中，進(jìn)程什么時(shí)候占用在單處理器的多進(jìn)程系統(tǒng)中，進(jìn)程什么時(shí)候占用處理器和能占用多長(zhǎng)時(shí)間，取決于處理器和能占用多長(zhǎng)時(shí)間，取決于_ 。A.進(jìn)程相應(yīng)的程序段的長(zhǎng)度進(jìn)程相應(yīng)的程序段的長(zhǎng)度B.進(jìn)程總共需要運(yùn)行時(shí)間多少進(jìn)程總共需要運(yùn)行時(shí)間多少C.進(jìn)程自身和進(jìn)程調(diào)度策略進(jìn)程自身和進(jìn)程調(diào)度策略D.進(jìn)程完成什么功能進(jìn)程完成什么功能4考慮到公平對(duì)待進(jìn)程和提高系統(tǒng)資源工作的并行考慮到公平對(duì)待進(jìn)程和提高系統(tǒng)資源工作的并行度，操作系統(tǒng)會(huì)經(jīng)常調(diào)整進(jìn)程的優(yōu)先級(jí)，通常應(yīng)提高度，操作系統(tǒng)會(huì)經(jīng)常調(diào)整進(jìn)程的優(yōu)先級(jí)，通常應(yīng)提高_(dá)的進(jìn)程優(yōu)先級(jí)。的進(jìn)程優(yōu)先級(jí)。A

40、.需計(jì)算時(shí)間長(zhǎng)需計(jì)算時(shí)間長(zhǎng) B. 很少使用外設(shè)很少使用外設(shè)C.使用使用CPU時(shí)間長(zhǎng)時(shí)間長(zhǎng) D.啟動(dòng)外設(shè)次數(shù)多啟動(dòng)外設(shè)次數(shù)多375下列因素中，下列因素中， 不一定是引起進(jìn)程調(diào)度的因素。不一定是引起進(jìn)程調(diào)度的因素。A一個(gè)進(jìn)程運(yùn)行完畢一個(gè)進(jìn)程運(yùn)行完畢B運(yùn)行進(jìn)程被阻塞運(yùn)行進(jìn)程被阻塞C一個(gè)高優(yōu)先級(jí)進(jìn)程被創(chuàng)建一個(gè)高優(yōu)先級(jí)進(jìn)程被創(chuàng)建D實(shí)時(shí)調(diào)度中，一個(gè)緊迫的任務(wù)到來(lái)實(shí)時(shí)調(diào)度中，一個(gè)緊迫的任務(wù)到來(lái)6若進(jìn)程若進(jìn)程P一旦被喚醒就能投入運(yùn)行，則系統(tǒng)可能一旦被喚醒就能投入運(yùn)行，則系統(tǒng)可能是是 。A分時(shí)系統(tǒng)，進(jìn)程分時(shí)系統(tǒng)，進(jìn)程P的優(yōu)先級(jí)最高的優(yōu)先級(jí)最高B搶占式調(diào)度方式，就緒隊(duì)列上的所有進(jìn)程的優(yōu)先搶占式調(diào)度方式，就緒隊(duì)列上

41、的所有進(jìn)程的優(yōu)先級(jí)皆比級(jí)皆比P低低C就緒隊(duì)列為空隊(duì)列就緒隊(duì)列為空隊(duì)列D搶占式調(diào)度方式，搶占式調(diào)度方式，P的優(yōu)先級(jí)高于當(dāng)前運(yùn)行的進(jìn)的優(yōu)先級(jí)高于當(dāng)前運(yùn)行的進(jìn)程程387下面說(shuō)法正確的是下面說(shuō)法正確的是 。A引入線(xiàn)程后，處理機(jī)只能在線(xiàn)程間切換引入線(xiàn)程后，處理機(jī)只能在線(xiàn)程間切換B引入線(xiàn)程后，處理機(jī)仍在進(jìn)程間切換引入線(xiàn)程后，處理機(jī)仍在進(jìn)程間切換C線(xiàn)程的切換，不會(huì)引起進(jìn)程切換線(xiàn)程的切換，不會(huì)引起進(jìn)程切換D線(xiàn)程的切換，可能引起進(jìn)程切換線(xiàn)程的切換，可能引起進(jìn)程切換8若當(dāng)前運(yùn)行進(jìn)程若當(dāng)前運(yùn)行進(jìn)程_后，系統(tǒng)將會(huì)執(zhí)行進(jìn)程調(diào)度后，系統(tǒng)將會(huì)執(zhí)行進(jìn)程調(diào)度原語(yǔ)。原語(yǔ)。A執(zhí)行了一條轉(zhuǎn)移指令執(zhí)行了一條轉(zhuǎn)移指令B要求增加主存空間，

42、經(jīng)系統(tǒng)調(diào)用銀行家算法進(jìn)行要求增加主存空間，經(jīng)系統(tǒng)調(diào)用銀行家算法進(jìn)行 測(cè)算認(rèn)為是安全的測(cè)算認(rèn)為是安全的C執(zhí)行了一條執(zhí)行了一條I/O指令要求輸入數(shù)據(jù)指令要求輸入數(shù)據(jù)D執(zhí)行程序期間系統(tǒng)發(fā)生了執(zhí)行程序期間系統(tǒng)發(fā)生了I/O完成中斷完成中斷399在分時(shí)系統(tǒng)中，若當(dāng)前運(yùn)行的進(jìn)程連續(xù)獲得了兩在分時(shí)系統(tǒng)中，若當(dāng)前運(yùn)行的進(jìn)程連續(xù)獲得了兩個(gè)時(shí)間片，原因可能是個(gè)時(shí)間片，原因可能是 。A該進(jìn)程的優(yōu)先級(jí)最高該進(jìn)程的優(yōu)先級(jí)最高B就緒隊(duì)列為空就緒隊(duì)列為空C該進(jìn)程最早進(jìn)入就緒隊(duì)列該進(jìn)程最早進(jìn)入就緒隊(duì)列D該進(jìn)程是一個(gè)短進(jìn)程該進(jìn)程是一個(gè)短進(jìn)程10下列進(jìn)程調(diào)度算法中，下列進(jìn)程調(diào)度算法中，_可能會(huì)出現(xiàn)進(jìn)程長(zhǎng)可能會(huì)出現(xiàn)進(jìn)程長(zhǎng)期得不到調(diào)度

43、的情況。期得不到調(diào)度的情況。A靜態(tài)優(yōu)先權(quán)法靜態(tài)優(yōu)先權(quán)法B搶占式調(diào)度中采用動(dòng)態(tài)優(yōu)先權(quán)算法搶占式調(diào)度中采用動(dòng)態(tài)優(yōu)先權(quán)算法C分時(shí)處理中的時(shí)間片輪轉(zhuǎn)調(diào)度算法分時(shí)處理中的時(shí)間片輪轉(zhuǎn)調(diào)度算法D非搶占式調(diào)度中采用非搶占式調(diào)度中采用FIFO算法算法4011*實(shí)時(shí)系統(tǒng)中采用的調(diào)度算法可以有如下幾種：實(shí)時(shí)系統(tǒng)中采用的調(diào)度算法可以有如下幾種： 非搶占式優(yōu)先權(quán)調(diào)度算法非搶占式優(yōu)先權(quán)調(diào)度算法 立即立即搶占式優(yōu)先權(quán)調(diào)度算法搶占式優(yōu)先權(quán)調(diào)度算法 時(shí)間片輪轉(zhuǎn)調(diào)度算法時(shí)間片輪轉(zhuǎn)調(diào)度算法 基于時(shí)鐘中斷基于時(shí)鐘中斷搶占式優(yōu)先權(quán)調(diào)度算法搶占式優(yōu)先權(quán)調(diào)度算法按實(shí)時(shí)要求的嚴(yán)格程度由低到高的順序是按實(shí)時(shí)要求的嚴(yán)格程度由低到高的順序是_。A

44、-B-C-D-12 在采用動(dòng)態(tài)優(yōu)先權(quán)的調(diào)度算法中，如果所有進(jìn)程在采用動(dòng)態(tài)優(yōu)先權(quán)的調(diào)度算法中，如果所有進(jìn)程都具有相同優(yōu)先權(quán)初值，則此時(shí)的優(yōu)先權(quán)調(diào)度算法實(shí)都具有相同優(yōu)先權(quán)初值，則此時(shí)的優(yōu)先權(quán)調(diào)度算法實(shí)際上和際上和_調(diào)度算法相同。調(diào)度算法相同。A先來(lái)先服務(wù)先來(lái)先服務(wù)B短作業(yè)優(yōu)先短作業(yè)優(yōu)先C時(shí)間片輪轉(zhuǎn)時(shí)間片輪轉(zhuǎn)D長(zhǎng)作業(yè)優(yōu)先長(zhǎng)作業(yè)優(yōu)先4113. 有一個(gè)多道程序設(shè)計(jì)系統(tǒng)，采用不可移動(dòng)的可有一個(gè)多道程序設(shè)計(jì)系統(tǒng)，采用不可移動(dòng)的可變分區(qū)方式管理主存空間，設(shè)主存空間為變分區(qū)方式管理主存空間，設(shè)主存空間為100K，采用最先適應(yīng)分配算法分配主存，作業(yè)調(diào)度采用采用最先適應(yīng)分配算法分配主存，作業(yè)調(diào)度采用響應(yīng)比高者優(yōu)先算

45、法，進(jìn)程調(diào)度采用時(shí)間片輪轉(zhuǎn)響應(yīng)比高者優(yōu)先算法，進(jìn)程調(diào)度采用時(shí)間片輪轉(zhuǎn)算法算法(即內(nèi)存中的作業(yè)均分即內(nèi)存中的作業(yè)均分CPU時(shí)間時(shí)間)，今有如下，今有如下作業(yè)序列：作業(yè)序列：作業(yè)名作業(yè)名提交時(shí)間提交時(shí)間需要執(zhí)行時(shí)間需要執(zhí)行時(shí)間要求主存量要求主存量J110 : 0040分鐘分鐘25KJ210 : 1530分鐘分鐘60KJ310 : 3020分鐘分鐘50KJ410 : 3525分鐘分鐘18KJ510 : 4015分鐘分鐘20K42假定所有作業(yè)都是計(jì)算型作業(yè)且忽略系統(tǒng)調(diào)度時(shí)假定所有作業(yè)都是計(jì)算型作業(yè)且忽略系統(tǒng)調(diào)度時(shí)間?；卮鹣铝袉?wèn)題：間?；卮鹣铝袉?wèn)題：(1) 列表說(shuō)明各個(gè)作業(yè)被裝入主存的時(shí)間、完成時(shí)列表說(shuō)

46、明各個(gè)作業(yè)被裝入主存的時(shí)間、完成時(shí)間和周轉(zhuǎn)時(shí)間；間和周轉(zhuǎn)時(shí)間；(2) 寫(xiě)出各作業(yè)被調(diào)入主存的順序；寫(xiě)出各作業(yè)被調(diào)入主存的順序；(3) 計(jì)算計(jì)算5個(gè)作業(yè)的平均周轉(zhuǎn)時(shí)間。個(gè)作業(yè)的平均周轉(zhuǎn)時(shí)間。 解：通過(guò)分析解：通過(guò)分析(在黑板上分析在黑板上分析)，可得如下結(jié)果：，可得如下結(jié)果：43（1）各個(gè)作業(yè)被裝入主存的時(shí)間、完成時(shí)間和周）各個(gè)作業(yè)被裝入主存的時(shí)間、完成時(shí)間和周轉(zhuǎn)時(shí)間如下表所示：轉(zhuǎn)時(shí)間如下表所示： 作業(yè)名作業(yè)名裝入主存時(shí)間裝入主存時(shí)間作業(yè)完成時(shí)間作業(yè)完成時(shí)間周轉(zhuǎn)時(shí)間周轉(zhuǎn)時(shí)間J110：0011：0565J210：1511：1560J311：1511：5585J411：3512：1095J511：0

47、511：3555（2）作業(yè)被調(diào)入主存的順序?yàn)椋┳鳂I(yè)被調(diào)入主存的順序?yàn)镴1,J2,J5,J3,J4。（3）平均周轉(zhuǎn)時(shí)間）平均周轉(zhuǎn)時(shí)間=(65+60+85+95+55)/5=72(分鐘分鐘) 4414多道批處理系統(tǒng)中配有一個(gè)處理器和多道批處理系統(tǒng)中配有一個(gè)處理器和2臺(tái)外設(shè)臺(tái)外設(shè)(D1和和D2)，用戶(hù)存儲(chǔ)空間為用戶(hù)存儲(chǔ)空間為100MB。已知系統(tǒng)采用可搶占式的高優(yōu)先數(shù)調(diào)。已知系統(tǒng)采用可搶占式的高優(yōu)先數(shù)調(diào)度算法和不允許移動(dòng)的可變分區(qū)分配策略，設(shè)備分配按照動(dòng)態(tài)度算法和不允許移動(dòng)的可變分區(qū)分配策略，設(shè)備分配按照動(dòng)態(tài)分配原則。今有分配原則。今有4個(gè)作業(yè)同時(shí)提交給系統(tǒng)，如下表所示。個(gè)作業(yè)同時(shí)提交給系統(tǒng)，如下表所

48、示。作業(yè)名作業(yè)名優(yōu)先數(shù)優(yōu)先數(shù)運(yùn)行時(shí)間運(yùn)行時(shí)間內(nèi)存需求內(nèi)存需求A65分鐘分鐘50MB34分鐘分鐘10MC87分鐘分鐘60MD46分鐘分鐘20M作業(yè)運(yùn)行時(shí)間和作業(yè)運(yùn)行時(shí)間和I/O時(shí)間按下述順序進(jìn)行：時(shí)間按下述順序進(jìn)行：A. CPU (1分鐘分鐘)，D1(2分鐘分鐘)，D2(2分鐘分鐘)B. CPU (3分鐘分鐘)，D1(1分鐘分鐘)C. CPU (2分鐘分鐘)，D1(3分鐘分鐘)，CPU(2分鐘分鐘)D. CPU (4分鐘分鐘)，D1(2分鐘分鐘)忽略其他輔助操作，求忽略其他輔助操作，求4個(gè)作業(yè)的平均周轉(zhuǎn)時(shí)間是多少分鐘。個(gè)作業(yè)的平均周轉(zhuǎn)時(shí)間是多少分鐘。11分鐘分鐘分析見(jiàn)后頁(yè)分析見(jiàn)后頁(yè)45C C D

49、 D D C C A D BBBC C CA A D D BA A12345678910 11 12 13CPUD1D2時(shí)間時(shí)間A的周轉(zhuǎn)時(shí)間為的周轉(zhuǎn)時(shí)間為12分鐘分鐘B的周轉(zhuǎn)時(shí)間為的周轉(zhuǎn)時(shí)間為13分鐘分鐘C的周轉(zhuǎn)時(shí)間為的周轉(zhuǎn)時(shí)間為7分鐘分鐘D的周轉(zhuǎn)時(shí)間為的周轉(zhuǎn)時(shí)間為12分鐘分鐘所以平均周轉(zhuǎn)時(shí)間為所以平均周轉(zhuǎn)時(shí)間為(12+13+7+12)/4=11(分鐘分鐘)463.3 實(shí)時(shí)調(diào)度實(shí)時(shí)調(diào)度 由于在實(shí)時(shí)系統(tǒng)中都存在著若干個(gè)實(shí)時(shí)由于在實(shí)時(shí)系統(tǒng)中都存在著若干個(gè)實(shí)時(shí)進(jìn)程或任務(wù)，它們用來(lái)反應(yīng)或控制某個(gè)進(jìn)程或任務(wù)，它們用來(lái)反應(yīng)或控制某個(gè)( (些些) )外部事件，往往帶有某種程度的緊迫性，因外部事件，往往帶有某

50、種程度的緊迫性，因而對(duì)實(shí)時(shí)系統(tǒng)的調(diào)度提出了某些特殊要求，而對(duì)實(shí)時(shí)系統(tǒng)的調(diào)度提出了某些特殊要求，前面介紹的多種調(diào)度算法，并不能滿(mǎn)足實(shí)時(shí)前面介紹的多種調(diào)度算法，并不能滿(mǎn)足實(shí)時(shí)系統(tǒng)對(duì)調(diào)度的要求，為此需引入一種新的調(diào)系統(tǒng)對(duì)調(diào)度的要求，為此需引入一種新的調(diào)度，即度，即實(shí)時(shí)調(diào)度實(shí)時(shí)調(diào)度。473.3.1 實(shí)現(xiàn)實(shí)時(shí)調(diào)度的基本條件實(shí)現(xiàn)實(shí)時(shí)調(diào)度的基本條件 在實(shí)時(shí)系統(tǒng)中，硬實(shí)時(shí)任務(wù)在實(shí)時(shí)系統(tǒng)中，硬實(shí)時(shí)任務(wù)(存在著必須滿(mǎn)足的時(shí)間限制存在著必須滿(mǎn)足的時(shí)間限制)和和軟實(shí)時(shí)任務(wù)軟實(shí)時(shí)任務(wù)(偶爾超過(guò)時(shí)間限制是可以容忍的偶爾超過(guò)時(shí)間限制是可以容忍的)都聯(lián)系著一個(gè)截止都聯(lián)系著一個(gè)截止時(shí)間。為了保證系統(tǒng)能正常工作，實(shí)時(shí)調(diào)度必須滿(mǎn)足

51、實(shí)時(shí)任務(wù)對(duì)時(shí)間。為了保證系統(tǒng)能正常工作，實(shí)時(shí)調(diào)度必須滿(mǎn)足實(shí)時(shí)任務(wù)對(duì)截止時(shí)間的要求，為此，實(shí)現(xiàn)實(shí)時(shí)調(diào)度應(yīng)具備下述幾個(gè)條件：截止時(shí)間的要求，為此，實(shí)現(xiàn)實(shí)時(shí)調(diào)度應(yīng)具備下述幾個(gè)條件：1提供必要的信息提供必要的信息系統(tǒng)應(yīng)向調(diào)度程序提供有關(guān)任務(wù)的下述信息：系統(tǒng)應(yīng)向調(diào)度程序提供有關(guān)任務(wù)的下述信息：(1)(1)就緒時(shí)間就緒時(shí)間。這是該任務(wù)成為就緒狀態(tài)的起始時(shí)間。這是該任務(wù)成為就緒狀態(tài)的起始時(shí)間(2)(2)開(kāi)始截止時(shí)間和完成截止時(shí)間開(kāi)始截止時(shí)間和完成截止時(shí)間。對(duì)于典型的實(shí)時(shí)應(yīng)用，。對(duì)于典型的實(shí)時(shí)應(yīng)用，只需知道開(kāi)始截止時(shí)間，或者知道完成截止時(shí)間。只需知道開(kāi)始截止時(shí)間，或者知道完成截止時(shí)間。(3)(3)處理時(shí)間處理

52、時(shí)間。一個(gè)任務(wù)從開(kāi)始執(zhí)行直至完成所需的時(shí)間。一個(gè)任務(wù)從開(kāi)始執(zhí)行直至完成所需的時(shí)間。在某些情況下，該時(shí)間也是系統(tǒng)提供的。在某些情況下，該時(shí)間也是系統(tǒng)提供的。(4)(4)資源要求資源要求。(5)(5)優(yōu)先級(jí)優(yōu)先級(jí)。若某任務(wù)的開(kāi)始截止時(shí)間已經(jīng)錯(cuò)過(guò)，就會(huì)引起。若某任務(wù)的開(kāi)始截止時(shí)間已經(jīng)錯(cuò)過(guò)，就會(huì)引起故障，則應(yīng)賦予該任務(wù)故障，則應(yīng)賦予該任務(wù)“絕對(duì)絕對(duì)”優(yōu)先級(jí)；如果對(duì)系統(tǒng)的繼優(yōu)先級(jí)；如果對(duì)系統(tǒng)的繼續(xù)運(yùn)行無(wú)重大影響，則可賦予續(xù)運(yùn)行無(wú)重大影響，則可賦予“相對(duì)相對(duì)”優(yōu)先級(jí)，供調(diào)度參優(yōu)先級(jí)，供調(diào)度參考?？肌?82系統(tǒng)處理能力強(qiáng)系統(tǒng)處理能力強(qiáng) 若處理機(jī)的處理能力不強(qiáng)，則有可能因處理機(jī)忙若處理機(jī)的處理能力不強(qiáng)，則有可

53、能因處理機(jī)忙不過(guò)來(lái)而使某些實(shí)時(shí)任務(wù)不能得到及時(shí)處理，從而導(dǎo)不過(guò)來(lái)而使某些實(shí)時(shí)任務(wù)不能得到及時(shí)處理，從而導(dǎo)致發(fā)生難于預(yù)料的后果。致發(fā)生難于預(yù)料的后果。 假定系統(tǒng)中有假定系統(tǒng)中有m個(gè)周期性硬實(shí)時(shí)任務(wù)，它們的處個(gè)周期性硬實(shí)時(shí)任務(wù)，它們的處理時(shí)間為理時(shí)間為Ci，周期時(shí)間為，周期時(shí)間為Pi，則在單處理機(jī)情況下，則在單處理機(jī)情況下，必須滿(mǎn)足下面的限制條件：必須滿(mǎn)足下面的限制條件：1.22111mmmiiiPCPCPCPC系統(tǒng)才是可調(diào)度的。系統(tǒng)才是可調(diào)度的。49例如例如 設(shè)系統(tǒng)中有設(shè)系統(tǒng)中有6個(gè)硬實(shí)時(shí)任務(wù)，它們的周期都是個(gè)硬實(shí)時(shí)任務(wù)，它們的周期都是50ms，而每次的處理時(shí)間都是，而每次的處理時(shí)間都是10ms

54、，此時(shí)不能滿(mǎn)，此時(shí)不能滿(mǎn)足上式，因而系統(tǒng)是不可調(diào)度的。足上式，因而系統(tǒng)是不可調(diào)度的。又例如又例如 一個(gè)實(shí)時(shí)系統(tǒng)中有一個(gè)實(shí)時(shí)系統(tǒng)中有3個(gè)實(shí)時(shí)事件流，其周期分別個(gè)實(shí)時(shí)事件流，其周期分別為為100ms、200ms和和500ms，每次的處理時(shí)間分別，每次的處理時(shí)間分別為為50ms、30ms和和100ms，則因?yàn)?，則因?yàn)?.5+0.15+0.21故系統(tǒng)是可調(diào)度的。如果加入周期為故系統(tǒng)是可調(diào)度的。如果加入周期為1秒的第秒的第4個(gè)任務(wù)，個(gè)任務(wù)，則只要其處理時(shí)間不超過(guò)則只要其處理時(shí)間不超過(guò)150ms，系統(tǒng)仍是可調(diào)度，系統(tǒng)仍是可調(diào)度的。的。 當(dāng)然，上述運(yùn)算的隱含條件是進(jìn)行切換的時(shí)間足當(dāng)然，上述運(yùn)算的隱含條件是進(jìn)

55、行切換的時(shí)間足夠小，可以忽略。夠小，可以忽略。50設(shè)實(shí)時(shí)任務(wù)設(shè)實(shí)時(shí)任務(wù)A、B、C，周期分別為，周期分別為100ms、200ms、500ms，處理時(shí)間分別為處理時(shí)間分別為50ms、30ms、100ms，又設(shè)它們同時(shí)開(kāi)始計(jì)，又設(shè)它們同時(shí)開(kāi)始計(jì)時(shí)，則設(shè)想可有如下調(diào)度順序時(shí)，則設(shè)想可有如下調(diào)度順序(假設(shè)優(yōu)先級(jí)順序?yàn)榧僭O(shè)優(yōu)先級(jí)順序?yàn)锳、B、C)：ABCt(ms)100200300400500600700800900100011000思考思考：考慮加入一個(gè)周期為：考慮加入一個(gè)周期為1秒，處理時(shí)間為秒，處理時(shí)間為150ms的實(shí)的實(shí)時(shí)任務(wù)后的情況。時(shí)任務(wù)后的情況。51提高系統(tǒng)的可調(diào)度性的解決方法是提高系統(tǒng)的處

56、理提高系統(tǒng)的可調(diào)度性的解決方法是提高系統(tǒng)的處理能力，其途徑有二：能力，其途徑有二：NPCmiii1 上述限制條件并未考慮任務(wù)的切換時(shí)間，包括上述限制條件并未考慮任務(wù)的切換時(shí)間，包括執(zhí)行調(diào)度算法和進(jìn)程任務(wù)切換，以及消息的傳遞時(shí)間執(zhí)行調(diào)度算法和進(jìn)程任務(wù)切換，以及消息的傳遞時(shí)間等開(kāi)銷(xiāo)，因此，當(dāng)利用上述限制條件來(lái)確定系統(tǒng)是否等開(kāi)銷(xiāo)，因此，當(dāng)利用上述限制條件來(lái)確定系統(tǒng)是否可調(diào)度時(shí)，還應(yīng)適當(dāng)?shù)亓粲杏嗟??？烧{(diào)度時(shí)，還應(yīng)適當(dāng)?shù)亓粲杏嗟亍 仍采用單處理機(jī)系統(tǒng)，但需提高其處理能力，以仍采用單處理機(jī)系統(tǒng)，但需提高其處理能力，以顯著減少對(duì)每一個(gè)任務(wù)的處理時(shí)間；顯著減少對(duì)每一個(gè)任務(wù)的處理時(shí)間；n 采用多處理機(jī)系統(tǒng)，假

57、設(shè)系統(tǒng)中處理機(jī)數(shù)為采用多處理機(jī)系統(tǒng)，假設(shè)系統(tǒng)中處理機(jī)數(shù)為N，則應(yīng)將上述限制條件改為：則應(yīng)將上述限制條件改為：523采用搶占式調(diào)度機(jī)制采用搶占式調(diào)度機(jī)制 含有硬實(shí)時(shí)任務(wù)的實(shí)時(shí)系統(tǒng)中，廣泛采用搶占機(jī)含有硬實(shí)時(shí)任務(wù)的實(shí)時(shí)系統(tǒng)中，廣泛采用搶占機(jī)制。這樣可滿(mǎn)足硬實(shí)時(shí)任務(wù)對(duì)截止時(shí)間的要求，但這制。這樣可滿(mǎn)足硬實(shí)時(shí)任務(wù)對(duì)截止時(shí)間的要求，但這種調(diào)度機(jī)制比較復(fù)雜。種調(diào)度機(jī)制比較復(fù)雜。 對(duì)于一些小的實(shí)時(shí)系統(tǒng)，如果能預(yù)知任務(wù)的開(kāi)始對(duì)于一些小的實(shí)時(shí)系統(tǒng)，如果能預(yù)知任務(wù)的開(kāi)始截止時(shí)間，則對(duì)實(shí)時(shí)任務(wù)的調(diào)度可采用非搶占調(diào)度機(jī)截止時(shí)間，則對(duì)實(shí)時(shí)任務(wù)的調(diào)度可采用非搶占調(diào)度機(jī)制以簡(jiǎn)化調(diào)度程序和對(duì)任務(wù)調(diào)度所花費(fèi)的系統(tǒng)開(kāi)銷(xiāo)。制以簡(jiǎn)化

58、調(diào)度程序和對(duì)任務(wù)調(diào)度所花費(fèi)的系統(tǒng)開(kāi)銷(xiāo)。但在設(shè)計(jì)這種調(diào)度機(jī)制時(shí)，應(yīng)使所有的實(shí)時(shí)任務(wù)都比但在設(shè)計(jì)這種調(diào)度機(jī)制時(shí)，應(yīng)使所有的實(shí)時(shí)任務(wù)都比較小，并在執(zhí)行完關(guān)鍵性程序和臨界區(qū)后，能及時(shí)地較小，并在執(zhí)行完關(guān)鍵性程序和臨界區(qū)后，能及時(shí)地把自己阻塞起來(lái)，以便釋放處理機(jī)，供調(diào)度程序去調(diào)把自己阻塞起來(lái)，以便釋放處理機(jī)，供調(diào)度程序去調(diào)度那種開(kāi)始截止時(shí)間即將到達(dá)的任務(wù)。度那種開(kāi)始截止時(shí)間即將到達(dá)的任務(wù)。534具有快速切換機(jī)制具有快速切換機(jī)制 為了保證要求較高的硬實(shí)時(shí)任務(wù)能及時(shí)運(yùn)行，為了保證要求較高的硬實(shí)時(shí)任務(wù)能及時(shí)運(yùn)行，在實(shí)時(shí)系統(tǒng)中還應(yīng)具有快速切換機(jī)制，以保證能進(jìn)在實(shí)時(shí)系統(tǒng)中還應(yīng)具有快速切換機(jī)制，以保證能進(jìn)行任務(wù)的快

59、速切換。該機(jī)制應(yīng)具有下述兩方面的能行任務(wù)的快速切換。該機(jī)制應(yīng)具有下述兩方面的能力：力：n對(duì)外部中斷的快速響應(yīng)能力。要求系統(tǒng)具有快對(duì)外部中斷的快速響應(yīng)能力。要求系統(tǒng)具有快速硬件中斷機(jī)構(gòu)，還應(yīng)使禁止中斷的時(shí)間間隔速硬件中斷機(jī)構(gòu)，還應(yīng)使禁止中斷的時(shí)間間隔盡量短，以免耽誤其它緊迫任務(wù)。盡量短，以免耽誤其它緊迫任務(wù)。n快速的任務(wù)分派能力。在完成任務(wù)調(diào)度后，便快速的任務(wù)分派能力。在完成任務(wù)調(diào)度后，便應(yīng)進(jìn)行任務(wù)切換。為了提高分派程序進(jìn)行任務(wù)應(yīng)進(jìn)行任務(wù)切換。為了提高分派程序進(jìn)行任務(wù)切換時(shí)的速度，應(yīng)使系統(tǒng)中的每個(gè)運(yùn)行功能單切換時(shí)的速度，應(yīng)使系統(tǒng)中的每個(gè)運(yùn)行功能單位適當(dāng)?shù)男?，以減少任務(wù)切換的時(shí)間開(kāi)銷(xiāo)。位適當(dāng)?shù)男。?/p>

60、以減少任務(wù)切換的時(shí)間開(kāi)銷(xiāo)。543.3.2 實(shí)時(shí)調(diào)度算法的分類(lèi)實(shí)時(shí)調(diào)度算法的分類(lèi)n按實(shí)時(shí)任務(wù)性質(zhì)不同來(lái)劃分：按實(shí)時(shí)任務(wù)性質(zhì)不同來(lái)劃分：n硬實(shí)時(shí)調(diào)度算法硬實(shí)時(shí)調(diào)度算法n軟實(shí)時(shí)調(diào)度算法軟實(shí)時(shí)調(diào)度算法n按調(diào)度方式的不同按調(diào)度方式的不同n非搶占調(diào)度算法非搶占調(diào)度算法n搶占調(diào)度算法搶占調(diào)度算法n因調(diào)度程序調(diào)度時(shí)間的不同因調(diào)度程序調(diào)度時(shí)間的不同n靜態(tài)調(diào)度算法靜態(tài)調(diào)度算法進(jìn)程執(zhí)行前，調(diào)度程序便已經(jīng)決定進(jìn)程執(zhí)行前，調(diào)度程序便已經(jīng)決定了個(gè)進(jìn)程間的執(zhí)行順序了個(gè)進(jìn)程間的執(zhí)行順序n動(dòng)態(tài)調(diào)度算法動(dòng)態(tài)調(diào)度算法n多處理機(jī)環(huán)境下多處理機(jī)環(huán)境下n集中式調(diào)度集中式調(diào)度n分布式調(diào)度分布式調(diào)度55下面討論按調(diào)度方式的不同對(duì)調(diào)度算法進(jìn)行