进程调度

设想下列情况，如果有两个进程先后创建，操作系统需要决定先运行哪个后运行哪个，哪个进程的优先度更高等等问题。这就涉及到进程调度的策略问题，所以这章我们将就进程的各种调度策略进行逐级论述。

初级策略

工作负载

在考虑调度策略的初级阶段，我们需要对工作负载做一些前提假设，工作负载决定调度策略的背景，离开工作负载谈调度策略都是虚无缥缈的：

1. 每一个工作运行相同的时间。
2. 所有的工作同时到达
3. 一旦开始，每个工作保持运行直到完成。
4. 所有的工作只有用CPU（即它们不执行IO操作）。
5. 每个工作的运行时间是已知的。

调度指标

我们先关注一个调度指标，它是一个性能指标：

T_周转时间 = T_完成时间 – T_到达时间

先进先出

假设有A、B和C三个任务，假设三个任务基本同时到达，但是A早于B早于C，则A会先运行其次是B最后是C，假设运行时间都是10s，则平均周转时间为(10 + 20 + 30) / 3 = 20，但是当A任务的运行时间逐渐增加时，平均周转时间将基于A的运行时间呈线性增加，，但如果我们将A任务放在最后执行，平均周转时间将大幅减小，所以这并不是我们期待的性能效果。

最短任务优先

这次我们让最短的任务先运行，这时需要分两种情况讨论，一种是抢占式调度程序：当一个短时任务到达时，有可能会停止正在进行的长时间任务，转而运行短时间任务。另一种非抢占式调度程序则会将正在运行的长时间任务运行完后才会执行后到达的短时任务。最短任务优先属于非抢占式，所以当长时间任务首先运行，同样达不到很好的平均周转时间性能指标。

最短完成时间优先

最短完成时间优先则是抢占式，每当新任务进入系统时，他就会确定剩余工作和新工作，谁的剩余时间最少，然后调度该工作。它能大大提高平均周转时间。

新度量指标：响应时间

当只考虑平均周转时间，且任务只是用CPU时，最短完成时间优先是一个很好的调度策略。但是这忽略了用户的交互性，如果考虑系统交互性，我们会加入一个新的度量指标：响应时间。响应时间的定义为：

T_响应时间 = T_首次运行 – T_到达时间

为此我们不得不考虑一些能同时满足交互性和性能的调度算法。

轮转

轮转调度策略会在一个时间片内运行一个任务，然后切换到运行队列中的下一个任务，直到所有任务完成。轮转策略能很好的降低平均响应时间，但是平均周转时间将会变长，另一方面，进程的不断切换时的上下文切换也同要会增加时间成本，可以说此处的交互性提升的代价就是性能的降低，所以往往公平性和性能不能兼而得之，这是一个需要左右权衡的问题。

放宽负载条件

现在我们放宽负载条件，把I/O纳入考虑范围，并假设任务的运行时间未知。

当任务在I/O期间，它将不会使用CPU，这时我们可以将CPU给其他进程使用，用来提高CPU的利用率。

多级反馈队列

本小节介绍一种著名的算法：多级反馈队列。它同时对周转时间和响应时间进行了优化。算法基于先验知识对任务的优先级进行调整，从而满足对性能和交互性的平衡。

我们将有序介绍算法规则，首先是两条基本规则：

• 规则1：如果A的优先级>B的优先级，运行A（不运行B）
• 规则2：如果A的优先级=B的优先级，轮转运行A和B

在以上规则下，虽然能让有更高优先级的任务率先运行，但是会出现低优先级任务可能永远无法运行的情况，所以我们需要让优先级动态起来：新增三条规则：

• 规则3：工作进入系统时，放在最高优先级（最上层队列）
• 规则4a：工作用完整个时间片后，降低其优先级（移入下一个队列）
• 规则4b：如果工作在其时间片内主动释放CPU，则优先级不变

制定以上规则后，我们可以明确算法的一个主要目标：如果不知道工作是短工作还是长工作，那么就在开始的时候设置其是短工作，并赋予最高优先级。如果确实是短工作，则很快会执行完毕，否则将被慢慢移入优先级队列，而这时该工作也被认为是长工作了。通过这种方式，多级反馈调度队列近似于短任务优先。

另一点就是在有I/O的情况下，如果进程在用完时间片之前执行I/O并让出CPU，将保持优先级，这样如果一个任务频繁进行I/O操作并让出CPU就能保持最高优先级，这样如果B是交互型工作，这样就能保证B的交互性。

即使是这样依然有一些问题，比如常见的饥饿问题：如果有过多的交互型工作，长工作将永远得不到CPU；再比如如果某任务在时间片用完前调度无用I/O操作，并且一直如此操作，可以通过这样欺骗操作系统从而已知保持最高优先级。

基于前一个问题，我们可以再次增加规则：

• 规则5：经过一段时间S，就将系统中所有工作重新加入最高优先级队列。

新规则一下解决了两个问题。首先进程不会饿死；其次如果一个CPU密集型工作变成了交互型，当它优先级提升时，它能成功从CPU密集型转型成交互型应用。

基于后一个问题，我们可以通过修改规则4来实现：

• 规则4：一旦工作用完了其在某一层中的时间配额（无论中间主动放弃了多少次CPU），就降低其优先级（移入低一级队列）

在规则4的制约下，任务不可能通过单时间片结束前的I/O调用来保持最高优先级，它同样会从最高优先级慢慢降至最低优先级。

小节

多级反馈队列的调度工作的基本规则如下：

• 规则1：如果A的优先级>B的优先级，运行A（不运行B）
• 规则2：如果A的优先级=B的优先级，轮转运行A和B
• 规则3：工作进入系统时，放在最高优先级（最上层队列）
• 规则4：一旦工作用完了其在某一层中的时间配额（无论中间主动放弃了多少次CPU），就降低其优先级（移入低一级队列）
• 规则5：经过一段时间S，就将系统中所有工作重新加入最高优先级队列

基于以上规则，多级反馈队列可以同时满足交互性和较好的性能，但是想要更好的性能就需要对调度算法中的参数进行调优，例如每一级队列的时间片大小，提升优先级的时间间隔等，这些问题并没有固定最优解，只能通过对工作负载的经验才能达到令人满意的平衡。

比例份额

多处理器调度