LEC7-调度.ppt
Operating SystemLecture SevenUniprocessor SchedulingSchool of SoftwareNanjing University本主题教学目标本主题教学目标1.掌握调度的层次掌握调度的层次2.掌握低级调度及其策略掌握低级调度及其策略3.掌握掌握作业调度及其策略作业调度及其策略 Aim of SchedulingnResponse timenThroughputnProcessor efficiencyTypes of SchedulingLong-Term SchedulingnDetermines which programs are admitted to the system for processingnControls the degree of multiprogrammingnMore processes,smaller percentage of time each process is executedMedium-Term SchedulingnPart of the swapping functionnBased on the need to manage the degree of multiprogrammingShort-Term SchedulingnKnown as the dispatchernExecutes most frequentlynInvoked when an event occursnClock interruptsnI/O interruptsnOperating system callsnSignalsShort-Tem Scheduling CriterianUser-orientednResponse Time：Elapsed time between the submission of a request until there is output.nSystem-orientednEffective and efficient utilization of the processorShort-Term Scheduling CriterianPerformance-relatednQuantitativenMeasurable such as response time and throughputnNot performance relatednQualitativenPredictabilityPrioritiesnScheduler will always choose a process of higher priority over one of lower prioritynHave multiple ready queues to represent each level of prioritynLower-priority may suffer starvationnallow a process to change its priority based on its age or execution historyDecision ModenNonpreemptivenOnce a process is in the running state,it will continue until it terminates or blocks itself for I/OnPreemptivenCurrently running process may be interrupted and moved to the Ready state by the operating systemnAllows for better service since any one process cannot monopolize the processor for very longProcess Scheduling ExampleFirst-Come-First-Served(FCFS)nEach process joins the Ready queuenWhen the current process ceases to execute,the oldest process in the Ready queue is selectedFirst-Come-First-Served(FCFS)0510152012345First-Come-First-Served(FCFS)nA short process may have to wait a very long time before it can executenFavors CPU-bound processesnI/O processes have to wait until CPU-bound process completesRound-RobinnUses preemption based on a clocknAn amount of time is determined that allows each process to use the processor for that length of timeRound-Robin0510152012345Round-RobinnClock interrupt is generated at periodic intervalsnWhen an interrupt occurs,the currently running process is placed in the read queuenNext ready job is selectednKnown as time slicingShortest Process NextnNonpreemptive policynProcess with shortest expected processing time is selected nextnShort process jumps ahead of longer processesShortest Process Next0510152012345Shortest Process NextnPredictability of longer processes is reducednIf estimated time for process not correct,the operating system may abort itnPossibility of starvation for longer processesShortest Remaining TimenPreemptive version of shortest process next policynMust estimate processing timeShortest Remaining Time0510152012345Highest Response Ratio Next(HRRN)nChoose next process with the Highest ratiotime spent waiting+expected service timeexpected service timeHighest Response Ratio Next(HRRN)1234505101520FeedbacknPenalize jobs that have been running longernDont know remaining time process needs to execute0510152012345Feedbackn基本思想基本思想建立多个不同优先级的就绪进程队列建立多个不同优先级的就绪进程队列多个就绪进程队列之间按照优先数调度多个就绪进程队列之间按照优先数调度高优先级的就绪进程高优先级的就绪进程,分配的时间片短分配的时间片短单单个个就就绪绪进进程程队队列列中中的的进进程程的的优优先先数数和和时间片相同时间片相同,按照先来先服务算法调度按照先来先服务算法调度n分分级级原原则则：外外设设访访问问,交交互互性性,时时间间紧紧迫迫程程度度,系统效率系统效率,用户立场用户立场,Feedback低级就绪队列低级就绪队列高级就绪队列高级就绪队列中级就绪队列中级就绪队列等待磁等待磁盘磁带盘磁带等待其等待其他外设他外设运行运行选中选中,时间片时间片500ms500ms超过时间片超过时间片启动磁盘磁带启动磁盘磁带启动其他外设启动其他外设选中选中,时间片时间片200ms200ms选中选中,时间片时间片100ms100msFair-Share SchedulingnUsers application runs as a collection of processes(threads)nUser is concerned about the performance of the applicationnNeed to make scheduling decisions based on process setsTraditional UNIX SchedulingnMultilevel feedback using round robin within each of the priority queuesnPriorities are recomputed once per secondnBase priority divides all processes into fixed bands of priority levelsnAdjustment factor used to keep process in its assigned band实例研究：实例研究：Unix SVR4调度算法调度算法n多多级级反反馈馈队队列列，每每一一个个优优先先数数都都对对应应于于一一个个就就绪进程队列绪进程队列n实实时时优优先先级级层层次次：优优先先数数和和时时间间片片都都是是固固定定的的，在抢占点执行抢占在抢占点执行抢占n分分时时优优先先级级层层次次：优优先先数数和和时时间间片片是是可可变变的的，从从0优先数的优先数的100ms到到59优先数的优先数的10msdqactmapdispq159.1202100.1110PPPPPPBandsnDecreasing order of prioritynSwappernBlock I/O device controlnFile manipulationnCharacter I/O device controlnUser processes实例研究：实例研究：WIN-XP调度算法调度算法n主主要要设设计计目目标标：基基于于内内核核级级线线程程的的可可抢抢占占式式调调度度，向向单单个个用用户户提提供供交交互互式式的的计计算算环环境境，并并支支持各种服务器程序持各种服务器程序n优先级和优先数优先级和优先数n实实时时优优先先级级层层次次（优优先先数数为为31-1631-16）：用用于于通信任务和实时任务，优先数不可变通信任务和实时任务，优先数不可变n可可变变优优先先级级层层次次（优优先先数数为为15-015-0）：用用于于用用户提交的交互式任务，优先数可动态调整户提交的交互式任务，优先数可动态调整n多多级级反反馈馈队队列列，每每一一个个优优先先数数都都对对应应于于一一个个就就绪进程队列绪进程队列实例研究：实例研究：WIN-XP调度算法调度算法n优先数可动态调整原则优先数可动态调整原则n线线程程所所属属的的进进程程对对象象有有一一个个进进程程基基本本优优先先数数，取值范围从取值范围从0到到15n线线程程对对象象有有一一个个线线程程基基本本优优先先数数，取取值值范范围围从从-2到到2n线线程程的的初初始始优优先先数数为为进进程程基基本本优优先先数数加加上上线线程基本优先数，但必须在程基本优先数，但必须在0到到15的范围内的范围内n线线程程的的动动态态优优先先数数必必须须在在初初始始优优先先数数到到15的的范围内范围内n当当存存在在N个个处处理理器器时时，N-1个个处处理理器器上上将将运运行行N-1个个最最高高优优先先级级的的线线程程，其其他他线线程程将将共共享享剩剩下下的一个处理器的一个处理器彩票彩票调度算法调度算法n基本思想：为进程发放针对系统各种基本思想：为进程发放针对系统各种资源（如资源（如CPUCPU时间）的彩票；当调度时间）的彩票；当调度程序需要做出决策时，随机选择一张程序需要做出决策时，随机选择一张彩票，持有该彩票的进程将获得系统彩票，持有该彩票的进程将获得系统资源资源n合作进程之间的彩票交换合作进程之间的彩票交换批处理作业的调度批处理作业的调度批处理作业的管理批处理作业的管理n作业说明语言和作业说明书作业说明语言和作业说明书n脱机控制方式（批处理控制方式）脱机控制方式（批处理控制方式）n作业控制块作业控制块JCBn作业状态作业状态n输入状态：作业正在从输入设备上预输入信息输入状态：作业正在从输入设备上预输入信息n后备状态：作业预输入结束但尚未被选中执行后备状态：作业预输入结束但尚未被选中执行n执执行行状状态态：作作业业已已经经被被选选中中并并构构成成进进程程去去竞竞争争处理器资源以获得运行处理器资源以获得运行n完成状态：作业运行结束，正在等待缓输出完成状态：作业运行结束，正在等待缓输出批处理作业的状态批处理作业的状态执行状态执行状态运行运行就就绪绪等待等待输输入入状状态态后后备备状状态态完完成成状状态态进程调度进程调度中级调度中级调度缓输出缓输出作业作业调度调度预输入预输入完成完成批处理作业的调度批处理作业的调度n作作业业调调度度：按按一一定定的的策策略略选选取取若若干干个个作作业业让让它它们们进进入入内内存存、构构成成进进程程去去竞竞争争处处理器以获得运行机会理器以获得运行机会n用用户户立立场场：自自己己作作业业的的周周转转时时间间尽尽可可能能的小的小n系系统统立立场场：希希望望进进入入系系统统的的作作业业的的平平均均周转时间尽可能的小周转时间尽可能的小n适适当当的的作作业业调调度度算算法法必必须须既既考考虑虑用用户户的的要求又有利于系统效率的提高要求又有利于系统效率的提高批处理作业的调度算法批处理作业的调度算法n 先来先服务算法先来先服务算法n 最短作业优先算法最短作业优先算法n 响应比最高者优先算法响应比最高者优先算法 响应比响应比=已等待时间已等待时间/估计计算时间估计计算时间n 优先数法优先数法n 分类调度算法分类调度算法n 用磁带与不用磁带的作业搭配算法用磁带与不用磁带的作业搭配算法
