操作系统原理英文版课件：Chapter 5 CPU Scheduling

Chapter5CPUSchedulingOperatingSystemConceptsChapter5:CPUSchedulingBasicConceptsSchedulingCriteriaSchedulingAlgorithmsMultiple-ProcessorSchedulingThreadSchedulingAlgorithmEvaluationOperatingSystemConceptsBasicConceptsMaximumCPUutilizationobtainedwithmultiprogrammingCPU–I/OBurstCycle–ProcessexecutionconsistsofacycleofCPUexecutionandI/Owait.OperatingSystemConceptsAlternatingSequenceofCPUAndI/OBurstsOperatingSystemConceptsOperatingSystemConceptsCPU-I/OBurstCycleProcessexecutionrepeatstheCPUburstandI/Oburstcycle.WhenaprocessbeginsanI/Oburst,anotherprocesscanusetheCPUforaCPUburst.OperatingSystemConceptsCPU-boundandI/O-boundAprocessisCPU-boundifitgeneratesI/Orequestsinfrequently,usingmoreofitstimedoingcomputation.AprocessisI/O-boundifitspendsmoreofitstimetodoI/Othanitspendsdoingcomputation.ACPU-boundprocessmighthaveafewverylongCPUbursts.AnI/O-boundprocesstypicallyhasmanyshortCPUburstsOperatingSystemConceptsOperatingSystemConceptsCPUSchedulerWhentheCPUisidle,theOSmustselectanotherprocesstorun.Thisselectionprocessiscarriedoutbytheshort-termscheduler

(orCPUscheduler).TheCPUschedulerselectsaprocessfromthereadyqueue,andallocatestheCPUtoit.ThereadyqueuedoesnothavetobeaFIFOone.Therearemanywaystoorganizethereadyqueue.OperatingSystemConceptsCircumstancesthatscheduling

maytakeplace1.Aprocessswitchesfromtherunningstatetothewaitstate(e.g.,doingforI/O)2.Aprocessswitchesfromtherunningstatetothereadystate(e.g.,aninterruptoccurs)3.Aprocessswitchesfromthewaitstatetothereadystate(e.g.,I/Ocompletion)4.AprocessterminatesOperatingSystemConceptsOperatingSystemConceptsPreemptivevs.Non-preemptiveNon-preemptivescheduling:schedulingoccurswhenaprocessvoluntarilyentersthewaitstate(case1)orterminates(case4).Simple,butveryinefficientPreemptivescheduling:schedulingoccursinallpossiblecases.OperatingSystemConceptsDispatcherDispatchermodulegivescontroloftheCPUtotheprocessselectedbytheshort-termscheduler;thisinvolves:switchingcontextswitchingtousermodejumpingtotheproperlocationintheuserprogramtorestartthatprogramDispatchlatency–timeittakesforthedispatchertostoponeprocessandstartanotherrunning.OperatingSystemConceptsChapter6:CPUSchedulingBasicConceptsSchedulingCriteria

SchedulingAlgorithmsMultiple-ProcessorSchedulingReal-TimeSchedulingAlgorithmEvaluationOperatingSystemConceptsSchedulingCriteriaTherearemanycriteriaforcomparingdifferentschedulingalgorithms.Herearefivecommonones:CPUutilizationThroughputTurnaroundtimeWaitingtimeResponsetimeOperatingSystemConceptsCPUUtilizationWewanttokeeptheCPUasbusyaspossible.CPUutilizationrangesfrom0to100percent.Normally40%islightlyloadedand90%orhigherisheavilyloaded.YoucanbringupaCPUusagemetertoseeCPUutilizationonyoursystem.OperatingSystemConceptsThroughputThenumberofprocessescompletedpertimeunitiscalledthroughput.Higherthroughputmeansmorejobsgetdone.However,forlongprocesses,thisratemaybeonejobperhour,and,forshortjobs,thisratemaybe10perminute.OperatingSystemConceptsTurnaroundTimeThetimeperiodbetweenjobsubmissiontocompletionistheturnaroundtime.Fromauser’spointofview,turnaroundtimeismoreimportantthanCPUutilizationandthroughput.Turnaroundtimeisthesumofwaitingtimebeforeenteringthesystemwaitingtimeinthereadyqueuewaitingtimeinallotherevents(e.g.,I/O)timetheprocessactuallyrunningontheCPUOperatingSystemConceptsWaitingTimeWaitingtimeisthesumoftheperiodsthataprocessspendswaitinginthereadyqueue.Whyonlyreadyqueue?CPUschedulingalgorithmsdonotaffecttheamountoftimeduringwhichaprocessiswaitingforI/Oandotherevents.However,CPUschedulingalgorithmsdoaffectthetimethataprocessstaysinthereadyqueueOperatingSystemConceptsResponseTimeThetimefromthesubmissionofarequest(inaninteractivesystem)tothefirstresponseiscalledresponsetime.Itdoesnotincludethetimethatittakestooutputtheresponse.Forexample,infrontofyourworkstation,youperhapscaremoreaboutthetimebetweenhittingtheReturnkeyandgettingyourfirstoutputthanthetimefromhittingtheReturnkeytothecompletionofyourprogram(e.g.,turnaroundtime).OperatingSystemConceptsOptimizationCriteriaMaxCPUutilizationMaxthroughputMinturnaroundtimeMinwaitingtimeMinresponsetimeOperatingSystemConceptsChapter6:CPUSchedulingBasicConceptsSchedulingCriteriaSchedulingAlgorithmsMultiple-ProcessorSchedulingReal-TimeSchedulingAlgorithmEvaluationOperatingSystemConceptsSchedulingAlgorithmsWewilldiscussanumberofschedulingalgorithms:First-Come,First-Served(FCFS)Shortest-Job-First(SJF)PriorityRound-RobinMultilevelQueueMultilevelFeedbackQueueOperatingSystemConceptsFirst-Come,First-Served(FCFS)SchedulingTheprocessthatrequeststheCPUfirstisallocatedtheCPUfirst.Thiscaneasilybeimplementedusingaqueue.FCFSisnotpreemptive.OnceaprocesshastheCPU,itwilloccupytheCPUuntiltheprocesscompletesorvoluntarilyentersthewaitstate.OperatingSystemConceptsFCFSScheduling(Cont.)

