进程调度

进程调度的定义

进程的调度就是操作系统进程管理的一个重要组成部分。其任务是选择下一个要运行的进程。那么如何进行选择呢？
要探明这一点，首先需要确定操作系统进程调度的目标是什么。有了目标，我们就知道选择什么进程最合适了。

那么操作系统进程调度的目标是什么呢？这需要对进程使用 CPU 的模式进行分析。那么进程在执行时有什么样的模式呢？

一般来说，程序使用 CPU 的模式有 3 种：一种是程序大部分时间在 CPU 上执行；
另一种是程序大部分时间在进行输入输出；还有一种是程序介于前两种模式之间。

第 1 种程序运行的模式是在 CPU 上执行较长时间，接着进行短暂的输入，然后又在 CPU 上进行较长的运算，之后又进行短暂的输入输出操作，就这样循环往复。
这种程序由于使用 CPU 的时间远远长于其用于输入输出上的时间，因此称为CPU 导向(CPU-bound)或计算密集型程序。
计算密集型程序通常是科学计算方面的程序。计算宇宙大爆炸各种参数的程序、矩阵乘法程序等就都是 CPU 导向的程序。

第 2 种程序则与第 1 种相反，这种程序的大部分时间用来 I/O，每次 I/O 后进行短暂的 CPU 执行，因此称为 I/O 导向(I/O-bound)或输入输出密集型程序。
一般来说，人机交互式程序均属于这类程序。如游戏程序以及讲课时使用的 PPT 程序，都属于 I/O 导向的程序。

第 3 种程序自然介乎二者之间，既有长时间的 CPU 执行程序，又有长时间的 I/O 部分。
或者说，这种程序使用 CPU 和 I/O 的时间相差不大。这种程序称为平衡性程序。例如，网络浏览或下载、网络视频等就属于此类程序。

自然，对于不同性质的程序，调度所要达到的目的也有所不同。
例如，对于 I/O 导向的程序来说，响应时间非常重要；而对于 CPU 导向的程序来说，周转时间(turnaround)就比较重要；
对于平衡型程序来说，进行某种响应和周转之间的平衡就显得重要。

进程调度的目标

CPU 调度就是要达到极小化平均响应时间、极大化系统吞吐率、保持系统各个功能部件均处在繁忙状态和提供某种貌似公平的机制。

极小化平均响应时间就是要极小化用户发出命令和看到结果之间所花费的时间，即减少做一件工作平均等待的时间；
极大化系统吞吐率就是要在单位时间内完成尽可能多的程序，就是单位时间内能完成的工作数量，即整个程序运行效率高；
保持系统各个功能部件繁忙就是要让 CPU 和输入输出设备均处于忙碌状态。
由于 CPU 非常昂贵，让其闲置显然是一种浪费，因此保持 CPU 繁忙十分重要。
就像生命非常珍贵，因此要一直保持学习繁忙状态，才能不浪费生命。

提供公平就是要让各个程序感到某种“平等”，即在 CPU 面前“人人平等”。公平是任何系统都应该努力达到的目标。
因为没有公平，该系统对用户的吸引力就会急剧下降。这就像一个国家或者社会，如果缺乏公平，公民对该国家的认同感就会急剧下降一样。

对于不同的系统来说，在调度目标方面也有一些细微的不同。例如，对于批处理系统来说，由于用户并不坐在计算机面前等待结果，响应时间就显得不太重要，但系统吞吐率、CPU 利用率和周转时间则很重要。

对于交互式系统来说，由于用户在等待计算机，因此响应时间要很快。但在这里要注意的是适应性(proportionality)。适应性就是响应时间要和期望值相匹配。
这里是说你不要超越用户的期望。比如，用户期待 1 秒钟的响应时间，你就给他 1 秒钟的响应时间，而不必提供 0.1 秒钟的响应时间。
这是因为，提供超出用户期望的响应会增加系统设计的难度，而又不会提高用户的满意度(对于一个人来说，1 秒钟和 0.1 秒钟的差别并不是很大)

对于实时系统来说，调度就是要达到在截止时间前完成所应该完成的任务和提供性能可预测性。

先来先服务调度算法

先来先服务调度算法缩写为 FCFS(First Come First Serve)。谁先来，就先服务谁。这个算法所有地球人都能想到。
因为先来先到是人的本性中的一种公平观念，而且生活实际中这种规则随处可见。例如，我们排队买东西或者办理政务体现的就是先来先到原则。

