处理机调度

在多道程序环境下内存中存在着多个进程，而计算机的 CPU 资源时有限的，这就要求系统能按某种算法动态地将处理机分配给进程。调度的实质是一种资源分配，处理机调度是对处理机资源进行分配。分配处理机是由处理机调度程序完成的，系统的运行效率如何在很大程度上都取决于处理机调度性能。

处理机调度的层次

一个作业从提交到获得处理机执行，直至作业运行完毕，可能需要经历多级处理机调度。

高级调度

高级调度(High Level Scheduling)又称长程调度或作业调度，调度对象是作业，方向是从外存到内存。主要功能是根据某种算法，决定将外存上处于后备队列中的哪几个作业调入内存，为它们创建进程、分配必要的资源，并将它们放入就绪队列。放入就绪队列意味着作业获取竞争 CPU 的权利，调入时建立相对的 PCB，调出时撤销 PCB。
作业调度的频率较低，一般是几分钟发生一次，进行作业调度时调度程序必须决定操作系统可以接纳多少个作业。每次接纳的作业数量取决于多道程序的并发程度，当同时运行的作业太多时可能会影响操作系统的处理效率，当同时运行的作业太少时，又会导致系统资源利用率低下。

中级调度

中级调度(Intermediate Scheduling)又称为内存调度，方向是从外存到内存，引入的目的是为了提高内存利用率和系统的吞吐量。主要功能是把那些暂时不能运行的进程挂起，调至外存等待。当它们已具备运行条件且内存又稍有空闲时，通过某种算法将进程再重新调入内存，并修改其状态为就绪状态。

低级调度

低级调度(Low Level Scheduling)又称为进程调度或短程调度，调度的对象是进程(内核级线程)，方向是从内存到 CPU。主要功能是根据某种算法，决定就绪队列中的哪个进程应获得处理机，并由分派程序将处理机分配给被选中的进程。
进程调度的运行频率很高，一般每隔几秒钟就要发生一次。进程调度是最基本的一种调度，在多道批处理、分时和实时三种类型的 OS 中，都必须配置这级调度。

调度算法效率指标

资源利用率

调度要追求较高的资源李永禄，让系统中的 CPU 和资源尽可能处于忙碌状态。

平均周转时间

周转时间是指从作业被提交给系统开始，到作业完成为止的这段时间间隔(称为作业周转时间)，它包括四部分时间：作业在外存后备队列上等待(作业)调度的时间、进程在就绪队列上等待进程调度的时间、进程在 CPU 上执行的时间、以及进程等待 I/O 操作完成的时间。

使用带权周转时间，能更清晰地描述各进程在其周转时间中，等待和执行时间的具体分配状况，即作业的周转时间 T 与系统为它提供服务的时间 Ts 之比。

调度需要让作业周转时间和平均周转时间尽可能短，这样可以提高资源利用率并减少等待时间。

吞吐量

对于调度而言，吞吐量主要考量的是单位时间内完成了多少作业，调度需要追求较高的系统吞吐量。

等待和响应时间

等待时间是进程或作业处于等待 CPU 的状态时间之和，对于进程等待时间是进程创建以后等待被服务的时间，对于作业等待时间在外存后背队列中等待的时间加上调入内存后创建进程等待被服务的时间之和。
响应时间是用户提交请求后，到首次产生响应所用的时间。无论是等待时间还是响应时间，都是越短越好。

调度的目标

1. 运行效率高；
2. 公平性：进程都获得合理的 CPU 时间，不会发生进程饥饿现象；
3. 平衡性：使系统中的 CPU 和各种外部设备都能经常处于忙碌状态；

