《操作系统任爱华版第八章》-公开·课件设计.ppt

处理机调度 调度的类型与模型 调度算法 实时系统中的调度 多处理机调度 主要目的 CPU调度是多道程序设计的基础，通过在进程之间切换CPU，操作系统可以使计算机做更多的事，提高CPU的利用率，并使不同的用户能够公平地得到CPU资源 本节介绍处理机调度算法并对调度算法的特点进行简单分析。 调度的类型 高级调度 中级调度 低级调度（CPU调度） 高级调度 又称为“宏观调度”或者“作业调度” 从用户工作流程的角度，一次提交的若干个作业，对每个作业进行调度。时间上通常是分钟、小时或天。 接纳多少个作业，取决于允许多少个作业同时在内存运行（多道程序度） 接纳哪些作业，取决于采用的调度算法 作业调度出现在批处理系统中或者是实时系统中，分时系统中没有作业调度程序 中级调度 内存与外存对换区交换内容：从存储器资源的角度，将进程的部分或全部内容换出到外存上，将当前进程所需部分内容换入到内存 注意：CPU仅能直接访问内存，所以指令和数据放在内存，CPU方可执行与访问它们 低级调度（CPU调度） 从就绪队列中选择一个等待CPU的进程并分配CPU给它。调度程序负责将CPU分配给被选进程。 又称： 微观调度 进程调度：讨论一般调度概念时采用 线程调度：特指线程概念 决定就绪队列中的哪个进程将获得处理机 进程调度执行频繁，通常是几十毫秒执行一次 有两种实现方式： 非剥夺式nonpreemptive 剥夺式，剥夺的原则如下： 时间片原则(轮转RR) 优先权原则/FCFS 最短作业（进程）优先原则（SJF） 作业调度与进程调度队列 三级调度方式的队列 针对多个就绪对列的进程调度 CPU的三级调度示意图 调度准则Scheduling Criteria CPU利用率（utilization） 从资源使用的角度（系统资源利用率高） 吞吐量（Throughput） 周转时间（Turnaround time） 等待时间（Waiting time） 响应时间（Response time） 用户的角度（响应迅速） 实际的处理机调度算法选择是一个综合的判断结果 面向用户的调度准则1 周转时间(批处理系统) 作业从提交到完成（得到结果）所经历的时间。包括：在收容队列中等待，CPU上执行，就绪队列和阻塞队列中等待，结果输出等待 外存等待时间、就绪等待时间、CPU执行时间、I/O操作时间 Ti = 作业完成时间Tic － 作业到达时间Tia 平均周转时间 平均周转时间T=∑(Ti) / n （n为作业总数） 带权平均周转时间 W=∑ (Wi) = (∑ ( Ti /Tir)) / n （ Tir 为实际运行时间） 响应时间(分时系统) 用户输入一个请求（如击键）到系统给出首次响应（如屏幕显示）的时间 面向用户的调度准则2 截止时间的保证(实时系统) ： 开始截止时间，任务必须开始的最迟时间 完成截止时间，任务必须完成的最迟时间 是评价实时性能的重要指标。 优先级： 代表任务运行的紧迫程度，紧迫的任务具有高优先级别，严格的情况可采用剥夺调度方式。 公平性： 不因作业或进程本身的特性而影响对作业的调度性能，比如造成长作业等待很长时间一直得不到运行的情况。 面向系统的调度性能准则 吞吐量： 单位时间内所完成的作业数（批处理系统调度考虑的因素） 处理机利用率： 使CPU尽量处于忙碌状态（大型主机考虑的因素） 各种资源的均衡利用： 如CPU繁忙的作业和I/O繁忙的作业搭配（大型主机考虑的因素） 调度算法 操作系统中的调度的实质是一种资源分配 这些调度算法有的适用于作业调度，有的适用于进程调度，有的两者都适用。 先来先服务(FCFS, First Come First Service) 这是最简单的调度算法，按先后顺序调度。 按照作业提交或进程变为就绪状态的先后次序，分派CPU 当前作业或进程占用CPU，直到执行完或因申请资源而阻塞，如申请I/O，才出让CPU（非剥夺方式）。 在资源得到满足后作业或进程则被唤醒（如I/O完成），并不立即恢复执行，通常等到正在运行的作业或进程出让CPU （因为是非剥夺方式） FCFS的特点 比较有利于长作业，而不利于短作业。 有利于CPU繁忙的作业，不利于I/O繁忙的作业。 FCFS 最短作业优先(SJF, Shortest Job First) 又称为“短进程优先”SPN(Shortest Process Next)；这是对FCFS算法的改进，其目标是减少平均周转时间 对预计执行时间短的作业（进程）优先分派处理机。通常后来的短作业不抢占正在执行中的CPU。 该算法与每个进程的下一个CPU处理周期相关 SJF的特点 优点： 比FCFS改善平均周转时间和平均带权周转时间，缩短作业的等待时间； 提高系统的吞吐量； 缺点： 对长作业非常不利，