先来先到的一个隐含条件就是不能抢占，一个程序一旦启动就一直运行到结束或者受阻塞为止。
这是因为一旦允许抢占，就破坏了先来先到的原则。先来先到优点就是简单，人人都能理解，实现起来容易。
而缺点则是短的工作有可能变得很慢，因为其前面有很长的工作。这样就造成用户的交互式体验也比较差。

例如，现在有两个程序：A 需要运行 100 秒，B 需要运行 1 秒。
A 程序与 B 程序几乎同时启动，但 B 就是慢了一点儿，排在 A 之后执行，则需要等待 100 秒。
这样 A 的响应时间为 100 秒，而 B 的响应时间则为 101 秒，从而，平均响应时间 100.5 秒。那么响应时间非常慢。

就像我们排队办理事情，你要办理的事情只要几分钟就可办好，而你前面的一个人办理的事情因为复杂需要 1 个小时。
这个时候你要等在他后面就十分不高兴。这个时候你就想，要是每个人轮流办理 10 分钟事务的话，那多好呀

自然，研究进程调度的人也想到了这一点，而这种轮流办理的调度方式就是时间片轮转。

时间片轮转算法

时间片轮转算法是对 FCFS 算法的一种改进，其主要目的是改善短程序的响应时间。其方法就是周期性地进行进程切换。
例如，每 1 秒钟进行一次进程轮换。这样，短程序排在长程序后面也可以很快得到执行。
因此长程序执行 1 秒后就得把 CPU 让出来。这样整个系统的响应时间就得到了改善。
以前面的 A、B 程序为例，A 需要运行 100 秒，B 需要运行 1 秒。使用 FCFS 时系统平均响应时间为 100.5 秒。
而使用时间片轮转，则 A 在执行 1 秒后，CPU 切换到进程 B，在执行 1 秒后，B 结束，A 接着执行 99 秒。
这样 A 的响应时间是 101 秒，而 B 的响应时间为 2 秒。系统的平均响应时间是 51.5 秒。这显然比 FCFS 的效率强多了

系统响应时间依赖于时间片的选择。我们因为选择了 1 秒钟的时间片，上述系统的响应时间是 51.5 秒。
如果时间片是 10 秒钟，则上述系统的平均响应使劲将是 65 秒。
如果选择别的时间片，则响应时间还将不同。那我们自认想知道，到底选择多大的时间片才合适呢？

显然，如果选择的时间片过大，时间片轮转将越来越像 FCFS，当选择的时间片超过任何一个程序所需要的执行时间长度时，则完全退化为 FCFS。
而如果选择的时间片过小，则进程切换所用的系统消耗将太多，使得系统的大部分时间花在进程的上下文切换上，而用来真正执行程序的有用时间很少，从而降低系统效率，并造成浪费。

那如何选择一个合适的时间片呢？做研究。
我们需要知道进行一个进程切换所用系统消耗和我们能够承受的整个系统消耗，就可以得出合适的时间片。
例如，如果每次进程切换需要消耗 0.1 毫秒的 CPU 时间，则选择 10 毫秒的时间片将浪费约 1% 的 CPU 时间在上下文切换上；
如果选择 5 毫秒的时间片，则浪费约为 2%；20 毫秒的时间片，则浪费约为 0.5%。
如果我们能够承受的 CPU 浪费为 1%，则选择 10 毫秒的时间片就很合理。

时间片选择还需考虑的一个因素是，有多少进程在系统里运行？如果运行的进程多，时间片就需要短一些，不然，用户的交互体验会很差。
进程数量少，时间片就可以适当长一些。因此，时间片的选择是一个综合的考虑，需要权衡各方利益，进行适当折中。

时间片轮转看上去非常公平，响应时间非常好，每个进程周期性地获得 CPU 时间。但时间片轮转真的很公平吗？
时间片轮转的系统响应时间总比 FCFS 的响应时间短吗？答案却不一定。

还用上面的例子，假设是 B 比 A 略微先到，如果用 FCFS，则 B 的响应时间为 1 秒，A 的响应时间为 101 秒，这样系统的平均响应时间为 51 秒。
这是最优的响应时间。如果使用时间片轮转，除非时间片选择的是 1 秒，否则时间片轮转的系统响应时间将比 FCFS 慢(记住，进程切换是需要消耗系统时间的)。

短任务优先算法

诚然，时间片轮转和先来先服务到底哪一种方式更公平是一个仁者见仁、智者见智的话题。
但是一个事实是，现在的社会都不太认同终身制，而更认同轮流坐庄。
18 世纪以前，欧洲的皇帝是终身制，逃到美国的清教徒则显然不喜欢终身制，从而选择了 4 年一轮的总统制度。
而这种轮流坐庄的制度已被世界绝大多数国家和不同时期的社会制度所认可，皇帝终身制度已被世人唾弃。
从这一点来说，时间片轮转比起 FCFS 来说似乎更加公平。

