第九章：?jiǎn)我惶幚砥髋懦?Scheduling)

9.1排程的種類處理器排程排程的種類長(zhǎng)程(long-term)：決定是否將process加入系統(tǒng)。中程(medium-term)：決定是否將process的部分或全部載入主記憶體中。短程(short-term)：決定執(zhí)行哪個(gè)process。輸入/輸出(I/O)排程：決定等待I/O資源的process中，何者使用此I/O資源。(本章不討論)處理器排程的目的：安排process由處理器執(zhí)行，並考慮到系統(tǒng)的功能需求，如：回應(yīng)時(shí)間(Responsetime)、產(chǎn)量(throughput)、效率(efficiency)。排程影響系統(tǒng)的效能，排程是一種管理佇列的方式，希望能降低佇列延遲(queuingdelay)。1排程與process狀態(tài)轉(zhuǎn)移Figure9.1SchedulingandProcessStateTransitions23Figure9.2LevelsofSchedulingLongterm3Figure9.3QueuingDiagramforScheduling44s=預(yù)計(jì)的處理(服務(wù))時(shí)間。最短process優(yōu)先(ShortestProcessNext)(續(xù))排程方法：最短process優(yōu)先(ShortestProcessNext)輸入/輸出(I/O)排程：決定等待I/O資源的process中，何者使用此I/O資源。當(dāng)一個(gè)新的process加入readyqueue，其可能含有比正在執(zhí)行的process短的剩餘時(shí)間，如此則搶先執(zhí)行。(a)Increasingfunction公平性(fairness)：處理器應(yīng)該一視同仁，沒(méi)有process會(huì)發(fā)生飢餓。期限(deadline)：process給定的完成的截止時(shí)間。這些評(píng)量標(biāo)準(zhǔn)彼此相關(guān)，要做到所有標(biāo)準(zhǔn)的最佳化是不可能的。使用者導(dǎo)向，效能相關(guān)：決策模式：選擇函式執(zhí)行的時(shí)機(jī)w=花費(fèi)在等待處理器的時(shí)間。排程方法：最高回應(yīng)率優(yōu)先(HighestResponseRatioNext)9.2排程演算法(SchedulingAlgorithms)排程的原則，共分成四類：使用者導(dǎo)向(user-oriented)vs.系統(tǒng)導(dǎo)向(system-oriented)效能相關(guān)(performance-related)vs.其他使用者導(dǎo)向，效能相關(guān)：回應(yīng)時(shí)間(responsetime)：由工作發(fā)出要求到收到回應(yīng)的時(shí)間。往返時(shí)間(turnaroundtime)：由工作發(fā)出要求到其結(jié)束的時(shí)間。期限(deadline)：process給定的完成的截止時(shí)間。使用者導(dǎo)向，其他可預(yù)測(cè)度(predictability)：不論系統(tǒng)負(fù)載如何，執(zhí)行時(shí)間與花費(fèi)應(yīng)差不多。系統(tǒng)導(dǎo)向，效能相關(guān)產(chǎn)出率(throughput)：?jiǎn)挝粫r(shí)間完成的工作量。處理器使用率(processorutilization)：處理器忙碌的時(shí)間比例。5排程的原則(續(xù))系統(tǒng)導(dǎo)向，其他公平性(fairness)：處理器應(yīng)該一視同仁，沒(méi)有process會(huì)發(fā)生飢餓。確保優(yōu)先度(enforcingpriorities)：應(yīng)該對(duì)優(yōu)先度高的process有優(yōu)勢(shì)。平衡資源(balancingresources)：應(yīng)該盡量使系統(tǒng)的資源忙碌。這些評(píng)量標(biāo)準(zhǔn)彼此相關(guān)，要做到所有標(biāo)準(zhǔn)的最佳化是不可能的。例如：要提供好的回應(yīng)時(shí)間，可能使排程演算法頻繁的轉(zhuǎn)移process的執(zhí)行，造成系統(tǒng)額外的負(fù)荷並降低throughput。優(yōu)先等級(jí)(priorities)的使用排程程式優(yōu)先選擇比較高等級(jí)的process。問(wèn)題：低優(yōu)先等級(jí)的process，可能發(fā)生飢餓。解決方法：隨著時(shí)間或執(zhí)行情況，調(diào)整優(yōu)先等級(jí)。61SchedulingandProcessStateTransitionstimequantum(時(shí)間量)的長(zhǎng)度：quantum大小通常比一般的互動(dòng)時(shí)間稍長(zhǎng)。對(duì)短的process不錯(cuò)s=process所需的服務(wù)(service)時(shí)間，包括e。排程與process狀態(tài)轉(zhuǎn)移短程(short-term)：決定執(zhí)行哪個(gè)process。當(dāng)目前process完成或懸置(blocked)狀態(tài)，從readyqueue中，選擇R值最大的process。期限(deadline)：process給定的完成的截止時(shí)間。排程方法：最短process優(yōu)先(ShortestProcessNext)排程影響系統(tǒng)的效能，排程是一種管理佇列的方式，希望能降低佇列延遲(queuingdelay)。RoundRobin(RR)輪流(Round-Robin)，也稱為timeslicing(時(shí)間片段)對(duì)長(zhǎng)的process較不公平很長(zhǎng),當(dāng)process長(zhǎng)度變異性高時(shí)First-Come-First-Served(FCFS)或稱First-In-First-Out(FIFO)例如：max[w]表示First-Come-First-Served(FCFS)。排程方法：最高回應(yīng)率優(yōu)先(HighestResponseRatioNext)7Figure9.4PriorityQueuing7對(duì)短的process不錯(cuò)優(yōu)先等級(jí)(priorities)的使用First-Come-First-Served(FCFS)或稱First-In-First-Out(FIFO)如：回應(yīng)時(shí)間(Responsetime)、產(chǎn)量(throughput)、效率(efficiency)。2LevelsofScheduling迴轉(zhuǎn)時(shí)間與服務(wù)時(shí)間的比值：Tr/Ts。數(shù)值越高表示服務(wù)品質(zhì)越低。S1=第1次的估計(jì)，不是由計(jì)算得到。使用者導(dǎo)向，效能相關(guān)：往返時(shí)間(turnaroundtime)：接下工作到完成的時(shí)間，又稱queuingtime。最短process優(yōu)先(ShortestProcessNext)排程與process狀態(tài)轉(zhuǎn)移平衡資源(balancingresources)：應(yīng)該盡量使系統(tǒng)的資源忙碌。當(dāng)目前執(zhí)行的process將離開時(shí)，挑選在ready佇列中最久的process。例如：max[w]表示First-Come-First-Served(FCFS)。各種平均與實(shí)際觀測(cè)值的比較選擇排程策略(AlternativeSchedulingPolicies)三個(gè)重要的計(jì)量w=在系統(tǒng)內(nèi)等待(waiting)的時(shí)間。e=已經(jīng)執(zhí)行(executed)的時(shí)間。s=process所需的服務(wù)(service)時(shí)間，包括e。選擇函式：例如：max[w]表示First-Come-First-Served(FCFS)。(挑選等待最久的)決策模式：選擇函式執(zhí)行的時(shí)機(jī)非先佔(zhàn)式(Non-preemptive)先佔(zhàn)式(Preemptive)8排程方法：First-Come-First-Served(FCFS)First-Come-First-Served(FCFS)或稱First-In-First-Out(FIFO)當(dāng)目前執(zhí)行的process將離開時(shí)，挑選在ready佇列中最久的process。往返時(shí)間(turnaroundtime)：接下工作到完成的時(shí)間，又稱queuingtime。迴轉(zhuǎn)時(shí)間與服務(wù)時(shí)間的比值：Tr/Ts。最小值為1；數(shù)值越高表示服務(wù)品質(zhì)越低。ProcessABCDE到達(dá)時(shí)間02468服務(wù)時(shí)間(Ts)36452ProcessABCDE平均完成時(shí)間39131820往返時(shí)間(Tr)37912128.60Tr/Ts1.001.172.252.406.002.569排程方法：循環(huán)(Round-Robin)輪流(Round-Robin)，也稱為timeslicing(時(shí)間片段)利用計(jì)時(shí)器固定週期產(chǎn)生中斷，目前正在執(zhí)行的process便移至readyqueue。利用FCFS從readyqueue中擇一執(zhí)行。timequantum(時(shí)間量)的長(zhǎng)度：quantum大小通常比一般的互動(dòng)時(shí)間稍長(zhǎng)。ProcessABCDE到達(dá)時(shí)間02468服務(wù)時(shí)間(Ts)3645210TimeQuantum的選擇(a)TimequantumgreaterthantypicalinteractionFigure9.6EffectofSizeofPreemptionTimeQuantum(b)Timequantumlessthantypicalinteraction11排程方法：最短process優(yōu)先(ShortestProcessNext)最短process優(yōu)先(ShortestProcessNext)非先佔(zhàn)式(Nopreemption)的策略。選擇所需執(zhí)行時(shí)間最短的process，作為下一個(gè)執(zhí)行的process。ProcessABCDE到達(dá)時(shí)間02468服務(wù)時(shí)間(Ts)3645212最短process優(yōu)先(ShortestProcessNext)(續(xù))問(wèn)題：事先需知道或可以估算process所需的執(zhí)行時(shí)間。簡(jiǎn)單平均(simpleaveraging)：避免重複計(jì)算：指數(shù)平均(exponentialaveraging)：Ti=此process第i次執(zhí)行所花的時(shí)間。(對(duì)批次工作而言，是所有的時(shí)間，對(duì)互動(dòng)式工作為處理器bursttime)Si