4. 策略强制执行：对所制订的策略要准确地执行。

   作业调度

   作业

   在多道批处理系统中，作业是用户提交给系统的一项相对独立的工作。作业包含了程序、数据、作业说明书，系统根据该说明书来对程序的运行进行控制。用户提交的作业通过输入设备输入到磁盘存储器，并保存在一个后备作业队列中，再由作业调度程序将其从外存调入内存。
   在作业运行期间，每个作业都必须经过若干个加工步骤才能得到结果。每一个加工步骤称为一个作业步，一个典型的作业可分成编译、链接装配和运行 3 个作业步。为了管理和调度作业，每个作业设置了一个作业控制块 JCB，其中保存了系统对作业进行管理和调度所需的全部信息。

   作业运行的阶段

   当一个作业进入系统时，由“作业注册”程序为该作业建立一个作业控制块 JCB，再根据作业类型将它放到相应的作业后备队列中等待调度。调度程序依据一定的调度算法来调度，被调度到的作业将被装入内存。在作业运行期间，系统就按照 JCB 中的信息和作业说明书对作业进行控制。当一个作业执行结束时，系统中的“终止作业”程序将会回收作业控制块和所有资源，并将作业运行结果信息形成输出文件后输出作业撤销该作业控制块。作业从进入系统到运行结束，通常需要经历以下三个阶段，每种阶段都对应一种状态。

5. 收容阶段：用户提交的作业输入到硬盘上，为该作业建立 JCB 并放入作业后备队列中，此时作业的状态为“后备状态”；

6. 运行阶段：当作业被作业调度选中后，分配必要的资源和建立进程并将它放入就绪队列，此时作业的状态为“运行状态”；
7. 完成阶段：当作业运行完成、或发生异常情况而提前结束时，系统负责回收已分配的资源，此时作业的状态为“完成状态”。

   作业调度的任务

   作业调度的主要任务是根据 JCB 中的信息，检查系统中的资源能否满足作业对资源的需求，按照一定的调度算法从外存的后备队列中选取某些作业调入内存。为它们创建进程、分配必要的资源，再将新创建的进程排在就绪队列上等待调度。作业调度需要考虑允许多少个作业同时在内存中运行，以及应选择后备队列中的哪些作业调入内存 。

   作业调度算法

   先来先服务

   先来先服务(first-come first-served，FCFS)调度算法是最简单的调度算法，可用于作业调度和进程调度。作业调度时，系统将按照作业到达的先后次序来进行调度，从后备作业队列中选择几个最先进入该队列的作业，将它们调入内存并分配资源和创建进程，放入就绪队列。进程调度时，每次调度是从就绪的进程队列中选择一个最先进入该队列的进程，为之分配处理机运行。
   FCFS 算法是从公平角度考虑的非抢占式算法，不会导致饥饿，虽然在单处理机系统中已很少作为主调度算法，但经常把它与其它调度算法相结合使用。

   短作业优先

   在实际情况中，短作业(进程)占有很大比例，而长进程的存在可能会导致大量短进程无法即使执行。短作业优先(short job first，SJF)的调度算法以作业的长短来计算优先级，作业运行时间越短其优先级越高，SJF 算法可以用于作业调度和进程调度。
   SJF 调度算法对于 FCFS 算法有明显的改进，但仍然存在一些缺点。SJF 算法必须预知作业的运行时间，但是往往很难准确估计作业的运行时间。SJF 算法会使长作业的周转时间会明显地增长，甚至可能出现饥饿现象。同时 SJF 算法完全未考虑作业的紧迫程度，不能保证紧迫性作业被及时处理。

   优先级调度算

   优先级调度算法是基于作业的紧迫程度来考虑，可用于作业调度和进程调度。调度算法是根据外部赋予作业相应的优先级进行调度，这样就可以保证紧迫性作业优先运行，但是这就要求对作业都预先分配好优先级。

   高响应比优先调度算法

   FCFS 算法只考虑了作业的等待时间，而忽视了作业的运行时间，SJF 算法只考虑作业的运行时间，而忽视了作业的等待时间。高响应比优先调度算法(Highest Response Ratio Next，HRRN)将作业的等待时间和运行时间综合考虑，既让短作业能尽快执行，又不致使长作业的等待时间过长。
   高响应比优先算法引入一个动态优先级，优先级随等待时间延长而增加，这将使长作业的优先级在等待期间不断地增加。动态优先级的计算公式为：
   

   进程调度

   进程调度的任务

   在进行调度时首先需要保存当前进程的处理机的现场信息，如程序计数器、多个通用寄存器中的内容等。然后调度程序按某种算法从就绪队列中选取一个进程，将其状态改为运行状态，并准备把处理机分配给它。最后由分派程序把处理器分配给该进程，此时需要将选中进程的 PCB 内有关处理机现场的信息装入处理器相应的各个寄存器中，把处理器的控制权交予该进程，让它从上次的断点处恢复运行。
   狭义的进程调度指指就绪队列中选择一个要运行的程序，进程切换是一个进程让出 CPU 让另一个进程使用，广义的进程调度包括了上述 2 个过程。

   进程调度的机制

   进程调度机制的示意图如下，需要有排队器、分配器和上下文切换器 3 个基本部分。
   

