計算機知識點第六講cpu的調(diào)度

OperatingSystemConcepts第六講CPU的調(diào)度BasicConcepts基本概念SchedulingCriteria調(diào)度程序的評價標準SchedulingAlgorithms調(diào)度算法Multiple-ProcessorScheduling多處理機的調(diào)度Real-TimeScheduling實時調(diào)度AlgorithmEvaluation算法評價OperatingSystemConceptsBasicConcepts

基本概念MaximumCPUutilizationobtainedwithmultiprogramming進程調(diào)度的目的是要使采用多道程序設計的技術后將CPU的利用率最大化。CPU–I/OBurstCycle–ProcessexecutionconsistsofacycleofCPUexecutionandI/Owait.CPU和I/O操作段的周期-進程的執(zhí)行由CPU的執(zhí)行和等待I/O操作的周期組成的。CPUburstdistribution進程的調(diào)度就是如何為CPU的運行段分配資源。OperatingSystemConceptsAlternatingSequenceofCPUAndI/OBurstsOperatingSystemConceptsHistogramofCPU-burstTimesOperatingSystemConceptsCPUScheduler

CPU調(diào)度程序Selectsfromamongtheprocessesinmemorythatarereadytoexecute,andallocatestheCPUtooneofthem.在就緒的進程中選擇一個進程執(zhí)行，并分配CPUCPUschedulingdecisionsmaytakeplacewhenaprocess:需要做CPU調(diào)度決策的時機：1. Switchesfromrunningtowaitingstate.當進程從運行狀態(tài)轉(zhuǎn)入等待狀態(tài)時；2. Switchesfromrunningtoreadystate.當進程從運行狀態(tài)轉(zhuǎn)入就緒狀態(tài)時；3. Switchesfromwaitingtoready.當進程從等待狀態(tài)轉(zhuǎn)入就緒狀態(tài)時；4. Terminates.進程終止時Schedulingunder1and4isnonpreemptive.情形1和4是非搶奪的調(diào)度，其它情形是搶奪的調(diào)度Allotherschedulingispreemptive.OperatingSystemConceptsDispatcher

分派DispatchermodulegivescontroloftheCPUtotheprocessselectedbytheshort-termscheduler;thisinvolves:分派模塊將CPU的控制權交給CPU調(diào)度程序選擇的進程，分派操作的內(nèi)容：switchingcontext上下文的切換switchingtousermode切換到用戶模式jumpingtotheproperlocationintheuserprogramtorestartthatprogram跳轉(zhuǎn)到用戶程序的相應的位置，并啟動用戶程序的執(zhí)行Dispatchlatency–timeittakesforthedispatchertostoponeprocessandstartanotherrunning.分派時間-分派程序停止一個進程的執(zhí)行到啟動另一個進程的時間。OperatingSystemConceptsSchedulingCriteria

進程調(diào)度的評價標準CPUutilization–keeptheCPUasbusyaspossible(CPU利用率-盡可能使CPU處于忙的狀態(tài))Throughput–#ofprocessesthatcompletetheirexecutionpertimeunit(吞吐率-單位時間完成的進程數(shù))Turnaroundtime–amountoftimetoexecuteaparticularprocess(完成時間-完成一個特定的進程執(zhí)行的時間)Waitingtime–amountoftimeaprocesshasbeenwaitinginthereadyqueue(等待時間-進程在就緒隊列中等待的時間)Responsetime–amountoftimeittakesfromwhenarequestwassubmitteduntilthefirstresponseisproduced,notoutput(fortime-sharingenvironment)響應時間-從一個操作請求提交后到第一個反應產(chǎn)生的時間（通常用來定義分時系統(tǒng)的特性）OperatingSystemConceptsOptimizationCriteria

優(yōu)化調(diào)度程序的標準MaxCPUutilization使CPU利用率最大化Maxthroughput使吞吐率最大化Minturnaroundtime使完成時間最小Minwaitingtime使等待時間最少Minresponsetime使響應時間最小OperatingSystemConceptsFirst-Come,First-Served(FCFS)Scheduling

先來先服務(FCFS)調(diào)度程序

Process

BurstTime(時間段)

P1 24

P2 3

P3 3

假設進程到達就緒的順序是:P1,P2,P3

調(diào)度的甘特圖(GanttChart)是:

等待時間：P1=0;P2=24;P3=27平均等待時間:(0+24+27)/3=17P1P2P32427300OperatingSystemConceptsFCFSScheduling(Cont.)

