第六章 处理机调度.ppt

第六章处理机调度 CPUScheduling 6 1引起进程调度的原因6 2调度类型6 3进程调度性能的衡量6 4进程调度算法6 5调度的队列模型 ModelingMultiprogramming CPUutilizationasafunctionofnumberofprocessesinmemory Degreeofmultiprogramming 6 1引起进程调度的原因 进程调度的方式 Windows是一个抢占式多任务多线程的操作系统 进程调度的方式 剥夺方式 Preemptivemode 抢占式调度剥夺原则 优先级原则短进程优先原则时间片原则强制性剥夺 极重要进程或人工干预 进程调度的方式 非剥夺方式 Non preemptivemode 非抢占式调度 进程调度程序的功能 PCB表项 跟踪进程状态及资源使用情况根据调度算法选择一个就绪进程分配处理机给进程 OperatingSystem MainGoals InterleavetheexecutionofthenumberofprocessestomaximizeprocessorutilizationwhileprovidingreasonableresponsetimeOverhead ContextswitchSwitchtousermodeRestartuserprogramatrightlocationUpdateresourceuseandassignmentObservation processestendtoruninburstsofcpu i ouse BasicConcepts ObjectiveofMultiprogrammingCPU I OBurstCycleAnI O boundprogramtypicallywillhavemanyshortCPUburstsAnCPU boundprogrammighthaveafewlongCPUbursts Scheduling Typesofbehavior BurstsofCPUusagealternatewithperiodsofI OwaitaCPU boundprocessanI Oboundprocess 6 2TypesofScheduling Long termschedulingThedecisiontoaddtothepoolofprocessestobeexecutedMedium termschedulingThedecisiontoaddtothenumberofprocessesthatarepartiallyorfullyinmainmemoryShort termschedulingThedecisionastowhichavailableprocesswillbeexecutedbytheprocessorI OschedulingThedecisionastowhichprocess spendingI OrequestshallbehandledbyanavailableI Odevice 调度的队列模型 只有进程调度的队列模型具有高级调度和低级调度的队列模型具有三级调度的队列模型 调度的类型和模型 高级调度又称为作业调度或宏观调度 它决定将哪些在外存上处于后备状态的作业调入主机内存 准备执行 因此 有时把它称为接纳调度 作业的状态及其转换作业从输入到完成要经历提交 收容 执行 完成四个阶段 低级调度又称为进程调度或微观调度 它决定就绪队列中哪个进程将获得处理机 并实际执行将处理机分配给进程的操作 执行分配处理机的程序称为分派程序 只有进程调度的调度队列模型 Admit ReadyQueue Processscheduling Time out EventWait Release Processor BlockedQueue EventOccurs 具有高级和低级调度的调度队列模型 作业后备队列 ReadyQueue Time out Release Processor Processscheduling Long termscheduling 中级调度 中级调度中级调度的主要作用是在内存和外存之间进行进程交换 以解决内存紧张的问题 如它将内存中处于等待状态的某些进程调至外存对换区 以腾出内存空间 而将外存对换区上已具备运行条件的进程重新调入内存 准备运行 故又称为交换调度 ThreeLevelScheduling SchedulingandProcessStateTransition New Ready suspend Ready Blocked Blocked suspend Running Exit Long termscheduling Long termscheduling Medium termscheduling Medium termscheduling Short termscheduling 6 3进程调度性能的衡量 SchedulingCriteria 面向用户的指标 周转时间 Turnaroundtime forbatchusers totaltimeofbatch 响应时间 Responsetime minimize forinteractiveusers等待时间 Waitingtime minimizetheaverageoverprocesses可预测性 进程调度性能的衡量Qualitycriteriaforscheduling algorithm 面向系统的指标 吞吐量 Throughput maximalnumberofprocessedjobsperunittime处理器利用率 CPUUtilization Efficiency 公平性 Fairness eachprocessgetsa fairshare ofthecpu确保优先权资源平衡 SchedulingAlgorithmGoals 平均周转时间 三个并发进程P1 P2 P3 其独立运行时间分别为21 6 3个单位P1 P2 P3P3 P2 P1 6 4进程调度算法分析用例 SchedulingAlgorithms 先进先出 先来先服务 First Come First ServedScheduling短执行进程优先Shortest Job FirstScheduling轮转法Round RobinScheduling优先级调度PriorityScheduling高响应比优先调度HighResponse RatioNextScheduling多级队列法MultilevelQueueScheduling多级队列反馈法MultilevelFeedback QueueScheduling First Come First ServedScheduling TheprocessthatrequeststheCPUfirstisallocatedtheCPUfirst TheimplementationoftheFCFSpolicyiseasilymanagedwithaFIFOqueue NonpreemptiveGanttChart 进程调度算法分析用例 EachprocessjoinstheReadyqueueWhenthecurrentprocessceasestoexecute theoldestprocessintheReadyqueueisselectedAveragewaitingtimeis4 6 AverageTurnaroundis8 6 1 2 3 4 5 First Come First Served FCFS 先进先出法的一个例子 ConvoyEffect 先来先服务调度算法 FCFS 按照进程就绪的先后次序来调度进程优点 实现简单缺点 看似公平 但服务质量欠佳 利于长进程 不利于短进程 Shortest Job FirstScheduling Thisalgorithmassociateswitheachprocessthelengthofthelatter snextCPUburst WhentheCPUisavailable itisassignedtotheprocessthathasthesmallestnextCPUburst IftwoprocesseshavethesamelengthnextCPUburst FCFSschedulingisusedtobreakthetie 短进程优先算法 SJF 减少FCFS方法对长进程的偏袒现象非剥夺方法预期执行时间最短的进程被选择执行问题所在 要预测下一进程的执行时间是很困难的 ShortestJobFirst Ifruntimesareknowninadvance 5 2 4 1 1 2 4 5 A B C D D B C A 5 7 11 12 4 8 75 1 3 7 12 4 5 75 andiftheyarenotknowntheycanbeapproximated 2 0 2 0 ShortestRemainingTime SRTF PreemptiveversionofshortestprocessnextpolicyMustestimateprocessingtimeAveragewaitingtimeis3 2 AverageTurnaroundis7 2 Question TheAverageTurnaroundTime FCFS SJF SPN SRT SRTF Round RobinScheduling Especiallydesignedfortime sharingsystemsTheCPUSchedulergoesaroundthereadyqueue allocatingtheCPUtoeachprocessforatimeintervalofupto1timequantum 时间片轮转法 基于时钟的剥夺算法把CPU划分成若干时间片 并且按顺序赋给就绪队列中的每一个进程 进程轮流占有CPU 当时间片用完时 即使进程未执行完毕 系统也剥夺该进程的CPU 将该进程排在就绪队列末尾 同时系统选择另一个进程运行 RRSchedulingExample1 Thetimequantumq 1 RRSchedulingExample2 Thetimequantumq 4 RRSchedulingExample3 TheAverageTurnaroundTime TimeQuantum 20 在采用RR调度的系统中 你认为时间片长度是越短越好还是越长越好 为什么 Contextswitchoverhead example Assumeeach32bitsregistertakes2x100nanoseconds 10 9seconds tosaveFora32registers 8statusregistersmachine savingtimeis 32 8 x2x100 x10 9 8x10 6 8micro sec Fortime slicesof0 1msec Theschedulerhasanoverheadof16 2x8 oncontextswitch Real overheadismuchhigher schedulercomputes schedulersavesitsowncontext processmemoryhastobesavedtoo somecpushaveseveralsetsofregisters Dependenceontime quantum 时间片长度的确定问题 时间片选择问题 固定时间片可变时间片与时间片大小有关的因素 系统响应时间就绪进程个数CPU能力 RoundRobin theoldestmethod Eachprocessgetsasmallunitofcputime time quantum usually10 100millisecondsFornreadyprocessesandtime quantumq noprocesswaitsmorethan n 1 qInthelimitofverylargeq FCFSQuantumoftime switchingtimerelativelylargewasteofcputime i e switching Quantumoftime switchingtimelongresponse waiting time FCFS 优先级调度 优先选择就绪队列中优先级最高的进程投入运行优先级 根据进程执行任务的轻重缓急程度赋予进程的一个调度优先级别 PriorityScheduling Apriorityisassociatedwitheachprocess andtheCPUisallocatedtotheprocesswiththehighestpriority Equal priorityprocessesarescheduledinFCFSorder PreemptiveorNonpreemptive Example1 Nonpreemptive Lownumbersrepresenthighpriority arrivedatthesametime Example2 Nonpreemptive Example3 Preemptive 优先级的确定 静态优先级法 在进程创建时指定优先级 在进程运行时优先级不变动态优先级法 在进程创建时创立一个优先级 但在其生命周期内优先级可以动态变化 如等待时间长优先级可改变 静态优先级的确定方法 按进程类型确定系统进程 用户进程按作业资源要求确定处理机时间 内存需求 I O设备类型等按作业到达时间确定FCFS按用户类型和要求确定如 收费标准 HighestResponseRatioNext HRRN Choosenextprocesswiththehighestratio timespentwaiting expectedservicetimeexpectedservicetime 1 2 3 4 5 MultilevelQueueScheduling ThisalgorithmpartitionsthereadyqueueintoseveralseparatequeuesTheprocessesarepermanentlyassignedtoonequeueEachqueuehasitsownschedulingalgorithm MultilevelQueueScheduling Systemprocesses Interactiveprocesses Batchprocesses Lowestpriority highestpriority High priorityprocesswillpreemptCPUallocatedtolow priorityprocess Multi LevelQueueScheduling systemprocesses Interactiveeditingprocesses batchprocesses studentprocesses interactiveprocesses Lowestpriority Highestpriority 如何处理多级队列间的关系 队列优先权分配高优先权队列优先高优先权队列抢占 不抢占 为各队列分配一定的CPU时间占用比例 多级反馈队列法 Feedback FB 将就绪队列分为N级 每个就绪队列分配给不同的时间片 队列级别越高 时间越长 级别越小 时间片越小 最后一级采用时间片轮转 其他队列采用先进先出 系统从第一级调度 当第一级为空时 系统转向第二个队列 当运行进程用完一个时间片 放弃CPU时 进入下一级队列 等待进程被唤醒时 进入原来的就绪队列 当进程第一次就绪时 进入第一级队列 MultilevelFeedback QueueScheduling Quantum 8 Quantum 16 FCFS MultilevelFeedback QueueScheduling CPU 优先级 时间片长 度 ReadyQueue Parametersindefiningamultilevelfeedback queuescheduler Numberofqueuesandschedulingpolicyineachqueue FCFS Priority WhentodemoteaprocesstoalowerqueueWhichqueuetopromoteaprocessto ElapsedtimesinceprocessreceivedCPU aging ExpectedCPUburstMemoryrequiredProcesspriority Multiple ProcessorScheduling 自学 HomogeneousprocessorsTheprocessorsareidentical Multiple ProcessorScheduling AseparatequeueforeachprocessorCommonreadyqueuesharedbyallprocessorsSymmetricmultiprocessing SMP Asymmetricmultiprocessing 6 5实时调度 Real TimeComputing Real timecomputingmaybedefinedasthattypeofcomputinginwhichthecorrectnessofthesystemdependsnotonlyonthelogicalresultofthecomputation butalsoonthetimeatwhichtheresultsareproduced Deadlineofatask Adeadlineisassociatedwithaparticulartask Thedeadlinespecifieseitherastarttimeoracompletiontime Hard SoftReal TimeTask Hardreal timetaskThetaskmustmeetitsdeadline otherwiseitwillcauseundesirabledamageorafatalerrortothesystemSoftreal timetaskThetaskhasanassociateddeadlinethatisdesirablebutnotmandatory itstillmakessensetoscheduleandcompletethetaskevenifithaspasseditsdeadline Real TimeComputing Twotypesofreal timecomputingHardreal timeSpecial purposesoftwareDedicatedhardwareSoftreal timePriorityscheduling agingdisallowedLowdispatchlatency preemptiblesystemcallsToinsertpreemptionpointsinlong durationsystemcallsTomaketheentirekernelpreemptible Aperiodic Periodictask Aperiodictask 非周期性任务 Thetaskhasadeadlinebywhichitmustfinishorstart oritmayhaveaconstraintonbothstartandfinishtime PeriodictaskTherequirementofthetaskmaybestatedas onceperperiodT or exactlyTunitsapart CharacteristicsofReal timeOperatingSystems DeterminismDelaybeforeacknowledginganinterruptResponsivenessDelayafteracknowledgementtoservicetheinterruptUserControlReliabilityFail softOperation FeaturesTypicallyIncludedinCurrentReal timeOperatingSystems FastprocessorthreadswitchSmallsize withitsassociatedminimalfunctionality AbilitytorespondtoexternalinterruptsquicklyMultitaskingwithinterprocesscommunicationtollssuchassemaphores signals andeventsUseofspecialsequentialfilesthatcanaccumulatedataatafastrate FeaturesTypicallyIncludedinCurrentReal timeOperatingSystems Cont PreemptiveschedulingbasedonpriorityMinimizationofintervalsduringwhichinterruptsaredisabledPrimitivestodelaytasksforafixedamountoftimeandtopause resumetasksSpecialalarmsandtimeouts 实时系统调度相关信息 Readytime 就绪时间 StartingdeadlineCompletiondeadlineProcessingtimeResourcerequirementsPrioritySubtaskstructure 实时调度算法 时间片轮转调度秒级响应 适于一般实时信息处理非抢占优先权调度数秒至数百毫秒级响应 适于不太严格实时控制系统基于时钟中断抢占的优先权调度几十毫秒至几毫秒响应 适于大多数实时