0.前言

CPU调度是多道程序操作系统的基础。通过在进程间切换CPU，操作系统可以使得计算机更加高效。
本章目标：

1. 引入CPU调度，这是多道程序操作系统的基础
2. 描述各种CPU调度算法
3. 讨论为特定系统选择CPU调度算法的评估标准
4. 分析多个操作系统的调度算法

5.1 基本概念

多道程序操作系统的基础。通过在进程之间切换CPU，操作系统可以提高计算机的吞吐率。
对于单处理器系统，每次只允许一个进程运行：任何其他进程必须等待，直到CPU空闲能被调度为止。

5.1.1 CPU-I/O 区间周期

CPU的成功调度依赖于进程的如下属性：
进程执行由CPU执行周期和I/O等待周期组成。进程在这两个状态之间切换(CPU burst—I/O bust)。

进程执行从CPU区间（CPU burst）开始，在这之后是I/O区间（I/O burst）。接着另外一个CPU区间，然后是另外一个I/O区间，如此进行下去，最终，最后的CPU区间通过系统请求中止执行。

经过大量CPU区间的长度的测试。发现具有大量短CPU区间和少量长CPU区间。I/O约束程序通常具有很多短CPU区间。CPU约束程序可能有少量的长CPU区间。这种分布有助于选择合适的CPU调度算法。

5.1.2 CPU程序调度

每当CPU空闲时，操作系统就必须从就绪队列中选择一个进程来执行。进程选择由短期调度程序（short-term scheduler）或CPU调度程序执行。调度程序从内存中选择一个能够执行的进程，并为之分配CPU。

就绪队列不必是先进先出（FIFO）队列，也可为优先队列、树或简单的无序链表。不过队列中所有的进程都要排队以等待在CPU上运行。队列中的记录通常为进程控制块（PCB）。

5.1.3 抢占调度

CPU调度决策可在如下4种情况环境下发生：

1. 当一个进程从运行切换到等待状态（如：I/O请求，或者调用wait等待一个子进程的终止）
2. 当一个进程从运行状态切换到就绪状态（如：出现中断）
3. 当一个进程从等待状态切换到就绪状态（如：I/O完成）
4. 当一个进程终止时

对于第1和4两种情况，没有选择而只有调度。一个新进程（如果就绪队列中已有一个进程存在）必须被选择执行。
对于第２和第３两种情况，可以进行选择。

当调度只能发生在第1和4两种情况下时，称调度是非抢占的（nonpreemptive）或协作的（cooperative）；否则，称调度方案为抢占的（preemptive）。采用非抢占调度，一旦CPU分配给一个进程，那么该进程会一直使用CPU直到进程终止或切换到等待状态。

抢占调度对访问共享数据是有代价（如加锁）的，有可能产生错误，需要新的机制（如，同步）来协调对共享数据的访问。

抢占对于操作系统内核的设计也有影响。在处理系统调用时，内核可能忙于进程活动。这些活动可能涉及要改变重要内核数据(如I/O队列)。

因为根据定义中断能随时发生，而且不能总是被内核所忽视，所以受中断影响的代码段必须加以保护以避免同时访问。操作系统需要在任何时候都能够接收中断，否则输入会丢失或输出会被改写。为了这些代码段不被多个进程同时访问，在进入时就要禁止中断，而在退出时要重新允许中断。

5.1.4 分派程序

分派程序（dispatch） 是一个模块，用来将CPU的控制交给由短期调度程序选择的进程。
其功能包括：1. 切换上下文 2. 切换到用户模式3. 跳转到用户程序的合适位置，以重新启动程序。
分派程序停止一个进程而启动另一个所花的时间成为分派延迟。

5.2 调度准则

为了比较CPU调度算法所提出的准则：

1. CPU使用率 : 需要使CPU尽可能忙
2. 吞吐量 : 指一个时间单元内所完成进程的数量
3. 周转时间 :从进程提交到进程完成的时间段称为周转时间，周转时间是所有时间段之和，包括等待进入内存、在就绪队列中等待、在CPU上执行和I/O执行
4. 等待时间 : 在就绪队列中等待所花费时间之和
5. 响应时间 : 从提交请求到产生第一响应的时间

需要使CPU使用率和吞吐量最大化，而使周转时间、等待时间和响应时间最小化。绝大多数情况下需要优化平均值，有时需要优化最大值或最小值，而不是平均值。

5.3 调度算法

5.3.1 先到先服务调度(First-Come，First-Served scheduling)

最简单的CPU调度算法是先到先服务算法（First-Come，First-Served scheduling）：先请求CPU的进程先分配到CPU。FCFS策略可以用FIFO队列来容易实现。当一个进程进入就绪队列，其PCB链接到队列的尾部。当CPU空闲时，CPU分配给位于队列头的进程，接着运行进程从队列中删除。

FCFS策略的代码编写简单且容易理解，不过采用FCFS策略的平均等待时间通常比较长。当进程CPU区间时间变化很大，平均等待时间会变化很大。


另外考虑在动态情况下的性能，假设有一个CPU约束进程和许多I/O约束进程，CPU约束进程会移回到就绪队列并被分配到CPU。再次所有I/O进程会在就绪队列中等待CPU进程的完成。由于所有其他进程都等待一个大进程释放CPU，这称之为护航效果（convoy effect）。与让较短进程最先执行相比，这样会导致CPU和设备使用率变的很低。