那么时间片轮转真的那么公平吗？当然不是。
如果每个人的能力一样，大家轮流坐庄当然比较公平，问题是每个人的能力并不完全一样。
让一个能力很差的人与一个能力很好的人轮流执政恐怕没有多少人会同意。
我们不是因为不满大锅饭而提出让一部分人先富起来吗？而时间片轮转就是大锅饭！

从前面可以看出，时间片轮转改善了所谓系统响应时间的论断也不一定经得起推敲。
更为重要的是，时间片轮转所达到的系统响应时间并不是我们所能达到的响应时间下限。
如果有 30 个用户，其中一个用户只需要 1 秒钟时间执行，而其他 29 个用户需要 30 秒钟执行，如果因为某种原因，这个只要 1 秒钟的程序排在另外 29 个程序的后面轮转，则它需要等待 29 秒钟才能执行(假定时间片为 1 秒)。这个程序的响应时间和交互体验就变得非常差。

那要改善短任务排在长任务后面轮转而造成响应时间和交互体验下降的办法就是短任务优先(Shorted Time to Completion First, STCF)算法。
这种算法的核心是所有的程序并不都一样，而是有优先级的区分。
具体来说，就是短任务的优先级比长任务的高，而我们总是安排优先级高的程序先运行。就像晚辈在公交汽车上见到长辈需要让座一样。

短任务优先算法有两个变种：一种是非抢占，一种是抢占。
非抢占短任务优先算法的原理是让已经在 CPU 上运行的程序执行到结束或阻塞，然后在所有候选的程序中选择需要执行时间最短的进程来执行。
抢占式短任务优先算法则是每增加一个新的进程对所有进程(包括正在 CPU 上运行的进程)进行检查，谁的时间短，就运行谁

显然，由于短任务优先总是运行需要执行时间最短的程序，因此其系统平均响应时间在目前已经讨论过的几种调度算法里面是最优的。这就是 STCF 算法的优点。
事实上，在所有非抢占调度算法中，STCF 算法的响应时间最优，而在所有抢占调度算法中，抢占式 STCF 算法的响应时间最优。

下面来看一个例子：假定有 A、B、C 3 个进程，A、B 均是纯计算进程，分别需要使用 CPU 50 毫秒和 100 毫秒，而 C 每计算 1 毫秒后进行 9 毫秒的输入输出操作，并这样重复 10 次。

显然，如果 A、B 单独运行，则 CPU 利用率是 100%；如果 C 单独运行，则磁盘利用率为 90%。
如果将它们一起运行，结果会怎么样呢？这里假定使用 STCF 调度算法。

要使用 STCF 算法，首先需要清楚哪个工作是短工作，哪个是长工作。
A、B、C 3 个进程相对来说，C 是短工作，因为其使用 CPU 的时间远远短于其花在 I/O 上面的时间，而 A、B 皆是长工作。
但相对来说，A 又是短工作，因为其使用 CPU 的时间短于 B 进程。
这样，STCF 调度的优先级就是 C、A、B。

使用 STCF 调度算法对 A、B、C 3 个进程的调度情况(每个字符占用 1 毫秒)

在 STCF 调度算法下，磁盘 90% 的情况下保持繁忙，这与只运行 C 一个进程的结果相同。
A 进程在系统启动后 55 毫秒结束，B 进程在系统启动后 159 毫秒结束，C 进程在系统启动后 99 毫秒结束。
故整个系统的平均响应时间为 104.3 毫秒。

若使用 FCFS 算法，如果 A 或者 B 在 C 之前到达，则磁盘将被闲置 150 毫秒才能第一次启动，磁盘的利用率将大大低于 STCF 调度算法。
而系统的响应时间(假定 A 在 B 前面)为 A 是 50 毫秒，B 是 150 毫秒，C 是 250 毫秒，系统的平均响应时间是 150 毫秒。

如果使用时间片轮转，假定时间片大小为 10 毫秒，按照 C、A、B 的顺序轮转，我们获取如图所示的调度情况：

使用时间片轮转调度算法对 A、B、C 3 个进程的调度情况

在时间片轮转情况下，系统的响应时间是 A 为 104 毫秒，B 为 159 毫秒，C 为 99 毫秒，系统平均响应时间为 120.67 毫秒。

