OSTEP 全称叫《Operating System：Three Easy Pieces》，从 virtualization, concurrency, 和 persistence 三个角度谈论操作系统的设计和实现，是威斯康辛的研究生教材，即使本科不修 CS 的人也可以阅读，写得非常通俗易懂，是值得推荐的操作系统入门读物，难度较 CSAPP 低一点，可以先读这本再去看 CSAPP。书籍的章节 PDF 是开源的，地址在：http://pages.cs.wisc.edu/~remzi/OSTEP/。
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 由多个不同的对列组成，每个队列授予一个优先级，任务可以在队列间移动，但是保证某个时刻一个任务仅处于一个对列中，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 里，这叫局部性，又可分为时间局部性和空间局部性，时间局部性就是说当一份数据被访问之后，它很可能很快被再次访问。例如一个 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 是单个队列，可见什么技术都可以达到效果取决于怎么设计。
-
Previous
OSTEP[4-6]：Low-level Mechanisms Of Running Processes -
Next
OSTEP[13-15] Address Space And Address Translation
Comment