操作系統(tǒng)概念中文版

Chap5CPU調(diào)度內(nèi)容基本概念調(diào)度準(zhǔn)則調(diào)度算法多處理器調(diào)度實(shí)時(shí)調(diào)度算法評估總結(jié)基本概念CPU調(diào)度（進(jìn)程調(diào)度）是多任務(wù)操作系統(tǒng)的基礎(chǔ)。通過多道程序設(shè)計(jì)得到CPU的最高利用率CPU-I/O脈沖周期(CPU–I/OBurstCycle

)-進(jìn)程的執(zhí)行包括進(jìn)程在CPU上執(zhí)行和等待I/OCPU和I/O的交替順序CPU使用時(shí)間圖CPU調(diào)度程序選擇內(nèi)存中的就緒進(jìn)程，并分配CPU給其中之一CPU調(diào)度可能發(fā)生在當(dāng)一個(gè)進(jìn)程:1. 從運(yùn)行轉(zhuǎn)到等待.2. 從運(yùn)行轉(zhuǎn)到就緒.3. 從等待轉(zhuǎn)到就緒.4. 終止運(yùn)行.發(fā)生在1、4兩種情況下的調(diào)度稱為非搶占式調(diào)度(nonpreemptive).其他情況下發(fā)生的調(diào)度稱為搶占式調(diào)度(preemptive).調(diào)度模塊(Dispatcher)進(jìn)程調(diào)度(分派程序)模塊負(fù)責(zé)將對CPU的控制權(quán)轉(zhuǎn)交給由CPU調(diào)度程序，包括:切換上下文切換到用戶態(tài)跳轉(zhuǎn)到用戶程序的適當(dāng)位置并重新運(yùn)行之調(diào)度時(shí)間、分派延遲(Dispatchlatency)–調(diào)度程序終止一個(gè)進(jìn)程的運(yùn)行并啟動另一個(gè)進(jìn)程運(yùn)行所花的時(shí)間.調(diào)度準(zhǔn)則CPU利用率–使CPU盡可能的忙碌吞吐量–單位時(shí)間內(nèi)運(yùn)行完的進(jìn)程數(shù)周轉(zhuǎn)時(shí)間–進(jìn)程從提交到運(yùn)行結(jié)束的全部時(shí)間,帶權(quán)周轉(zhuǎn)時(shí)間—周轉(zhuǎn)時(shí)間/運(yùn)行時(shí)間等待時(shí)間–進(jìn)程在就緒隊(duì)列中等待調(diào)度的時(shí)間片總和響應(yīng)時(shí)間–從進(jìn)程提出請求到首次被響應(yīng)[而不是輸出結(jié)果]的時(shí)間段[在分時(shí)系統(tǒng)環(huán)境下]優(yōu)化準(zhǔn)則最大的CPU利用率最大的吞吐量最短的周轉(zhuǎn)時(shí)間最短的等待時(shí)間最短的響應(yīng)時(shí)間eFirst-Served(FCFS)Scheduling

先來先服務(wù)調(diào)度算法舉例: 進(jìn)程

區(qū)間時(shí)間

P1 24

P2 3

P3 3

假定進(jìn)程到達(dá)順序如下:P1,P2,P3該調(diào)度的Gantt圖為:

等待時(shí)間：

P1=0;P2=24;P3=27平均等待時(shí)間:(0+24+27)/3=17P1P2P32427300FCFS調(diào)度假定進(jìn)程到達(dá)順序如下

P2,P3,P1.該調(diào)度的Gantt圖為:

等待時(shí)間:

P1=6;

P2=0;P3=3平均等待時(shí)間:(6+0+3)/3=3比前例好得多此種結(jié)果（護(hù)航效果convoyeffect）產(chǎn)生是由于長進(jìn)程先于短進(jìn)程到達(dá)P1P3P263300FCFS調(diào)度－動畫演示Shortest-Job-First(SJF)Scheduling

