中科大操作系统原理与实现课件5_CPU_Scheduling0.pdf

《中科大操作系统原理与实现课件5_CPU_Scheduling0.pdf》由会员分享，可在线阅读，更多相关《中科大操作系统原理与实现课件5_CPU_Scheduling0.pdf（53页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、.操作系统原理与设计第5章 CPU Scheduling(1)陈香兰中国科学技术大学计算机学院2009年09月01日.CPU scheduling is the basis of multiprogrammed OSes.提纲CPU scheduling(1).Basic ConceptsCPU-I/O Burst CycleCPU SchedulerPreemptive SchedulingDispatcherScheduling CriteriaScheduling CriteriaScheduling AlgorithmsFCFS SchedulingSJF SchedulingPrio

2、rity SchedulingRound Robin SchedulingMultilevel Queue SchedulingMultilevel Feedback Queue Scheduling小结和作业.Objective of multiprogrammingIMaximum CPU utilization.Outline.Basic ConceptsCPU-I/O Burst CycleCPU SchedulerPreemptive SchedulingDispatcherScheduling CriteriaScheduling CriteriaScheduling Algori

3、thmsFCFS SchedulingSJF SchedulingPriority SchedulingRound Robin SchedulingMultilevel Queue SchedulingMultilevel Feedback Queue Scheduling小结和作业.CPU-I/O Burst Cycle IIA property of process:CPU-I/O Burst CycleIProcess execution consists of a cycleof CPU execution and I/O waitIProcess execution=n(CPU ex

4、ecution+I/O wait)IAlternating Sequence of CPU And I/OBursts.CPU-I/O Burst Cycle IIICPU burst distributionIHistogram of CPU-burst Times.Outline.Basic ConceptsCPU-I/O Burst CycleCPU SchedulerPreemptive SchedulingDispatcherScheduling CriteriaScheduling CriteriaScheduling AlgorithmsFCFS SchedulingSJF Sc

5、hedulingPriority SchedulingRound Robin SchedulingMultilevel Queue SchedulingMultilevel Feedback Queue Scheduling小结和作业.CPU SchedulerICPU scheduler(Short-term Scheduler)ISelects from among the processes in memory that are ready toexecute,and allocates the CPU to one of themIReady Queue:IFIFO Queue?Iby

6、 priority?Itree?Iunordered linked list?.Outline.Basic ConceptsCPU-I/O Burst CycleCPU SchedulerPreemptive SchedulingDispatcherScheduling CriteriaScheduling CriteriaScheduling AlgorithmsFCFS SchedulingSJF SchedulingPriority SchedulingRound Robin SchedulingMultilevel Queue SchedulingMultilevel Feedback

7、 Queue Scheduling小结和作业.Preemptive Scheduling IICPU scheduling decisions may take place when a process:1.Switches from running to waiting state2.Switches from running to ready state3.Switches from waiting to ready4.TerminatesIThe scheduling scheme:Inonpreemptive:only 1&4IWindows 3.xIbefore Mac OS XIo

8、therwise preemptive(usually needs a hardware timer,synchronization overhead)IWindows 95&.IMac OS X.Preemptive Scheduling IIpreemptive kernel VS.nonpreemptive kernel?Interrupt affected code VS normal kernel code?.Outline.Basic ConceptsCPU-I/O Burst CycleCPU SchedulerPreemptive SchedulingDispatcherSch

9、eduling CriteriaScheduling CriteriaScheduling AlgorithmsFCFS SchedulingSJF SchedulingPriority SchedulingRound Robin SchedulingMultilevel Queue SchedulingMultilevel Feedback Queue Scheduling小结和作业.DispatcherIDispatcher module gives control of the CPU to the processselected by the short-term scheduler;

10、this involves:Iswitching contextIswitching to user modeIjumping to the proper location in the user program to restartthat programIDispatch latency time it takes for the dispatcher to stopone process and start another runningImust be short.Dispatch latency.Outline.Basic ConceptsCPU-I/O Burst CycleCPU

11、 SchedulerPreemptive SchedulingDispatcherScheduling CriteriaScheduling CriteriaScheduling AlgorithmsFCFS SchedulingSJF SchedulingPriority SchedulingRound Robin SchedulingMultilevel Queue SchedulingMultilevel Feedback Queue Scheduling小结和作业.Scheduling Criteria IICPU utilization（CPU 利用率）keep the CPU as

12、 busy aspossibleIconceptually:0%100%Iin a real system:40%90%IThroughput（吞吐率）#of processes that complete theirexecution per time unitIdifferent from one process set to another process setIfor long processes:may be 1 process per hourIfor short transactions:may be 10 processes per secondITurnaround tim

