調(diào)度的隊列模型-中國科學(xué)技術(shù)大學(xué)

1、第四講 CPU調(diào)度,中國科學(xué)技術(shù)大學(xué)計算機(jī)系 陳香蘭xlanchen@ustc.edu.cnFall 2013,內(nèi)容提要,調(diào)度的類型調(diào)度的隊列模型調(diào)度的準(zhǔn)則調(diào)度的算法,內(nèi)容提要,調(diào)度的類型調(diào)度的隊列模型調(diào)度的準(zhǔn)則調(diào)度的算法,調(diào)度的類型,按調(diào)度的層次：長期（長程、作業(yè)、高級）調(diào)度；中期（中級、中程）調(diào)度；短期（短程、進(jìn)程、低級）調(diào)度按OS的類型：批處理調(diào)度分時調(diào)度實時調(diào)度多處理機(jī)調(diào)度等等,作業(yè)調(diào)度,在批

2、處理系統(tǒng)中，一般需要進(jìn)行作業(yè)調(diào)度；分時系統(tǒng)和實時系統(tǒng)大多不需要作業(yè)調(diào)度作業(yè)調(diào)度要考慮1）接納多少個作業(yè)??多道程序度2）接納哪些作業(yè)??調(diào)度算法,中期調(diào)度,與掛起狀態(tài)相關(guān)目的：提高內(nèi)存利用率和系統(tǒng)吞吐量對換,進(jìn)程調(diào)度,在分時系統(tǒng)中，進(jìn)程調(diào)度的運行頻率很高Linux中，常規(guī)經(jīng)驗值，時間片大小50ms左右進(jìn)程調(diào)度要考慮1）什么時候 發(fā)生調(diào)度的時機(jī)2）哪個進(jìn)程 調(diào)度原則和調(diào)度算法3）如何分派 進(jìn)程上下文切換,調(diào)

3、度的方式：搶占式／非搶占式,可剝奪式（可搶占式Preemptive）： 當(dāng)有比正在運行的進(jìn)程優(yōu)先級更高的進(jìn)程就緒時，系統(tǒng)可強(qiáng)行剝奪正在運行進(jìn)程的CPU，提供給具有更高優(yōu)先級的進(jìn)程使用不可剝奪式（不可搶占式 Non-preemptive ）： 某一進(jìn)程被調(diào)度運行后，除非由于它自身的原因不能運行，否則一直運行下去,Scheduling time 調(diào)度的時機(jī),When a processSwitches from run

4、ning to waiting stateSwitches from running to ready stateSwitches from waiting to readyTerminatesSchedulingNonpreemptive: for 1 & 4Till 1 or 4Win 3.x, old versions of MacOS, …Preemptive: for 2 & 3根據(jù)時間片搶

5、占、根據(jù)優(yōu)先關(guān)系搶占,,與進(jìn)程調(diào)度相關(guān)的進(jìn)程運行規(guī)律分析,Process execution = n (CPU execution + I/O wait)Objective of multiprogrammingMaximum CPU utilization Scheduling is a fundamental OS function for almost all resources,Alternating Seq

6、uence of CPU And I/O Bursts,A property of process：CPU-I/O burst cycleProcess Starts as a CPU burstEnds as a CPU burstCPU burst distributionCPU-bound VS. I/O-bound,Histogram of CPU-burst Times,,內(nèi)容提要,調(diào)度的類型調(diào)度的隊列模型調(diào)

