《操作系统导论》中对于多级反馈队列的原理、设计思路和规则给了清晰的论述，看完之后心血来潮想要摘抄总结一下这块知识点。

多级反馈队列

调度算法的优化

对于调度算法需要解决两方面的问题，首先要优化周转时间，可以通过先执行短工作来实现，然而操作系统通常不知道工作要运行多久。其次调度算法希望给交互用户很好的交互体验，因此需要降低响应时间。然而像轮转这样的算法虽然降低了响应时间，周转时间却很差。所以这里的问题是：通常我们对进程一无所知，应该如何设计调度算法？

多级反馈队列原理

多级反馈队列调度算法(multileved feedback queue, MLFQ)不必事先知道各种进程所需的执行时间，还可以较好地满足各种类型进程的需要，是目前公认的一种较好的进程调度算法。
image.png
多级反馈队列调度算法设置多个就绪队列，并为每个队列赋予不同的优先级，第一个队列的优先级最高，其余队列的优先级逐个降低。不同队列中的进程所赋予的执行时间片的大小也各不相同，在优先级愈高的队列中其时间片就愈小。
接着每个队列都采用 FCFS 算法，当新进程进入内存后先将它放入第一等待队列的末尾进行调度。如果该进程能在该时间片内完成便可撤离，否则调度程序将其转入第二队列的末尾等待调度。当进程最后被降到第 n 队列后，在第 n 队列中按 RR 调度算法运行。

设置优先级

MLFQ 调度策略的关键在于如何设置优先级，MLFQ 没有为每个工作指定不变的优先顺序，而是根据观察到的行为调整它的优先级。例如，如果一个工作不断放弃 CPU 去等待键盘输入，这是交互型进程的可能行为，MLFQ 因此会让它保持高优先级。相反，如果一个工作长时间地占用 CPU，MLFQ 会降低其优先级。MLFQ 在进程运行过程中学习其行为，从而利用工作的历史来预测它未来的行为。至此，我们得到了 MLFO 的两条基本规则。

  1. 如果 A 的优先级 > B 的优先级，运行 A（不运行 B）；
  2. 如果 A 的优先级 = B 的优先级，轮转运行 A 和 B。

image.png

改变优先级

在一个工作的生命周期中，MLFQ 改变优先级主要基于工作负载：既有运行时间很短、频繁放弃 CPU 的交互型工作，也有需要很多 CPU 时间、响应时间却不重要的长时间计算密集型工作。根据这样的原则，可以采用以下 3 个规则：

  1. 工作进入系统时，放在最高优先级（最上层队列）。
  2. 工作用完整个时间片后，降低其优先级（移入下一个队列）。
  3. 如果工作在其时间片以内主动释放 CPU，则优先级不变。

对于长工作，在一个有 3 个队列的调度程序中，该工作首先进入最高优先级。随着时间的推移，这个工作会逐渐降低优先级，最后进入最下面的队列。
image.png
而如果有两个工作，分别是一个长时间运行的 CPU 密集型工作 A，和一个运行时间很短的交互型工作 B。假设 A 执行一段时间后 B 到达，由于 B 的运行时间很短，经过两个时间片，在被移入最低优先级队列之前就执行完毕，然后 A 继续运行。
image.png
如果进程在时间片用完之前主动放弃 CPU，则保持它的优先级不变。这条规则的意图是，在交互型工作中有大量的 I/O 操作的情况下，它会在时间片用完之前放弃 CPU。此时我们不想处罚它，只是保持它的优先级不变。例如交互型工作 B 每执行一小段时间便需要进行 I/O 操作，它与长时间运行的工作 A 竞争 CPU。MLFQ 算法保持 B 在最高优先级，这样就可让交互型工作快速运行。
image.png

提升优先级