13、e(周转时间)amount of time to execute aparticular processIfrom the time of submission of a process to the time ofcompletion=the periods spent waiting to get into memory,waiting in theready queue,executing on the CPU,and doing I/O.Scheduling Criteria IIIWaiting time amount of time a process has been waiti

14、ng inthe ready queueIResponse time amount of time it takes from when arequest was submitted until the first response is produced,notoutput(for time-sharing environment).Optimization CriteriaIMaximize?ICPU utilizationIthroughputIMinimize?Iturnaround timeIwaiting timeIresponse timeIAverage?IStability?

15、different from system to system.Outline.Basic ConceptsCPU-I/O Burst CycleCPU SchedulerPreemptive SchedulingDispatcherScheduling CriteriaScheduling CriteriaScheduling AlgorithmsFCFS SchedulingSJF SchedulingPriority SchedulingRound Robin SchedulingMultilevel Queue SchedulingMultilevel Feedback Queue S

16、cheduling小结和作业.FCFS SchedulingIFirst-Come,First-ServedInonpreemptiveIImplementation:INormal Queue:FIFO QueueIordered by request timeIlinked listIInsert:linked to the tail of the queueIscheduling:removed from the head of the queue.Example of FCFS Scheduling.ISuppose that the processes arrivein the or

17、der:P1,P2,P3The Gantt Chart for the schedule is:ProcessBurstTime(ms)P124P23P33IWaiting time for P1=0;P2=24;P3=27IAverage waiting time:(0+24+27)/3=17.Example of FCFS Scheduling II.ISuppose that the processes arrivein the orderP2,P3,P1IThe Gantt chart for the schedule is:ProcessBurstTime(ms)P124P23P33

18、IWaiting time for P1=6;P2=0;P3=3IAverage waiting time:(6+0+3)/3=3IMuch better than previous case.Convoy effectIexample situation:Ione CPU-bound processImany I/O-bound processesIConvoy effect（护航效应；护卫效应）:Iall the other processes wait for the one big process to get offthe CPUIshort process behind long

19、process.Outline.Basic ConceptsCPU-I/O Burst CycleCPU SchedulerPreemptive SchedulingDispatcherScheduling CriteriaScheduling CriteriaScheduling AlgorithmsFCFS SchedulingSJF SchedulingPriority SchedulingRound Robin SchedulingMultilevel Queue SchedulingMultilevel Feedback Queue Scheduling小结和作业.SJF Sched

20、ulingIShortest-Job-First(shortest-next-CPU-burst algorithm)IAssociate with each process the length of its next CPUburst.IUse these lengths to schedule the process with the shortesttime.SJF scheduling example.ProcessBurstTime(ms)P16P28P37P43IThe Gantt chart for the schedule is:IWaiting time for P1=3;

21、P2=16;P3=9;P4=0IAverage waiting time:(3+16+9+0)/4=7IIf FCFS,average waiting time would be:(0+6+14+21)/4=10.25.ISJF is optimal gives minimum average waiting time for agiven set of processes.SJF scheduling schemesITwo schemes:Inonpreemptive once CPU given to the process it cannot bepreempted until com

22、pletes its CPU burstIpreemptive if a new process arrives with CPU burst lengthless than remaining time of current executing process,preempt.This scheme is know as theShortest-Remaining-Time-First(SRTF).Example of Non-Preemptive SJFProcessArrivalTimeBurstTime(ms)P10.07P22.04P34.01P45.04ISJF(non-preem

23、ptive)IAverage waiting time=(0+6+3+7)/4=4.Example of Preemptive SJFProcessArrivalTimeBurstTime(ms)P10.07P22.04P34.01P45.04ISJF(preemptive)IAverage waiting time=(11-2)+(5-4)+0+(7-5)/4=3.Determining Length of Next CPU Burst.IFor job schedulingIdepend on user?IFor CPU schedulingICan only estimate the l

24、engthICan be done by using the length of previous CPU bursts,using exponential averaging1.tn=actual length of nthCPU burst2.n+1=predicted value for the next CPU burst3.,0 14.Define:n+1=tn+(1 )n.Prediction of the Length of the Next CPU BurstI=1/2;0=10.Examples of Exponential AveragingI=0In+1=nIRecent

25、 history does not countI=1In+1=nIOnly the actual last CPU burst countsIIf we expand the formula,we get:n+1=n+(1 )n1+(1 )jnj+(1 )n+10ISince both and(1 )are less than or equal to 1,eachsuccessive term has less weight than its predecessor.Outline.Basic ConceptsCPU-I/O Burst CycleCPU SchedulerPreemptive

26、 SchedulingDispatcherScheduling CriteriaScheduling CriteriaScheduling AlgorithmsFCFS SchedulingSJF SchedulingPriority SchedulingRound Robin SchedulingMultilevel Queue SchedulingMultilevel Feedback Queue Scheduling小结和作业.Priority SchedulingIA priority number(integer)is associated with each processIpri