进程调度的方式

非抢占方式

非抢占方式(Nonpreemptive Mode)是早期的调度方式，只允许进程主动放弃 CPU，也就是直至该进程完成或被阻塞时才把处理机分配给其它进程。这种调度方式的优点是实现简单，系统开销小，适用于大多数的批处理系统，但不能用于分时系统和大多数实时系统。

抢占方式

抢占方式(Preemptive Mode)允许调度程序根据某种原则暂停某个正在执行的进程，将已分配给该进程的 CPU 重新分配给另一进程。抢占方式最大的优点是可以防止一个长进程长时间地占用处理机，以确保处理机能为所有进程提供更为公平的服务。抢占必须遵循一定的原则，主要有：

1. 优先权原则：允许优先级高的新到进程抢占当前进程的处理机；
2. 短进程优先原则：允许新到的短进程可以抢占当前长进程的处理机；
3. 时间片原则：当正在执行的进程的一个时间片用完后，便停止该进程的执行，重新进行调度。

   进程调度算法

   轮转调度算法

   基于时间片的轮转(round robin，RR)调度算法是一种基本的调度算法，是一种抢占式的算法。系统将所有的就绪进程按 FCFS 策略排成一个就绪队列，系统每隔一定时间就激活进程调度程序进行调度，把 CPU 分配给队首进程并其执行一个时间片。
   需要调度的时机有 2 种，第一种是在时间片尚未用完时进程已经完成运行，就立即激活调度程序将它从就绪队列中删除。第二种是在一个时间片用完时，计时器中断处理程序被激活，调度程序将把它送往就绪队列的末尾。由于当前进程已经进入队尾，队列头的新进程将会被调度并执行一个时间片。每个进程每次仅运行一个时间片，如果就绪队列上有 n 个进程，则每个进程每次大约都可获得 1/n 的处理机时间。
   时间片的大小对系统性能有很大的影响，若选择很小的时间片，会导致频繁地执行进程调度和进程上下文的切换。
   
   若时间片选择得太长，每个进程可能都能在一个时间片内完成，设置时间片就没有意义了。
   
   时间片大小最好是略大于一次典型的交互所需要的时间，使大多数交互式进程能在一个时间片内完成。

   优先级调度算法

   在时间片轮转调度算法中，系统中所有进程的优先级是相同的，但是实际情况下进程的优先级不同。优先级进程调度算法是把处理机分配给就绪队列中优先级最高的进程，抢占式的实现是把处理机分配给就绪队列中优先级就不打断。抢占式的实现是把处理机分配给优先级最高的进程后，执行期间若出现了另一个其优先级更高的进程，调度程序就将处理机分配给新到的优先级最高的进程。
   优先级调度算法的参照就是优先级，它是用某一范围内的一个整数来表示的，有静态优先级和动态优先级 2 种。

确定进程优先级大小的依据有以下三个：

多队列调度算法

前 2 种调度算法只设置了 1 个就绪队列，这样无法满足系统中不同用户对进程调度策略的不同要求。多队列调度算法设置多个进程就绪队列，可以将不同类型或性质的进程分配在不同的就绪队列，不同的就绪队列采用不同的调度算法。一个就绪队列中的进程可以设置不同的优先级，不同的就绪队列本身也可以设置不同的优先级，这样就可以对不同的用户进行更加合适的调度。

多级反馈队列调度算法

多级反馈队列调度算法(multileved feedback queue)不必事先知道各种进程所需的执行时间，还可以较好地满足各种类型进程的需要，是目前公认的一种较好的进程调度算法。
多级反馈队列调度算法设置多个就绪队列，并为每个队列赋予不同的优先级，第一个队列的优先级最高，其余队列的优先级逐个降低。不同队列中的进程所赋予的执行时间片的大小也各不相同，在优先级愈高的队列中其时间片就愈小。接着每个队列都采用 FCFS 算法，当新进程进入内存后先将它放入第一等待队列的末尾进行调度。如果该进程能在该时间片内完成便可撤离，否则调度程序将其转入第二队列的末尾等待调度。当进程最后被降到第 n 队列后，在第 n 队列中按 RR 调度算法运行。

