第9周-處理機(jī)調(diào)度ppt課件

1、單擊此處編輯母版標(biāo)題樣式單擊此處編輯母版標(biāo)題樣式 單擊此處編輯母版副標(biāo)題樣式單擊此處編輯母版副標(biāo)題樣式第第4章章 處理機(jī)調(diào)度處理機(jī)調(diào)度4.1 分級(jí)調(diào)度分級(jí)調(diào)度4.2 作業(yè)調(diào)度作業(yè)調(diào)度4.3 進(jìn)程調(diào)度進(jìn)程調(diào)度4.4 調(diào)度算法調(diào)度算法4.5 算法評(píng)價(jià)算法評(píng)價(jià)4.6 實(shí)時(shí)系統(tǒng)調(diào)度方法實(shí)時(shí)系統(tǒng)調(diào)度方法本章小結(jié)本章小結(jié)習(xí)題習(xí)題4.4 調(diào)度算法調(diào)度算法 包括進(jìn)程調(diào)度、作業(yè)調(diào)度兩種不同包括進(jìn)程調(diào)度、作業(yè)調(diào)度兩種不同的調(diào)度機(jī)制）的調(diào)度機(jī)制） 關(guān)于進(jìn)程的關(guān)于進(jìn)程的CPU burst 與與 I/O burst： 陣發(fā)期陣發(fā)期 : CPU burst cycle: 進(jìn)程使用進(jìn)程使用CPU計(jì)算；計(jì)算； I/O bur

2、st cycle: 進(jìn)程使用設(shè)備進(jìn)程使用設(shè)備I/O。進(jìn)程運(yùn)行行為：進(jìn)程運(yùn)行行為： CPU burst, I/O burst, CPU burst, I/O burst, 進(jìn)程調(diào)度：對(duì)處于進(jìn)程調(diào)度：對(duì)處于CPU burst的進(jìn)程集合的進(jìn)程集合的調(diào)度。的調(diào)度。1. 先來先服務(wù)調(diào)度算法先來先服務(wù)調(diào)度算法FCFS） First Come First Serve將用戶作業(yè)或就緒進(jìn)程按提交順序或變?yōu)榫蛯⒂脩糇鳂I(yè)或就緒進(jìn)程按提交順序或變?yōu)榫途w狀態(tài)的順序排成隊(duì)列，并按照先進(jìn)先出緒狀態(tài)的順序排成隊(duì)列，并按照先進(jìn)先出(先先來先服務(wù)來先服務(wù))的方式進(jìn)行調(diào)度處理，是一種最簡(jiǎn)的方式進(jìn)行調(diào)度處理，是一種最簡(jiǎn)單的方法。單的

3、方法。特點(diǎn)特點(diǎn):(1)實(shí)現(xiàn)簡(jiǎn)單實(shí)現(xiàn)簡(jiǎn)單(2)適于作業(yè)調(diào)度、進(jìn)程調(diào)度適于作業(yè)調(diào)度、進(jìn)程調(diào)度(3)公平公平? 對(duì)于執(zhí)行時(shí)間較短的作業(yè)或進(jìn)程來說，等對(duì)于執(zhí)行時(shí)間較短的作業(yè)或進(jìn)程來說，等待時(shí)間可能較長(zhǎng)。待時(shí)間可能較長(zhǎng)。先來先服務(wù)調(diào)度算法續(xù)）先來先服務(wù)調(diào)度算法續(xù)）考慮下面的例子考慮下面的例子:如果作業(yè)隊(duì)列依次如果作業(yè)隊(duì)列依次(幾乎同時(shí)幾乎同時(shí))到達(dá)如到達(dá)如下下3個(gè)作業(yè)個(gè)作業(yè),按按“先來先服務(wù)的方式進(jìn)行調(diào)度完成后，先來先服務(wù)的方式進(jìn)行調(diào)度完成后，計(jì)算平均等待時(shí)間：計(jì)算平均等待時(shí)間：作業(yè)需運(yùn)行時(shí)間J150J210J31運(yùn)行情況：運(yùn)行情況：0506061平均等待時(shí)間平均等待時(shí)間=（0+50+60）/336.6