先來先服務調(diào)度（序）假設進程到達就緒的順序是：

P2,P3,P1.調(diào)度的甘特圖是:

等待時間P1=6;

P2=0;P3=3平均等待時間:(6+0+3)/3=3這里的性能比前一種情形的性能就要好得多ConvoyeffectshortprocessbehindlongprocessP1P3P263300OperatingSystemConceptsShortest-Job-First(SJR)Scheduling

短作業(yè)優(yōu)先(SRJ)AssociatewitheachprocessthelengthofitsnextCPUburst.Usetheselengthstoscheduletheprocesswiththeshortesttime.將進程下一個時間段參數(shù)記下來，用這些時間長度的參數(shù)來調(diào)度進程，以使進程在最短的時間內(nèi)調(diào)度運行；Twoschemes:兩種方式nonpreemptive–onceCPUgiventotheprocessitcannotbepreempteduntilcompletesitsCPUburst.非搶奪的-一旦進程分配了CPU開始運行，就在它運行結束之前不能搶奪。preemptive–ifanewprocessarriveswithCPUburstlengthlessthanremainingtimeofcurrentexecutingprocess,preempt.Thisschemeisknowasthe搶奪的Shortest-Remaining-Time-First(SRTF).最短剩余時間優(yōu)先SJFisoptimal–givesminimumaveragewaitingtimeforagivensetofprocesses.短作業(yè)優(yōu)先使對一組進程的平均等待時間最小。OperatingSystemConcepts

Process ArrivalTime

BurstTime

P1 0.0 7

P2 2.0 4

P3 4.0 1

P4 5.0 4SJF(non-preemptive)Averagewaitingtime=(0+6+3+7)/4=4ExampleofNon-PreemptiveSJF

非搶奪的短作業(yè)優(yōu)先法舉例P1P3P273160P4812OperatingSystemConceptsExampleofPreemptiveSJF

Process ArrivalTime

BurstTime

P1 0.0 7

P2 2.0 4

P3 4.0 1

P4 5.0 4SJF(preemptive)Averagewaitingtime=(9+1+0+2)/4=3P1P3P242110P457P2P116OperatingSystemConceptsDeterminingLengthofNextCPUBurst

決定下一個CPU時間段的長度Canonlyestimatethelength.只能夠估計長度CanbedonebyusingthelengthofpreviousCPUbursts,usingexponentialaveraging.可以通過前一個CPU時間段的參數(shù)來估計，但必須使用指數(shù)平均值。OperatingSystemConceptsPredictionoftheLengthoftheNextCPUBurstOperatingSystemConceptsExamplesofExponentialAveraging

指數(shù)平均計算的舉例=0n+1=nRecenthistorydoesnotcount.=1n+1=tnOnlytheactuallastCPUburstcounts.Ifweexpandtheformula,weget:n+1=tn+(1-)tn-1+…

+(1-)jtn-1+…

+(1-)n=1tn0Sincebothand(1-)arelessthanorequalto1,eachsuccessivetermhaslessweightthanitspredecessor.OperatingSystemConceptsPriorityScheduling

基于優(yōu)先級的調(diào)度Aprioritynumber(integer)isassociatedwitheachprocess每一個進程都有一個優(yōu)先級的參數(shù)TheCPUisallocatedtotheprocesswiththehighestpriority將CPU分配給優(yōu)先級最高的進程(smallestintegerhighestpriority).優(yōu)先級數(shù)字低，優(yōu)先級高Preemptive搶奪的Nonpreemptive非搶奪的SJFisapriorityschedulingwherepriorityisthepredictednextCPUbursttime.SJF也可以看成是一種基于優(yōu)先級的調(diào)度算法，其中優(yōu)先級就是預測的下一個CPU時間段。ProblemStarvation–lowpriorityprocessesmayneverexecute.可能存在的問題：低優(yōu)先級的進程可能永遠不會執(zhí)行，這種現(xiàn)象稱為餓死。SolutionAging–astimeprogressesincreasethepriorityoftheprocess.解決辦法：隨著時間增加使優(yōu)先級也增加。OperatingSystemConceptsRoundRobin(RR)時間輪轉(zhuǎn)法EachprocessgetsasmallunitofCPUtime(timequantum),usually10-100milliseconds.Afterthistimehaselapsed,theprocessispreemptedandaddedtotheendofthereadyqueue.每一個進程都分配一個小的時間片，時間片用完后，其占用的資源被剝奪，并且將該進程插入到就緒隊列尾部。Iftherearenprocessesinthereadyqueueandthetimequantumisq,theneachprocessgets1/noftheCPUtimeinchunksofatmostqtimeunitsatonce.Noprocesswaitsmorethan(n-1)qtimeunits.如果就緒隊列中有n個進程，時間片是q,則每個進程獲得1/n的CPU的時間，每次最多獲得CPU時間q。所以進程的最大的等待時間是(n-1)qPerformance性能qlargeFIFOqsmallqmustbelargewithrespecttocontextswitch,otherwiseoverheadistoohigh.Q值必須至少大到與上下文切換的時間相當，否則開銷太大。OperatingSystemConceptsExampleofRRwithTimeQuantum=20