由此可见，STCF 算法的响应时间确实最短。
当然，在时间片轮转的情况下，时间片选择的大小不同，结果将有所不同，但其响应时间不会短于 STCF 算法的响应时间。

但 STCF 调度算法也有缺点。第一是可能造成长程序无法得到 CPU 时间而导致“饥饿”。
除此之外，还有一个重大缺点，就是我们怎么知道每个进程还需要运转多久？难道我们能够预测将来不成？
就好像你第一次做某种事情时怎么知道需要多长时间呢？

这个时候就需要做研究！
我们可以用一些启发式(heuristic)方法来进行估算，例如，根据程序大小来推测一个程序所需 CPU 执行时间。但这个方法并不可靠。
另外一个办法就是先将每个程序运行一般，记录其所用 CPU 时间，这样在以后的运行中，即可根据这个实测数据来进行 STCF 调度了。

优先级调度算法

前面介绍的 STCF 算法有一个缺点是可能造成长进程“饥饿”。但这个问题比较容易解决，使用优先级即可。
优先级调度算法的原理是给每个进程赋予一个优先级，每次需要进程切换时，找一个优先级最高的进程进行调度。
这样，如果赋予长进程一个高优先级，则该进程就不会再“饥饿”。
事实上，STCF 算法本身就是一种优先级调度，只不过它给予短进程高优先级而已。

优先级调度的优点是可以赋予重要的进程以高优先级以确保重要任务能够得到 CPU 时间。
其缺点则与 STCF 算法一样，低优先级的进程可能会“饥饿”。
不过，这个问题在优先级调节算法里比在 STCF 里好解决：只要动态地调节优先级即可。
例如，在一个进程执行特定 CPU 时间后将其优先级降低一个级别，或者将处于等待进程的优先级提高一个级别。
这样，一个进程如果等待时间很长，其优先级将因持续提升而超越其它进程的优先级，从而得到 CPU 时间。
这样，“饥饿”现象就可以防止。

不过，优先级调度还有一个缺点，就是响应时间不能保证，除非将一个进程的优先级设置为最高。
即使将优先级设置为最高，但如果每个人都将自己进程的优先级设为最高，则响应时间还是无法保证。

混合调度算法

之前介绍的所有算法都存在缺点，我们自然想设计一个算法合并它们的优点，摒弃它们的缺点。这就是所谓的混合调度算法。
该算法的原理是将所有进程分成不同的大类，每个大类为一个优先级。
如果两个进程处于不同的大类，则处于高优先级大类的进程优先执行；如果两个进程处于同一个大类，则采用时间片轮转来执行。
混合调度算法的示意图如下：

其他调度算法

除了上面介绍的各种算法外，有的操作系统还实现了一些其他算法，它们包括：保证调度(Guaranteed Scheduling)、彩票调度(Lotery Scheduling)、用户公平调度(Fair Share Scheduling Per User)。
其中保证调度算法的目标是保证每个进程占用 CPU 的时间完全一样，即如果系统里一共有 n 个进程，则每个进程占用 CPU 的时间为 1/n。
保证调度算法就是保障每个进程使用 1/n 的 CPU 时间。保障就是肯定运转 1/n 的时间，而不是运转大概 1/n 时间。
那么保障调度和轮转调度是一样的吗？时间片轮转能不能达到 1/n 的效果？关键就是达到 1/n 不一定要靠轮转。
轮转是能够达到 1/n 的，但是保障调度不一定要轮转。每次给的时间片不一定要一样。

彩票调度算法是一种概率调度算法。若买过彩票就知道，买的越多中奖的概率越大。
在该算法里，给每个进程分发一定数量的彩票，而调度器则从所有彩票里随机抽取一张彩票，而持有该彩票的进程就获得 CPU。
这样，如果想让某个进程获得更多的 CPU 时间，我们可以给该进程多发几张彩票。
彩票调度算法的优越性是显而易见的，通过给每个进程至少一张彩票就可以防止“饥饿”，因为该进程获得 CPU 的概率将大于 0.
除此之外，彩票算法还可以用于模拟其他进程调度算法。
例如，如果给每个进程一样多的彩票，则该算法就近似保证调度算法；
如果给短任务赋予更多的彩票，则该算法将类似于短任务优先算法。

那么彩票调度算法有什么用呢？比如，如果要保障 A 进程 50% 的 CPU 时间，那么就把一半的彩票分给 A，这样的话就能保障 50% 的 CPU 时间。
别的调度方法也可能达到这个效果，但是不灵活。