4、7如果到達(dá)順序?yàn)槿绻竭_(dá)順序?yàn)镴3、J2、J1，運(yùn)行情況：，運(yùn)行情況：011161平均等待時(shí)間平均等待時(shí)間=（0+1+11）/3=4J1J2J3J3J2J12. 輪轉(zhuǎn)調(diào)度算法輪轉(zhuǎn)調(diào)度算法Round Robin）輪轉(zhuǎn)法的基本概念是將輪轉(zhuǎn)法的基本概念是將CPU的處理時(shí)間分成固定大的處理時(shí)間分成固定大小的時(shí)間片（小的時(shí)間片（T）。如果一個(gè)進(jìn)程在被調(diào)度選中之后）。如果一個(gè)進(jìn)程在被調(diào)度選中之后用完了系統(tǒng)規(guī)定的時(shí)間片，但未完成要求的任務(wù)，則用完了系統(tǒng)規(guī)定的時(shí)間片，但未完成要求的任務(wù)，則它自行釋放自己所占有的它自行釋放自己所占有的CPU而排到就緒隊(duì)列的末尾，而排到就緒隊(duì)列的末尾，等待下一次調(diào)度。同時(shí)，進(jìn)程調(diào)

5、度程序又去調(diào)度當(dāng)前等待下一次調(diào)度。同時(shí)，進(jìn)程調(diào)度程序又去調(diào)度當(dāng)前就緒隊(duì)列中的第一個(gè)進(jìn)程。就緒隊(duì)列中的第一個(gè)進(jìn)程。注意：注意：（1該算法適于進(jìn)程調(diào)度，一般不適于作業(yè)調(diào)度該算法適于進(jìn)程調(diào)度，一般不適于作業(yè)調(diào)度為什么？）為什么？）（2適應(yīng)系統(tǒng)：分時(shí)系統(tǒng)適應(yīng)系統(tǒng)：分時(shí)系統(tǒng)圖圖4.4輪轉(zhuǎn)法調(diào)度輪轉(zhuǎn)法調(diào)度輪轉(zhuǎn)調(diào)度算法續(xù)）輪轉(zhuǎn)調(diào)度算法續(xù)）例：設(shè)某系統(tǒng)時(shí)間片值為例：設(shè)某系統(tǒng)時(shí)間片值為20，下列進(jìn)程的調(diào)度情況：，下列進(jìn)程的調(diào)度情況： Process Burst TimeP153 P2 17 P368 P4 24 在實(shí)際系統(tǒng)中，通常情況下隨著時(shí)間的推移，某些進(jìn)程運(yùn)在實(shí)際系統(tǒng)中，通常情況下隨著時(shí)間的推移，某些進(jìn)程運(yùn)

6、行完成本次的行完成本次的CPU Burst而撤離就緒隊(duì)列，同時(shí)還會(huì)有新的就而撤離就緒隊(duì)列，同時(shí)還會(huì)有新的就緒進(jìn)程不斷地加入。緒進(jìn)程不斷地加入。P1P2P3P4P1P3P4P1P3P302037577797117121 134154 162（3時(shí)間片長(zhǎng)度的取值時(shí)間片長(zhǎng)度的取值固定時(shí)間片固定時(shí)間片時(shí)間片長(zhǎng)度：幾十毫秒時(shí)間片長(zhǎng)度：幾十毫秒幾百毫秒幾百毫秒(例如例如 50ms) 過長(zhǎng)：響應(yīng)速度慢過長(zhǎng)：響應(yīng)速度慢 算法會(huì)退化為算法會(huì)退化為FCFS； 過短：進(jìn)程切換過于頻繁過短：進(jìn)程切換過于頻繁系統(tǒng)開銷系統(tǒng)開銷(overhead)大。大。可變時(shí)間片可變時(shí)間片設(shè)系統(tǒng)對(duì)響應(yīng)時(shí)間的要求是設(shè)系統(tǒng)對(duì)響應(yīng)時(shí)間的要求是

7、R，就緒隊(duì)列中最大進(jìn)程數(shù)為，就緒隊(duì)列中最大進(jìn)程數(shù)為Nmax。 因?yàn)橐驗(yàn)?R |T|*Nmax 所以所以 |T| R/Nmax一種可行的辦法是，每當(dāng)一輪調(diào)度開始時(shí)，系統(tǒng)便根據(jù)就緒一種可行的辦法是，每當(dāng)一輪調(diào)度開始時(shí)，系統(tǒng)便根據(jù)就緒隊(duì)列中已有進(jìn)程數(shù)目計(jì)算一次隊(duì)列中已有進(jìn)程數(shù)目計(jì)算一次T值，作為新一輪調(diào)度的時(shí)間片。值，作為新一輪調(diào)度的時(shí)間片。這種方法得到的時(shí)間片值隨就緒隊(duì)列中的進(jìn)程數(shù)變化。這種方法得到的時(shí)間片值隨就緒隊(duì)列中的進(jìn)程數(shù)變化。輪轉(zhuǎn)調(diào)度算法續(xù)）輪轉(zhuǎn)調(diào)度算法續(xù)）3. 最短作業(yè)優(yōu)先調(diào)度算法最短作業(yè)優(yōu)先調(diào)度算法SJF） Shortest Job First最短作業(yè)優(yōu)先法最短作業(yè)優(yōu)先法SJF就是選擇

