3.2.7　处理器调度

1.调度类型

按照操作系统类型分为批处理调度、分时调度和实时调度；按照调度频率分为宏观调度和微观调度；按照调度层次分为高级调度、中级调度和低级调度。

（1）高级调度

高级调度又称为作业调度或宏观调度。作业调度就是按照某种策略从外存的一批作业中选出若干作业，分配内存、外设等资源，为它们建立相应的用户作业进程和为其服务的系统进程，最后将它们的程序和数据调入内存，等待进程调度程序对其进行调度，并在作业完成后做善后处理。可以说，作业调度就是实现作业从后备状态到执行状态的转换，以及从执行状态到完成状态的过渡。

在批处理系统中，需要高级调度将作业分批装入内存；而在分时操作系统和实时操作系统中，不需要高级调度。

（2）中级调度

在采用虚拟存储技术的系统或分时系统中，中级调度尤为重要。它的主要功能是：内存空间紧张时，将一些暂时不能运行的进程从内存换出到外存等待；当内存足够时，再将合适的进程重新换入内存，等待进程调度。

（3）低级调度

低级调度又称为进程调度。该调度的运行频率很高，其调度的优劣直接影响整个系统性能。它的主要功能是根据一定的策略将CPU分派给进程就绪队列中的一个进程。

2.评价调度算法性能的指标

1）CPU利用率：CPU处于忙状态的时间与开机运行总时间的比值。

2）吞吐率：单位时间内CPU处理作业的个数。它是批处理系统评价调度性能的重要指标之一。

3）I/O设备利用率：以I/O为主的进程优先运行，提高CPU与I/O的并行度。

4）响应时间：通常是交互式进程提交一个请求至得到响应的时间间隔。它是分时和实时系统评价调度性能的重要指标之一。

5）周转时间：用户从向系统提交作业开始，直到作业完成的时间间隔。它是批处理系统评价调度性能的重要指标之一。

6）时空代价：选择调度算法时应考虑其所需的时间和空间开销。

一般情况下，应根据设计的总体目标，合理地选择以上指标，从而有利于确定优良的调度算法。

3.作业调度

作业调度程序选择到的作业只是有资格获得处理机的作业，而不一定立刻就能占有CPU并在其上运行。一个已被作业调度程序调度到的作业（或者它相应的进程）何时能真正在处理机上运行，取决于“进程调度”所遵循的调度策略和作业的优先级等性质。

作业调度程序通常作为一个进程在系统中执行，它在系统初始化时被创建，它的主要功能是审查系统是否能满足用户作业的资源要求，按照一定的算法选取作业。

（1）作业的概念

作业是指在一次应用业务处理过程中，从输入开始到输出结束，用户要求计算机所做的有关该次业务处理的全部工作。从系统的角度看，一个作业包括程序、数据和作业说明书。系统根据作业说明书控制程序和数据的执行操作。在批处理系统中，作业是抢占内存的基本单位。

作业步是指作业中要求计算机系统做的一项相对独立的工作。在逻辑上，可以说一个作业是由一系列有序的作业步所组成的。一个作业内的作业步总是相互关联的。每个作业步可能对应一个进程或线程。

在批处理系统中，通常把一批作业或者按用户提交的先后次序，或者按某种优先原则，一次安置在响应的输入系统上，并在系统控制下，一次将它们输入到辅助存储器中，这样就形成了一个作业流。小的计算机系统只有一个作业流，大的系统可能有多个作业流。

（2）作业状态

1）提交状态：从用户把作业交给机房到该作业被选中，进入到输入井为止，这一阶段作业的状态为提交状态。处于提交状态的作业因为信息尚未全部进入系统，所以不能被作业调度所选取。

2）后备状态：从作业进入输入井到该作业被选中，进入主存执行为止，该作业处于后备状态。处于后备状态的作业是由SPOOLing系统输入进程，或者其他输入程序将作业全部信息装入直接存取的后援存储器，然后由“作业注册”程序负责为进入系统的作业建立、填写作业控制块（Job Control Block,JCB），加入后备作业队列中，纳入作业调度程序控制下，随时可以被调入主存执行，这时作业处于后备状态。

