OSTEP[7-10] High-level Policies An OS Scheduler Employs

文 | YoungChen

封面 | Matthew Henry

CPU Scheduling

首先假设：操作系统了解每个任务运行时间的长短，文章介绍了两类调度策略，第一类是选择执行时间最短的任务先运行（STCF），全称 Shortest Time-to-Completion First，这样可以最小化系统回转时间（turnaround time），但问题是虽然 STCF 在减小系统回转时间上表现得非常好，但当我们新增加响应时间指标时（response time），它就无法解决问题了，STCF 会拖长系统响应时间，带来糟糕的用户体验。

第二类策略叫 RR，全称 Round-Robin，意为任务间轮番运行，每次运行时间是一个时间分片（time-slice），这样可以最小化响应时间，而且时间分片越小，系统响应时间越短，但进程切换也越频繁，系统开销越大，这是个利弊权衡的问题，因此时间分片的大小需要合理。但如果将系统回转时间重新考虑进来，很可惜 RR 这种策略就又是灾难性的了。

假如我们再把 IO 考虑进来呢？进程通常需要 IO 操作，当某个进程等待 IO 完毕时将 CPU 让给其他进程，最大化保证 CPU 处于满载运行状态，例如下图，但可惜的是还是没解决问题。

因为上述内容基于一个“不可能”的假设：操作系统知晓进程允许时间，而实际上操作系统是很难知晓一个任务的具体运行时长的。为了解决这个问题，我们介绍现代操作系统常用的思路，多级反馈队列，核心思想是能根据当下的情况预测未来的行为。

The Multi-Level Feedback Queue

多级反馈队列（MLFQ）目的解决两类问题，第一是优化系统回转时间，我们之前聊过，方法是优先运行执行时间短的任务（job），但问题是操作系统很难知晓任务具体的运行时长。第二个目标是对用户交互反应迅速，上文也聊过，是通过轮询加时间分片机制实现，缺点是无法兼顾系统回转时间。

MLFQ 由多个不同的队列组成，每个队列授予一个优先级，任务可以在队列间移动，但是保证某个时刻一个任务仅处于一个队列中，MLFQ 会根据优先级决定先运行哪个任务，如果两个任务优先级一样，则二者通过 RR 机制交替运行。

显然 MLFQ 的关键在于如何确定任务优先级，它通过观察当下任务的行为动态调整任务所处的队列，从而调整任务运行优先级。例如当一个任务放弃 CPU 等待用户输入，操作系统就维持它的高优先级，因此当输入完毕之后任务可以迅速被调度到，缩短响应时间；如果一个任务长时间占用了 CPU，操作系统就调低它的优先级，让其他高优先级任务先运行。

例如下图是一个 MLFQ 的例子，由于 AB 两个任务优先级最高，调度器会让二者交易运行，C 和 D 的优先级较低，调度器会先将二者晾在一边。

下面细述如何调整优先级，由三条规则控制，当一个新任务加入进来时，先默认处于最高优先级的队列中；当一个任务运行一个时间分片后还未结束的，其优先级开始降低；当一个任务在时间分片中途释放了 CPU，则其当前优先级不变。下面通过例子看看：

这是个运行时间很长的任务，它刚进来时先处于 Q2，优先级最高，运行完毕一个时间分片后降级到 Q1，再然后继续降级到 Q0，优先级最低的队列后一直处于 Q0 直到运行完毕。

当下的 MLFQ 有个问题，一是优先级低的任务可能会饿死，因为新来的任务很多，而且运行时间都很短，调度器会一直让优先级高的队列中的任务运行，从而优先级低的任务分配不到 CPU，一直处于饥饿状态；二是用户可能编写代码尝试控制调度器一直调度自己的任务，例如我尝试通过 IO 操作释放 CPU 让自己的程序一直处于优先级高的队列中，这可能造成某些任务垄断 CPU。

如何解决这个问题呢，方法叫优先级重置（The Priority Boost），很简单就是说隔一段时间，我就一次性把所有任务重新放到优先级最高的队列中去。

这样一来，当大家都处于最高队列中时，调度器会通过 RR 轮询分配 CPU，因此所有任务都会被分配到，不至于饿死；二来如果是 IO 绑定型的任务，通过重置优先级，调度器可以顺利纠正它的行为。