8、那些估計(jì)需要就是選擇那些估計(jì)需要執(zhí)行時(shí)間最短的作業(yè)投入執(zhí)行。執(zhí)行時(shí)間最短的作業(yè)投入執(zhí)行。例：如果作業(yè)隊(duì)列依次例：如果作業(yè)隊(duì)列依次(幾乎同時(shí)幾乎同時(shí))到達(dá)如下到達(dá)如下3個(gè)作個(gè)作業(yè)業(yè),按最短作業(yè)優(yōu)先法按最短作業(yè)優(yōu)先法SJF調(diào)度。調(diào)度。作業(yè)需運(yùn)行時(shí)間J150J210J31011161平均等待時(shí)間平均等待時(shí)間=（0+1+11）/3=4J3J2J1最短作業(yè)優(yōu)先調(diào)度算法續(xù)）最短作業(yè)優(yōu)先調(diào)度算法續(xù)）優(yōu)點(diǎn)：優(yōu)點(diǎn)：（1可使得系統(tǒng)在單位時(shí)間內(nèi)處理的作業(yè)個(gè)數(shù)最可使得系統(tǒng)在單位時(shí)間內(nèi)處理的作業(yè)個(gè)數(shù)最多多吞吐量最大。吞吐量最大。（2對(duì)同一批作業(yè)而言，該算法使得作業(yè)的平均等對(duì)同一批作業(yè)而言，該算法使得作業(yè)的平均等待時(shí)間最

9、短。待時(shí)間最短。缺點(diǎn)：缺點(diǎn)： 可能使得某些運(yùn)行時(shí)間較長(zhǎng)的作業(yè)得不到調(diào)度執(zhí)行可能使得某些運(yùn)行時(shí)間較長(zhǎng)的作業(yè)得不到調(diào)度執(zhí)行的機(jī)會(huì)。的機(jī)會(huì)。 兩種調(diào)度方式：兩種調(diào)度方式： （1非剝奪方式非剝奪方式 （2剝奪方式，即最短剩余時(shí)間優(yōu)先剝奪方式，即最短剩余時(shí)間優(yōu)先Shortest-Remaining-Time First (SRTF)。最短作業(yè)優(yōu)先調(diào)度算法續(xù)）最短作業(yè)優(yōu)先調(diào)度算法續(xù)）非剝奪方式示例：非剝奪方式示例： Process Arrival Time Burst TimeP10.07 P22.04 P34.01 P45.04平均等待時(shí)間平均等待時(shí)間 = (0 + 6 + 3 + 7)/4 = 4P1

10、P3P273160P4812最短作業(yè)優(yōu)先調(diào)度算法續(xù)）最短作業(yè)優(yōu)先調(diào)度算法續(xù)）剝奪方式示例：剝奪方式示例：Process Arrival Time Burst TimeP10.07 P22.04 P34.01 P45.04平均等待時(shí)間平均等待時(shí)間 = (9 + 1 + 0 +2)/4 = 3P1P3P242110P457P2P116 最短作業(yè)優(yōu)先調(diào)度算法續(xù)）最短作業(yè)優(yōu)先調(diào)度算法續(xù)） 對(duì)運(yùn)行時(shí)間的估計(jì)：對(duì)運(yùn)行時(shí)間的估計(jì)： （1作業(yè)調(diào)度：系統(tǒng)要求用戶在提交作業(yè)時(shí)聲明估作業(yè)調(diào)度：系統(tǒng)要求用戶在提交作業(yè)時(shí)聲明估計(jì)作業(yè)的運(yùn)行時(shí)間。計(jì)作業(yè)的運(yùn)行時(shí)間。 （2進(jìn)程調(diào)度：進(jìn)程調(diào)度：CPU burst時(shí)間的確定時(shí)間

