[What]Scheduling:The Multi-Level Feedback Queue

理解调度策略中的 多级反馈队列(Multi-level Feedback Queue, MLFQ)

MLFQ 的目的就是要尽量实现很短的轮转时间和响应时间。

MLFQ 具有多个独立的队列,每个队列代表着不同的优先级。

任务根据不同的优先级而被放入不同的队列:

  • 高优先级队列中的任务先运行
  • 相同优先级的任务采用 round-robin 策略分时轮询调度

MLFQ 自动的为任务分配优先级(根据任务的行为而预测):

  • 当一个任务是 IO 密集型(占用的 CPU 时间少)时, 会提高其优先级
    • 因为这样可以提高任务的响应速度,用户体验好
  • 当一个任务是 CPU 密集型(占用的 CPU 时间多)时, 会降低其优先级
    • 因为 IO 密集型占用 CPU 时间少,所以要让它先执行,更多的时间会留给 CPU 密集型。

普通策略

  • 当任务被创建时,它被默认放置在最高优先级队列,此时最高优先级队列使用 RR 策略轮询调度
  • 当一个任务完整的使用了调度的时间片,那么降低其优先级
    • 这意味着被调度过程中没有进行 IO 操作,属于 CPU 密集型且执行时间较长
  • 当一个任务在时间片耗尽之前就主动放弃了 CPU,那么保持其优先级
    • 属于 IO 密集型或任务本身执行时间就短

此调度策略具有一下不足:

  1. 如果当前有很多的 IO 密集型任务,那么就需要轮询调度它们,这样低优先级的 CPU 密集型任务便会被饿死(starve)
  2. 如果某个 IO 密集型任务做的 IO 时间很短,而占用了 99% 的时间片时间。按照当前策略也不会降低其优先级,

最终的结果就是此任务占用了绝大部分 CPU 时间,低优先级任务每次运行时间极短。

  1. 某些任务很可能会根据当前运行状态的不同,时而是 CPU 密集型,时而是 IO 密集型。那么当它是 IO 密集型时,

这部分的响应时间就极长(因为当它为 CPU 密集型时其优先级已经被降低了)

优先级提升

为了解决低优先级任务被饿死的情况,采用优先级提升的策略:每隔一定调度周期 S,将所有任务的优先级提升到最高优先级队列中。

这样所有的任务就会使用 RR 策略轮询调度:

  • CPU 密集型任务就会被调度
  • 当任务切换为 IO 密集型任务时,它的优先级便会被保持

这里的问题就在于 S 的值该如何设置:

  • 如果设置得太小,那相当于所有的任务都在最高优先级了,IO 密集型任务的响应时间便会被拉长
  • 如果设置得太大,低优先级的 CPU 密集型任务的调度时间依然太短

调度计数

前面通过查看一个任务是否占满调度时间片来确定是否降低优先级的方式并不科学, 因为这个层面太微观了,仅凭一次的调度时间就改变优先级,对于那种会转变状态的任务并不公平。 应该站在更为宏观的层面来统计一个任务被调度的总时间与阈值比较。

  • 一旦一个任务调度的时间超过其阈值,便降低其优先级

基于这种策略,便可以避免一些任务由于是 IO 密集型且每次调度低于时间片而一直占有 CPU 的情况, 它会被降级以使得 CPU 密集型任务可以被调度。

量化参数

根据以上改进,最终得出 MLFQ 策略规则如下:

  • 当任务被创建时,它被默认放置在最高优先级队列,此时最高优先级队列使用 RR 策略轮询调度
  • 一旦一个任务调度的时间超过其阈值,便降低其优先级
  • 每隔一定调度周期 S,将所有任务的优先级提升到最高优先级队列中。

与 MLFQ 的相关参数有:

  • 优先级队列的个数
  • 每个优先级队列每次调度的时间片长度
  • 每隔多久提升优先级
  • 计数阈值的设置

这些参数都需要根据实际情况而做调整,以下是常用的经验设定:

  • 高优先级队列的时间片要低于低优先级队列的时间片
    • 这样保证高优先级的高响应速度和低优先级的吞吐量
Last Updated 2019-08-29 四 07:38.
Render by hexo-renderer-org with Emacs 26.1 (Org mode 9.1.14)