3）执行状态：从作业被作业调度程序选中，进入主存并分配了必要的资源，建立了一组相应的进程后，该作业就进入了执行状态。处于执行状态的作业获取了在处理机上运行的资格后，就可以等待进程调度程序的调度，在处理机上执行。

此时根据其进程活动状态又分为3种状态：就绪状态、运行状态和等待状态。到作业计算完成为止，该作业处于执行状态，即作业一被调入主存就处于作业的执行状态。但是，在单CPU多道环境中，同时处于主存中的作业不是只有一个，因此，从宏观上看，它们都处于执行状态；而从微观上，始终只有一个作业获得CPU，处于“运行”状态，其余在主存中的作业，要么处于等待获得“就绪”状态，要么处于因等待某一事件发生的“等待”状态。即在单CPU上运行多个作业时，每一时刻只有一个作业处于运行状态，其他作业可能处于就绪状态，也可能处于等待状态。

4）完成状态：从作业计算完成开始，到善后处理完毕，并退出系统为止，该作业处于完成状态。在该状态中，系统要完成的任务是输出计算结果，归还作业所用过的资源。

（3）作业调度的实现

在系统初始化时，创建作业调度进程。具体实现步骤如下：

1）记录已进入系统的作业情况。通过管理作业控制块实现。作业调度程序根据作业控制块中所记录的作业情况对作业进行调度，也可随时记录作业在运行中的变化。

2）按照必要的调度算法，从后备作业队列中挑选“一批”作业投入主存执行。由于可能有多个作业处在后备作业队列中，而处于执行状态的作业一般都只有有限几个，因此，可按照一定策略从众多后备态作业中选取有限的几个作业投入执行状态，为被选中的作业做好运行前的准备工作。主要包括：为选中的作业建立相应的进程；根据作业中所指出的资源要求，为选中的作业提供所需资源，包括主存空间、外设等。而对于CPU这一关键性资源，作业调度程序只保证被选中的作业具有获得使用CPU的资格，而要真正获得CPU，是由进程调度程序完成的（详见本小节“进程调度”）。

3）作业结束处理。当作业正常结束或者在运行中因某种原因而需要撤出时，作业调度程序要对该作业进行善后处理：将计算结果、作业运行中的有关信息（如运行时间、运行状态）等组织成输出文件，而后由输出程序将其输出到输出井中，等待输出打印；回收该作业的一切资源，如主存空间、外存空间、外部设备等；撤销本作业的所有进程，从现行作业队列中撤销本作业的JCB。

作业调度时机一般是输入井中有一道作业建立时，以及主存中的一道作业运行结束时，系统便立即启动作业调度程序工作。

（4）作业的分类

根据系统对作业处理方式的不同，可以把用户作业分为两类：脱机作业和联机作业。

1）脱机作业：指作业运行时，用户不直接与计算机交互，而由系统自动控制运行的作业。这类作业通常应用在批量处理系统中，所以也叫做批量型作业。

2）联机作业：指在作业运行时，用户通过终端或者控制台键盘上的操作命令，直接与计算机系统交互控制作业运行，又称为交互型作业或终端型作业。

在一个兼有分时和批量处理的系统中，常把联机用户作业称为前台作业，把批量型作业称为后台作业，前者具有较高优先级，可以及时得到响应。

（5）作业控制

作业控制完成的功能包括作业的输入，程序的汇编（编译）及装入，作业在运行过程中出现故障后的处理，作业运行结束后的处理。作业控制方式分为：

1）脱机作业控制：也称为作业的自动控制方式，它是为脱机用户提供的。所谓脱机作业控制，就是用户把自己对作业运行的控制意图，连同程序和操作数据，甚至包括发生故障时的处理手段一起输入到系统中，由系统根据该意图来控制整个作业的运行。脱机作业控制又分为作业控制卡和作业说明书两种形式。

作业控制卡方式是指用户将其操作意图穿在若干张卡片上，以控制作业运行的一种形式；作业说明书方式采用作业控制语言来表达用户对作业的控制意图。

2）联机作业控制：也称为作业的直接控制方式，它是为联机或终端用户提供的。所谓联机作业控制方式，是采用人工会话的方式来控制作业运行的。也就是说，一方面联机用户通过控制台输入设备键入各条操作命令，经系统解释后，控制和监督作业的运行；另一方面，系统也通过相应的设备把作业运行的情况和操作结果通知用户，以便用户根据当前情况决定下一步的行动。