11、的確定根據(jù)進(jìn)程根據(jù)進(jìn)程以前的行為推測(cè)。以前的行為推測(cè)。 1. tn=第第n次次CPU burst的實(shí)際運(yùn)行時(shí)間的實(shí)際運(yùn)行時(shí)間 2.n+1=下一次下一次CPU burst的估計(jì)的估計(jì)(預(yù)測(cè)預(yù)測(cè))運(yùn)行時(shí)間運(yùn)行時(shí)間 3. 0 1 4.定義定義:.1 1nnnt =0時(shí)，時(shí)， n+1 = n，即估計(jì)時(shí)間為常量，沒考慮實(shí)際運(yùn)行時(shí)，即估計(jì)時(shí)間為常量，沒考慮實(shí)際運(yùn)行時(shí)間間 =1時(shí)，時(shí)， n+1 = tn，即估計(jì)時(shí)間為上次的實(shí)際運(yùn)行時(shí)間，即估計(jì)時(shí)間為上次的實(shí)際運(yùn)行時(shí)間通常，可以選擇通常，可以選擇 =1/2最短作業(yè)優(yōu)先調(diào)度算法續(xù)）最短作業(yè)優(yōu)先調(diào)度算法續(xù)）例：現(xiàn)有某進(jìn)程，各例：現(xiàn)有某進(jìn)程，各CPU burst實(shí)際

12、時(shí)間為：實(shí)際時(shí)間為：6、4、6、4、13、13、13。給出系統(tǒng)每次調(diào)度前。給出系統(tǒng)每次調(diào)度前CPU burst的估計(jì)值。的估計(jì)值。系統(tǒng)設(shè)定的系統(tǒng)設(shè)定的1=10 ，選擇，選擇=1/2。 2=10+0.5*(6-10)=8 3=8+0.5*(4-8)=6 4=6+0.5*(6-6)=6 5=6+0.5*(4-6)=5 6=5+0.5*(13-5)=9 7=9+0.5*(13-9)=11 8=11+0.5*(13-11)=12 4. 最高響應(yīng)比優(yōu)先調(diào)度算法最高響應(yīng)比優(yōu)先調(diào)度算法HRN） Highest Response ratio Next 最高響應(yīng)比優(yōu)先法最高響應(yīng)比優(yōu)先法HRN是對(duì)是對(duì)FCFS方式

13、和方式和SJF 方式的方式的一種綜合平衡。一種綜合平衡。 響應(yīng)比響應(yīng)比R定義如下：定義如下：R=(W+T)/T=1+W/T 其中其中T為該作業(yè)估計(jì)需要的執(zhí)行時(shí)間，為該作業(yè)估計(jì)需要的執(zhí)行時(shí)間，W為作業(yè)的等待時(shí)為作業(yè)的等待時(shí)間。間。 每當(dāng)要進(jìn)行作業(yè)調(diào)度時(shí)，系統(tǒng)計(jì)算每個(gè)作業(yè)的響應(yīng)比，選每當(dāng)要進(jìn)行作業(yè)調(diào)度時(shí)，系統(tǒng)計(jì)算每個(gè)作業(yè)的響應(yīng)比，選擇其中擇其中R最大者投入執(zhí)行。最大者投入執(zhí)行。 這種算法是介于這種算法是介于FCFS和和SJF 之間的一種折中算法。由于之間的一種折中算法。由于每次調(diào)度前要計(jì)算響應(yīng)比，系統(tǒng)開銷也要相應(yīng)增加。每次調(diào)度前要計(jì)算響應(yīng)比，系統(tǒng)開銷也要相應(yīng)增加。 最高響應(yīng)比優(yōu)先調(diào)度算法續(xù)）最高響

14、應(yīng)比優(yōu)先調(diào)度算法續(xù)） R=(W+T)/T=1+W/T 考慮下面的例子考慮下面的例子作業(yè)到達(dá)時(shí)間需運(yùn)行時(shí)間開始時(shí)間 完成時(shí)間等待時(shí)間J18:0050分8:008:500分J28:3020分J38:4015分J48:555分8:50 9:10 20分分9:15 9:30 35分分9:10 9:15 15分分 平均等待時(shí)間平均等待時(shí)間(0203515)417.5 分別采用分別采用FCFS、SJF算法進(jìn)行調(diào)度，各自的平均等待算法進(jìn)行調(diào)度，各自的平均等待時(shí)間？反映了什么問題？時(shí)間？反映了什么問題？5. 優(yōu)先級(jí)調(diào)度算法優(yōu)先級(jí)調(diào)度算法HPF） Highest Priority First 系統(tǒng)或用戶按某種原