FCFS调度算法是非抢占的。对于分时系统（每个用户需要定时的等待一定的CPU时间）是特别麻烦。允许一个进程保持CPU时间过长是个严重错误。

5.3.2 最短作业优先调度(shortest-job-first scheduling,SJF)

将每个进程与下一个CPU区间段相关联。当CPU为空闲时，它会赋给具有最短CPU区间的进程。如果两个进程具有同样长度，那么可以使用FCFS调度来处理。注意，一个更为适当地表示是最短下一个CPU区间的算法，这是因为调度检查进程的下一个CPU区间的长度，而不是其总长度。

5.3.3 优先级调度(priority scheduling algorithm)

SJF算法可作为通用的优先级调度算法的一个特例。每个进程都有一个优先级与其关联，具有最高优先级的进程会分配到CPU。具有相同优先级的进程按FCFS顺序调度。SJF，其优先级（p）为下一个CPU区间的倒数。CPU区间越大，则优先级越小，反之亦然。

优先级通常是固定区间的数字，如０～７，但是数字大小与优先级的高低没有定论。

平均等待时间为：（0+1+6+16+18）/5=8.2

优先级可通过内部或外部方式来定义。内部定义优先级使用一些测量数据以计算进程优先级。外部优先级是通过操作系统之外的准则来定义，如进程重要性等。

优先级调度可以是抢占的或非抢占的。

优先级调度算法的一个重要问题是无限阻塞（indefinite blocking）或饥饿（starvation）。可以运行但缺乏CPU的进程可认为是阻塞的，它在等待CPU。优先级调度算法会使某个有低优先级无穷等待CPU。

低优先级进程务求等待问题的解决之一是老化（aging）。老化是一种技术，以逐渐增加在系统中等待很长时间的进程的优先级。

5.3.4 轮转法调度(round-robin,RR)

专门为分时系统设计。它类似于FCFS调度，但是增加了抢占以切换进程。定义一个较小的时间单元，称为时间片（time quantum，or time slice）。将就绪队列作为循环队列。CPU调度程序循环就绪队列，为每个进程分配不超过一个时间片段的CPU。

新进程增加到就绪队列的尾部。CPU调度程序从就绪队列中选择第一个进程，设置定时器在一个时间片之后中断，再分派该进程。接下来将可能发生两种情况。进程可能只需要小于时间片的CPU区间。对于这种情况，进程本身会自动释放CPU。调度程序接着处理就绪队列的下一个进程。否则，如果当前运行进程的CPU区间比时间片要长，定时器会中断产生操作系统中断，然后进行上下文切换，将进程加入到就绪队列的尾部，接着CPU调度程序会选择就绪队列中的下一个进程。


如果就绪，那么每个进程会得到1n的CPU时间，其长度不超过q时间单元。每个进程必须等待CPU时间不会超过(n−1)×q个时间单元，直到它的下一个时间片为止。

RR算法的性能很大程度上依赖于时间片的大小。在极端情况下，如果时间片非常大，那么RR算法与FCFS算法一样。如果时间片很小，那么RR算法称为处理器共享，n个进程对于用户都有它自己的处理器，速度为真正处理器速度的1/n。小的时间片会增加上下文切换的次数，因此，希望时间片比上下文切换时间长，事实上，绝大多数现代操作系统，上下文切换的时间仅占时间片的一小部分。周转时间也依赖于时间片的大小。

5.3.5 多级队列调度(Multilevel Queue Scheduling)

前台（交互）进程和后台（批处理）进程。这两种不同各类型的进程具有不同响应时间要求，也有不同调度需要。与后台进程相比，前台进程要有更高（或外部定义）的优先级。

多级队列调度算法将就绪队列**分成多个独立队列。**根据进程的属性，如内存大小等，一个进程被永久地分配到一个队列(低调度开销但是不够灵活)，每个队列有自己的调度算法。前台队列可能采用RR算法调度，而后台调度可能采用FCFS算法调度。

另外，队列之间必须有调度，通常采用固定优先级抢占调度，例如前台队列可以比后台队列具有绝对优先值。另一种可能在队列之间划分时间片例如，前台队列可以有80%的时间用于在进程之间进行RR调度，而后台队列可以有20%的CPU时间采用FCFS算法调度进程。

5.3.6 多级反馈队列调度(Multilevel Feedback-Queue Scheduling)

与多级队列调度相反，多级反馈队列调度允许进程在队列之间移动。主要思想是根据不同CPU区间的特点以区分进程。如果进程使用过多CPU时间，那么它可能被转移到较低优先级队列。这种方案将I/O约束和交互进程留在更高优先级队列。此外，在较低优先级队列中等待时间过长的进程会被转移到更高优先级队列。这种形式的老化组织饥饿的发生。

通常，多级反馈队列调度程序可由下列参数来定义：
队列数量
每个队列的调度算法。
用以确定何时升级到更高优先级队列的方法。
用以确定何时降级到更低优先级队列的方法。
用以确定进程在需要服务时应进入哪个队列的方法。