用户公平调度算法按照每个用户而不是每个进程来进行公平分配。前面讲过的算法均以进程为单位。
这样一个贪婪的用户可以通过启动许多进程来抢占 CPU 时间。
如果每个用户都很贪婪，都试图启动很多进程，则将造成整个系统效率低下，甚至停顿。
用户公平调度算法就是将 CPU 时间按照用户进行平均分配。
如果一个用户的进程多，则其所拥有的进程所获得的 CPU 时间将短；反之，则多。

自然，CPU 调度算法并不只有上面介绍的几种。
由于不同系统的目标不同，不同进程的性质和重要性不同，因此进程调度也就不同。
事实上，调度算法非常多，有大量的论文可以参阅。

实时调度算法

实时系统是一种必须提供时序可预测性的系统。
由于其应用范围广和特性不同于一般计算机系统，因此其调度算法也别出一格，和前面讲过的所有调度算法均有所不同。
前面的算法主要考虑的是平均响应时间和系统吞吐率的问题，而实时系统则必须考虑每个具体任务的响应时间必须符合要求，即每个任务必须在什么时间之前完成，而无须考虑如何降低整个系统的响应时间或吞吐率。

比如，计算来袭导弹轨迹的进程，其计算时间是非常有限的。如果该进程不能在规定时间内计算出来袭导弹的轨迹，则结果毫无意义。
但如果能够在截止时间前完成，那么提前多少则无关紧要。这就是说，只要达到一定响应时间后，再提升响应时间并不能获得任何好处。

比如，视频输出，在 NTSC 制式下(美国、日本、中国台湾使用的电视视频制式)，只要每 33 毫秒发出一个图像桢，所看到的视频就是连贯的。
而即使发送得比这更快，也不会获得任何额外的好处。其他实时系统还有物理控制系统(如核反应堆控制温度的系统、汽车测速机制等)。

实时系统调度算法种类繁多。最主要或者说最经典的来个闹钟功能算法：动态优先调度和静态优先级调度。
动态优先级调度又称为最早截止任务优先(Earliest Deadline First, EDF)算法，而静态优先级调度又称为最短周期优先(Rate Monotonic Scheduling, RMS)算法。

EDF 调度算法

EDF 调度算法就是最早截止的任务先做。
如果新的工作来了，比正在运行的程序的截止时间更靠前，那么就抢占当前进程。EDF 调度算法是实时调度里面的最优算法。
如果一组任务可以被调度的话(指所有任务的截止时间在理论上能够满足)，则 EDF 可以满足。
一批任务如果不能全部满足，那么 EDF 能满足的任务数最多。这就是它最优的体现。

例如，任务 A 需要 15 毫秒执行时间，截止时间在进入到系统后第 20 毫秒，B 需要执行 10 毫秒，截止时间为进入系统后第 30 毫秒，C 需要 5 毫秒执行时间，截止时间为进入到系统后第 10 毫秒。
使用 EDF 调度算法的结果就是先运行 C ，再运行 A，最后运行 B。

EDF 调度算法就是 STCF 算法变化来的。
如果将 STCF 算法的任务所需执行时间变为截止时间，则抢占式 STCF 算法就是 EDF 调度算法

RMS 调度算法

EDF 算法是一种动态调度算法。意思是该算法动态地计算每个任务的截止时间并动态调节优先级。
如果需要，还会对当前进程进行抢占。虽然 EDF 算法在理论上是最优的，但动态计算截止时间和动态抢占 CPU 均要消耗系统资源，因此 EDF 算法实际效果比其理论效果要差一截。与 EDF 算法相对的是所谓的 RMS 调度算法。
该算法在进行调度前先计算出所有任务的优先级，然后按照计算出来的优先级进行调度，任务执行中间既不接收新的进程，也不进行优先级的调整或进行 CPU 抢占。因此这种算法的优点是系统消耗小，缺点是不灵活。
一旦该系统的任务决定了，就不能再接收新的任务。

进程调度的过程

在更换进程的时候到底有哪些操作需要完成呢？
首先，当然需要将当前进程的状态予以保护，以便将来能够重新执行。
然后是将选中的进程的环境布置好，这包括设置寄存器、栈指针、状态字等操作。
最后是跳转到选中的进程，也就是设置或恢复其程序计算器。下面给出的是调度进程时操作系统所执行的操作概览：

• 因时序或外部中断或进程挂起而导致操作系统获得 CPU 控制权
• 操作系统在所有就绪的进程中按照某种算法遴选进程
• 如果选中的是非当前进程，则操作系统将当前进程(中断或挂起的进程)状态予以保护
• 将选中的进程的环境布置好(设置寄存器、栈指针、状态字等)
• 跳转到选中的进程