Operating System,Lecture Five Uniprocessor Scheduling School of Software Nanjing University,本主题教学目标,掌握调度的层次 掌握低级调度及其策略 掌握作业调度及其策略,Aim of Scheduling,Response time Throughput Processor efficiency,Types of Scheduling,Long-Term Scheduling,Determines which programs are admitted to the system for processing Controls the degree of multiprogramming More processes, smaller percentage of time each process is executed,Medium-Term Scheduling,Part of the swapping function Based on the need to manage the degree of multiprogramming,Short-Term Scheduling,Known as the dispatcher Executes most frequently Invoked when an event occurs Clock interrupts I/O interrupts Operating system calls Signals,Short-Tem Scheduling Criteria,User-oriented Response Time：Elapsed time between the submission of a request until there is output. System-oriented Effective and efficient utilization of the processor Performance-related Quantitative, Measurable such as response time and throughput,Priorities,Scheduler will always choose a process of higher priority over one of lower priority Have multiple ready queues to represent each level of priority Lower-priority may suffer starvation allow a process to change its priority based on its age or execution history,Decision Mode,Nonpreemptive Once a process is in the running state, it will continue until it terminates or blocks itself for I/O Preemptive Currently running process may be interrupted and moved to the Ready state by the operating system Allows for better service since any one process cannot monopolize the processor for very long,Process Scheduling Example,First-Come-First-Served (FCFS),Each process joins the Ready queue When the current process ceases to execute, the oldest process in the Ready queue is selected,First-Come-First-Served (FCFS),1,2,3,4,5,First-Come-First-Served (FCFS),A short process may have to wait a very long time before it can execute Favors CPU-bound processes I/O processes have to wait until CPU-bound process completes,Round-Robin,Uses preemption based on a clock An amount of time is determined that allows each process to use the processor for that length of time,Round-Robin,1,2,3,4,5,Round-Robin,Clock interrupt is generated at periodic intervals When an interrupt occurs, the currently running process is placed in the read queue Next ready job is selected Known as time slicing,Shortest Process Next,Nonpreemptive policy Process with shortest expected processing time is selected next Short process jumps ahead of longer processes,Shortest Process Next,Shortest Process Next,Predictability of longer processes is reduced If estimated time for process not correct, the operating system may abort it Possibility of starvation for longer processes,Shortest Remaining Time,Preemptive version of shortest process next policy Must estimate processing time,Shortest Remaining Time,Highest Response Ratio Next (HRRN),Choose next process with the Highest ratio,time spent waiting + expected service time expected service time,Highest Response Ratio Next (HRRN),1,2,3,4,5,Feedback,Feedback,基本思想 建立多个不同优先级的就绪进程队列 多个就绪进程队列之间按照优先数调度 高优先级的就绪进程, 分配的时间片短 单个就绪进程队列中的进程的优先数和时间片相同, 按照先来先服务算法调度 分级原则：外设访问, 交互性, 时间紧迫程度, 系统效率, 用户立场, ,Feedback,Traditional UNIX Scheduling,Multilevel feedback using round robin within each of the priority queues Priorities are recomputed once per second Base priority divides all processes into fixed bands of priority levels Adjustment factor used to keep process in its assigned band,实例研究：Unix SVR4调度算法,多级反馈队列，每一个优先数都对应于一个就绪进程队列 实时优先级层次：优先数和时间片都是固定的，在抢占点执行抢占 分时优先级层次：优先数和时间片是可变的，从0优先数的100ms到59优先数的10ms,Bands,Decreasing order of priority Swapper Block I/O device control File manipulation Character I/O device control User processes,实例研究：WIN-XP调度算法,主要设计目标：基于内核级线程的可抢占式调度，向单个用户提供交互式的计算环境，并支持各种服务器程序 优先级和优先数 实时优先级层次（优先数为31-16）：用于通信任务和实时任务，优先数不可变 可变优先级层次（优先数为15-0）：用于用户提交的交互式任务，优先数可动态调整 多级反馈队列，每一个优先数都对应于一个就绪进程队列,实例研究：WIN-XP调度算法,优先数可动态调整原则 线程所属的进程对象有一个进程基本优先数，取值范围从0到15 线程对象有一个线程基本优先数，取值范围从-2到2 线程的初始优先数为进程基本优先数加上线程基本优先数，但必须在0到15的范围内 线程的动态优先数必须在初始优先数到15的范围内 当存在N个处理器时，N-1个处理器上将运行N-1个最高优先级的线程，其他线程将共享剩下的一个处理器,彩票调度算法,基本思想：为进程发放针对系统各种资源（如CPU时间）的彩票；当调度程序需要做出决策时，随机选择一张彩票，持有该彩票的进程将获得系统资源 合作进程之间的彩票交换,批处理作业的调度,批处理作业的管理,作业说明语言和作业说明书 脱机控制方式（批处理控制方式） 作业控制块JCB 作业状态 输入状态：作业正在从输入设备上预输入信息 后备状态：作业预输入结束但尚未被选中执行 执行状态：作业已经被选中并构成进程去竞争处理器资源以获得运行 完成状态：作业运行结束，正在等待缓输出,批处理作业的状态,批处理作业的调度,作业调度：按一定的策略选取若干个作业让它们进入内存、构成进程去竞争处理器以获得运行机会 用户立场：自己作业的周转时间尽可能的小 系统立场：希望进入系统的作业的平均周转时间尽可能的小 适当的作业调度算法必须既考虑用户的要求又有利于系统效率的提高,批处理作业的调度算法,先来先服务算法 最短作业优先算法 响应比最高者优先算法 响应比=已等待时间/估计计算时间 优先数法 分类调度算法 用磁带与不用磁带的作业搭配算法,