上述改变优先级的规则会产生一些问题，首先会导致饥饿，如果系统有“太多”交互型工作，就会不断占用 CPU，导致长工作永远无法得到 CPU。
image.png
一个简单的思路是周期性地提升（boost）所有工作的优先级，经过一段时间 S，就将系统中所有工作重新加入最高优先级队列。这样的规则能让进程不会饿死，在最高优先级队列中，它会以轮转的方式，与其他高优先级工作分享 CPU，从而最终获得执行。其次如果一个 CPU 密集型工作变成了交互型，当它优先级提升时，调度程序会正确对待它。
image.png
S 值的确定是关键所在，如果设置得太高，长工作会饥饿，如果设置得太低，交互型工作又得不到合适的 CPU 时间比例。

CPU 计时

上述的规则中可能还会有恶意程序的问题，这类程序会使用一些手段欺骗调度程序，让它给你远超公平的资源。例如进程在时间片用完之前，调用一个 I/O 操作主动释放 CPU，如此便可以保持在高优先级，占用更多的 CPU 时间。
image.png
这是因为工作在时间片以内释放 CPU，之前的规则是保留它的优先级。解决方案是为 MLFQ 的每层队列提供更完善的 CPU 计时方式（accounting），调度程序应该记录一个进程在某一层中消耗的总时间，而不是在调度时重新计时。只要进程用完了自己的配额，就将它降到低一优先级的队列中去。
image.png

MLFQ 工作规则

经过上述的分析，可以总结出 MLFQ 基于以下基本规则来工作：

  1. 如果 A 的优先级 > B 的优先级，运行 A；
  2. 如果 A 的优先级 = B 的优先级，轮转运行 A 和 B；
  3. 工作进入系统时，放在最上层队列。
  4. 一旦工作用完了其在某一层中的时间配额（无论中间主动放弃了多少次），就移入低一级队列；

  5. 经过一段时间 S，就将系统中所有工作重新加入最高优先级队列。

    比例份额算法

    比例份额（proportional-share）调度算法，有时也称为公平份额（fair-share）调度程序，它的目的是确保每个工作获得一定比例的 CPU 时间，而不是优化周转时间和响应时间。基本思想是：每隔一段时间，都会举行一次彩票抽奖，以确定接下来应该运行哪个进程。越是应该频繁运行的进程，越是应该拥有更多地赢得彩票的机会。

    彩票数

    算法使用彩票数（ticket）来刻画，一个进程拥有的彩票数占总彩票数的百分比，就是它占有资源的份额。假设有两个进程 A 和 B，A 拥有 75 张彩票，B 拥有 25 张，因此我们希望 A 占用
    75% 的 CPU 时间，而 B 占用 25%。
    调度程序知道总共的彩票数（例如有 100 张），调度程序抽取中奖彩票（0~99），拥有这个数对应的彩票的进程中奖并被调度。假设进程 A 拥有 0~74 的彩票，进程 B 拥有 75~99，则一次中奖彩票序列如下：
    image.png
    对应的调度结果如下：
    image.png
    彩票调度中利用了随机性，这导致了从概率上满足期望的比例，但并不能确保。这两个工作运行得时间越长，它们得到的 CPU 时间比例就会越接近期望。随机性方法的优点有：

  6. 随机方法常常可以避免各种奇怪的边界情况；

  7. 随机方法几乎不需要记录任何状态；
  8. 随机方法运行速度快。

    彩票机制

    彩票调度还提供了一些机制，以不同且有效的方式来调度彩票。
彩票机制 说明
彩票货币（ticket currency） 允许拥有一组彩票的用户以他们喜欢的某种货币，将彩票分给自己的不同工作。
彩票转让（ticket transfer） 通过转让，一个进程可以临时将自己的彩票交给另一个进程。
彩票通胀（ticket inflation） 利用通胀，一个进程可以临时提升或降低自己拥有的彩票数量。

彩票调度数据结构

彩票调度只需要一个随机数生成器来选择中奖彩票，和一个记录系统中所有进程的数据结构（一个列表）即可实现。在做出调度决策之前，首先要从彩票总数中选择一个随机数（中奖号码），然后遍历链表找到被调度的程序即可。
image.png
要让这个过程更有效率，建议将列表项按照彩票数递减排序。这个顺序并不会影响算法的正确性，但能保证用最小的迭代次数找到需要的节点。

