第5章处理器调度

第第5章章 处理器调度处理器调度引言引言51 三级调度的概念三级调度的概念52 作业调度作业调度53 进程调度进程调度54 常用的调度算法常用的调度算法55 实例分析：实例分析：UNIX进程调度进程调度引言引言 处理器是计算机系统中一个十分重要的资源。随着多道程序设计技术出现，处理器的管理也日趋复杂。对于不同类型的操作系统，处理器的管理方法各不相同。不同的处理器管理方法将为用户提供不同性能的操作系统。因此，根据操作系统目标的不同，处理器的管理策略是不尽相同的。本章将以处理器管理为核心，讨论与处理器调度有关的概念，并介绍常用的调度算法。51 三级调度的概念三级调度的概念 在多道程序系统中，一个作业被提交后，并不一定能立即执行，必须经过处理器调度，方可为其创建进程，分配内存，从而进入执行状态，称为作业调度或高级调度。而作业的执行归结为进程的调度，又称为低级调度。在比较完善的系统中，为了提高内存的利用率，往往还设置了对换调度，即中级调度。511 作业的状态及其转换作业的状态及其转换 作业是用户在一次解题或一个事务处理过程中要求计算机系统所做的工作的集合。作业由用户程序、所需的数据及作业说明书三部分组成。计算机系统完成一个作业过程中所做的一项相对独立的工作称为一个作业步。在多道程序系统中，一个作业在它的生命期内要经历提交、后备、运行和完成四个主要的阶段。511 作业的状态及其转换作业的状态及其转换 n提交状态：提交状态：当用户将自己的作业提交给操作员，操作员通过某种输入方式将用户提交的作业输入到外存上时，称此阶段为作业处于提交状态。作业输入方式通常有5种：u联机输入方式：联机输入方式：该方式大多用在交互式系统中，用户和系统通过交互式会话来输入作业。在联机方式中，外围设备直接和主机相连接，一台主机可连接一台或多台外围设备。u脱机输入方式：脱机输入方式：脱机输入方式利用低档I/O处理器作为外围处理器进行输入处理，提高了主机的资源利用率。511 作业的状态及其转换作业的状态及其转换 u联机输入方式：联机输入方式：该方式大多用在交互式系统中，用户和系统通过交互式会话来输入作业。在联机方式中，外围设备直接和主机相连接，一台主机可连接一台或多台外围设备。u脱机输入方式：脱机输入方式：脱机输入方式利用低档I/O处理器作为外围处理器进行输入处理，提高了主机的资源利用率。511 作业的状态及其转换作业的状态及其转换 u直接耦合方式：直接耦合方式：该方式是把主机和外围低档机通过一个公用的大容量外存直接耦合起来，从而省去了在脱机输入时依靠人工干预来传递给后援存储器的过程。u SPOOLing系统：系统：在SPOOLing系统中，多台外围设备通过通道或DMA器件将主机与外存连接起来，作业的输入过程由主机中的操作系统控制。u网络输入方式：网络输入方式：该方式以上述几种输入方式为基础。当用户需要把在网络中某一台主机上输入的信息传递到同一网络中的另一台主机上进行操作或执行时，就构成了网络输入方式。511 作业的状态及其转换作业的状态及其转换 n后备状态：后备状态：当操作系统为输入并存放在外存输入井上的作业建立一个作业控制块（JCB，Job Control Block）之后，作业就进入了后备状态。作业从建立JCB到被作业调度程序选中运行，所处的状态叫做后备状态。n运行状态：运行状态：作业调度程序从处于后备状态的作业队列中按一定的算法选中一个作业调入内存，并为之建立相应的进程后，由于此时的作业已具有独立运行的资格，如果处理器空闲，便可立即开始执行，称此时的作业进入了运行状态。n完成状态：完成状态：当作业（进程）运行正常完成或异常结束时，便自我终止（正常完成），或被迫终止（异常终止），此时作业便进入完成状态。511 作业的状态及其转换作业的状态及其转换 n作业状态及其转换如下图所示：作业状态及其转换如下图所示：提交状态提交状态后备状态后备状态完成状态完成状态运行状态运行状态512 调度的层次调度的层次 n高级调度：高级调度：高级调度又称作业调度。作业调度程序决定把哪些后备队列中的作业调入内存，并为其创建进程，分配必要的资源，最后将所创建的进程插入就绪队列，以使该作业的进程获得竞争处理器的权利。在批处理系统中或者是操作系统中的批处理部分都配有作业调度。n中级调度：中级调度：中级调度又称交换调度，它的主要功能是按一定的算法在内存和外存之间进行进程对换，其目的是为了使内存紧张的情况得以缓解。交换调度的主要工作是将内存中处于阻塞状态的某些进程换至外存，腾出内存空间以便将外存上已具备运行条件的进程换入内存，准备运行。进程在其整个生命期间可能要经历多次换进换出，在分时系统中常采用交换调度。512 调度的层次调度的层次 n低级调度：低级调度：低级调度又称进程调度。其主要任务是按照某种策略和方法选取一个处于就绪状态的进程占用处理器。它决定就绪队列中哪个进程先获得处理器，然后再由分派程序执行将处理器分配给进程的操作。513 调度模型调度模型 从上述操作系统的调度类型可知，虽然操作系统的调度机制不尽相同，有的操作系统仅设有低级调度，有的操作系统则拥有高级调度和低级调度，有的操作系统三级调度一应俱全。但是操作系统中的任何一种调度都涉及进程队列，因此根据操作系统的不同性能，一般有三种相应的调度队列模型。512 调度的层次调度的层次 n一级调度队列模型：一级调度队列模型：一级调度模型仅设置了进程调度。在这种调度模型中，用户输入的命令和数据都直接送入内存。操作系统会为每一个作业建立一个或多个进程，并将它们插入就绪队列，然后按照时间片轮转方式进行调度。一级调度队列模型如下图所示：512 调度的层次调度的层次 就绪队列就绪队列阻塞队列阻塞队列进程调度进程调度时间片完时间片完事件发生事件发生等待事件等待事件交互用户交互用户进程完成进程完成512 调度的层次调度的层次 n二级调度队列模型：二级调度队列模型：在二级调度队列中，不仅有进程调度，还有作业调度。作业调度从外存中选择一批作业调入内存，为其创建进程并送入就绪队列。同时，当操作系统任务较多时，阻塞队列有可能很长。为了提高执行效率，通常设置若干个阻塞队列，不同队列对应于引起进程阻塞的不同原因。二级调度队列模型如下图所示：512 调度的层次调度的层次：后备作业队列等待事件2阻塞队列2就绪队列事件1发生等待事件1阻塞队列1时间片完事件2发生等待事件n阻塞队列n事件n发生作业调度进程调度：512 调度的层次调度的层次 n三级调度队列模型：三级调度队列模型：三级调度队列模型同时拥有作业调度，交换调度和进程调度。在引入交换调度之后，可以把处于静止就绪和静止阻塞的进程从内存交换到外存上，以使内存紧张的状况得以缓解。三级调度队列模型如下图所示：512 调度的层次调度的层次 交换调度(外存)进程完成后备作业队列就绪队列静止就绪队列时间片完等待事件阻塞队列n事件发生作业调度静止阻塞队列进程调度52 作业调度作业调度 只有批处理系统才必须具有作业调度。在分时系统和实时系统中都没有作业调度的概念。因为在分时系统中，由于要进行人机交互，系统必须能及时响应，为此应把用户从终端输入的作业直接送入内存而不是建立在外存上，因此，不再需要专门用于把作业从外存调入内存的作业调度过程。对于实时系统中的实时任务，因为通常对其响应的时间更为严格，故也不需要作业调度。521 作业调度的功能作业调度的功能 作业调度主要是完成作业从后备状态到运行状态的转变，以及从运行状态到完成状态的转变。其主要功能如下：n记录系统中各作业的状况记录系统中各作业的状况 ：作业调度程序要能挑选出一个作业投入运行，并且在运行中对其进行管理。它必须掌握作业在各个状态，包括运行阶段的有关情况。为此，系统为每个作业建立一个作业控制块JCB（Job Control Block）来记录这些有关信息。JCB的主要内容包括作业名、作业类型、资源要求、当前状态、资源使用情况以及该作业的优先级等。与系统感知进程存在时要通过进程控制块PCB一样，系统通过JCB而感知作业的存在。521 作业调度的功能作业调度的功能 n从后备队列中挑选出一部分作业投入执行从后备队列中挑选出一部分作业投入执行：作业调度程序根据选定的调度算法，从后备作业队列中挑选出若干作业去投入运行。n为被选中的作业做好运行前的准备工作为被选中的作业做好运行前的准备工作：作业调度程序为选中的作业建立相应的进程，并为这些进程分配它们所需要的全部资源，如分配给它们内存、外存、外设等。n在作业运行结束时做善后处理工作在作业运行结束时做善后处理工作：善后处理主要是输出作业管理信息，例如执行时间等。再就是回收该作业所占用的资源，撤消与该作业有关的全部进程和该作业的作业控制块等。522 作业调度的目标与性能衡量作业调度的目标与性能衡量 n面向系统的准则面向系统的准则：不同的操作系统有不同的要求，为了满足系统功能的要求，在设计操作系统时，应遵循一些准则，最重要的有以下几点：u吞吐量大吞吐量大：这是用来评价批处理系统的重要指标。吞吐量是单位时间内完成的作业数，它与批处理作业的平均长度有着密切关系。但作业调度的方式和算法，对吞吐量的大小也将产生较大的影响。u CPU利用率高利用率高：对于大中型多用户系统，由于CPU价格十分昂贵，所以CPU的利用率成为衡量大中型系统性能的十分重要的指标。而调度方式和算法，对CPU的利用率起着十分重要的作用。522 作业调度的目标与性能衡量作业调度的目标与性能衡量 u各类资源的平衡利用各类资源的平衡利用：在大中型系统中，有效地利用各类资源（如CPU、内存、外存和I/O设备等），也是一个重要指标。对于微机和某些实时系统，该准则也不那么重要。522 作业调度的目标与性能衡量作业调度的目标与性能衡量 n面向用户的准则面向用户的准则：为了满足用户对操作系统的要求，应满足如下准则：u周转时间短周转时间短：周转时间是评价批处理系统的一个重要性能指标。作业周转时间是指从作业提交给系统开始，到作业完成为止的时间间隔。p平均周转时间：平均周转时间：计算机系统为使大多数用户对周转时间感到满意，引入了平均周转时间T的评价指标。对于有n个作业的系统，平均周转时间可描述为：)(1111ininiiiTsTenTnT522 作业调度的目标与性能衡量作业调度的目标与性能衡量 式中，n是系统中的作业个数，Ti是第i个作业的周转时间，Tei是作业的完成时间，Tsi是作业的提交时间。p平均带权周转时间：周转时间没有考虑作业的运行时间，不能准确反映作业周转时间与作业运行时间的关系。为此引入了平均带权周转时间。一个作业的带权周转时间定义为作业的周转时间与系统为它提供的实际服务时间之比，即W=Ti/Tri。n个作业的平均带权周转时间为：式中，Tri是系统为作业i提供的实际服务时间。niiiTrTnW11522 作业调度的目标与性能衡量作业调度的目标与性能衡量 u响应时间快响应时间快：响应时间是评价分时系统的性能指标。它是从用户通过键盘提交一个请求开始，直至系统首次产生响应为止的时间，或者说直到屏幕显示结果为止的时间。u截止时间的保证：截止时间的保证：在实时系统中，截止时间是衡量系统性能好坏的重要指标。截止时间是指某任务必须完成的最迟时间。对于严格的实时系统，其调度方式和调度算法必须保证这一点，否则将可能引起难以预料的后果。u优先权准则：优先权准则：在批处理、分时、实时和多模式系统中，都可使用优先权准则，以便让那些紧急的作业得到及时的处理。在要求较严格的场合，往往还需要选择抢占调度方式，才能保证紧急作业得到及时的处理。53 进程调度进程调度 进程调度的任务是控制、协调多个进程对处理器的竞争，即按照一定的调度算法从就绪队列中选中一个进程，并把处理器的使用权交给被选中的进程。操作系统为了对进程进行有效的监控，需要维护一些与进程相关的数据结构，记录所有进程的运行情况，并在进程让出处理器或调度程序剥夺运行状态进程占用处理器时，选择适当的进程分派处理器，完成上下文的切换。我们把操作系统内核中完 成 这 些 功 能 的 部 分 称 为 进 程 调 度 程 序（scheduler），它所使用的算法称为调度算法（scheduling algorithm）。53 进程调度进程调度 进程调度的任务是控制、协调多个进程对处理器的竞争，即按照一定的调度算法从就绪队列中选中一个进程，并把处理器的使用权交给被选中的进程。操作系统为了对进程进行有效的监控，需要维护一些与进程相关的数据结构，记录所有进程的运行情况，并在进程让出处理器或调度程序剥夺运行状态进程占用处理器时，选择适当的进程分派处理器，完成上下文的切换。我们把操作系统内核中完 成 这 些 功 能 的 部 分 称 为 进 程 调 度 程 序（scheduler），它所使用的算法称为调度算法（scheduling algorithm）。53 1 进程调度的功能进程调度的功能 n进程调度的功能进程调度的功能：作为进程调度的准备，进程管理模块必须将系统中各进程的执行情况和状态特征记录在各进程的PCB中，作为管理进程的依据。n选择占有处理器的进程选择占有处理器的进程：进程调度的主要功能是按照一定的策略选择一个处于就绪状态的进程，使其获得处理器运行。根据不同的系统设计目标，有各种各样的选择策略。n进行进程上下文的切换进行进程上下文的切换：进程的上下文是进程执行活动全过程的静态描述。一个进程的上下文包括进程的状态、有关变量和数据结构的值、机器寄存器的值和PCB以及有关程序、数据等。一个进程的执行是在进程的上下文中执行的。当正在运行的进程由于某种原因要让出处理器时，系统要做进程上下文切换，以使另一个进程得以运行。53 2 进程调度方式进程调度方式 n非剥夺调度方式非剥夺调度方式：调度程序一旦把处理器分配给某进程，该进程就将一直运行下去，只有当进程完成或发生其事件而阻塞时，系统才把处理器分配给另一进程的调度方式称为非剥夺调度，也称非抢占方式（nonpreemptive scheduling）方式。在此调度方式下，系统不得以任何理由剥夺现行进程所占用的处理器。该调度方式的优点是简单、系统开销小，但却可能导致系统性能的恶化，表现为：u当一个紧急任务到达时，不能立即投入运行，以至于延误时机；u若干个后到的短作业，需要等待先到的长作业运行完毕后才能运行，致使短作业的周转时间较长。53 2 进程调度方式进程调度方式 n剥夺调度方式剥夺调度方式：进程的另一种调度方式是剥夺调度方式，或称抢占方式（preemptive scheduling），这是指进程正在运行时，系统可根据某种原则，剥夺已分配给它的处理器，并将处理器再分配给其他进程的一种调度方式。剥夺的原则有：u优先权原则。优先权高的进程可以剥夺优先权低的进程的运行；u短进程优先原则。短进程到达后可以剥夺长进程的运行；u时间片原则。一个时间片运行完后重新调度。53 3 进程调度的时机进程调度的时机 进程调度发生的时机，与引起进程调度的原因以及进程调度的方式有关。引起进程调度的原因有以下几类：u正在执行的进程执行完毕或由于某种错误而异常中止。u执行中的进程自己调用阻塞原语将自己阻塞起来而进入等待状态（如等待某一事件而事件未发生或调用了wait原语而资源不足等）。u分时系统中的时间片用完。u在执行完系统调用等系统程序后返回用户进程时，这时可看作系统进程运行完毕，从而可选择一新的用户进程执行。53 3 进程调度的时机进程调度的时机 u在基于优先级调度的策略时，就绪队列中的某进程的优先级变得高于当前运行进程的优先级，从而也将引发进程调度。以上14条是在剥夺和不可剥夺情况下引起进程调度的原因，而第5条是在剥夺情况下引起调度的原因。54 常用的调度算法常用的调度算法 调度算法是指：根据系统的资源分配策略所规定的资源分配算法。对于不同的系统和系统目标，通常采用不同的调度算法。目前存在着多种调度算法，有的算法适用于作业调度，有的算法适用于进程调度，但也有些调度算法，既可用于作业调度，也可用于进程调度。54 1 先来先服务调度算法先来先服务调度算法 n实现方法：实现方法：先来先服务FCFS（First Come First Serve，FCFS）调度算法是一种最简单的调度算法。其基本思想是：将用户作业或就绪进程按提交或变为就绪状态的先后次序排成队列，调度时总是选择队首作业或进程投入运行。该算法既可用于作业调度，也可用于进程调度。n优缺点：优缺点：虽然FCFS调度算法易于实现，表面上也公平，但服务质量不佳，对短作业用户不公平。n使用场合：使用场合：FCFS算法很少作为进程调度的主调度算法，但常作为一种辅助调度算法。54 1 先来先服务调度算法先来先服务调度算法 【例5-1】假设有五道作业，它们的进入时间和运行时间由下表给出：作业号进入时间运行时间104213326432544在不剥夺方式的单道环境下，采用FCFS调度算法，试说明它们的调度顺序，并计算在该种调度算法下的平均周转时间和平均带权周转时间。54 1 先来先服务调度算法先来先服务调度算法 解：采用FCFS调度算法，调度顺序是1，2，3，4，5五道作业的执行时间、完成时间和周转时间如下表所示：作业号进入时间 运行时间 开始执行时间完成时间 周转时间10404421347632671311432131512544151915平均周转时间T（4+6+11+12+15）/5=9.8小时平均带权周转时间W=(4/4+6/3+11/6+12/2+15/4)/5=2.9254 2 短作业（进程）优先调度算法短作业（进程）优先调度算法 n实现方法：实现方法：SJF调度算法是从后备队列中选择一个或若干个估计运行时间最短的作业，将它们调入内存运行。该调度算法可以照顾到实际上在所有作业中占很大比例的短作业，使它们能比长作业优先执行。n优缺点：优缺点：这种算法能有效地降低作业的平均周转时间，提高系统的吞吐量，但是，它们存在着不容忽视的缺点：u该算法对长作业不利。由于系统状态是动态的，如果不断地有短作业进入，则可能导致长作业长时间得不到响应；u该算法未考虑作业的紧迫程度；54 2 短作业（进程）优先调度算法短作业（进程）优先调度算法 u由于作业（进程）的长短只是根据用户所提供的估计运行时间而定，而用户又可能会有意或无意地缩短其作业的估计执行时间，致使该算法不一定能真正做到短作业优先调度。54 2 短作业（进程）优先调度算法短作业（进程）优先调度算法 【例5-2】仍采用例5-1的题目，在不剥夺方式的单道环境下，采用SJF调度算法，试说明它们的调度顺序，并计算在该种调度算法下的平均周转时间和平均带权周转时间。作业号进入时间运行时间10421332643254454 2 短作业（进程）优先调度算法短作业（进程）优先调度算法解：采用SJF调度算法，调度顺序是1，4，2，5，3五道作业的执行时间、完成时间和周转时间如下表所示：作业号进入时间 运行时间 开始执行时间完成时间 周转时间1040444324632136985449139326131917平均周转时间T（4+3+8+9+17）/5=8.2小时平均带权周转时间W=(4/4+3/2+8/3+9/4+17/6)/5=2.0554 3 时间片轮转调度算法时间片轮转调度算法 n实现方法：实现方法：时间片轮转法RR（Round Robin）是将CPU的处理时间分成固定大小的时间片，且采用剥夺调度方式。在简单轮转法中，系统将所有就绪进程按先进先出规则排成一个环形队列，把CPU分配给队首进程，并规定它执行一个时间片。当时间片用完时，系统剥夺该进程的运行并将它送到就绪队列末尾，重新把处理器分配给就绪队列中新的队首进程。54 3 时间片轮转调度算法时间片轮转调度算法 【例5-3】假设有五道作业，它们的进入时间和运行时间由下表给出：作业号进入时间运行时间A04B12C25D33E43画出当时间片分别为q=1和q=4时的调度图，并计算该种调度算法时的平均周转时间和平均带权周转时间。54 3 时间片轮转调度算法时间片轮转调度算法 时刻运行进程 排队进程时刻运行进程 排队进程01A910DAEC12BA1011AECD23ACB1112ECD34CBDA1213CDE45BDAEC1314DEC56DAEC1415EC67AECD1516C78ECDA1617C89CDAE解：当时间片q=1时，列出下表，找出运行序列：54 3 时间片轮转调度算法时间片轮转调度算法 根据上表，画出调度图如下图所示：ABCDE0123456789111012 13 14 15 16 17 54 3 时间片轮转调度算法时间片轮转调度算法 从上图得出的五道作业的完成时间和周转时间如下表所示：作业号进入时间运行时间完成时间周转时间A041111B1254C251715D331411E431511平均周转时间T（11+4+15+11+11）/5=10.4 平均带权周转时间W=(11/4+4/2+15/5+11/3+11/3)/5=3.0254 3 时间片轮转调度算法时间片轮转调度算法 当时间片q=4时，调度图如下图所示：ABCDE0123456789111012 13 14 15 16 17 54 3 时间片轮转调度算法时间片轮转调度算法 如果一个作业的时间片没有用完，剩余时间可由下一个作业使用。从上图得出的五道作业的完成时间和周转时间如下表所示：作业号进入时间运行时间完成时间周转时间A0444B1265C25119D331411E431713平均周转时间T（4+5+9+11+13）/5=8.4 平均带权周转时间W=(4/4+5/2+9/5+11/3+13/3)/5=2.66 54 4 高优先权优先调度算法高优先权优先调度算法 n实现方法：实现方法：为了使紧急的作业得到优先调度，在许多系统中，每个作业或进程都被指定一个优先级，调度程序总是选择相应队列中具有最高优先权的作业或进程，这就是高优先权优先（First Priority First，FPF）调度算法。n优先权确定方法：优先权确定方法：u静态优先权：静态优先权：静态优先权是在创建进程时确定的，在整个运行期间不再改变。基于静态优先权的调度算法实现简单，系统开销小。但由于静态优先权一旦确定之后，直到运行结束为止始终保持不变，从而使优先级低的进程长时间得不到调度。54 4 高优先权优先调度算法高优先权优先调度算法 u动态优先权：动态优先权：动态优先权是基于某种原则，使进程的优先权随时间而改变，例如在就绪队列中的进程，其优先权以速度a增加，若再令正在执行进程的优先权以速度b下降，便可防止一个长作业长期垄断处理器这种情况的发生。n优先数与优先级的关系优先数与优先级的关系；在UNIX和许多其他的系统中，优先级数值越大，表示的进程优先权越低；而在某些系统中的用法则刚好相反，如Windows，大数值表示高优先级。54 4 高优先权优先调度算法高优先权优先调度算法 【例5-4】假设有五道作业，它们的进入时间、运行时间和静态优先数由下表给出：作业号进入时间运行时间优先数10462134326243255443假定优先数越高，优先级越低，系统采用静态FPF调度算法，且不可剥夺，试计算采用该调度算法时的平均周转时间和平均带权周转时间。54 4 高优先权优先调度算法高优先权优先调度算法 解：解：采用静态FPF调度算法，调度顺序是1，3，5，2，4。五道作业的执行时间、完成时间和周转时间如下表所示：作业号进入时间运行时间开始执行时间完成时间周转时间1040443264108544101410213141716432171916平均周转时间T（4+8+10+16+16）/5=10.8小时平均带权周转时间W=(4/4+8/6+10/4+16/3+16/2)/5=3.63 54 5 最高响应比优先调度算法最高响应比优先调度算法 n响应比计算公式：响应比计算公式：最高响应比优先（Highest Response_ratio Next，HRN）调度算法是FCFS和SJF的一种折衷。HRN调度算法同时考虑每个作业的等待时间和估计的运行时间。设响应比为R，则作业p的响应比为：TWTTWRp1式中，W为作业的等待时间，T为作业的估计运行时间。54 5 最高响应比优先调度算法最高响应比优先调度算法 n算法思想：算法思想：在当前进程完成或被阻塞时，选择Rp值最大的就绪进程投入运行。n优点：优点：即考虑了作业的等待时间，又照顾了短作业。54 5 最高响应比优先调度算法最高响应比优先调度算法 【例5-4】假设有五道作业，它们的进入时间、运行时间由下表给出：系统采用HRN调度算法，试计算采用该调度算法时的平均周转时间和平均带权周转时间。作业号进入时间运行时间106214324431543 54 5 最高响应比优先调度算法最高响应比优先调度算法 解：解：采用HRN调度算法，应在每次调度时计算各作业的响应比，选择响应比高的作业进入运行状态。在时刻0，由于只有作业1，因此调度作业1投入运行，作业1运行到时刻6结束，在时刻6时进行调度；在时刻6，计算各作业的响应比为：作业2的响应比：R2=1+（6-1）/4=2.25 作业3的响应比：R3=1+（6-2）/4=2 作业4的响应比：R4=1+（6-3）/1=4 作业5的响应比：R5=1+（6-4）/3=1.67 选择作业4投入运行，作业4运行到时刻7时结束，在时刻7时进行调度；54 5 最高响应比优先调度算法最高响应比优先调度算法 在时刻7，计算各作业的响应比为：作业2的响应比：R2=1+（7-1）/4=2.5 作业3的响应比：R3=1+（7-2）/4=2.25 作业5的响应比：R5=1+（7-4）/3=2 选择作业2投入运行，作业2运行到时刻11时结束，在时刻11时进行调度；作业3的响应比：R3=1+（11-2）/4=3.25 作业5的响应比：R5=1+（11-4）/3=3.33 选择作业5投入运行，作业5运行到时刻14时结束，在时刻14时进行调度；在时刻14，只有作业3等待运行，因此五道作业的调度顺序是1，4，2，5，3。54 5 最高响应比优先调度算法最高响应比优先调度算法 五道作业的执行时间、完成时间和周转时间如下表所示：作业号进入时间运行时间（小时）开始执行时间完成时间周转时间10606643167421471110543111410324141816平均周转时间T（6+4+10+10+16）/5=9.2小时平均带权周转时间W=(6/6+4/1+10/4+10/3+16/4)/5=2.97 546 多级队列调度算法多级队列调度算法 多级队列调度算法（Multiple-level Queue，MQ）的基本思想是引入多个就绪队列，通过各队列的区别对待，达到一个综合的调度目标。在多级队列调度算法中，根据作业或进程的性质或类型的不同，将就绪队列再分成若干个子队列，每个作业固定归入一个队列，例如，系统进程、用户交互进程、批处理进程等不同队列。不同队列可有不同的优先级、时间片长度、调度策略等。547 多级反馈队列调度算法多级反馈队列调度算法 多级反馈队列（Round Robin with Multiple Feedback，RRMF）调度算法是时间片轮转算法和优先级调度算法的综合和发展。在多级反馈队列调度算法中，通常设置多个就绪队列，并赋予各队列不同的优先级。如队列1的优先级最高，然后逐级降低。每个队列的执行时间片长度也不同，如规定优先级越低则时间片越长。547 多级反馈队列调度算法多级反馈队列调度算法 多级反馈队列调度算法如下图所示：第一级队列（FIFO）完成第二级队列（FIFO）完成第n级队列（FIFO）完成：55 实例分析：实例分析：UNIX进程调度进程调度 UNIX System V的进程调度涉及调度时机、调度标记设置、优先数计算、调度的实现等。下面分别说明。551 调度时机调度时机 UNIX System V在以下5种情况之一发生时进行进程调度：u现行进程自己调用sleep或wait等进入睡眠状态时；u现行进程调用exit自我终止时；u现行进程的时间片到期且优先级低于其它就绪进程时；u现行进程在完成中断和陷入处理后返回用户态时，它的优先级已低于其它就绪进程或者调度标记被置位；u现行进程从系统调用执行结束后返回用户态时，它的优先级已低于其它就绪进程或者调度标记被置位。552 调度标记设置调度标记设置 runrun是要求进行进程调度时的标记。若wakeup，setrun以及setpri（设置优先级）命令发现某进程的优先级高于现行进程时，置runrun为1。另外在秒中断处理过程中也将检查各就绪进程的优先级，发现优先级高于现行进程时，同样置runrun为1。553 优先数计算优先数计算 传统的UNIX System V采用动态优先数调度策略，优先数越大优先级越低。调度程序从内存就绪队列中选取优先数最小的进程作为上行进程。优先数基于进程类型和运行历史，计算公式如下：NZEROnicepPUSERCPUpprip_2_其中，PUSER和NZERO分别取常数25和20，称它们为基本用户优先数的阈值，p_CPU为进程最近一次使用CPU的时间。当进程使用CPU时，系统每个时钟周期对该进程的p_CPU加1，该值最多可达80。此外，秒中断时对p_CPU执行除以2的衰减操作。这样，如果系统的时钟周期为16.667ms的话，则遇秒中断时p_CPU将由60变为30。553 优先数计算优先数计算p_nice是系统允许用户使用nice系统调用影响进程优先数的偏移值，范围在040之间。但一旦设置后，普通用户只能作递增修改。554 调度的实现调度的实现 UNIX 系统的进程调度是由swtch过程实现的，swtch过程是进程0的一部分。首先，首先，调度程序把现行进程的上下文（主要是寄存器上下文和栈指针）保存到核心栈或user结构内的u_rsav，u_pcb字段中，这是由过程save（u.u_rsav）完成的。其次，其次，按计算优先数的公式从内存就绪队列中寻找优先级最高的进程作为上行进程。若内存就绪队列中没有这样的进程存在，就调用空闲进程等待某进程变成就绪状态。清除runrun标记。最后，最后，调用resume过程恢复上行进程的上下文，恢复核心栈或user结构内的u_rsav及u_pcb，从而使上行进程变成现行进程。