1、第九章：單一處理器排程第九章：單一處理器排程(Scheduling)9.1 排程的種類排程的種類z 處理器排程排程的種類y長程(long-term)：決定是否將process加入系統。y中程(medium-term)：決定是否將process的部分或全部載入主記憶體中。y短程(short-term)：決定執行哪個process。z 輸入/輸出(I/O)排程：決定等待I/O資源的process中，何者使用此I/O資源。(本章不討論)z 處理器排程的目的：安排process由處理器執行，並考慮到系統的功能需求，y如：回應時間(Response time)、產量(throughput)、效率(eff
2、iciency)。z 排程影響系統的效能，排程是一種管理佇列的方式，希望能降低佇列延遲(queuing delay)。1排程與排程與process 狀態轉移狀態轉移Figure 9.1 Scheduling and Process State Transitions23Figure 9.2 Levels of SchedulingLong term3Figure 9.3 Queuing Diagram for Scheduling4 49.2 排程演算法排程演算法(Scheduling Algorithms)z 排程的原則，共分成四類：y使用者導向(user-oriented)vs.系統導向(
3、system-oriented)y效能相關(performance-related)vs.其他z 使用者導向，效能相關：y回應時間(response time)：由工作發出要求到收到回應的時間。y往返時間(turnaround time)：由工作發出要求到其結束的時間。y期限(deadline)：process給定的完成的截止時間。z 使用者導向，其他y可預測度(predictability)：不論系統負載如何，執行時間與花費應差不多。z 系統導向，效能相關y產出率(throughput)：單位時間完成的工作量。y處理器使用率(processor utilization)：處理器忙碌的時間比例
4、。5排程的原則排程的原則(續續)z 系統導向，其他y公平性(fairness)：處理器應該一視同仁，沒有process會發生飢餓。y確保優先度(enforcing priorities)：應該對優先度高的process有優勢。y平衡資源(balancing resources)：應該盡量使系統的資源忙碌。z 這些評量標準彼此相關，要做到所有標準的最佳化是不可能的。y例如：要提供好的回應時間，可能使排程演算法頻繁的轉移process的執行，造成系統額外的負荷並降低throughput。z 優先等級(priorities)的使用y排程程式優先選擇比較高等級的process。y問題：低優先等級的pr
5、ocess，可能發生飢餓。y解決方法：隨著時間或執行情況，調整優先等級。67Figure 9.4 Priority Queuing7選擇排程策略選擇排程策略(Alternative Scheduling Policies)z 三個重要的計量yw=在系統內等待(waiting)的時間。ye=已經執行(executed)的時間。ys=process所需的服務(service)時間，包括e。z 選擇函式：y例如：maxw 表示 First-Come-First-Served(FCFS)。(挑選等待最久的)z 決策模式：選擇函式執行的時機y非先佔式(Non-preemptive)y先佔式(Preemp
6、tive)8排程方法：排程方法：First-Come-First-Served(FCFS)z First-Come-First-Served(FCFS)或稱First-In-First-Out(FIFO)y當目前執行的process將離開時，挑選在ready佇列中最久的process。y往返時間(turnaround time)：接下工作到完成的時間，又稱queuing time。y迴轉時間與服務時間的比值：Tr/Ts。最小值為1；數值越高表示服務品質越低。ProcessA B C D E到達時間02 4 6 8服務時間(Ts)36 4 5 2ProcessABCDE平均完成時間3913182
7、0往返時間(Tr)37912128.60Tr/Ts1.001.172.252.406.002.569排程方法：循環排程方法：循環(Round-Robin)z 輪流(Round-Robin)，也稱為time slicing(時間片段)y利用計時器固定週期產生中斷，目前正在執行的process便移至ready queue。y利用FCFS從ready queue中擇一執行。ytime quantum(時間量)的長度：quantum大小通常比一般的互動時間稍長。ProcessA B C D E到達時間02 4 6 8服務時間(Ts)36 4 5 210Time Quantum 的選擇的選擇(a)Tim
8、e quantum greater than typical interactionFigure 9.6 Effect of Size of Preemption Time Quantum(b)Time quantum less than typical interaction11排程方法：最短排程方法：最短process優先優先(Shortest Process Next)z 最短process優先(Shortest Process Next)y非先佔式(No preemption)的策略。y選擇所需執行時間最短的process，作為下一個執行的process。ProcessA B C D
9、E到達時間02 4 6 8服務時間(Ts)36 4 5 212最短最短process優先優先(Shortest Process Next)(續續)z 問題：事先需知道或可以估算process所需的執行時間。y簡單平均(simple averaging)：y避免重複計算：y指數平均(exponential averaging)：yTi=此process第i次執行所花的時間。(對批次工作而言，是所有的時間，對互動式工作為處理器burst time)ySi=第i次的估計。yS1=第1次的估計，不是由計算得到。iinTnS11nnnSTS11nnnSnnTnS11113指數平均的係數指數平均的係數Fi
10、gure 9.8 Exponential Smoothing Coefficients14各種平均與實際觀測值的比較各種平均與實際觀測值的比較(a)Increasing functionFigure 9.9 Use of Exponential Averaging15排程方法：最短剩餘時間排程方法：最短剩餘時間(Shortest Remaining Time)z 最短剩餘時間(Shortest Remaining Time)：選擇剩下執行時間最少的process執行。y先佔式(preemptive)版本的SPN。y當一個新的process加入ready queue，其可能含有比正在執行的pro
11、cess短的剩餘時間，如此則搶先執行。y與SPN相同，必須先估計process的執行時間。ProcessA B C D E到達時間02 4 6 8服務時間(Ts)36 4 5 216排程方法：最高回應率優先排程方法：最高回應率優先(Highest Response Ratio Next)z 最高回應率優先(Highest Response Ratio Next)y回應率(Response Ratio)：R=(w+s)/s。yw=花費在等待處理器的時間。ys=預計的處理(服務)時間。yR的最小值為1。(process剛進入到系統時)y當目前process完成或懸置(blocked)狀態，從rea
12、dy queue中，選擇R值最大的process。ProcessA B C D E到達時間02 4 6 8服務時間(Ts)36 4 5 217排程方法：回饋排程方法：回饋(Feedback)z 若未指出process執行時間的長短，則SPN、SRT、HRRN都不能使用。z 回饋：基於先佔式(preemptive)的概念，動態的優先等級(priority)機制。Figure 9.10 Feedback Scheduling18排程方法：比較、整理排程方法：比較、整理排程方法選擇方式決策模式總產能回應時間額外花費影響飢餓First Come First Served(FCFS)Maxw非先佔式未強
13、調很長,當process長度變異性高時最小對短process與I/O bound較不公平NoRound Robin(RR)constant(沒有偏好)先佔式(時間區段q到了)q很小時，可能很低對短的process不錯最小公平NoShortest Process Next(SPN)mins非先佔式高對短的process不錯可能很高對長的process較不公平可能Shortest Remaining Time(SRT)mins-e先佔式(在抵達時)高不錯可能很高對長的process較不公平可能Highest Response Ratio Next (HRRN)max(w+s)/s非先佔式高不錯可能很高公平NoFeedback動態的優先等級先佔式(時間區段q到了)未強調未強調可能很高對I/O bound較佳可能19