彩票分配

如何为工作分配彩票是一个非常棘手的问题，系统的运行严重依赖于彩票的分配。假设用户自己知道如何分配，可以给每个用户一定量的彩票，由用户按照需要自主分配给自己的工作。但是大部分情况下无法让用户直接指定彩票数，因此对于给定的一组工作，彩票分配的问题依然没有最佳答案，导致这种算法目前没有广泛应用。

多处理器调度

多核处理器（multicore）将多个 CPU 核组装在一块芯片上，多核 CPU 带来了许多困难，主要是典型的应用程序都只使用一个 CPU，增加了更多的 CPU 并没有让这类程序运行得更快。为了解决这个问题，不得不重写这些应用程序，使之能并行（parallel）执行。多线程应用可以将工作分散到多个 CPU 上，因此 CPU 资源越多就运行越快。

多 CPU 带来的问题

cache 一致性

在单 CPU 系统中，存在多级的硬件缓存（hardware cache)，一般来说会让处理器更快地执行程序。如果系统有多个处理器，并共享同一个内存，多 CPU 的情况下缓存要复杂得多。假设一个运行在 CPU1 上的程序从内存地址 A 读取数据，由于不在 CPU1 的缓存中，所以系统直接访问内存得到值 D。程序然后修改了地址 A 处的值，只是将它的缓存更新为新值 D’。将数据写回内存比较慢，因此系统（通常）会稍后再做。假设这时操作系统中断了该程序的运行，并将其交给 CPU2，重新读取地址 A 的数据，由于 CPU2 的缓存中并没有该数据，所以会直接从内存中读取，得到了旧值 D，而不是正确的值 D’。
image.png
这一普遍的问题称为缓存一致性（cache coherence）问题，基本解决方案是通过监控内存访问，硬件可以保证获得正确的数据，并保证共享内存的唯一性。

同步

跨 CPU 访问共享数据或数据结构时，需要使用互斥原语（比如锁）才能保证正确性，其他方法如使用无锁（lock-free）数据结构很复杂，偶尔才使用。随着 CPU 数量的增加，访问同步共享的数据结构会变得很慢。

缓存亲和度

缓存亲和度（cache affinity）问题是，一个进程在某个 CPU 上运行时，会在该 CPU 的缓存中维护许多状态。下次该进程在相同 CPU 上运行时，由于缓存中的数据而执行得更快。相反，在不同的 CPU 上执行，会由于需要重新加载数据而很慢。

单队列调度

多处理器系统的调度程序中，最基本的方式是简单地复用单处理器调度的基本架构，将所有需要调度的工作放入一个单独的队列中，称之为单队列多处理器调度（Single Queue Multiprocessor Scheduling, SQMS）。
image.png
这个方法最大的优点是简单，不需要太多修改，就可以将原有的策略用于多个 CPU。主要的缺点是缺乏可扩展性（scalability），为了保证在多 CPU 上正常运行，调度程序的开发者需要在代码中通过加锁（locking）来保证原子性，锁可能带来巨大的性能损失。第二个主要问题是缓存亲和性，这种方法可能会导致每个工作在不同的 CPU 中频繁转移。

多队列调度

有些系统使用了**多队列多处理器调度（Multi-Queue Multiprocessor Scheduling, MQMS），基本调度框架包含多个调度队列，每个队列可以使用不同的调度规则，比如轮转或其他任何可能的算法。当一个工作进入系统后，系统会依照一些启发性规则将其放入某个调度队列，每个 CPU 调度之间相互独立，就避免了单队列的方式中由于数据共享及同步带来的问题。
image.png
MQMS 比 SQMS 有明显的优势，队列的数量会随着 CPU 的增加而增加，因此锁和缓存争用的开销不是大问题。此外 MQMS 所有工作都保持在固定的 CPU 上，因而可以很好地利用缓存数据。

参考资料

《操作系统导论》[美]Remzi H.Arpaci-Dusseau，Andrea C.Arpaci-Dusseau 著，王海鹏 译，人民邮电出版社