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

1、1第第3 3章章 處理機調(diào)度與死鎖處理機調(diào)度與死鎖3.1 3.1 處理機調(diào)度的基本概念處理機調(diào)度的基本概念3.2 3.2 調(diào)度算法調(diào)度算法3.3 3.3 實時調(diào)度實時調(diào)度 3.4 3.4 產(chǎn)生死鎖的原因和必要條件產(chǎn)生死鎖的原因和必要條件3.5 3.5 預防和避免死鎖的方法預防和避免死鎖的方法3.6 3.6 死鎖的檢測和解除死鎖的檢測和解除23.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)存，并為它

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

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

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

5、業(yè)優(yōu)先原則；短作業(yè)優(yōu)先原則； 時間片原則。時間片原則。 43.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)度相比較：進程調(diào)度的運行頻率最高進程調(diào)度的運行頻率最高 作業(yè)調(diào)度頻率最低作業(yè)調(diào)度頻率最低 中級調(diào)度界于之間中級調(diào)度界于之間 53.1.2 調(diào)度隊列模型調(diào)度隊列模型三種類型的調(diào)度隊列模型：三種類型的調(diào)度隊列模型： 1. 僅

6、有進程調(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-1 僅具有進程調(diào)度的調(diào)度隊列模型僅具有進程調(diào)度的調(diào)度隊列模型63.1.2 調(diào)度隊列模型調(diào)度隊列模型2. 具有高級和低級調(diào)度的調(diào)度隊列模型具有高級和低級調(diào)度的調(diào)度隊列模型 批處理系統(tǒng)中批處理系統(tǒng)中的調(diào)度模型的調(diào)度模型

7、比第一種情況比第一種情況多了后備隊列多了后備隊列就就 緒緒 隊隊 列列阻阻 塞塞 隊隊 列列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出現(xiàn)出現(xiàn)事件事件2 2出現(xiàn)出現(xiàn)事件事件n n出現(xiàn)出現(xiàn)后備隊列后備隊列73.1.2 調(diào)度隊列模型調(diào)度隊列模型3. 同時具有三級調(diào)度的調(diào)度隊列模型同時具有三級調(diào)度的調(diào)度隊列模型 具有掛起狀具有掛起狀態(tài)的系統(tǒng)。態(tài)的系統(tǒng)。 83

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

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

10、系統(tǒng)的準則面向系統(tǒng)的準則 （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)，該準則并不重要時系統(tǒng)，該準則并不重要 113.2 調(diào)度算法調(diào)度算法3.2.1 先來先服務調(diào)度算法先來先服務調(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.

11、4 高響應比優(yōu)先調(diào)度算法高響應比優(yōu)先調(diào)度算法3.2.5 基于時間片的輪轉(zhuǎn)調(diào)度算法基于時間片的輪轉(zhuǎn)調(diào)度算法 123.2.1 先來先服務調(diào)度算法先來先服務調(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è)中，選擇一個或幾個最先從后備隊列作業(yè)中，選擇一個或幾個最先進入該隊列的作業(yè)，將它們調(diào)入內(nèi)存，為進入該隊列的作業(yè)，將它們調(diào)入內(nèi)存，為它們分配資源、創(chuàng)建進程，然后放入進程它們分配資源、創(chuàng)建進程，然后放入進程就緒隊列。就緒隊列。 用于進程用于進程調(diào)度時：調(diào)

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

13、分鐘 完成時間完成時間 周轉(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繁忙型作業(yè)（進程），不利于繁忙型作業(yè)（進程），不利于I/O繁忙型作業(yè)（進程）繁忙型作業(yè)（進程）因非搶占式因非搶占式 CPU繁忙型作業(yè)繁忙型作業(yè)需要大量的需要大量的CPU時間進行計時間進行計算，而很少請求算，而很少請求I/O。如

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

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

16、點調(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)度。程）會被及時調(diào)度。 n由于作業(yè)（進程）的長短只是根據(jù)用戶所提供由于作業(yè)（進程）的長短只是根據(jù)用戶所提供的估計時間而定的，致使該算法不一定能真正的估計時間而定的，致使該算法不一定能真正做到短作業(yè)優(yōu)先調(diào)度。做到短作業(yè)優(yōu)先調(diào)度。 當多個作業(yè)同時到達時，當多個作業(yè)同時到達時，SJF算法可使平均周轉(zhuǎn)時算法可使平均周轉(zhuǎn)時間最短。間最短。173.2

17、.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)從后備中選擇一個或幾個優(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)還適用于

18、實時系統(tǒng) 181優(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)一旦把處理機分配給就緒隊列中優(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)最高的進程

19、，使之執(zhí)系統(tǒng)把處理機分配給就緒隊列中優(yōu)先權(quán)最高的進程，使之執(zhí)行，但在其執(zhí)行期間，只要出現(xiàn)了另一個優(yōu)先權(quán)更高的進程，行，但在其執(zhí)行期間，只要出現(xiàn)了另一個優(yōu)先權(quán)更高的進程，系統(tǒng)就立即停止當前進程的執(zhí)行，重新將處理機分配給新的系統(tǒng)就立即停止當前進程的執(zhí)行，重新將處理機分配給新的優(yōu)先權(quán)最高的進程。優(yōu)先權(quán)最高的進程。 它能更好地滿足緊迫作業(yè)的要求。常用于實時系統(tǒng)中，以它能更好地滿足緊迫作業(yè)的要求。常用于實時系統(tǒng)中，以及對實時性能要求較高的批處理系統(tǒng)和分時系統(tǒng)中。及對實時性能要求較高的批處理系統(tǒng)和分時系統(tǒng)中。 192優(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)

20、先權(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ù)值越大，優(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)。進程

21、對資源的需求進程對資源的需求 如進程的估計執(zhí)行時間及內(nèi)存需求量的多少，對如進程的估計執(zhí)行時間及內(nèi)存需求量的多少，對這些要求少的進程賦予較高的優(yōu)先權(quán)。這些要求少的進程賦予較高的優(yōu)先權(quán)。 用戶要求用戶要求 這是由用戶進程的緊迫程度和用戶所付費用的多少來確定這是由用戶進程的緊迫程度和用戶所付費用的多少來確定優(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)度。 202）動態(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)，是

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

23、NIX 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_nice是基本進程控制塊中的兩個項，分別表示進是基本進程控制塊中的兩個項，分別表示進程使用處理器的情況和用戶自己設(shè)置的計算優(yōu)先數(shù)的偏置程使用處理器的情況和用戶自己設(shè)置的計算優(yōu)先數(shù)的偏置量。量。系統(tǒng)對正在占用系統(tǒng)對正在占用CPU的進程每隔一個時鐘周期的進程每隔一個時鐘周期(20ms)對其對其p_cpu加加1。這使得占用處理器時間長的進程的

24、。這使得占用處理器時間長的進程的p_cpu值增大，值增大，其優(yōu)先數(shù)也增大，優(yōu)先權(quán)就相應降低。其優(yōu)先數(shù)也增大，優(yōu)先權(quán)就相應降低。系統(tǒng)每隔系統(tǒng)每隔1s對所有進程執(zhí)行對所有進程執(zhí)行p_cpu/2，這使就緒進程優(yōu)先級，這使就緒進程優(yōu)先級提高。提高。p_nice的值允許用戶根據(jù)任務的輕重緩急程度來設(shè)置，其值的值允許用戶根據(jù)任務的輕重緩急程度來設(shè)置，其值在在039之間。一旦一個進程的之間。一旦一個進程的p_nice設(shè)置后，此后用戶只設(shè)置后，此后用戶只能使其值增加。能使其值增加。22【例例3-3】設(shè)有一個最多可有兩道作業(yè)同時裝入內(nèi)存執(zhí)設(shè)有一個最多可有兩道作業(yè)同時裝入內(nèi)存執(zhí)行的批處理系統(tǒng)，作業(yè)調(diào)度采用最短作業(yè)

25、優(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)越高）：值越小優(yōu)先權(quán)越高）： (1)(1)列出所有作業(yè)進入內(nèi)存時間及結(jié)束時間。列出所有作業(yè)進入內(nèi)存時間及結(jié)束時間。 (2)(2)計算平均周轉(zhuǎn)時間。計算平均周轉(zhuǎn)時間。 作業(yè)名作業(yè)名到達時間到達時間估計運行時間估計運行時間進程優(yōu)先數(shù)進程優(yōu)先數(shù)J110:1020分鐘分鐘5J210:2030分鐘分鐘3J310:3025分鐘分鐘4J410:5020分鐘分鐘

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

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

28、4題題) )A時間片輪轉(zhuǎn)調(diào)度算法時間片輪轉(zhuǎn)調(diào)度算法B短進程優(yōu)先調(diào)度算法短進程優(yōu)先調(diào)度算法C先來先服務調(diào)度算法先來先服務調(diào)度算法D高響應比優(yōu)先調(diào)度算法高響應比優(yōu)先調(diào)度算法26【例例3-4】設(shè)有一個最多可有兩道作業(yè)同時裝入內(nèi)存執(zhí)設(shè)有一個最多可有兩道作業(yè)同時裝入內(nèi)存執(zhí)行的批處理系統(tǒng)，作業(yè)調(diào)度采用行的批處理系統(tǒng)，作業(yè)調(diào)度采用高響應比優(yōu)先高響應比優(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)越高）： (1)(1)

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