7、度的準(zhǔn)則調(diào)度的算法,調(diào)度隊列模型,按照系統(tǒng)中調(diào)度層次的數(shù)目，有3種模型僅有進(jìn)程調(diào)度的具有高級和低級調(diào)度的同時具有三種調(diào)度的,僅具有進(jìn)程調(diào)度的調(diào)度隊列模型,具有高、低兩級調(diào)度的調(diào)度隊列模型,具有三級調(diào)度的調(diào)度隊列模型,內(nèi)容提要,調(diào)度的類型調(diào)度的隊列模型調(diào)度的準(zhǔn)則調(diào)度的算法,選擇調(diào)度方式和算法的若干準(zhǔn)則,面向用戶的準(zhǔn)則周轉(zhuǎn)時間短響應(yīng)時間快截止時間的保證優(yōu)先權(quán)準(zhǔn)則面向系統(tǒng)的準(zhǔn)則系統(tǒng)吞吐率高處理機(jī)利用率好各類資源的

8、平衡利用,面向用戶的準(zhǔn)則：1、周轉(zhuǎn)時間短,定義：作業(yè)周轉(zhuǎn)時間(Turnaround time)是指從作業(yè)提交給系統(tǒng)開始，到作業(yè)完成為止的這段時間間隔。包括：1）作業(yè)在外存后備隊列上等待作業(yè)調(diào)度的時間2）進(jìn)程在就緒隊列上等待進(jìn)程調(diào)度的時間(waiting time)3）進(jìn)程在CPU上執(zhí)行的時間4）等待I/O操作完成的時間 其中，第2、3、4項在一個作業(yè)的處理過程中，可能發(fā)生多次用戶和系統(tǒng)管理員對周轉(zhuǎn)時間有不同的需求,,定義

9、：平均周轉(zhuǎn)時間定義：帶權(quán)周轉(zhuǎn)時間：作業(yè)周轉(zhuǎn)時間T與系統(tǒng)為它提供的實際服務(wù)時間Ts之比，即W=T/Ts定義：平均帶權(quán)周轉(zhuǎn)時間：通常將周轉(zhuǎn)時間作為評價批處理系統(tǒng)的性能、選擇作業(yè)調(diào)度方式和算法的準(zhǔn)則,面向用戶的準(zhǔn)則：2、響應(yīng)時間快,定義：響應(yīng)時間(Response time)是從用戶通過鍵盤提交一個請求開始，直至系統(tǒng)首次產(chǎn)生響應(yīng)為止的的時間，或者說直到在屏幕上顯示出結(jié)果為止的一段時間間隔。包括：從鍵盤輸入的請求信息傳送到處理機(jī)的

10、時間處理機(jī)對請求信息進(jìn)行處理的時間將所形成的響應(yīng)回送到終端顯示器的時間響應(yīng)時間常用于評價分時操作系統(tǒng)的性能，是選擇分時系統(tǒng)中進(jìn)程調(diào)度算法的重要準(zhǔn)則之一,面向用戶的準(zhǔn)則：3、截止時間的保證,定義：截止時間(Deadline)是指某任務(wù)必須開始執(zhí)行的最遲時間，或者必須完成的最遲時間。截止時間是用來評價實時系統(tǒng)性能的重要指標(biāo)，因而是選擇實時調(diào)度算法的重要準(zhǔn)則實時系統(tǒng)軟實時系統(tǒng)(soft real-time) vs 硬實時系統(tǒng)

11、(hard real-time)非實時系統(tǒng),面向用戶的準(zhǔn)則：4、優(yōu)先權(quán)準(zhǔn)則,引入優(yōu)先權(quán)使用優(yōu)先數(shù)表示優(yōu)先權(quán)優(yōu)先權(quán)高者優(yōu)先執(zhí)行必要時，引入搶占,面向系統(tǒng)的準(zhǔn)則：1、系統(tǒng)吞吐率高,定義：吞吐率(Throughput)是指系統(tǒng)在單位時間內(nèi)完成的作業(yè)數(shù)是用于評價批處理系統(tǒng)性能的重要指標(biāo)，也是用于選擇批處理作業(yè)調(diào)度的重要準(zhǔn)則吞吐率與作業(yè)的平均長度有關(guān)大型作業(yè)中、小型作業(yè)吞吐率與作業(yè)的調(diào)度算法也有關(guān),面向系統(tǒng)的準(zhǔn)則：2、處理