联机控制方式又可以分为键盘命令和会话语言两种方式。

3）分时作业管理：从系统的角度看，分时系统中不存在作业的概念。其原因是，在分时系统中，每个用户分到的时间片有限，用户的程序和数据信息直接输入到内存工作区中，和其他程序一起抢占系统资源投入执行，而不必进入外存输入井等待作业调度程序选择。因此，分时系统没有作业控制表，也没有作业调度程序。

从用户的角度看，分时系统也使用计算机来完成所要求的业务处理过程，所以作业和作业步的概念是存在的。而这只是一种逻辑上的抽象，它只用来描述分时系统的控制过程，并不表示操作系统中包含有相应的数据结构和管理软件。

（6）作业调度算法

作业调度算法的设计目标是尽量提高系统的处理能力，即作业的吞吐量；充分利用系统的资源，尽量使外部设备保持忙碌状态；对所有的作业应公平合理，尽量做到使所有用户都满意；使输入、输出设备得到充分利用。

这些目标往往互相冲突，任何一个调度算法想要同时满足上述目标是不可能的。所以，实际采用的调度算法往往是根据需要而兼顾某些目标。

确定调度算法时应考虑的因素包括：

1）调度算法应与系统的总体设计目标一致（例如，在批处理操作系统中，应尽量提高系统的平均吞吐量；分时操作系统中应保证用户所能忍受的响应时间等）。

2）注意系统资源的均衡使用，使输入、输出繁忙的作业与CPU繁忙的作业搭配运行。

3）应保证进入系统的作业在规定的截止时间内完成，设法缩短作业的平均周转时间。

在批处理系统中，评价一个调度算法性能的优劣，通常用平均周转时间或者平均带权周转时间来衡量。

周转时间是指作业从进入系统直至完成所经历的时间，包括：在作业后备队列中等待时间、被作业调度选中调入内存在就绪队列中的等待时间、被进程调度程序选中、在CPU上的执行时间以及等待事件发生的时间等。作业i的周转时间Ti定义为：

Ti=Tei-Tsi

其中Tei为作业i的完成时间，Tsi为作业i的提交时间。

N个作业的平均周转时间为：

T=（T1+T2+T3+…+Tn）/N

其中，N是被测定作业流中的作业数，Ti是作业流中第i个作业的周转时间。

带权周转时间=作业周转时间/作业实际运行时间，即

Wi=Ti/Tri

N个作业的平均带权周转时间W为：

W=(W1+W2+W3+…+Wn)/N

作业调度使作业以进程的形式进入内存，但要真正获得CPU还需要进程调度或者线程调度。常见的作业调度算法包括：

（1）先来先服务调度算法

先来先服务（First Come First Served,FCFS）调度算法按照作业到达的先后次序进行调度，即按照作业进入系统后备作业队列的先后次序挑选作业进入主存，创建用户进程，分配所需资源，然后送入进程就绪队列。该算法考虑在系统中等待时间长的作业，而不管作业要求运行时间的长短。

（2）最短作业优先调度算法

最短作业优先（Shortest Job First,SJF）调度算法该算法考虑作业的运行时间，总是优先调度预计运行时间最短的作业进入主存。SJF算法的平均作业周转时间短于FCFS算法，但需要预知作业的运行时间。

（3）响应比最高者优先调度算法

响应比最高者优先（Highest Response-Ratio First,HRRF）调度算法在每调度一个作业投入运行时，计算后备作业队列中每个作业的响应比，挑选响应比最高者投入运行。响应比定义为作业周转时间与作业运行时间的估计值的比值。

响应比=周转时间/运行时间

响应比=1+（等待时间/运行时间）

该算法兼顾了短作业与等待时间长的作业，是FCFS与SJF结合的产物。但因为HRRF算法每次需要计算各道作业的响应比而导致一定的时间开销，所以性能略差于SJF算法。

（4）基于优先级的作业调度算法

基于优先级的作业（Highest Priority First,HPF）调度算法系统给每一个作业一个优先级，当一个新的作业被录入或者一个作业步运行结束时，系统调用作业调度程序，从非空队列中的最高优先级开始扫描，挑选满足资源要求的作业步投入运行，在同一优先级内按先来先服务的原则进行调度。

