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