资源描述
按一下以編輯母片標題樣式,按一下以編輯母片本文樣式,第二階層,*,*,*,第九章：單一處理器排程(,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,排程與,process,狀態轉移,Figure 9.1 Scheduling and Process State Transitions,2,3,Figure 9.2 Levels of Scheduling,Long term,3,Figure 9.3 Queuing Diagram for Scheduling,4,4,9.2 排程演算法(,Scheduling Algorithms),排程的原則，共分成四類：,使用者導向(,user-oriented)vs.,系統導向(,system-oriented),效能相關(,performance-related)vs.,其他,使用者導向，效能相關：,回應時間(,response time)：,由工作發出要求到收到回應的時間。,往返時間(,turnaround time)：,由工作發出要求到其結束的時間,。,期限(,deadline)：process,給定的完成的截止時間。,使用者導向，其他,可預測度(,predictability)：,不論系統負載如何，執行時間與花費應差不多。,系統導向，效能相關,產出率(,throughput)：,單位時間完成的工作量。,處理器使用率(,processor utilization)：,處理器忙碌的時間比例,。,5,排程的原則(續),系統導向，其他,公平性(,fairness)：,處理器應該一視同仁，沒有,process,會發生飢餓。,確保優先度(,enforcing priorities)：,應該對優先度高的,process,有優勢。,平衡資源(,balancing resources)：,應該盡量使系統的資源忙碌,。,這些評量標準彼此相關，要做到所有標準的最佳化是不可能的,。,例如：要提供好的回應時間,，,可能使排程演算法頻繁的轉移,process,的執行，造成系統額外的負荷並降低,throughput。,優先等級(,priorities),的使用,排程程式優先選擇比較高等級的,process。,問題：低優先等級的,process，,可能發生飢餓。,解決方法：隨著時間或執行情況，調整優先等級。,6,7,Figure 9.4 Priority Queuing,7,選擇排程策略(,Alternative Scheduling Policies),三個重要的計量,w,=,在系統內等待(,waiting),的時間。,e,=,已經執行(,executed),的時間。,s,=process,所需的服務(,service),時間，包括,e,。,選擇函式：,例如,：,max,w,表示,First-Come-First-Served(FCFS)。(,挑選等待最久的),決策模式：選擇函式執行的時機,非先佔式(,Non-preemptive),先佔式(,Preemptive),8,排程方法：,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,排程方法：循環(,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,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,排程方法：最短,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 Process Next)(,續),問題：事先需知道或可以估算,process,所需的執行時間。,簡單平均(,simple averaging)：,避免重複計算：,指數平均(,exponential averaging)：,T,i,=,此,process,第,i,次執行所花的時間。(對批次工作而言，是所有的時間，對互動式工作為處理器,burst time),S,i,=,第,i,次的估計。,S,1,=,第,1次的估計，不是由計算得到。,13,指數平均的係數,Figure 9.8 Exponential Smoothing Coefficients,14,各種平均與實際觀測值的比較,(a)Increasing function,Figure 9.9 Use of Exponential Averaging,15,排程方法：最短剩餘時間(,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,排程方法：最高回應率優先(,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,排程方法：回饋(,Feedback),若未指出,process,執行時間的長短，則,SPN、SRT、HRRN,都不能使用。,回饋,：,基於先佔式(,preemptive),的概念，動態的優先等級(,priority),機制。,Figure 9.10 Feedback Scheduling,18,排程方法：比較、整理,排程方法,選擇方式,決策模式,總產能,回應時間,額外花費,影響,飢餓,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,
展开阅读全文