CPU调度是多道程序操作系统的基础。通过在进程间转换CPU，操作系统可以提高计算机的生产力。在本章，我们要介绍基本的调度概念并例举几种不同的CPU调度算法。我们还要讨论为特定的系统选择调度算法的问题。
6.1 基本概念
为了最大限度的提高CPU利用率，多道程序设计的目标是保持总是有进程可供执行。在单处理机系统中，一次只能运行一个进程；其它的任何进程都必须等到CPU空闲时才能够被重新调度。
多道程序设计的思想十分简单。一个进程持续运行直到它必须等待某些操作（I/O请求是个典型）的完成。在简单的计算机系统中，进程等待时CPU将处于空闲状态；这浪费了所有的等待时间。利用多道程序设计，我们可以有效地利用这段时间。在内存中同时保留多个进程。当一个进程必须等待时，操作系统将CPU撤离该进程并把CPU分配给另一个进程。然后以这种方式继续运行。
调度是一个基本的操作系统功能。几乎所有的计算机资源在使用前都需要调度。当然了，CPU是首要的计算机资源之一。因此CPU调度是操作系统设计的核心问题。
6.1.1 CPU-I/O Burst周期
CPU调度依赖于进程的这一特性：进程执行包含了CPU执行周期（cycle）和I/O等待时间。进程在这两个状态之间交替转换。进程执行开始于一个CPU burst。随后是一个I/O burst，然后是另一个CPU burst，再是一个I/O burst，等等。最终，最后的CPU burst以一个终止执行的系统请求结束，而不是一个I/O burst（图6.1）。
可以测量CPU burst的持续时间。虽然对进程和计算机来说它们的差异很大，但是它们趋向于图6.2所示的频率曲线。由于短的CPU burst很多长的很少，所以这条曲线通常被表现为指数分布或超指数分布的形式。一个I/O繁忙型程序通常有很多非常短的CPU burst。一个CPU繁忙型程序可能有少数非常长的CPU burst。这种分布（distribution）能够帮助我们选择一个合适的CPU调度算法。
6.1.2 CPU调度程序
只要CPU空闲，操作系统就必须从就绪队列中选择一个进程执行。进程的选择由短程调度程序（或CPU调度程序）完成。调度程序从内存中的就绪进程中做出选择，并将CPU分配给其中之一（调度程序选择的进程）。
就绪队列没有必要是一个先进先出（FIFO）队列。正如在稍后讨论各种调度算法时所见，可以把就绪队列实现为FIFO队列、优先队列、树或者仅仅是个无序链表（unordered linked list）。然而从概念上讲，就绪队列中的所有进程排队等待获取CPU执行的机会。队列中的记录通常是进程的进程控制块（PCB）。
6.1.3 抢占式调度
在如下的四种情况下可能会进行CPU调度：
1. 当进程从运行状态转换到等待状态时（例如：I/O请求或等待一个子进程的终止）（for example, I/O request, or invocation of wait for the termination of one of the child processes）
2. 当进程从运行状态转换到就绪状态时（例如：当发生中断时）
3. 当进程从等待状态转换到就绪状态时（例如：I/O完成）
4. 当进程终止时
在第一种和第四种情况下没有调度方面的选择。（In circumstances 1 and 4, there is no choice in terms of scheduling.）必须要选择一个新进程（如果就绪队列中有进程存在）执行。然而，在第二种和第三种情况下需要作出选择。（There is a choice, however, in circumstances 2 and 3.）
我们称只在第一种和第四种情况下进行的调度为非抢占式的（nonpreemptive）；否则为抢占式的（preemptive）。在非抢占式调度下，一旦把CPU分配给一个进程，那么该进程就会保持CPU直到终止或转换到等待状态。Microsoft Windows 3.1和Apple Macintosh采用了这种调度方式。因为非抢占式调度不像抢占式调度那样需要专门的硬件（如计时器），所以在某些硬件平台上它是唯一可用的方法。
可是抢占式调度要付出一定的代价。考虑一下两个进程共享数据的情况。当一个进程被抢占时它可能正在更新数据并且第二个进程被运行。（One may be in the midst of updating the data when it is preempted and the second process is run.）第二个进程可能试图读取这个数据，现在这个数据处在一个不一致的状态。这就需要新的机制来协调对共享数据的访问；第七章讨论这个问题。
抢占（Preemption）也会影响到操作系统内核的设计。在系统调用的处理过程中，内核可能会为某个进程做一些工作。这可能会改变重要的内核数据（如I/O队列）。如果在这个过程中该进程被抢占，并且内核（或设备驱动程序）需要读取或修改同样的数据结构，那么会怎样呢？结果可能会混乱不堪。有些操作系统（包括大多数UNIX版本）通过在上下文转换之前等待一个系统调用结束或发生一个I/O阻塞来处理这个问题。因为当内核数据结构处于不一致状态时不允许内核抢占进程，所以这种机制保持了内核结构的简单化。问题是这种内核执行模型（kernel-execution model）并不适于实时计算和多道处理。6.4节和6.5节描述了这些问题和它们的解决方案。
在UNIX中，代码段的使用也有危险。（In the case of UNIX, sections of code are still at risk.）根据定义中断可以随时发生，而且内核并不能够总是忽视中断，必须要确保首中断影响的代码段不被同时使用。操作系统几乎总是需要接收中断，否则就有可能丢失输入或输出被重写。所以这些代码段就不可以被几个进程同时访问，它们在入口禁止中断，在退出时恢复。但是，禁止和允许中断要耗费时间，尤其是在多处理机系统中。For systems to scale efficiently beyond a few CPUs, interrupt state changes must be minimized and fine-grained locking maximized. For instance, this is a challenge to the scalability of Linux.
6.1.4 调度程序
CPU调度中的另一个组成部分是调度程序（dispatcher）。调度程序是一个模块，它将CPU控制提交给短程调度程序选择的进程。其工作包括：
转换上下文
转换到用户摸式
跳转到用户程序中的正确位置重新开始该程序
调度程序应该尽可能的快，因为每次进程转换都要调用它。调度程序停止一个进程并开始运行另一个进程所需的时间被称为调度时间。
6.2 调度准则
不同的CPU调度算法有不同的性质并且可能会更适用于某个进程类型（与其它进程类型相比）。在一个特定的环境中采用哪个算法必须要考虑到各种算法的特性。
可以用有多个准则来比较CPU调度算法。在确定最好的算法中所用的特征可以使各种算法产生实质性的不同。（The characteristics used for comparison can make a substantial difference in the determination of the best algorithm.）这些准则包括：
CPU利用率：我们希望尽可能的保持CPU忙碌。CPU利用率可能在0到100之间。在实际的系统中，CPU利用率的范围应该在40%（系统负荷较轻）到90%（系统负荷较重）之间。
吞吐量：如果CPU忙于执行进程，那么工作正在进行（就要完成了）。对工作量的一种测量是单位时间内完成的进程数，被称为吞吐量。（If the CPU is busy executing processes, then work is being done. One measure of work is the number of processes completed per time unit, called throughput.）对较长的进程来说吞吐量可能是每小时一个进程；对于较短的事务来说可能是每秒十个进程。
周转时间：对一个进程来说，一个重要的指标是它执行所需要的时间。（From the point of view of a particular process, the important criterion is how long it takes to execute that process.）从进程提交到进程完成的时间间隔为周转时间。周转时间是等待进入内存的时间、在就绪队列中等待的时间、在CPU中执行的时间和I/O操作的时间的总和。
等待时间：CPU调度算法并不能影响进程的执行时间和I/O操作时间；它只能影响进程在就绪队列中等待的时间。等待时间是进程在就绪队列中耗费时间的总和。
响应时间：在交互式系统中，周转时间可能不是最好的指标。进程通常会很早的产生一些输出，并且在先前的结果输出给用户时继续计算。因此，另一个度量标准是从进程提交请求到产生首次响应的时间。这被称为响应时间，是开始响应所需的时间，而不是到产生输出结果所需的时间。周转时间通常受限于输出设备的速度。
我们希望最大化CPU利用率和吞吐量，最小化周转时间、等待时间和响应时间。在大多数情况下，我们最优化平均值。然而，在某些情况下我们需要最优化最小或最大值，而不是平均值。例如，为了保证所有的用户获得满意的服务，我们可能需要最小化最大的响应时间。
对于交互式系统（如实时系统）来说，有些分析者建议最小化响应时间的差异（variance in the response time）比最小化平均响应时间更为重要。拥有合理的可预测的（predictable）响应时间的系统比具备更快的平均时间的系统更令人满意。然而，在CPU调度算法上最小化差异所做的工作很少。
在我们讨论各种CPU调度算法时会举例说明它们的操作。一个精确的例子应该包含许多进程，每个进程有一个由数百个CPU burst和I/O burst组成的序列。为了简化，在例子中我们设想每个进程只有一个CPU burst（以毫秒计）。我们比较平均等待时间。在6.6节讨论更多精确的评估机制。
6.3 调度算法
CPU调度决定了从就绪队列中选择哪个进程并为其分配CPU。本节我们描述几种现有的CPU调度算法。
6.3.1 先来先服务调度算法
先来先服务（FCFS）调度算法是目前最简单的CPU调度算法。利用这种策略，先请求CPU的进程先获得CPU。利用一个FIFO队列可以很容易实现FCFS。当一个进程进入就绪队列后，它的PCB被链接到队尾。当CPU空闲时，处于队列头部的进程获得CPU。然后，运行的进程从该队列中移掉。FCFS调度算法的代码易写易懂。
然而FCFS策略的平均时间通常非常长。考虑如下的进程组合，在时间0，给定CPU burst时间长度（以毫秒计）：
进程 Burst时间
P1 24
P2 3
P3 3
如果进程以P1、P2、P3的顺序到达，并且以FCFS规则服务，我们将获得如下的甘特图：
P1
P2
P3
0 24 27 30
进程P1的等待时间是0毫秒，进程P2是24毫秒，P3是27毫秒。这样，平均时间是(0 + 24 + 27)/3 = 17毫秒。如果进程到达的顺序是P2、P3、P1，那么结果如下：
P2
P3
P1
0 3 6 30
现在的平均等待时间是(6 + 0 + 3)/3 = 3 毫秒。平均时间很明显的减少了。因而，FCFS策略下的平均等待时间通常不是最小的，而且如果进程的CPU burst时间有明显的变化时平均时间也会有很明显的变化。
另外，考虑一下在动态的情况下的FCFS调度算法的性能。假设有一个CPU繁忙型进程和许多I/O繁忙型进程。随着进程在系统中运行，结果可能如下。（As the processes flow around the system, the following scenario may result.）CPU繁忙型进程将获得CPU并持有它。在这段时间内，其它所有的进程将结束它们的I/O操作并移动到就绪队列中等待CPU。当进程在就绪队列中等待时，I/O设备空闲。最后，CPU繁忙型进程结束它的CPU burst并移动到一个I/O设备。所有的I/O繁忙型进程（具有很短的CPU burst）迅速执行并返回到I/O队列。这时，CPU空闲。CPU繁忙型进程将返回到就绪队列并被分配到CPU。再次，所有的I/O进程在就绪队列中等待，直到CPU繁忙型进程完成。其它所有的进程等待一个大进程释放CPU，这就是护送效应（convoy effect）。如果允许更短的进程首先执行，那么相对之下这种影响降低了CPU和设备的利用率。
FCFS调度算法是非抢占性的。一旦CPU被分配给一个进程，该进程将持有CPU直到它释放CPU（通过终止或请求I/O）。对分时系统来说，FCFS算法尤其糟糕，因为这种系统中的每个用户以有规则的时间间隔共享CPU。允许一个进程长期的占有CPU会产生灾难性的后果。
6.3.2 短作业优先调度算法
另一个CPU调度方法是短作业优先（SJF）调度算法。这种算法联系到了每个进程下次运行的CPU burst长度。当CPU有效时，它将被赋给下一个CPU burst最小的进程。如果两个进程的下一个CPU burst相同，就使用FCFS调度。要注意到一个更恰当的术语是最短的下一个CPU burst（the shortest next CPU burst），因为调度是通过检测进程的下一个CPU burst长度来完成的，而不是其总长度。我们使用术语SJF是因为大多数人和教科书都是作为SJF提及这种调度类型的。
作为一个例子，考虑如下的一组进程，给定了CPU burst长度：
进程 Burst时间
P1 6
P2 8
P3 7
P4 3
利用SJF调度，我们将依照如下的甘特图来调度这些进程：
P4
P1
P3
P2
0 3 9 16 24
P1的等待时间是3毫秒，P2是16毫秒，P3是9毫秒，P4是0毫秒。因而，平均等待时间是(3 + 16 + 9 + 0)/4 = 7毫秒。如果使用FCFS调度策略，那么平均等待时间是10.25毫秒。
可证明SJF调度算法是最佳的算法，因为它为指定的进程组给出了最小的平均等待时间。通过在一个长进程之前移动一个短进程，短进程等待时间的减少要比长进程等待时间的增加更甚。因此而降低了平均等待时间。
SJF所面临的实际困难在于难以获知下一个CPU请求的长度。对于批处理系统中的长程调度（或作业调度）来说，我们可以使用用户在提交作业时指定的处理时间限制长度。这样，用户需要准确的估计处理时间，因为越小的值意味着越快的响应速度。（太小的值会造成超时错误（time-limit-exceeded error），需要重新提交作业。）SJF通常在长程调度中使用。
虽然SJF算法是最理想的，但是却不能够在短程CPU调度级实现。没有方法可以获知下一个CPU burst的长度。一种方案是设法达到一种近似的SJF调度。我们可能不知道下一个CPU burst的长度，但是我们可以预测这个值。我们设想进程的下一个CPU burst与其上一个相近。因此，通过近似估算下一个CPU burst的长度，我们能够挑选一个拥有最短的预测CPU burst的进程。
通常可以将下一个CPU burst作为先前测量的CPU burst的一个指数平均值来预测。（The next CPU burst is generally predicted as an exponential average of the measured lengths of previous CPU bursts.）令第n个CPU burst的长度是tn，我们预测的下一个CPU burst为Tn+1。那么，对于ɑ（0 <= ɑ <= 1），定义：
Tn+1 = ɑtn + (1 -ɑ)Tn
这个公式定义了指数平均数（exponential average）。tn包含了最近的信息；Tn则包含了过去的历史信息。在预测中，参数ɑ控制近来和过去历史的权重。（The parameter ɑ controls the relative weight of recent and past history in our prediction.）如果ɑ = 0，那么Tn+1 = Tn，近来的历史没有产生影响（假定当前的条件是瞬时的）；如果ɑ = 1，那么Tn+1 = tn,，只有最近的CPU burst有作用（假设历史记录陈旧了，没有关系了）。更普遍的，ɑ= 1/2，所以最近的历史记录与过去的相当。可以把初始的T0定义为常数或整个系统的平均值。图6.3表示了一个指数平均值（ɑ= 1/2，T0 = 10）
====================================未完待续===================================
