操作系统：调度

调度

当存在多个进程或线程同时竞争CPU的时候，CPU需要选择下一个运行的进程或线程。在操作系统中，完成选择工作的部分称作调度程序，该程序使用的算法称为调度算法。

调度的原则

我们什么时候需要调度？怎样的调度算法是好的调度算法？例如交互式程序会存在需要CPU处理的工作和I/O，在出现CPU突发（需要CPU处理的工作）时，调度程序需要给此进程分配CPU时间，而在等待I/O的时候，调度程序则选择其他需要CPU处理的进程。具体一点，在这样几种情况下，我们需要调度：

1. 在创建一个新进程之后，决定是运行父进程还是子进程。（此时两个进程都处于就绪状态！）
2. 当一个进程退出的时候（比如被杀死）
3. 当一个进程阻塞的时候（比如等待I/O）
4. 当一个I/O中断发生的时候（中断过后，是让等到I/O的进程运行，还是让原进程继续运行，或者再调度一个其他的进程？）

这种调度可能是抢占式的或者非抢占式的。非抢占的调度必须要等到正在运行的进程结束，而抢占式的调度则可以趁某个中断（时钟中断，I/O中断）抢占，此时原先运行的进程将被挂起。

那么什么样的调度是好的呢？一般来讲，我们对调度程序的评价主要基于以下方面：

1. CPU使用率（CPU处于忙的时间和总时间的比率）
2. 吞吐量（单位时间内完成的进程数量）
3. 周转时间（一个进程从初始化到结束，包括所有等待花费的时间）
4. 等待时间（进程在就绪队列中等待的总时间）
5. 响应时间（一个请求从提交到第一次响应所花费的时间）
6. 公平

调度算法

1.FCFS（先来先服务）

FCFS是一种最为直观的调度算法。即按进程请求的先后顺序安排进程的调度。

例如图中的三个进程P1，P2，P3，我们按照FCFS进行调度。

在第一种情况下，进程的周转时间=（12+15+18）/3 = 15。而在第二种情况下，进程的

周转时间=（3+6+18）/3 = 9。

这种调度方式的最大优点是简单。但通过上述计算，我们发现进程的平均等待时间和到达顺序关系很大，以及很明显的一点，如果让用时短的进程先运行，可以大幅缩短平均等待时间。

2.短任务优先

正如刚才所言，如果我们能够预先知道这些任务所需时间的长短（例如，类似的任务每天都要进行），那我们总是可以让所需时间短的任务先执行，以降低整体的等待时间。

但是这种算法也有缺陷。连续的短任务可能会使长任务一直得不到调度，从而陷入饥饿。以及如果短任务不是同时到达而是分批到达，这种算法的优势也会缩小。

如果我们使用抢占式的调度算法，那短任务优先就变成了最短剩余时间优先，即总是优先运行剩余时间最短的请求。在新请求到达的时候，把它的时间与队列中所有请求的时间相比较，如果它最短，则抢占，否则入队等待。

3.轮循调度

轮循调度是一种简单，公平的调度算法。操作系统给每个进程分配一个时间片（Quantum？），如果该进程在限定时间内未能完成，则阻塞该进程，并把CPU分给下一进程。若该进程提前完成或阻塞，则CPU立即进行切换。

这种设计的好处很明显，公平。但是公平往往会带来额外的开销。进程切换（或称上下文切换）也需要一定的时间。如果时间片过小（切换过于频繁），则大量的时间会被浪费。但如果时间片过大，又会引起交互时间过长——如果时间片足够大，轮循调度会退化成FCFS！因此，选择一个合适的时间片是相当重要的。前人的经验是将上下文切换的消耗控制在总时间的1%左右。

4.多级队列

上述的几个算法各有优劣，不同的算法可能适应于不同类型的进程。比如，几乎纯CPU的进程（比如高性能运算）就很适合使用FCFS。而一些需要及时反馈的可能更适用轮循调度。那么为什么不能为这些进程设立不同的队列呢？

多级队列就是这样的一个抽象。我们设立不同优先级的队列，并给每个队列分配时间片。当一个进程用完它的时间片之后，它被移到下一个队列。这样，需要CPU时间比较短的进程往往可以得到优先处理，而CPU消耗高的进程几乎必然被移到优先级低的队列中慢慢运行。这样既能够保证系统的反应速度，又能使CPU尽量少空转。

当然，复杂的设计必然带来更大的开销。以及还有一个我们一直没讨论的问题：在运行之前，我们怎么知道这个进程需要多长时间？

实时调度

现实生活中，我们对有些程序的要求除了能够完成任务，还要按时完成任务。这就引出了实时系统的概念。在实时系统的调度中，操作的正确性依赖于时间和功能两方面。这种系统又分软实时和硬实时，即期望按时和绝对按时。在这种系统中，我们可以采用RM（速率单调调度），即优先调度周期最短的进程，或者EDF（最早期限调度），优先调度Deadline最早的任务。