《05第二章处理机管理4.ppt

第五章 调度与死锁 一、 处理器调度的层次 处理机是计算机系统中的重要资源。 处理机调度算法对整个计算机系统的综合性能指标有重要影响。 可把处理机调度分成三个层次： 高级调度 中级调度 低级调度 1.高级调度 也称为作业调度或长程调度。 作业调度的主要功能是根据作业调度算法选择外存上处于后备队列中的某些作业调入内存，并为他们分配必要的资源、创建作业相应的进程，在作业完成后还要做结束阶段的善后工作。 2.低级调度 也称进程/线程调度、短程调度。 进程调度的主要功能是根据一定的调度算法从就绪队列中选中一个进程/内核级线程获得处理器，让它使用。 低级调度是操作系统最核心部分，执行十分频繁，其调度策略的好坏直接影响整个系统的性能。 低级调度的调度方式： （1）非剥夺式（非抢先式） 调度程序一旦把cpu分配给某一进程/线程后，便让他一直运行下去，直到进程完成或发生某事件不能运行时，才将cpu分配给其他进程。 这种调度方式通常用于批处理系统中。 优点：简单，系统开销小 缺点：难以满足紧急任务的要求，实时系统不宜采用。 （2）剥夺式（抢先式） 当一个进程/线程正在处理器上执行时，调度程序可根据某种原则剥夺cpu分配给其他进程/线程。 这种调度方式通常用于分时系统和实时系统中。 剥夺的原则： 优先权原则 短作业（进程）优先原则 时间片原则 3.中级调度 又称平衡调度，中程调度 涉及进程在内外存间的交换，当主存资源紧缺时将暂不运行的进程从内存调至外存，此时这个进程处于“挂起”状态；当进程又具备运行条件且主存资源有空闲时，再将进城从外存调至内存。 中级调度的主要目的是提高内存利用率和系统吞吐量。 低级调度是各类操作系统必备的，在纯粹的分时系统或实时系统中，通常不需高级调度。一般系统都有高级调度和低级调度；功能完善的系统引入了中级调度。 三、作业与进程的关系 1. 作业的基本概念 （1）作业（job） 用户提交给操作系统计算的一个独立任务。 （2）作业步（job step） 一个作业可划分成若干加工步骤，称为一个作业步。 典型的作业控制过程： “编译”、“链接” “装入”、“运行” （3）作业控制块（ Job Control Block ，JCB） 为有效地管理作业，必须为进入系统的每个作业建立作业控制块。JCB是在批作业进入系统时，由Spooling系统建立的，它是作业存在于系统的标志，作业撤离时，JCB也被撤销。 JCB保存有系统对于作业进行管理所需要的全部信息。 主要信息见图。 2. 批处理作业的组织和管理 一个作业从进入系统到运行结束经历四个不同的状态： 输入状态： 后备状态： 执行状态： 完成状态： 作业调度与进程调度的关系 作业是任务实体，进程是完成任务的执行实体;没有作业任务，进程无事可干，没有进程，作业任务没法完成。 作业概念更多地用在批处理操作系统，而进程则可以用在各种多道程序设计系统。 2.6 处理器调度算法 不同系统中由于其类型和系统目标不同，采用的调度算法也不同。 有多种调度算法，有的算法仅适用于作业调度，有的仅适用于进程/线程调度，但大多数对二者都适用。 一、先来先服务（First Come First Served，FCFS ） 最简单的调度算法，即可用于作业调度，也可用于进程调度。 按作业（进程）来到的先后次序进行调度。 优点：易于实现 缺点：调度程序每次选择的作业是等待时间最久的，而不管作业的运行时间的长短，此算法效率低； 有利于长作业，不利于短作业 二、最短作业（进程）优先算法SJF：Shortest Job FirstSPF：Shortest Process First 可用于作业调度和进程调度。 估计作业（进程）的CPU运行时间，选取估计时间最短的作业（进程）投入运行。 上例： 优点： (1)易于实现。 (2)在一般情况下这种调度算法比先来先服务调度算法的调度性能比FCFS好。 缺点： (1)作业（进程）的执行时间是用户估计的，不一定准确，所以实现时不一定真正做到短作业优先调度。 (2)对长作业不利 若系统不断接受新作业，就有可能使长作业长时间得不到调度。出现饥饿现象 (3)缺少剥夺机制，对分时、实时系统仍不理想 三、响应比最高者优先算法（HRRF:Highest Response Ratio First） FCFS与SJF是片面的调度算法。FCFS只考虑作业等候时间而忽视了作业的计算时问，SJF只考虑用户估计的作业计算时间而忽视了作业等待时间。 HRRF是介乎这两者之间的折衷算法，既考虑作业等待时间，又考虑作业的运行时间，既照顾短作业又不使长作业的等待时间过长，改进了调度