为了规避用户程序对调度器的恶意控制，操作系统需要仔细计算在每个层级的队列中，任务都消耗了多少时间，如何一个任务耗光了为其分配的 CPU 时间，降级它的优先级。

如何配置 MLFQ 呢，例如它应该有多少个队列，每个队列的时间分片是多长，隔多长时间重置一次等。

遗憾的是这些没有标准答案，需要经验和调优。一般来说优先级高的队列时间分片越短，因为这些任务可能是交互式的，在它们之间进行短轮询作业比较合理；而低优先级的队列经常充斥着长时间运行的任务，给予它们更长的时间分片也是合理的。

Multi-CPU Scheduling

多核处理器越发常见，能加速应用执行速度，但平时单个应用仅使用一个 CPU，要想使用多核的福利，需要用户撰写能够并发执行的代码，这种技术采用多线程并发执行任务，从而可以利用到多个 CPU。

但问题是如何在多核间进行调度，关键在于 CPU 缓存，CPU 会将内存数据缓存一份在 CPU Cache 里，这叫局部性（locality），又可分为时间局部性（temporal locality）和空间局部性（spatial locality），前者是说当一份数据被访问之后，它很可能很快被再次访问。例如一个 for 循环内部同一个变量被反复访问的情况；后者是说当某个地址的数据被访问时，与它相邻的数据也很可能被访问，例如数组。

CPU Cache 的存在会带来缓存一致性问题，因为 CPU 总是先更新 Cache 的数据，写回内存是慢操作，会之后再进行不是同步进行的。硬件通过总线窥探技术（bus snooping），CPU 通过连接到内存的总线监听数据更新，当监听到某个数据更新时，让自己缓存中的数据过期强制从内存中拉取。

有了硬件保证用户代码还是需要关心并发问题，通常要使用锁来保证并发访问共享数据的一致性，否则在多核之间访问共享数据通常不会得到期望的结果。

还有个问题是 cache affinity，一个进程运行在 CPU 1 上，它会在 CPU 1 的缓存中维护一些自己的状态信息，当进程再次运行在 CPU 1 上时恢复上下文的速度就会很快，如果调度到不同的 CPU 上的话由于 Cache 里没有关于这个进程的状态信息，需要重新从内存获取（一致性协议）因此速度就变慢了，因此调度器最好能保证进程永远在同一个 CPU 上运行。

有了上述的基础，我们下面叙述如何构建一个多核调度器，首先想到的解决方案很简单，我们复用下单核下的调度策略，将所有的任务塞进单个队列里，一个个取出来就行了，这种方案叫 SQMS，全程 singlequeue multiprocessor scheduling，但缺点是低效而且无法避免 cache affinity 问题，如下图：

由于每个任务都允许一个时间分片，因此无法保证单个任务被同一个 CPU 调度到，从而无法避免 cache affinity 问题。有的 SQMS 用一些特殊的策略来尽可能保证单个任务运行在同一个 CPU 上，实在不行的情况下才换核执行：

为了解决 SQMS 的缺点，诞生了 MQMS，全程叫 multi-queue multiprocessor scheduling，思想就是为每个 CPU 分配一个调度队列，假设两个队列 Q0 和 Q1 分别分配给两个 CPU：

每个队列中有两个任务，现在 CPU 采用 RR 的方式来执行两个任务：

MQMS 很好地解决了扩展性和 cache affinity 的问题，但缺点在于无法做到负载均衡（load imbalance），如果 Q0 的两个任务很快执行完成了，Q1 的两个任务却很慢，那么此时 CPU0 将处于空闲状态，CPU 1 反而要执行两个任务，这显然不太合理，我们浪费了 CPU0 的计算资源。

显然我们需要一种机制让任务可以在不同的队列间迁移（migration），系统该怎么做呢？有种技术叫 work stealing，空闲的队列定期选择一个目标队列，查看它里面的任务是否比自己满，是的话就从中取出几个帮忙执行，从而达到负载均衡的目的，但是这种窥探频率不能过高，否则影响性能。

Linux 社区中出现过三种类型的多核调度器，分别是 O(1)、CFS（Completely Fair Scheduler）、BS（BF Scheduler），其中前两者都是多队列，BS 是单个队列，可见什么技术都可以达到效果取决于怎么设计。

参考资料

《Operating System：Three Easy Pieces》