短作業(yè)優(yōu)先調(diào)度算法關(guān)聯(lián)到每個(gè)進(jìn)程下次運(yùn)行的CPU脈沖長度，調(diào)度最短的進(jìn)程兩種模式:

非搶占式調(diào)度nonpreemptive–一旦進(jìn)程擁有CPU，它的使用權(quán)限只能在該CPU脈沖結(jié)束后讓出.搶占式調(diào)度Preemptive–發(fā)生在有比當(dāng)前進(jìn)程剩余時(shí)間片更短的進(jìn)程到達(dá)時(shí)，也稱為最短剩余時(shí)間優(yōu)先調(diào)度Shortest-Remaining-Time-First(SRTF).

SJF是最優(yōu)的–對一組指定的進(jìn)程而言，它給出了最短的平均等待時(shí)間

進(jìn)程

到達(dá)時(shí)間

區(qū)間時(shí)間

P1 0.0 7

P2 2.0 4

P3 4.0 1

P4 5.0 4SJF(non-preemptive)平均等待時(shí)間=(0+6+3+7)/4=4ExampleofNon-PreemptiveSJF

非搶占式SJF例子P1P3P273160P4812搶占式SJF例子

進(jìn)程

到達(dá)時(shí)間

區(qū)間時(shí)間

P1 0.0 7

P2 2.0 4

P3 4.0 1

P4 5.0 4SJF(preemptive)平均等待時(shí)間=(9+1+0+2)/4=3P1P3P242110P457P2P116短作業(yè)優(yōu)先調(diào)度－動畫演示CPU下一次脈沖的探測其長度只能估計(jì).可以通過先前的CPU脈沖長度及計(jì)算指數(shù)均值進(jìn)行PredictionoftheLengthoftheNextCPUBurst指數(shù)平均例子=0n+1=n近來歷史沒有影響=1n+1=tn只有最近的CPU區(qū)間才重要如果擴(kuò)展公式，得到:n+1=tn+(1-)tn-1+…+(1-)jtn-j+…+(1-)n+10由于和(1-)都小于或等于1，所以后面項(xiàng)的權(quán)比前面項(xiàng)的權(quán)小PriorityScheduling

優(yōu)先級調(diào)度每個(gè)進(jìn)程都有自己的優(yōu)先數(shù)[整數(shù)]CPU分配給最高優(yōu)先級的進(jìn)程[假定最小的整數(shù)最高的優(yōu)先級].Preemptive（搶占式）Nonpreemptive（非搶占式）SJF是以下一次CPU脈沖長度為優(yōu)先數(shù)的優(yōu)先級調(diào)度.問題饑餓–低優(yōu)先級的可能永遠(yuǎn)得不到運(yùn)行.解決方法老化–視進(jìn)程等待時(shí)間的延長提高其優(yōu)先數(shù).PR例子

進(jìn)程

優(yōu)先級

區(qū)間時(shí)間

P1 3 10

P2 1 1

P3 3 2

P4 4 1

P5 2 5平均等待時(shí)間=(0+5+16+18+1)/4=10P2P3P51160P4618P119RoundRobin(RR)

時(shí)間片輪轉(zhuǎn)每個(gè)進(jìn)程將得到小單位的CPU時(shí)間[時(shí)間片]，通常為10-100毫秒。時(shí)間片用完后，該進(jìn)程將被搶占并插入就緒隊(duì)列末尾.假定就緒隊(duì)列中有n個(gè)進(jìn)程、時(shí)間片為q,則每個(gè)進(jìn)程每次得到1/n的、不超過q單位的成塊CPU時(shí)間，沒有任何一個(gè)進(jìn)程的等待時(shí)間會超過(n-1)q單位.特性q

大FIFOq小q相對于切換上下文的時(shí)間而言必須足夠長，否則將導(dǎo)致系統(tǒng)開銷過大.時(shí)間片為20的RR例子

進(jìn)程

區(qū)間時(shí)間 P1 53

P2 17

P3 68

P4 24Gantt圖如下:

典型的說，RR的平均周轉(zhuǎn)時(shí)間比SJF長，但響應(yīng)時(shí)間要短一些.P1P2P3P4P1P3P4P1P3P302037577797117121134154162時(shí)間片輪轉(zhuǎn)調(diào)度－動畫演示顯示小時(shí)間片增加上下文切換時(shí)間時(shí)間片和周轉(zhuǎn)時(shí)間的關(guān)系MultilevelQueue

多級隊(duì)列就緒隊(duì)列分為:前臺[交互式]后臺[批處理]每個(gè)隊(duì)列有自己的調(diào)度算法

前臺–RR

后臺–FCFS調(diào)度須在隊(duì)列間進(jìn)行.固定優(yōu)先級調(diào)度，即前臺運(yùn)行完后再運(yùn)行后臺。有可能產(chǎn)生饑餓.給定時(shí)間片調(diào)度，即每個(gè)隊(duì)列得到一定的CPU時(shí)間，進(jìn)程在給定時(shí)間內(nèi)執(zhí)行；如，80%的時(shí)間執(zhí)行前臺的RR調(diào)度，20%的時(shí)間執(zhí)行后臺的FCFS調(diào)度MultilevelQueueScheduling

多級隊(duì)列調(diào)度MultilevelFeedbackQueue

多級反饋隊(duì)列調(diào)度進(jìn)程能在不同的隊(duì)列間移動；可實(shí)現(xiàn)老化.多級反饋隊(duì)列調(diào)度程序由以下參數(shù)定義:隊(duì)列數(shù)每一隊(duì)列的調(diào)度算法決定進(jìn)程升級的方法決定進(jìn)程降級的方法決定需要服務(wù)的進(jìn)程將進(jìn)入哪個(gè)隊(duì)列的方法MultilevelFeedbackQueues

多級反饋隊(duì)列調(diào)度多級反饋隊(duì)列調(diào)度例子三個(gè)隊(duì)列:Q0–時(shí)間片為8毫秒Q1–時(shí)間片為16毫秒Q2–FCFS調(diào)度新的作業(yè)進(jìn)入FCFS的Q0隊(duì)列，它得到CPU時(shí)能使用8毫秒，如果它不能在8毫秒內(nèi)完成，將移動到隊(duì)列Q1

.作業(yè)在Q1仍將作為FCFS調(diào)度，能使用附加的16毫秒，如果它還不能完成，將被搶占，移至隊(duì)列Q2

.多處理器調(diào)度多個(gè)CPU可用時(shí)，CPU調(diào)度將更為復(fù)雜.多處理器內(nèi)的同類處理器.負(fù)載共享對稱多處理器(SMP)

–每個(gè)處理器決定自己的調(diào)度方案.非對稱多處理器(ASMP)

–僅一個(gè)處理器能處理系統(tǒng)數(shù)據(jù)結(jié)構(gòu)，這就減輕了對數(shù)據(jù)的共享需求Real-TimeScheduling

實(shí)時(shí)調(diào)度硬實(shí)時(shí)系統(tǒng)(hardreal-time)–用于實(shí)現(xiàn)要求在給定的時(shí)間內(nèi)執(zhí)行完關(guān)鍵進(jìn)程的場合

軟實(shí)時(shí)計(jì)算(softreal-time)

–當(dāng)要求臨界進(jìn)程得到比其他進(jìn)程更高的優(yōu)先級時(shí)使用線程調(diào)度局部調(diào)度(LocalScheduling)–線程庫怎樣決定將哪個(gè)線程列入有效的輕量級進(jìn)程LWP全局調(diào)度(GlobalScheduling)–內(nèi)核怎樣決定下一個(gè)運(yùn)行的內(nèi)核線程調(diào)度響應(yīng)時(shí)間算法評估

確定性建模法–精確預(yù)定作業(yè)量，并定義該作業(yè)量在每個(gè)算法上執(zhí)行的情況排隊(duì)模型模擬通過模擬CPU調(diào)度程序來評價(jià)Solaris2SchedulingWindows2