15、則為作業(yè)或進(jìn)程指定一個(gè)優(yōu)系統(tǒng)或用戶按某種原則為作業(yè)或進(jìn)程指定一個(gè)優(yōu)先級(jí)，系統(tǒng)按優(yōu)先級(jí)進(jìn)行調(diào)度。先級(jí)，系統(tǒng)按優(yōu)先級(jí)進(jìn)行調(diào)度。 優(yōu)先級(jí)法可被用于作業(yè)或進(jìn)程的調(diào)度策略。優(yōu)先級(jí)法可被用于作業(yè)或進(jìn)程的調(diào)度策略。 （1優(yōu)先級(jí)的確定優(yōu)先級(jí)的確定 靜態(tài)法：在作業(yè)或進(jìn)程開始執(zhí)行之前就確靜態(tài)法：在作業(yè)或進(jìn)程開始執(zhí)行之前就確定它們的優(yōu)先級(jí)，一旦開始執(zhí)行之后就不能改變。定它們的優(yōu)先級(jí)，一旦開始執(zhí)行之后就不能改變。 動(dòng)態(tài)法：隨著作業(yè)或進(jìn)程的執(zhí)行，其優(yōu)先動(dòng)態(tài)法：隨著作業(yè)或進(jìn)程的執(zhí)行，其優(yōu)先級(jí)不斷變化。級(jí)不斷變化。 （2影響優(yōu)先級(jí)因素影響優(yōu)先級(jí)因素 外部因素：任務(wù)的緊迫程度、付費(fèi)、進(jìn)程外部因素：任務(wù)的緊迫程度、付費(fèi)、進(jìn)程類

16、型類型(系統(tǒng)、用戶進(jìn)程系統(tǒng)、用戶進(jìn)程)。例如，在操作系統(tǒng)中，對(duì)于。例如，在操作系統(tǒng)中，對(duì)于鍵盤中斷的處理優(yōu)先級(jí)和對(duì)于電源掉電中斷的處理鍵盤中斷的處理優(yōu)先級(jí)和對(duì)于電源掉電中斷的處理優(yōu)先級(jí)是不相同的。優(yōu)先級(jí)是不相同的。 內(nèi)部因素：作業(yè)類型內(nèi)部因素：作業(yè)類型IO型、計(jì)算型）、型、計(jì)算型）、資源需求資源需求 （3剝奪剝奪非剝奪優(yōu)先級(jí)調(diào)度非剝奪優(yōu)先級(jí)調(diào)度 非剝奪方式：獲得處理機(jī)的進(jìn)程，直至終非剝奪方式：獲得處理機(jī)的進(jìn)程，直至終止、等待止、等待 剝奪方式：獲得處理機(jī)的進(jìn)程，直至終止、剝奪方式：獲得處理機(jī)的進(jìn)程，直至終止、等待、出現(xiàn)高優(yōu)先級(jí)的就緒進(jìn)程等待、出現(xiàn)高優(yōu)先級(jí)的就緒進(jìn)程 優(yōu)先級(jí)調(diào)度算法續(xù)）優(yōu)先級(jí)調(diào)度

17、算法續(xù)） 其實(shí)優(yōu)先級(jí)調(diào)度算法僅僅是一種思想，前面介紹其實(shí)優(yōu)先級(jí)調(diào)度算法僅僅是一種思想，前面介紹的所有算法都可看成是優(yōu)先級(jí)調(diào)度。的所有算法都可看成是優(yōu)先級(jí)調(diào)度。 UNIX例子：可剝奪、動(dòng)態(tài)優(yōu)先級(jí)調(diào)度例子：可剝奪、動(dòng)態(tài)優(yōu)先級(jí)調(diào)度 優(yōu)先級(jí)計(jì)算公式：優(yōu)先級(jí)計(jì)算公式： p_pri=min127, USER+p_cpu/16+p_nice 定義定義USER=100； p_cpu: 運(yùn)行進(jìn)程每運(yùn)行進(jìn)程每20ms加加1優(yōu)先級(jí)降低），優(yōu)先級(jí)降低），其它就緒進(jìn)程每其它就緒進(jìn)程每1200ms減減10優(yōu)先級(jí)提高）；優(yōu)先級(jí)提高）； p_nice: 可以通過系統(tǒng)調(diào)用可以通過系統(tǒng)調(diào)用nice()修改的量。修改的量。 6.多

