操作系统05第二章处理机管理4

1一、处理器调度的层次2.5处理器调度处理机是计算机系统中的重要资源。处理机调度算法对整个计算机系统的综合性能指标有重要影响。可把处理机调度分成三个层次：高级调度中级调度低级调度21.高级调度也称为作业调度或长程调度。作业调度的主要功能是根据作业调度算法选择外存上处于后备队列中的某些作业调入内存，并为他们分配必要的资源、创建作业相应的进程，在作业完成后还要做结束阶段的善后工作。32.低级调度也称进程/线程调度、短程调度。进程调度的主要功能是根据一定的调度算法从就绪队列中选中一个进程/内核级线程获得处理器，让它使用。低级调度是操作系统最核心部分，执行十分频繁，其调度策略的好坏直接影响整个系统的性能。4低级调度的调度方式：（1）非剥夺式（非抢先式）调度程序一旦把cpu分配给某一进程/线程后，便让他一直运行下去，直到进程完成或发生某事件不能运行时，才将cpu分配给其他进程。这种调度方式通常用于批处理系统中。优点：简单，系统开销小缺点：难以满足紧急任务的要求，实时系统不宜采用。5（2）剥夺式（抢先式）当一个进程/线程正在处理器上执行时，调度程序可根据某种原则剥夺cpu分配给其他进程/线程。这种调度方式通常用于分时系统和实时系统中。剥夺的原则：优先权原则短作业（进程）优先原则时间片原则63.中级调度又称平衡调度，中程调度涉及进程在内外存间的交换，当主存资源紧缺时将暂不运行的进程从内存调至外存，此时这个进程处于“挂起”状态；当进程又具备运行条件且主存资源有空闲时，再将进城从外存调至内存。中级调度的主要目的是提高内存利用率和系统吞吐量。低级调度是各类操作系统必备的，在纯粹的分时系统或实时系统中，通常不需高级调度。一般系统都有高级调度和低级调度；功能完善的系统引入了中级调度。7处理器三级调度模型处理器低级调度高级调度完成超时挂起就绪队列挂起等待队列等待队列就绪队列等待事件交互式用户事件出现后备作业队列中级调度8处理器两级调度模型等待事件事件发生进程完成后备作业队列就绪队列高级调度低级调度等待队列CPU时间片完9二、选择调度算法的原则l.资源利用率（特别是CPU利用率）CPU利用率=CPU有效工作时间/CPU总的运行时间，CPU总的运行时间=CPU有效工作时间+CPU空闲等待时间。2.吞吐率单位时间内处理的作业数。评价批处理系统性能的另一个重要指标。3.公平性确保每个用户每个进程获得合理的CPU份额或其他资源份额，不会出现饿死情况。104.响应时间交互式进程从提交一个请求(命令)到接收到响应之间的时间间隔称响应时间。响应时间包括：请求传送到CPU时间、CPU处理请求的时间、响应回送到终端显示器的时间。使交互式用户的响应时间尽可能短，或尽快处理实时任务，这是分时系统和实时系统衡量调度性能的一个重要指标。115.周转时间批处理用户从作业提交给系统开始，到作业完成为止的时间间隔称作业周转时间。包括四部分时间：在外存后备队列上等待作业调度的时间，相应进程在就绪队列中等待进程调度的时间，进程在cpu上执行的时间、进程等待I/O操作完成的时间。应使作业周转时间或平均作业周转时间尽可能短，这是批处理系统衡量调度性能的一个重要指标。12周转时间ti作业i提交给系统的时刻是ts，完成时刻是tf，该作业的周转时间ti为：ti=tf–ts。周转时间=作业等待时间+作业运行时间。为了提高系统的性能，要让若干个用户的平均作业周转时间和平均带权周转时间最小。平均作业周转时间TT=(Σti)/n13带权周转时间wi如果作业i的周转时间为ti，所需运行时间为tk，则wi=ti/tk平均作业带权周转时间WW=(Σwi)/n14三、作业与进程的关系1.作业的基本概念（1）作业（job）用户提交给操作系统计算的一个独立任务。（2）作业步（jobstep）一个作业可划分成若干加工步骤，称为一个作业步。典型的作业控制过程：“编译”、“链接”“装入”、“运行”15（3）作业控制块（JobControlBlock，JCB）为有效地管理作业，必须为进入系统的每个作业建立作业控制块。JCB是在批作业进入系统时，由Spooling系统建立的，它是作业存在于系统的标志，作业撤离时，JCB也被撤销。JCB保存有系统对于作业进行管理所需要的全部信息。16主要信息见图。172.批处理作业的组织和管理一个作业从进入系统到运行结束经历四个不同的状态：输入状态：后备状态：执行状态：完成状态：18作业调度与进程调度的关系进程调度运行就绪等待输入状态后备状态完成状态预输入完成作业控制作业调度(选中并创建进程)作业调度(作业终止并撤离)SPOOLing作业预输入SPOOLing作业缓输出19作业是任务实体，进程是完成任务的执行实体;没有作业任务，进程无事可干，没有进程，作业任务没法完成。作业概念更多地用在批处理操作系统，而进程则可以用在各种多道程序设计系统。202.6处理器调度算法不同系统中由于其类型和系统目标不同，采用的调度算法也不同。有多种调度算法，有的算法仅适用于作业调度，有的仅适用于进程/线程调度，但大多数对二者都适用。一、先来先服务（FirstComeFirstServed，FCFS）最简单的调度算法，即可用于作业调度，也可用于进程调度。按作业（进程）来到的先后次序进行调度。21优点：易于实现缺点：调度程序每次选择的作业是等待时间最久的，而不管作业的运行时间的长短，此算法效率低；有利于长作业，不利于短作业进程到达时间服务时间开始时间完成时间周转时间带权周转时间A040441B134762C25712102D321214115.5E441418143.5平均周转时间=9平均带权周转时间=2.8例：22二、最短作业（进程）优先算法SJF：ShortestJobFirstSPF：ShortestProcessFirst可用于作业调度和进程调度。估计作业（进程）的CPU运行时间，选取估计时间最短的作业（进程）投入运行。上例：进程到达时间服务时间开始时间完成时间周转时间带权周转时间A040441B136982.67C251318163.1D324631.5E4491392.25平均周转时间=8平均带权周转时间=2.123优点：(1)易于实现。(2)在一般情况下这种调度算法比先来先服务调度算法的调度性能比FCFS好。缺点：(1)作业（进程）的执行时间是用户估计的，不一定准确，所以实现时不一定真正做到短作业优先调度。(2)对长作业不利若系统不断接受新作业，就有可能使长作业长时间得不到调度。出现饥饿现象(3)缺少剥夺机制，对分时、实时系统仍不理想24三、响应比最高者优先算法（HRRF:HighestResponseRatioFirst）FCFS与SJF是片面的调度算法。FCFS只考虑作业等候时间而忽视了作业的计算时问，SJF只考虑用户估计的作业计算时间而忽视了作业等待时间。HRRF是介乎这两者之间的折衷算法，既考虑作业等待时间，又考虑作业的运行时间，既照顾短作业又不使长作业的等待时间过长，改进了调度性能。25响应比R=作业周转时间/作业处理时间=（作业处理时间+作业等待时间）/作业处理时间=1+（作业等待时间/作业处理时间）响应比最高者优先算法:每次调度时，计算所有作业的响应比，选择响应比最高的调度。短作业容易得到较高响应比，长作业等待时间足够长后，也将获得足够高的响应比，饥饿现象不会发生。26计算响应比导致一定的时间开销，此算法性能介于FCFS和SJF之间。进程到达时间服务时间开始时间完成时间周转时间带权周转时间A040441B134762C25914122.4D327963E441418143.5平均周转时间=8.4平均带权周转时间=2.38上例：27四、优先级调度算法（HPF—HighestPriorityFirst）为作业或进程确定优先级，选择优先级最高的作业或进程调度。1.两种方式非剥夺式：某一进程被调度运行后，除非由于它自身的原因不能运行，否则一直运行下去。剥夺式：当有比正在运行的进程优先级更高的进程就绪时，系统可强行剥夺正在运行进程的CPU，提供给具有更高优先级的进程使用。采用这种调度算法的关键是如何确定进程的优先级、一个进程的优先级确定之后是固定的，还是随着该进程运行的情况的变化而变化。282.优先级类型（1）静态优先级在进程创建时确定优先级，在进程运行时保持不变。确定优先级方法：系统确定（内部优先级）：考虑进程运行时间、使用资源，进程类型。用户确定（外部优先级）：考虑进程紧迫程度，计费与进程优先级有关。（2）动态优先级在进程创建时创立一个优先级，系统在运行的过程中，根据系统的设计目标，不断地调整进程的优先级，这种方法的优点是能比较客观地反映进程的实际情况和保证达到系统设计目标。如等待时间长优先级可改变。29五、时间片轮转调度算法(RoundRobin，RR)分时系统中常用时间片轮转法。把CPU划分成若干时间片,并且按顺序分配给就绪队列中的每一个进程，进程轮流占有CPU，当时间片用完时，即使进程未执行完毕，系统也剥夺该进程的CPU，将该进程排在就绪队列末尾，等候下一轮调度。1.时间片大小的确定时间片大小对系统性能有很大影响。时间片太小，会导致频繁切换，增大系统开销；时间片太大，轮转一次时间加长，进程在一个时间片内完成，时间片轮转算法退化为FCFS算法，无法满足交互式用户需求。确定时间片长度要从进程数目、切换开销、系统效率和响应时间等多方面加以考虑。302.RR改进RR由于采用固定时间片和仅有一个就绪队列，所以服务质量不够理想，进一步改进沿两个方向：（1）将固定时间片改为可变时间片引入可变时间片轮转调度算法（2）将单就绪队列改为多就绪队列引入多级反馈队列调度算法31六、多级反馈队列调度算法（MLFQ：Multi-levelFeedbackQueue）设置多个就绪队列，并为各个队列赋予不同的优先级，第一个队列最高，第二个次之……；各个队列时间片大小也不同，在优先级越高的队列中，为每个进程分配的时间片越小。处理器调度先从第一个就绪进程队列中选取进程，同一队列中的进程按FCFS算法进行排队。只有在未选到时，才从较低级的就绪进程队列中选取。当新进程进入内存后，首先放在第一个队列末尾，到轮到该进程执行时，如在该时间片完成，便可撤离系统；若未完成，则将该进程转入第二个队列末尾…32该算法具有较好的性能，能满足各类应用的需要。•分时交互型短作业：通常在第一队列规定的时间片完成，可使终端型用户满意。•短批处理作业：通常在第一队列和第二队列各执行一个时间片就能完成，周转时间仍很短。•长批处理作业：它将一次在第1，2，3…n个队列中运行。33第二章作业P151习题二一、思考题5，8，13，19，32，34，41，46，54，73二、应用题7，8，13，15，22（1）