30、。10:20 J2到達，調(diào)入內(nèi)存，因其優(yōu)先級高，到達，調(diào)入內(nèi)存，因其優(yōu)先級高，J2執(zhí)行。執(zhí)行。28J1J2J3J1J4CPU10:1010:2010:5011:1511:2511:45作業(yè)名作業(yè)名 到達時間到達時間 調(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(分鐘分鐘)293.2.5 基于時間片的輪轉(zhuǎn)調(diào)度算法基于時間片的輪轉(zhuǎn)調(diào)度算法 用于進

31、程調(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)把就緒隊列中的所有進程，按先來先服務的系統(tǒng)把就緒隊列中的所有進程，按先來先服務的原則，排成一個隊列；原則，排成一個隊列； n每次調(diào)度時，把每次調(diào)度時，把CPU分配給隊首進程，并讓它執(zhí)分配給隊首進程，并讓它執(zhí)行一個時間片；行一個時間片； n每當執(zhí)行的時間片用完，調(diào)度程序便停止該進程每當執(zhí)行的時間片用完，調(diào)度程序便停止該進程的執(zhí)行，將其送入就緒隊列尾部；然后進行下一的執(zhí)行，將其

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

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

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

35、不到服務。其作業(yè)長期得不到服務。32【例例3-5】設(shè)有一個最多可有兩道作業(yè)同時裝入內(nèi)存執(zhí)設(shè)有一個最多可有兩道作業(yè)同時裝入內(nèi)存執(zhí)行的批處理系統(tǒng)，作業(yè)調(diào)度采用行的批處理系統(tǒng)，作業(yè)調(diào)度采用高響應比優(yōu)先高響應比優(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)時間。計算平均周轉(zhuǎn)時間。 作業(yè)名作業(yè)名到達時間到達時間估計運行時間估計運行時間J110:1020分鐘

36、分鐘J210:2030分鐘分鐘J310:3025分鐘分鐘J410:5020分鐘分鐘33先在草稿上分析如下：先在草稿上分析如下：10:10J1到達，調(diào)入內(nèi)存執(zhí)行到達，調(diào)入內(nèi)存執(zhí)行10:20J2到達，調(diào)入內(nèi)存與到達，調(diào)入內(nèi)存與J1一起均分一起均分CPU運行。運行。J1已運行已運行10分鐘，還需與分鐘，還需與J2一起運行一起運行20分鐘分鐘10:30J3到達，不調(diào)入內(nèi)存到達，不調(diào)入內(nèi)存10:40J1結(jié)束，結(jié)束，J3調(diào)入內(nèi)存與調(diào)入內(nèi)存與J2一起均分一起均分CPU運行。運行。J2已運行已運行10分鐘，還需與分鐘，還需與J3一起運行一起運行40分鐘分鐘10:50J4到達，不調(diào)入內(nèi)存到達，不調(diào)入內(nèi)存11:2

37、0J2結(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+55)/4=51.25(分鐘分鐘)解：解：(1)各各作業(yè)進入內(nèi)存時間及結(jié)束時間如下表所示。作業(yè)進

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

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

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

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

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

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

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

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

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

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

48、示。作業(yè)名作業(yè)名優(yōu)先數(shù)優(yōu)先數(shù)運行時間運行時間內(nèi)存需求內(nèi)存需求A65分鐘分鐘50MB34分鐘分鐘10MC87分鐘分鐘60MD46分鐘分鐘20M作業(yè)運行時間和作業(yè)運行時間和I/O時間按下述順序進行：時間按下述順序進行：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個作業(yè)的平均周轉(zhuǎn)時間是多少分鐘。個作業(yè)的平均周轉(zhuǎn)時間是多少分鐘。11分鐘分鐘分析見后頁分析見后頁45C C D

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

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

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

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

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

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

55、行切換的時間足夠小，可以忽略。夠小，可以忽略。50設(shè)實時任務設(shè)實時任務A、B、C，周期分別為，周期分別為100ms、200ms、500ms，處理時間分別為處理時間分別為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的實的實時任務后的情況。時任務后的情況。51提高系統(tǒng)的可調(diào)度性的解決方法是提高系統(tǒng)的處

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

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

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

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

60、以減少任務切換的時間開銷。543.3.2 實時調(diào)度算法的分類實時調(diào)度算法的分類n按實時任務性質(zhì)不同來劃分：按實時任務性質(zhì)不同來劃分：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)度算法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)度55下面討論按調(diào)度方式的不同對調(diào)度算法進行