Process

BurstTime P1 53

P2 17

P3 68

P4 24TheGanttchartis:

Typically,higheraverageturnaroundthanSJF,butbetterresponse.P1P2P3P4P1P3P4P1P3P302037577797117121134154162OperatingSystemConceptsTimeQuantumandContextSwitchTimeOperatingSystemConceptsTurnaroundTimeVariesWithTheTimeQuantumOperatingSystemConceptsMultilevelQueue多級隊列Readyqueueispartitionedintoseparatequeues:

就緒隊列分成以下不同的隊列foreground(interactive)前臺交互式進程隊列background(batch)后臺批處理隊列Eachqueuehasitsownschedulingalgorithm,每個隊列有不同的調(diào)度算法foreground–RR前臺進程隊列使用時間輪轉(zhuǎn)算法background–FCFS后臺隊列使用先來先服務算法Schedulingmustbedonebetweenthequeues.調(diào)度程序要處理不同的隊列Fixedpriorityscheduling;(i.e.,serveallfromforegroundthenfrombackground).Possibilityofstarvation.固定優(yōu)先級的調(diào)度Timeslice–eachqueuegetsacertainamountofCPUtimewhichitcanscheduleamongstitsprocesses;i.e.,80%toforegroundinRR時間片20%tobackgroundinFCFSOperatingSystemConceptsMultilevelQueueSchedulingOperatingSystemConceptsMultilevelFeedbackQueue

多級反饋隊列Aprocesscanmovebetweenthevariousqueues;agingcanbeimplementedthisway.進程可以在不同的隊列之間移動，優(yōu)先級按時間提高就可以用這樣的方法來實現(xiàn)Multilevel-feedback-queueschedulerdefinedbythefollowingparameters:多級反饋隊列調(diào)度程序定義了下列參數(shù)numberofqueues隊列的數(shù)量schedulingalgorithmsforeachqueue每個隊列的調(diào)度算法methodusedtodeterminewhentoupgradeaprocess決定提高進程優(yōu)先級的方法methodusedtodeterminewhentodemoteaprocess決定降低進程優(yōu)先級的方法methodusedtodeterminewhichqueueaprocesswillenterwhenthatprocessneedsservice當一個進程需要執(zhí)行時，決定該進程進入哪一個隊列。OperatingSystemConceptsExampleofMultilevelFeedbackQueue

多級反饋隊列的舉例Threequeues:三個隊列Q0–timequantum8milliseconds8毫秒時間片Q1–timequantum16milliseconds16毫秒時間片Q2–FCFS先來先服務隊列Scheduling調(diào)度AnewjobentersqueueQ0

whichisserved

FCFS.WhenitgainsCPU,jobreceives8milliseconds.Ifitdoesnotfinishin8milliseconds,jobismovedtoqueueQ1.新作業(yè)進入隊列Q0進程獲得8毫秒CPU時間，如果8毫秒內(nèi)沒有完成，就將該作業(yè)放入隊列Q1AtQ1jobisagainservedFCFSandreceives16additionalmilliseconds.Ifitstilldoesnotcomplete,itispreemptedandmovedtoqueueQ2.Q1隊列的進程獲得16毫秒CPU時間，如果16毫秒內(nèi)沒有完成，就將該作業(yè)放入隊列Q2OperatingSystemConceptsMultilevelFeedbackQueuesOperatingSystemConceptsMultiple-ProcessorScheduling

多處理機的調(diào)度CPUschedulingmorecomplexwhenmultipleCPUsareavailable.當有多個CPU時，處理機調(diào)度的方法更復雜。Homogeneousprocessorswithinamultiprocessor.多處理