18、級(jí)隊(duì)列算法多級(jí)隊(duì)列算法(MLQ)Multilevel Queue 多個(gè)就緒隊(duì)列，進(jìn)程所屬的隊(duì)列固定。不同就緒隊(duì)多個(gè)就緒隊(duì)列，進(jìn)程所屬的隊(duì)列固定。不同就緒隊(duì)列具有不同優(yōu)先級(jí)；各個(gè)隊(duì)列擁有自己的調(diào)度算法；列具有不同優(yōu)先級(jí)；各個(gè)隊(duì)列擁有自己的調(diào)度算法；處理機(jī)要在不同隊(duì)列中調(diào)度。處理機(jī)要在不同隊(duì)列中調(diào)度。 例如：某通用系統(tǒng)例如：某通用系統(tǒng) 隊(duì)列隊(duì)列1：實(shí)時(shí)進(jìn)程就緒隊(duì)列：實(shí)時(shí)進(jìn)程就緒隊(duì)列HPF） 隊(duì)列隊(duì)列2：分時(shí)進(jìn)程就緒隊(duì)列：分時(shí)進(jìn)程就緒隊(duì)列RR） 隊(duì)列隊(duì)列3：批處理進(jìn)程就緒隊(duì)列：批處理進(jìn)程就緒隊(duì)列HPF） 7. 多級(jí)反饋隊(duì)列調(diào)度算法多級(jí)反饋隊(duì)列調(diào)度算法MFQ） Multilevel Feedback

19、Queue （1多個(gè)就緒進(jìn)程隊(duì)列多個(gè)就緒進(jìn)程隊(duì)列 （2進(jìn)程會(huì)在不同隊(duì)列中移動(dòng)進(jìn)程會(huì)在不同隊(duì)列中移動(dòng) （3該算法的關(guān)鍵點(diǎn)：該算法的關(guān)鍵點(diǎn)： 就緒隊(duì)列個(gè)數(shù)就緒隊(duì)列個(gè)數(shù) 每個(gè)隊(duì)列采用的調(diào)度算法每個(gè)隊(duì)列采用的調(diào)度算法 何時(shí)提升、降低進(jìn)程優(yōu)先級(jí)何時(shí)提升、降低進(jìn)程優(yōu)先級(jí) 進(jìn)程就緒該進(jìn)程進(jìn)入哪個(gè)就緒隊(duì)列進(jìn)程就緒該進(jìn)程進(jìn)入哪個(gè)就緒隊(duì)列Q1RR，HPF）Q2RR，HPF）QnRR，HPF）運(yùn)行運(yùn)行s1時(shí)間片時(shí)間片運(yùn)行運(yùn)行s2時(shí)間片時(shí)間片.創(chuàng)建創(chuàng)建喚醒喚醒高高 優(yōu)先級(jí)優(yōu)先級(jí) 低低運(yùn)行運(yùn)行sn時(shí)間片時(shí)間片多級(jí)反饋隊(duì)列調(diào)度算法續(xù)）多級(jí)反饋隊(duì)列調(diào)度算法續(xù)）一個(gè)實(shí)例一個(gè)實(shí)例: n個(gè)就緒隊(duì)列；每個(gè)隊(duì)列采用類似的個(gè)就緒隊(duì)列；

20、每個(gè)隊(duì)列采用類似的RR算法；隊(duì)列之算法；隊(duì)列之間采用剝奪間采用剝奪HPF算法；算法；Q1優(yōu)先級(jí)最高，對(duì)應(yīng)的時(shí)間片優(yōu)先級(jí)最高，對(duì)應(yīng)的時(shí)間片S1最小，最小，Qn優(yōu)先級(jí)最低，對(duì)應(yīng)的時(shí)間片優(yōu)先級(jí)最低，對(duì)應(yīng)的時(shí)間片Sn最大；就緒進(jìn)程最大；就緒進(jìn)程進(jìn)入進(jìn)入Q1就緒隊(duì)列。就緒隊(duì)列。運(yùn)行結(jié)束退出運(yùn)行結(jié)束退出運(yùn)行結(jié)束退出運(yùn)行結(jié)束退出運(yùn)行結(jié)束退出運(yùn)行結(jié)束退出小小 時(shí)時(shí)間間片片大大（1該算法宗旨：以該算法宗旨：以IO為主的進(jìn)程響應(yīng)速度較快，以計(jì)為主的進(jìn)程響應(yīng)速度較快，以計(jì)算為主的進(jìn)程運(yùn)行一段時(shí)間后，會(huì)下降到低優(yōu)先級(jí)隊(duì)列運(yùn)行。算為主的進(jìn)程運(yùn)行一段時(shí)間后，會(huì)下降到低優(yōu)先級(jí)隊(duì)列運(yùn)行。（2系統(tǒng)效率較高、資源利用率高。系統(tǒng)效