=第i次的估計(jì)。S1

=第1次的估計(jì)，不是由計(jì)算得到。13指數(shù)平均的係數(shù)Figure9.8ExponentialSmoothingCoefficients14各種平均與實(shí)際觀測(cè)值的比較(a)IncreasingfunctionFigure9.9UseofExponentialAveraging15排程方法：最短剩餘時(shí)間(ShortestRemainingTime)最短剩餘時(shí)間(ShortestRemainingTime)：選擇剩下執(zhí)行時(shí)間最少的process執(zhí)行。先佔(zhàn)式(preemptive)版本的SPN。當(dāng)一個(gè)新的process加入readyqueue，其可能含有比正在執(zhí)行的process短的剩餘時(shí)間，如此則搶先執(zhí)行。與SPN相同，必須先估計(jì)process的執(zhí)行時(shí)間。ProcessABCDE到達(dá)時(shí)間02468服務(wù)時(shí)間(Ts)3645216排程方法：最高回應(yīng)率優(yōu)先(HighestResponseRatioNext)最高回應(yīng)率優(yōu)先(HighestResponseRatioNext)回應(yīng)率(ResponseRatio)：R=(w+s)/s。w=花費(fèi)在等待處理器的時(shí)間。s=預(yù)計(jì)的處理(服務(wù))時(shí)間。R的最小值為1。(process剛進(jìn)入到系統(tǒng)時(shí))當(dāng)目前process完成或懸置(blocked)狀態(tài)，從readyqueue中，選擇R值最大的process。ProcessABCDE到達(dá)時(shí)間02468服務(wù)時(shí)間(Ts)3645217排程方法：回饋(Feedback)若未指出process執(zhí)行時(shí)間的長(zhǎng)短，則SPN、SRT、HRRN都不能使用?；仞仯夯断葋?zhàn)式(preemptive)的概念，動(dòng)態(tài)的優(yōu)先等級(jí)(priority)機(jī)制。Figure9.10FeedbackScheduling18排程方法：比較、整理排程方法選擇方式?jīng)Q策模式總產(chǎn)能回應(yīng)時(shí)間額外花費(fèi)影響飢餓FirstComeFirstServed(FCFS)Max[w]非先佔(zhàn)式未強(qiáng)調(diào)很長(zhǎng),當(dāng)process長(zhǎng)度變異性高時(shí)最小對(duì)短process與I/Obound較不公平NoRoundRobin(RR)constant(沒(méi)有偏好)先佔(zhàn)式(時(shí)間區(qū)段q到了)q很小時(shí)，可能很低對(duì)短的process不錯(cuò)最小公平NoShortestProcessNext(SP