进程调度， 一个调度器的自白

我是一个进程调度器。

我的职责是调度计算机内所有的进程，为他们分配 cpu 资源。

1. 批处理时代

想当初，操作系统创造我时，只是打算让我用 fcfs 调度算法，简单维护下进程的秩序。但我后来的发展，远远超过了他的想象。

1.1 fcfs

所谓 fcfs 就是「先来先服务（first come first serve）」，每个进程按进入内存的时间先后排成一队。每当 cpu 上的进程运行完毕或者阻塞，我就会选择队伍最前面的进程，带着他前往 cpu 执行。

就拿这几个进程来说吧：

按照 fcfs 算法，我就会就按 a，b，c，d，e这样的顺序来将他们送往 cpu：

这一算法听起来简单又公平，然而好景不长，我收到了一个短进程的抱怨：”上次我前面排了一个长进程，等了足足 200 秒他才运行完。我只用 1 秒就运行结束了，就因为等他，我多花了这么长时间，太不值得了。”

我仔细一想， fcfs 算法确实有这个缺陷——短进程的响应时间太长了，用户交互体验会变差。

所以我决定，更换调度算法。

1.2 spn

这次我设计的算法叫做「短任务优先」（shortest process next，spn）。每次选择预计处理时间最短的进程。因此，在排队的时候，我会把短进程从队列里提到前面。

这一次，短进程得到了很好的照顾，进程的平均响应时间大大降低，我和操作系统都很满意。

但长进程们不干了：那些短进程天天插队，导致他们经常得不到 cpu 资源，造成了「饥饿」现象。

取消 spn 算法的呼声越来越高。

这可是个大问题。fcfs 虽然响应时间长，但最后所有进程一定有使用 cpu 资源的机会。但 spn 算法就不一样了，如果短进程源源不断加入队列，长进程们将永远得不到执行的机会——太可怕了。

因此，短任务优先算法需要得到改进。有什么方法既能照顾短进程，又能照顾长进程呢？

1.3 hrrn

经过和操作系统的讨论，我们决定综合考量进程的两个属性：等待时间和要求服务时间——等待时间长，要求服务时间短（就是短进程）的进程更容易被选中。

为了量化，我们制定了一个公式：响应比 = （等待时间+要求服务时间）/ 要求服务时间。响应比高的算法会先执行。我们称之为「高响应比优先」（highest response ratio next，hrrn）。

这个算法得到了长短进程的一致好评。虽然我的工作量增加了（每次调度前，我都要重新计算所有等待进程的响应比）但为了进程们的公平性，这一切都是值得的。

2. 并发时代

新时代到了。

随着计算机的普及，个人用户大量增长，并发，即一次运行多个程序的需求出现了。这可难倒我了——处理器只有一个，怎么运行多个程序？

所幸 cpu 点醒了我：“我现在的运算速度既然这么快，何不发挥这项长处，弄一个「伪并行」出来？“

“伪并行？什么意思”

“就是看起来像并行，实际上还是串行。每个进程短时间交替使用我的资源，但在人类看来，这些进程就像在「同时」运行。”

我恍然大悟。

2.1 rr

经过 cpu 的提醒，我很快制定出了新的调度算法——时间片轮转算法（round robin，rr）。

在这个算法里，每个进程将轮流使用 cpu 资源，只不过在他们开始运行时，我会为他们打开定时器，如果定时器到时间（或者执行阻塞操作），进程将*「下机」，切换至下一个进程。至于下一个进程的选择嘛，直接用 fcfs 就好了。

新的算法必然会面临新的问题，现在我的问题就是，时间片的长度怎么设计？

直观来看，时间片越短，固定时间里可运行的进程就越多，可 cpu 说过，切换进程是要消耗他不少指令周期的，时间片过短会导致大量 cpu 资源浪费在切换上下文上。时间片过长，短交互指令响应会变慢。所以具体怎么取，还得看交互时间大小（感觉像没说一样，但至少给了个标准嘛）。

这一阶段，我的工作量大大提升——以前十几秒都不用切换一次程序，现在倒好，一秒钟就得切换数十次。

2.2 vrr

时间片轮转算法看起来十分公平——所有的进程时间片都是一样的。但事实真是这样吗？

i/o 密集型进程不这么认为，他对我说：“调度器大哥，时间片轮转没有照顾到我们这类进程啊！我们经常在 cpu 没呆到一半时间片，就遇到了阻塞操作，被你赶下去。而且我们在阻塞队列，往往要停留很长时间。等阻塞操作结束，我们还得在就绪队列排好长时间队。那些处理器密集型进程，使用了大部分的处理器时间，导致我们性能降低，响应时间跟不上”

考虑到这些进程的要求，我决定为他们创建一个新的辅助队列。阻塞解除的进程，将进入这个辅助队列，进行进程调度时，优先选择辅助队列里的进程。

这就是「虚拟轮转法」（virtual round robin，vrr）。

从后来实际性能结果来看，这种方法确实优于轮转法。我颇为自豪。

2.3 优先级调度

有一天，操作系统忽然找到我，神神秘秘的说：“调度器啊，你是知道的，我要给整个系统提供服务，可最近用户进程太多，导致我的服务进程有时候响应跟不上。我有点担心这会给系统稳定性造成影响。”

我一听，这可是个大事，系统不稳定那还得了？调度算法得换！

既然要让操作系统的服务得到足够的运行资源，那就，干脆让他们具有最高的 cpu 使用优先权吧。

优先级调度算法就此产生了。

我向大家做出了规定——每个进程将被赋予一个优先级，自己根据自己的情况确定优先级数值，但是，用户进程的优先级不准高于内核进程的优先级。

切换程序的时候，我会从优先级 1 的队列里选择一个进程，如果优先级 1 队列为空，才会选择优先级 2 中的进程，以此类推。

当然，为了保证低优先级进程不会饥饿，我会调高等待时间长的进程的优先级。

使用这个算法，我更忙碌了，不仅需要大量切换进程，还需要动态调节优先级。可能这就是能力越大，责任越大吧。

不过我知道，正是因为我的存在，人类才能在计算机上运行多道程序——这令我感到自豪。

希望你在看完我的文章之后有所收获。

感谢你的阅读，我们后会有期！

声明：原创文章，未经授权，禁止转载