21、率較高、資源利用率高。（3算法的改進(jìn)：算法的改進(jìn)： 考慮某些以計(jì)算為主的進(jìn)程，偶爾一次考慮某些以計(jì)算為主的進(jìn)程，偶爾一次IO； 開始時(shí)以計(jì)算為主，后來變?yōu)橐蚤_始時(shí)以計(jì)算為主，后來變?yōu)橐訧O為主。為主。 改進(jìn)方法：改進(jìn)方法： 每一次每一次IO結(jié)束后，再次就緒時(shí)進(jìn)入高一級(jí)就緒隊(duì)列。結(jié)束后，再次就緒時(shí)進(jìn)入高一級(jí)就緒隊(duì)列。 例如例如VAX VMS操作系統(tǒng)的處理。操作系統(tǒng)的處理。 多級(jí)反饋隊(duì)列調(diào)度算法續(xù)）多級(jí)反饋隊(duì)列調(diào)度算法續(xù)） 優(yōu)先級(jí)調(diào)度算法實(shí)例）優(yōu)先級(jí)調(diào)度算法實(shí)例）例如：線性優(yōu)先級(jí)調(diào)度策略例如：線性優(yōu)先級(jí)調(diào)度策略selfish round robin）使用輪轉(zhuǎn)法調(diào)度進(jìn)程時(shí)，新創(chuàng)建的進(jìn)程也放入就緒使用