27、ority number VS.priorityIThe CPU is allocated to the process with the highest priority(smallest integer highest priority)IPreemptiveInonpreemptiveISJF is a special case of general priority scheduling wherepriority is the predicted next CPU burst time.Example.ProcessBurstTime(ms)PriorityP1103P211P324

28、P415P542IThe Gantt chart for the schedule is:IAverage waiting time=(6+0+16+18+1)/5=8.2.IThe determination of priorityIinternally,for example:Itime limits,memory requirement,the number of open files,.Iexternally,for example:Ithe importance,the type and amount of funds,thedepartment,.IPriority Schedul

29、ing:IProblem Starvation(indefinite blocking)low priorityprocesses may never executeISolution Aging as time progresses increase the priority ofthe process.Outline.Basic ConceptsCPU-I/O Burst CycleCPU SchedulerPreemptive SchedulingDispatcherScheduling CriteriaScheduling CriteriaScheduling AlgorithmsFC

30、FS SchedulingSJF SchedulingPriority SchedulingRound Robin SchedulingMultilevel Queue SchedulingMultilevel Feedback Queue Scheduling小结和作业.Round Robin(RR)ITime quantum,time sliceIa small unit of CPU timeIusually 10-100 msIImplementationIReady queue:a FIFO circular queueIEach process gets 1 time quantu

31、mIInsert:to the tail of the queueIScheduling:pick the first process;set timer;and dispatchItwo situation:ICPU burst 1 time quantumICPU burst 1 time quantum.After this time has elapsed,the process is preempted and added to the end of the readyqueue.Example of RR with Time Quantum=20ProcessBurstTimeP1

32、53P217P368P424IThe Gantt chart is:ITypically,higher average turnaround than SJF,but betterresponse.PerformanceIIf there are n processes in the ready queue and the timequantum is q,then each process gets 1/n of the CPU time inchunks of at most q time units at once.No process waitsmore than(n-1)q time

33、 units.IPerformanceIq large FIFOIq small q must be large with respect to context switch,otherwise overhead is too high.Time Quantum and Context Switch TimeIThe effect of context switching on the performance of RRscheduling.Turnaround Time Varies With The Time Quantum.Outline.Basic ConceptsCPU-I/O Bu

34、rst CycleCPU SchedulerPreemptive SchedulingDispatcherScheduling CriteriaScheduling CriteriaScheduling AlgorithmsFCFS SchedulingSJF SchedulingPriority SchedulingRound Robin SchedulingMultilevel Queue SchedulingMultilevel Feedback Queue Scheduling小结和作业.Multilevel Queue Scheduling IIReady queue is part

35、itioned into separate queues:Iforeground(interactive)Ibackground(batch)IEach queue has its own scheduling algorithmIforeground RRIbackground FCFSIScheduling must be done between the queuesIFixed priority scheduling;Ii.e.,serve all from foreground then from backgroundIPossibility of starvation.ITime

36、slice each queue gets a certain amount of CPU timewhich it can schedule amongst its processes;i.e.,I80%to foreground in RRI20%to background in FCFS.example.Outline.Basic ConceptsCPU-I/O Burst CycleCPU SchedulerPreemptive SchedulingDispatcherScheduling CriteriaScheduling CriteriaScheduling Algorithms

37、FCFS SchedulingSJF SchedulingPriority SchedulingRound Robin SchedulingMultilevel Queue SchedulingMultilevel Feedback Queue Scheduling小结和作业.Multilevel Feedback Queue SchedulingIA process can move between the various queues;aging can beimplemented this wayIMultilevel-feedback-queue scheduler defined b

38、y the followingparameters:Inumber of queuesIscheduling algorithms for each queueImethod used to determine when to upgrade a processImethod used to determine when to demote a processImethod used to determine which queue a process will enterwhen that process needs service.Example of Multilevel Feedbac

39、k Queue IIThree queues:IQ0 RR with time quantum 8 millisecondsIQ1 RR time quantum 16 millisecondsIQ2 FCFSISchedulingIA new job enters queue Q0which is served FCFS.When itgains CPU,job receives 8 milliseconds.If it does not finish in 8milliseconds,job is moved to queue Q1.IAt Q1job is again served FC

40、FS and receives 16 additionalmilliseconds.If it still does not complete,it is preempted andmoved to queue Q2.Example of Multilevel Feedback Queue II.小结.Basic ConceptsCPU-I/O Burst CycleCPU SchedulerPreemptive SchedulingDispatcherScheduling CriteriaScheduling CriteriaScheduling AlgorithmsFCFS SchedulingSJF SchedulingPriority SchedulingRound Robin SchedulingMultilevel Queue SchedulingMultilevel Feedback Queue Scheduling小结和作业.谢谢！