Process

BurstTime

P1 24

P2 3

P3 3

Supposethattheprocessesarriveintheorder:P1,P2,P3

TheGanttChartforthescheduleis:P1P2P32427300Waitingtime?Averagewaitingtime?OperatingSystemConceptsFCFSScheduling(Cont.)Supposethattheprocessesarriveintheorder

P2,P3,P1.TheGanttchartforthescheduleis:

WaitingtimeforP1=6;

P2=0;P3=3Averagewaitingtime:(6+0+3)/3=3Muchbetterthanpreviouscase.ConvoyeffectshortprocessbehindlongprocessP1P3P263300OperatingSystemConceptsFCFSProblemsItiseasytohavetheconvoyeffect:alltheprocesseswaitfortheonebigprocesstogetofftheCPU.CPUutilizationmaybelow.ConsideraCPU-boundprocessrunningwithmanyI/O-boundprocess.Itisinfavoroflongprocessesandmaynotbefairtothoseshortones.Whatifyour1-minutejobisbehinda10-hourjob?Itistroublesomefortime-sharingsystems,whereeachuserneedstogetashareoftheCPUatregularintervals.OperatingSystemConceptsShortest-Job-First(SJF)SchedulingAssociatewitheachprocessthelengthofitsnextCPUburst.Usetheselengthstoscheduletheprocesswiththeshortesttime.Whenaprocessmustbeselectedfromthereadyqueue,theprocesswiththesmallestnextCPUburstisselected.Thus,theprocessesinthereadyqueuearesortedinCPUburstlength.OperatingSystemConceptsShortest-Job-First(SJF)Scheduling(Cont.)SJFcanbenon-preemptiveorpreemptive.nonpreemptive–onceCPUgiventotheprocessitcannotbepreempteduntilcompletesitsCPUburst.preemptive–ifanewprocessarriveswithCPUburstlengthlessthanremainingtimeofcurrentexecutingprocess,preempt.Thisschemeisknowasthe

Shortest-Remaining-Time-First(SRTF).SJFisoptimal–givesminimumaveragewaitingtimeforagivensetofprocesses.OperatingSystemConceptsSJFisprovablyoptimalEverytimewemakeashortjobbeforealongjob,wereduceaveragewaitingtime.Wemayswitchoutoforderjobsuntilalljobsareinorder.Ifthejobsaresorted,jobswitchingisimpossible.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-PreemptiveSJFP1P3P273160P4812OperatingSystemConceptsExampleofPreemptiveSJF

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=3P1P3P242110P457P2P116OperatingSystemConceptsHowdoweknowtheNextCPUBurst?Withoutagoodanswertothisquestion,SJFcannotbeusedforCPUscheduling.WetrytopredictthenextCPUburst!CanbedonebyusingthelengthofpreviousCPUbursts,usingexponentialaveraging.OperatingSystemConceptsOperatingSystemConceptsExamplesofExponentialAveraging=0n+1=nRecenthistorydoesnotcount.=1n+1=tnOnlytheactuallastCPUburstcounts.OperatingSystemConceptsPredictionoftheLengthoftheNextCPUBurstOperatingSystemConceptsExamplesofExponentialAveraging(Cont.)Ifweexpandtheformula,weget:n+1=tn+(1-)tn-1

+…

+(1-)jtn-j

+…