调度程序首先调度最高优先级队列中的诸进程运行仅当第 1~(i-1) 所有队列均空时才会调度第 i 队列中的进程运行。

基于公平原则的调度算法

上述几种调度算法所保证的只是优先运行，但并不保证作业占用了多少处理机时间，没有考虑到调度的公平性，因此又提出了 2 种相对公平的调度算法。保证调度算法保证处理机分配的公平性，如果在系统中有 n 个相同类型的进程同时运行，为公平起见须保证每个进程都获得相同的 CPU 时间 1/n。
公平分享调度算法面向的是用户，因为不同的用户同时启用的进程数量不同，所以该算法要保证所有用户能获得相同的 CPU 时间。

实时调度

实时系统的调度

在实时系统中存在 HRT 任务和 SRT 任务(硬实时任务和软实时任务)，这 2 类任务都有截止时间，实时调度必须能满足实时任务对截止时间的要求。要实现实时调度，系统除了向调度程序提供就绪时间、处理时间、资源要求和优先级，也要提供开始截止时间和完成截止时间。
由于 HRT 和 SRT 任务的调度更为复杂，所以实时系统中对处理机的处理能力要求较高。假定系统中有 m 个周期性的硬实时任务 HRT，处理时间可表示为 Ci，周期时间表示为 Pi，则在单处理机情况下必须满足下面的限制条件系统才是可调度的。实际情况下限制条件还需要留有任务切换的时间，因此如果采用单处理机系统就必须增强 CPU 处理能力，如果采用多处理机系统也不能超过 N 个 CPU 的处理能力。

因为 HRT 任务有截止时间的需求，因此往往实时调度是基于抢占式的机制来实现。为保证硬实时任务能及时运行，在系统中还应具有快速切换机制，对于中断要能够快速响应，并且能快速地进行任务切换。

实时调度算法

算法类型

实时调度可以分为抢占式和非抢占式调度算法，其中非抢占式调度算法主要有：

抢占式调度算法根据抢占发生时间的不同分成以下两种：

最早截止时间优先算法

最早截止时间优先EDF(Earliest Deadline First)算法是根据任务的截止时间确定任务的优先级，任务的截止时间愈早优先级越高，具有最早截止时间的任务排在队列的队首。调度程序在选择任务时选择就绪队列中的第一个任务，为之分配处理机。最早截止时间优先算法既可用于抢占式调度方式中，也可用于非抢占式调度方式中。

最低松弛度优先算法

最低松弛度优先LLF(Least Laxity First)算法根据的是任务的紧急(或松弛)程度确定优先级，任务紧急程度愈高优先级就愈高。例如有一个任务需要在 400ms 时必须完成，它需要运行 150ms，得到其松弛程度为 400 - 150 = 250ms。系统中需要一个按松弛度排序的实时任务就绪队列，松弛度最低的任务排在最前面，调度程序选择队列中的队首任务执行。

优先级倒置

在系统中由于多个进程对临界资源的互斥，导致高优先级进程(或线程)被低优先级进程(或线程)延迟或阻塞的优先级倒置的现象。假如有三个完全独立的进程 P1、P2 和 P3，优先级 P1 > P2 > P3，P1 和 P3 共享的一个临界资源进行交互。假如 P3 最先执行并执行 P(mutex) 操作后进入临界区，而 P2 此时就绪了，由于 P2 比 P3 的优先级高所以 P2 抢占了 P3 的处理机而运行。此时 P1 也就绪了，因为 P1 比 P2 的优先级高所以 P1 抢占了 P2 的处理机而运行。但是此时临界资源已被 P3 占用，所以 P1 将被阻塞。
解决方法有 2 种，第一种是规定 P3 进入临界区后 P3 所占用的处理机就不允许被抢占，但是如果 P3 临界区非常长则高优先级进程 P1 仍会等待很长的时间。另一个方法是建立在动态优先级继承，当高优先级进程要进入临界区时，如果已有一个低优先级进程正在使用该资源，则由低优先级进程继承高优先级进程的优先级，并一直保持到低优先级进程退出临界区。