第三章处理机调度.

实用操作系统教程第三章处理机调度2本章内容3.1三级调度体系3.2进程调度目标和调度方式3.3调度算法的评价准则3.4典型进程调度算法3.5线程调度算法3.6实时调度算法3本章学习目标理解三级调度的含义和比较；理解抢占式调度、非抢占式调度的区别与联系；了解调度算法的评价准则；掌握常见调度算法及其比较；理解等待时间、周转时间、加权周转时间的含义，并会计算；了解实时调度和多处理机调度的特点43.1三级调度体系3.1.1高级调度1．高级调度（high-levelscheduling）又称作业调度或长程调度，它是根据某种算法将外存上处于后备作业队列中的若干作业调入内存，为作业分配所需资源并建立相应进程。2．作业通常分成若干个既相对独立又互相关联的加工步骤，每个步骤称为一个作业步。每个作业步可能对应一个或多个进程。53.1.1高级调度作业一般要经历“提交”、“后备”、“执行”和“完成”四个状态。63.1.1高级调度高级调度决定允许哪些作业可进入内存，参与竞争CPU和系统其他资源，将一个或一批作业从后备状态变为运行状态。73.1.1高级调度在多道批处理系统中，为了管理和调度作业，系统为每个作业设置了一个作业控制块(JCB)，它记录作业的相关信息。83.1.1高级调度9重点回顾管程由四部分组成：管程的名称局部于管程内部的共享数据结构说明对该数据结构进行操作的一组过程对管程内部共享数据设置初始值的语句高级进程通信机制可分为：共享存储器系统消息传递系统管道通信10重点回顾线程在引入线程之后，进程作为资源分配的基本单位，而线程作为独立调度和运行的基本单位高级调度（high-levelscheduling）又称作业调度或长程调度，它是根据某种算法将外存上处于后备作业队列中的若干作业调入内存，为作业分配所需资源并建立相应进程。113.1.2中级调度中级调度(middle-levelscheduling)又称内存调度，它是进程在内存和外存之间的对换。具有中级调度的系统中，进程除了具有三个基本状态外，还具有静止就绪和静止阻塞两个状态。123.1.3低级调度低级调度（low-levelscheduling）又称进程调度、短程调度，它决定哪个就绪态进程获得处理机，即选择某个进程从就绪态变为执行态。执行低级调度的原因多是处于执行态的进程由于某种原因放弃或被剥夺处理机。低级调度是三级调度中的最终调度，又称底层调度。在这级调度中真正实现了处理机的分配，它是系统不可缺少的最基本调度。133.1.3低级调度进程调度的功能主要包括以下两部分：①选择就绪进程②进程切换143.1.4三级调度关系分级调度系统中，各级调度分别在不同的调度时机进行。对于一个用户作业来说，通常要经历高级调度、中级调度和低级调度才能完成整个作业程序的运行。153.1.4三级调度关系163.2进程调度目标和调度方式3.2.1进程调度目标（1）公平性（2）高效率（3）低响应时间（4）高吞吐量（5）特殊应用要求173.2.1进程调度目标（1）多道批处理操作系统多道批处理系统强调高效利用系统资源和高作业吞吐量。进程提交给处理机后就不再与外部进行交互，系统按照调度策略安排它们运行，直到诸进程完成为止。（2）分时操作系统分时系统更关心多个用户的公平性和及时响应性，它不允许某个进程长时间占用处理机。分时系统多采用时间片轮转调度算法或在其基础上改进的其他调度算法。但处理机在各个进程之间频繁切换会增加系统时空开销，延长各个进程在系统中的存在时间。分时系统最关注的是交互性和各进程的均衡性，对进程的执行效率和系统开销往往要求并不苛刻。183.2.1进程调度目标（3）实时操作系统实时操作系统必须保证实时进程的请求得到及时响应，往往不考虑处理机的使用效率。实时系统采取的调度算法和其他类型系统采取的调度算法相比有很大不同，其调度算法的最大特点是可抢占性。（4）通用操作系统通用操作系统中，对进程调度没有特殊限制和要求，选择进程调度算法时主要追求处理机使用的公平性以及各类资源使用的均衡性193.2.2进程调度方式进程调度有两种基本方式：非抢占方式和抢占方式。（1）非抢占方式（Nonpreemptive）进程一旦获得处理机执行，其他进程就不能中断它的执行，即使当前等待进程中出现了优先级更高的请求进程也不允许该进程抢占处理机。直到执行态进程完成或发生某个事件主动放弃处理机，才能调度其他进程获得处理机执行。这种调度方式的优点是实现简单、系统开销小，适用于大多数批处理系统。但它难以满足实时任务的要求，在要求比较严格的实时操作系统中，一般不宜采用此类调度方式。203.2.2进程调度方式（2）抢占方式（Preemptive）抢占式调度是指在进程并发执行中，如果就绪进程中某个进程优先级比当前运行进程的优先级还高，无论当前正在运行的进程是否结束，允许高优先级进程抢占当前运行进程的处理机并立即执行。抢占式调度可确保高优先级进程立即获得处理机。抢占式调度在实际系统中具有重要意义。213.2.2进程调度方式支持抢占式调度的系统中，一般的抢占原则如下：①优先权原则就绪的高优先权进程有权抢占低优先权进程的CPU。②短作业优先原则就绪的短作业有权抢占长作业的CPU。③时间片原则一个时间片用完后，系统重新进行进程调度223.3调度算法的评价准则(1)作业周转时间所谓作业周转时间是指从作业被提交给系统开始，到作业完成为止的这段时间间隔。平均周转时间：平均带权周转时间：niiTnT11niSiiTTnW11233.3.1面向用户的评价准则(2)响应时间响应时间是指从进程输入第一个请求到系统给出首次响应的时间间隔。用户请求的响应时间越短，用户的满意度越高。响应时间通常由三部分时间组成：进程请求传送到处理机的时间、处理机对请求信息进行处理的时间、响应信息回送到显示器显示的时间。243.3.1面向用户的评价准则(3)截止时间截止时间是指用户或其他系统对运行进程可容忍的最大延迟时间。在实时系统中，通常用该准则衡量一个调度算法是否合格。在实际系统评价中，主要考核的是开始截止时间和完成截止时间。(4)优先权准则在批处理、分时和实时系统中选择调度算法时，为保证某些紧急作业得到及时处理，必须遵循优先权准则。因此，系统对不同进程设立优先级，高优先级进程优先获得处理机的使用权。253.3.2面向系统的评价准则对计算机系统而言，在保证用户请求被高效处理的基础上，尽量使计算机系统中的各类资源得到充分利用。面向系统的调度指标有：(1)系统吞吐量(2)处理机利用率(3)各类资源均衡利用(4)调度算法实现准则263.4典型进程调度算法3.4.1先来先服务调度算法3.4.2短作业（进程）优先调度算法3.4.4时间片轮转调度算法3.4.5优先级调度算法3.4.6高响应比优先调度算法3.4.7多级反馈队列调度算法重点273.4.1先来先服务调度算法FCFS(FirstComeFirstService)算法按照进程就绪的先后顺序调度进程，越早到达的进程，越先执行。FCFS算法的优缺点：①有利于长进程，不利于短进程，排在长进程后边的短进程往往等待的时间较长，导致其周转时间过长，没有体现出短进程优先原则。②有利于处理机繁忙的进程，不利于输入输出繁忙的进程。③算法简单，易于实现，系统开销小。283.4.2短作业（进程）优先调度算法又称为“短进程优先”SPN(ShortestProcessNext)；这是对FCFS算法的改进，其目标是减少平均周转时间。其思想是：对预计执行时间短的作业（进程）优先分派处理机。通常后来的短作业不抢先正在执行的作业。29SJ(P)F的特点优点：比FCFS改善平均周转时间和平均带权周转时间，缩短作业的等待时间；提高系统的吞吐量；缺点：对长作业非常不利，可能长时间得不到执行；未能依据作业的紧迫程度来划分执行的优先级；难以准确估计作业（进程）的执行时间，从而影响调度性能。303.4.4时间片轮转调度算法时间片轮转算法（RR，RoundRobin）依据公平服务的原则，将处理机的运行时间划分成等长的时间片，轮转式分配给各个就绪进程使用。采用此算法的系统中，所有就绪进程按照先来先服务的原则排成一个队列，每次调度时将处理机分派给队首进程。如果进程在一个时间片内没执行完，那么调度程序强行将该进程中止，进程由执行态变为就绪态并把处理机分配给下一个就绪进程。该算法能保证就绪队列中的所有进程在一给定的时间段内均能获得处理机运行。31时间片轮转法的原理见图所示。图轮转法调度323.4.5优先级调度算法优先级调度算法（PriorityScheduling）为每个进程赋予一个整数，表示其优先级。就绪进程按照优先级的大小顺序排队，调度程序选择优先级最高的进程获得CPU。该算法常被用于批处理系统中。1．优先权调度算法的类型为了照顾紧迫型作业，使之在进入系统后便获得优先处理，引入了最高优先权优先(FPF)调度算法。此算法常被用于批处理系统中，作为作业调度算法，也作为多种操作系统中的进程调度算法，还可用于实时系统中。当把该算法用于作业调度时，系统将从后备队列中选择若干个优先权最高的作业装入内存。当用于进程调度时，该算法是把处理机分配给就绪队列中优先权最高的进程，这时，又可进一步把该算法分成如下两种。331．优先级调度算法的类型1)非抢占式优先权算法系统一旦把处理机分配给就绪队列中优先权最高的进程后，该进程便一直执行下去，直至完成；或因发生某事件使该进程放弃处理机时，系统方可再将处理机重新分配给另一优先权最高的进程。这种调度算法主要用于批处理系统中；也可用于某些对实时性要求不严的实时系统中。2)抢占式优先权调度算法系统同样是把处理机分配给优先权最高的进程，使之执行。但在其执行期间，只要又出现了另一个其优先权更高的进程，进程调度程序就立即停止当前进程(原优先权最高的进程)的执行，重新将处理机分配给新到的优先权最高的进程。显然，这种抢占式的优先权调度算法能更好地满足紧迫作业的要求，故而常用于要求比较严格的实时系统中，以及对性能要求较高的批处理和分时系统中。342．优先级的类型对于最高优先权优先调度算法，其关键在于：它是使用静态优先权，还是用动态优先权，以及如何确定进程的优先权。1)静态优先权静态优先权是在创建进程时确定的，且在进程的整个运行期间保持不变。一般地，优先权是利用某一范围内的一个整数来表示的。确定进程优先权的依据有如下三个方面：(1)进程类型。(2)进程对资源的需求。(3)用户要求。352．优先级的类型2)动态优先级动态优先权是指在创建进程时所赋予的优先权，是可以随进程的推进或随其等待时间的增加而改变的，以便获得更好的调度性能。363.4.6高响应比优先调度算法最高响应比作业优先算法是对FCFS方式和SJF方式的一种综合平衡。响应比R定义为系统对作业的响应时间与作业要求运行时间的比值。一个作业或进程的响应比RHRRF调度程序开始调度时，首先计算各个后备作业或各个就绪进程的响应比,然后选择值最大的作业或进程。需运行时间需运行时间等待时间需运行时间响应时间/R需运行时间等待时间1R37举例例：假定在一个处理机上执行以下五个作业：作业号ABCDE到达时间01234运行时间43524优先数14253(优先数越大代表优先级越高)分别采用FCFS、SJF、RR（时间片＝1），HRRF(响应比高者优先)和四种调度算法时，试做：（1）计算每个作业的周转时间和带权周转时间；（2）计算平均周转时间和平均带权周转时间。382.11.518342.25913④6②3.11618⑤2.6789③4①SJF带权周转时间周转时间完成时间2.83.55.5221带权周转时间914111064周转时间18⑤14④12③7②4①完成时间FCFS42534运行时间43210到达时间平均EDCBA作业号39图3-5qq=1和qq=4时的进程运行情况ABED(b)qq=