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

Operating System:Three Easy Pieces

Posted by ChenJY on August 3, 2020 | Viewed times
本站图床基于新浪微博,图片加载异常请强制刷新或直接访问语雀空间查阅文章备份

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 处于满载运行状态,例如下图,但可惜的是还是没解决问题。

undefined

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

The Multi-Level Feedback Queue

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

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

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

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

undefined

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

undefined

这是个运行时间很长的任务,它刚进来时先处于 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 通过连接到内存的总线监听数据更新,当监听到某个数据更新时,让自己缓存中的数据过期强制从内存中拉取。

undefined

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

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

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

undefined

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

undefined

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

undefined

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

undefined

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 是单个队列,可见什么技术都可以达到效果取决于怎么设计。


Comment