4.进程调度

进程调度的任务是控制、协调进程对CPU的竞争，按照一定的调度算法，使某一就绪进程得到CPU，转换成运行状态。相对于作业调度（高级调度），人们习惯地称进程调度为低级调度。

进程调度分为两种基本方式：“非剥夺”和“剥夺”，又称为“非抢占式”和“抢占式”。

所谓非剥夺调度是指某个进程一旦被执行，则一直执行下去直至结束。而剥夺调度是指一旦出现了比执行进程优先权更高的进程或运行的进程消耗完分给它的时间片，则剥夺正在运行进程的CPU。由此可见，剥夺调度较为复杂。下面是几种常见的进程调度算法：

（1）先来先服务调度算法

先来先服务调度算法（First Come First Served,FCFS）是按照进程进入就绪队列的先后次序进行调度，使其获取CPU，是一种非剥夺式调度算法。

（2）短进程优先调度算法

短进程优先调度算法（Shortest Process First,SPF）是根据进程所需运行时间的长短，从就绪队列中选择运行时间最短的进程，使其获取CPU。SPF算法有利于提高设备利用率，但容易导致“饥饿”问题。SPF是一种非剥夺式调度算法。

（3）最高响应比优先调度算法

最高响应比优先调度算法（Highest Response Ratio First,HRRF）从就绪队列中选择响应比最高的进程，使其获取CPU。HRRF是一种非剥夺式调度算法，性能略差于SPF算法。

（4）优先级调度算法

优先级调度算法（Highest Priority First,HPF）在每个进程的PCB中有一个数字表示优先数，用于标志该进程的优先级。该算法总是选择就绪队列中优先级最高的进程，使其获取CPU。可静态或动态确定优先级。动态优先级使进程的优先级随时间而改变，可以消除饥饿现象。HPF算法可采用“非剥夺”方式，也可以采用“剥夺”方式。

（5）轮转调度算法

轮转调度算法（Round Robin,RR）轮转调度算法又称为环形调度或时间片调度。在该算法中，进程先按先入先出（First Input First Output,FIFO）规则排成一个队列，每次从就绪队列首取出一个进程分配给CPU，并规定一个称为时间片的固定时间单位，当该进程执行完一个时间片后便被剥夺，并被送至就绪队列尾部，等候下一轮调度。如此反复，从而体现了公平性。该算法在进程切换上的开销比较大，与时间片取值大小有一定的关系。RR是一种剥夺式调度算法。

（6）队列调度算法

队列调度算法（Multi Level Queues,MLQ）队列调度算法又称为分类排队算法，是将系统内进程按各自属性分为若干类，由相同的类组织一个就绪队列。每个进程只属于一个就绪队列。通常规定一个调度优先级，当优先级高的队列为空时，再选择下一个优先级队列中的进程，依次类推。每个就绪队列内部又可以采用HPF算法或RR算法。

（7）多级反馈队列调度算法

多级反馈队列调度算法（Multi Level Feedback Queue,MLFQ）又称为反馈循环队列算法或反馈排队算法。它是一种综合了FCFS、RR以及HPF 3种算法的剥夺式调度算法。

系统为N个就绪队列规定不同的优先级，仅当优先级高的就绪队列为空时，才选择优先级次之的就绪队列中的进程。通常，前N-1个队列内部采用RR调度算法，最后一个队列采用FCFS调度算法。队列的优先级依次递减，而时间片的长度依次递增。如果一个进程在规定的时间片内完成，则从系统中撤离，否则被移入优先级次之的就绪队列中。

MLFQ算法是UNIX操作系统采用的一种调度算法之一，它具有较好的性能，提高了设备资源的利用率，减小了系统的开销，对短进程优先处理。但会导致“饥饿”问题。采用某些规则提升等待时间过长的进程的优先级，是解决“饥饿”问题的一种有效方法。

5.UNIX进程调度时机

UNIX进程调度时机实质上只有两个：一个是进程自动放弃处理机时自动转入调度进程；另外一个是在进程由核心态转入用户态时，系统设置了高优先级就绪进程的强迫调度标志。