22、輪轉(zhuǎn)法調(diào)度進(jìn)程時(shí)，新創(chuàng)建的進(jìn)程也放入就緒隊(duì)列末尾享受平等的處理機(jī)時(shí)間片。這對(duì)于執(zhí)行時(shí)間隊(duì)列末尾享受平等的處理機(jī)時(shí)間片。這對(duì)于執(zhí)行時(shí)間長(zhǎng)的進(jìn)程來說是有點(diǎn)不公平的，因?yàn)樗鼈冃枰鄠€(gè)時(shí)長(zhǎng)的進(jìn)程來說是有點(diǎn)不公平的，因?yàn)樗鼈冃枰鄠€(gè)時(shí)間片才能完成。因而，線性優(yōu)先級(jí)調(diào)度策略采用如下間片才能完成。因而，線性優(yōu)先級(jí)調(diào)度策略采用如下方式，即新創(chuàng)建的進(jìn)程按方式，即新創(chuàng)建的進(jìn)程按FCFS方式排成就緒隊(duì)列，而方式排成就緒隊(duì)列，而其他已得到過時(shí)間片服務(wù)的進(jìn)程也按其他已得到過時(shí)間片服務(wù)的進(jìn)程也按FCFS方式排成另方式排成另一個(gè)就緒隊(duì)列或稱享受服務(wù)隊(duì)列一個(gè)就緒隊(duì)列或稱享受服務(wù)隊(duì)列(圖圖4.5）。）。圖圖4.5 線性優(yōu)先級(jí)調(diào)

23、度線性優(yōu)先級(jí)調(diào)度對(duì)于這兩個(gè)不同隊(duì)列中的進(jìn)程，設(shè)新創(chuàng)建進(jìn)程就對(duì)于這兩個(gè)不同隊(duì)列中的進(jìn)程，設(shè)新創(chuàng)建進(jìn)程就緒隊(duì)列中進(jìn)程的優(yōu)先級(jí)緒隊(duì)列中進(jìn)程的優(yōu)先級(jí)P以以 P=a*t (a0) 的速率增的速率增加。另外，享受服務(wù)隊(duì)列中進(jìn)程的優(yōu)先級(jí)加。另外，享受服務(wù)隊(duì)列中進(jìn)程的優(yōu)先級(jí)P以以 P=b*t (ab0) 的速率增長(zhǎng)。設(shè)某一進(jìn)程在時(shí)刻的速率增長(zhǎng)。設(shè)某一進(jìn)程在時(shí)刻t1時(shí)被創(chuàng)建，在時(shí)刻時(shí)被創(chuàng)建，在時(shí)刻t時(shí)，該進(jìn)程的優(yōu)先級(jí)為時(shí)，該進(jìn)程的優(yōu)先級(jí)為P(t)=a*(t-t1) (t1tt1)又設(shè)該進(jìn)程在又設(shè)該進(jìn)程在t1時(shí)刻轉(zhuǎn)入享受服務(wù)隊(duì)列，則在時(shí)時(shí)刻轉(zhuǎn)入享受服務(wù)隊(duì)列，則在時(shí)刻刻t，該進(jìn)程的優(yōu)先級(jí)變?yōu)椋撨M(jìn)程的優(yōu)先級(jí)變?yōu)镻(

24、t)=a*(t1-t1)+b*(t-t1) (t1tb0 的條的條件是必要的。否則，當(dāng)件是必要的。否則，當(dāng)ba0 時(shí)，兩個(gè)不同隊(duì)列中的時(shí)，兩個(gè)不同隊(duì)列中的就緒態(tài)進(jìn)程的優(yōu)先級(jí)將永遠(yuǎn)不會(huì)相等，從而，在享就緒態(tài)進(jìn)程的優(yōu)先級(jí)將永遠(yuǎn)不會(huì)相等，從而，在享受服務(wù)進(jìn)程隊(duì)列中永遠(yuǎn)只有一個(gè)進(jìn)程。因而，上述受服務(wù)進(jìn)程隊(duì)列中永遠(yuǎn)只有一個(gè)進(jìn)程。因而，上述線性優(yōu)先級(jí)調(diào)度策略退回到線性優(yōu)先級(jí)調(diào)度策略退回到FCFS方式。另外，如果方式。另外，如果ab=0，則線性優(yōu)先級(jí)調(diào)度策略退回到輪轉(zhuǎn)法調(diào)度方，則線性優(yōu)先級(jí)調(diào)度策略退回到輪轉(zhuǎn)法調(diào)度方式。事實(shí)上，線性優(yōu)先級(jí)調(diào)度策略是一種介于輪轉(zhuǎn)式。事實(shí)上，線性優(yōu)先級(jí)調(diào)度策略是一種介于輪轉(zhuǎn)法和法

25、和FCFS方式之間的調(diào)度策略。這幾種方式的調(diào)度方式之間的調(diào)度策略。這幾種方式的調(diào)度性能，將在下一節(jié)中更進(jìn)一步討論。性能，將在下一節(jié)中更進(jìn)一步討論。習(xí)習(xí) 題題 4.1 什么是分級(jí)調(diào)度？分時(shí)系統(tǒng)中有作業(yè)調(diào)什么是分級(jí)調(diào)度？分時(shí)系統(tǒng)中有作業(yè)調(diào)度的概念嗎？如果沒有，為什么？度的概念嗎？如果沒有，為什么？4.2 試述作業(yè)調(diào)度的主要功能。試述作業(yè)調(diào)度的主要功能。4.3 作業(yè)調(diào)度的性能評(píng)價(jià)標(biāo)準(zhǔn)有哪些？這些作業(yè)調(diào)度的性能評(píng)價(jià)標(biāo)準(zhǔn)有哪些？這些性能評(píng)價(jià)標(biāo)準(zhǔn)在任何情況下都能反映調(diào)度策略性能評(píng)價(jià)標(biāo)準(zhǔn)在任何情況下都能反映調(diào)度策略的優(yōu)劣嗎？的優(yōu)劣嗎？4.4 進(jìn)程調(diào)度的功能有哪些？進(jìn)程調(diào)度的功能有哪些？4.5 進(jìn)程調(diào)度的時(shí)機(jī)有哪幾種？進(jìn)程調(diào)度的時(shí)機(jī)有哪幾種？4.6 進(jìn)程上下文切換由哪幾部分組成？形式進(jìn)程上下文切換由哪幾部分組成？形式化地描述進(jìn)程上下文切換過程?；孛枋鲞M(jìn)程上下文切換過程。4.7 為什么說在進(jìn)程上下文切換過程中，上為什么說在進(jìn)程上下文切換過程中，上下文切換程序不能破壞下文切換程序不能破壞“老進(jìn)程的上下文結(jié)老進(jìn)程的上下文結(jié)構(gòu)？構(gòu)？4.8 假設(shè)有假設(shè)有4道作業(yè)，它們的提交時(shí)刻及執(zhí)行時(shí)間道作業(yè)，它們的提交時(shí)刻及執(zhí)行時(shí)間由下表給出：由下表給出：計(jì)算在單道程序環(huán)境下，采用先來先服務(wù)調(diào)度算計(jì)算在單道程序環(huán)境下，采用先來先服務(wù)調(diào)度算法和最