+(1-)n+10Sincebothand(1-)arelessthanorequalto1,eachsuccessivetermhaslessweightthanitspredecessor.OperatingSystemConceptsSJFProblemsItisdifficulttoestimatethenextbursttimevalueaccurately.SJFisinfavorofshortjobs.Asaresult,somelongjobsmaynothaveachancetorunatall.Thisisstarvation.OperatingSystemConceptsPrioritySchedulingEachprocesshasapriority.Prioritymaybedeterminedinternallyorexternally:internalpriority:determinedbytimelimits,memoryrequirement,#offiles,andsoon.externalpriority:notcontrolledbytheOS(e.g.,importanceoftheprocess)Thescheduleralwayspickstheprocess(inreadyqueue)withthehighestprioritytorun.FCFSandSJFarespecialcasesofpriorityscheduling.(Why?)OperatingSystemConceptsPriorityScheduling(Cont.)Priorityschedulingcanbenon-preemptiveorpreemptive.Withpreemptivepriorityscheduling,ifthenewlyarrivedprocesshasahigherprioritythantherunningone,thelatterispreempted.Indefiniteblock(orstarvation)mayoccur:alowpriorityprocessmayneverhaveachancetorunOperatingSystemConceptsAgingAgingisatechniquetoovercomethestarvtionproblem.Aging:graduallyincreasesthepriorityofprocessesthatwaitinthesystemforalongtime.Example:If0isthehighest(resp.,lowest)priority,thenwecoulddecrease(resp.,increase)thepriorityofawaitingprocessby1everyfixedperiod(e.g.,everyminute).OperatingSystemConceptsRoundRobin(RR)RRissimilartoFCFS,exceptthateachprocessisassignedatimequantum.AllprocessesinthereadyqueueisaFIFOlist.WhentheCPUisfree,theschedulerpicksthefirstandletsitrunforonetimequantum.IfthatprocessusesCPUforlessthanonetimequantum,itismovedtothetailofthelist.Otherwise,whenonetimequantumisup,thatprocessispreemptedbytheschedulerandmovedtothetailofthelist.OperatingSystemConceptsExampleofRRwithTimeQuantum=20

Process

BurstTime P1 53

P2 17

P3 68

P4 24TheGanttchartis:

Typically,higheraverageturnaroundthanSJF,butbetterresponse.P1P2P3P4P1P3P4P1P3P302037577797117121134154162OperatingSystemConceptsRRScheduling:SomeIssuesIftimequantumistoolarge,RRreducestoFCFSIftimequantumistoosmall,RRbecomesprocessorsharingContextswitchingmayaffectRR’sperformanceShortertimequantummeansmorecontextswitchesTurnaroundtimealsodependsonthesizeoftimequantum.Ingeneral,80%oftheCPUburstsshouldbeshorterthanthetimequantumOperatingSystemConceptsTimeQuantumandContextSwitchTimeOperatingSystemConceptsTurnaroundTimeVariesWithTheTimeQuantumHowtocalculate?OperatingSystemConceptsMultilevelQueueReadyqueueispartitionedintoseparatequeues:

foreground(interactive)

background(batch)Eachprocessisassignedpermanentlytoonequeuebasedonsomepropertiesoftheprocess(e.g.,memoryusage,priority,processtype)Eachqueuehasitsownschedulingalgorithm,

foreground–RR

background–FCFSOperatingSystemConceptsAprocessPcanrunonlyifallqueuesabovethequeuethatcontainsPareempty.Whenaprocessisrunningandaprocessinahigherpriorityqueuecomesin,therunningprocessispreempted.OperatingSystemConceptsMultilevelQueue(Cont.)Schedulingmustbedonebetweenthequeues.Fixedpriorityscheduling;(i.e.,serveallfromforegroundthenfrombackground).Possibilityofstarvation.Timeslice–eachqueuegetsacertainamountofCPUtimewhichitcanscheduleamongstitsprocesses;i.e.,80%toforegroundinRR,20%tobackgroundinFCFSOperatingSystemConceptsMultilevelFeedbackQueueMultilevelqueuewithfeedbackscheduling

issimilartomultilevelqueue;however,itallowsprocessestomovebetweenqueues.agingcanbeimplementedthiswayIfaprocessusesmore(resp.,less)CPUtime,itismovedtoaqueueoflower(resp.,higher)priority.Asaresult,I/O-bound(resp.,CPU-bound)processeswillbeinhigher(resp.,lower)priorityqueues.OperatingSystemConceptsExampleofMultilevelFeedbackQueueThreequeues:Q0–timequantum8millisecondsQ1–timequantum16millisecondsQ2–FCFSSchedulingAnewjobentersQ0

whichisserved

FCFS.WhenitgainsCPU,jobreceives8milliseconds.Ifitdoesnotfinishin8milliseconds,jobismovedtoQ1.AtQ1jobisagainservedFCFSandreceives16additionalmilliseconds.Ifitstilldoesnotcomplete,itispreemptedandmovedtoqueueQ2.OperatingSystemConceptsMultilevelFeedbackQueuesOperatingSystemConceptsProcessesinqueueihavetimequantum2iWhenaprocess’behaviorchanges,itmaybeplaced(i.e.,promotedordemoted)intoadifferencequeue.Thus,whenanI/O-boundprocessstartstousemoreCPU,itmaybedemotedtoalowerqueueOperatingSystemConceptsMultilevelFeedbackQueue(Cont.)Multilevel-feedback-queueschedulerdefinedbythefollowingparameters:numberofqueuesschedulingalgorithmsforeachqueuemethodusedtodeterminewhentoupgradeaprocessmethodusedtodeterminewhentodemoteaprocessmethodusedtodeterminewhichqueueaprocesswillen