08. Scheduling The Multi-Level Feedback Queue¶

总体来说，人们对进程是一无所知的，不知道任务有哪些，也不知道任务时间的长短。没有完备的知识如何调度？

这章介绍一种著名的调度方法：Multi-Level Feedback Queue

它解决了两方面的问题：

1. 对于短任务，优化周转时间（Turnaround time，从提交到完成之间的时间）

2. 对于交互任务，降低响应时间（Response time，从提交到运行之间的时间）

像轮转这样的算法，虽然降低了响应的时间（每个任务很快能分到一个时间片），但是周转时间却很差（短任务的完成速度被拖长了）。 「预测」是关键。分支预测（CPU 在流水线里提前猜条件），cache 预测，还有这章中介绍的多级反馈队列，都是根据历史数据来预测。

MLFQ: 算法规则¶

MLFQ 具有多个队列，每个队列有不同的优先级。

• 规则 1：优先执行优先级高的队列中的工作

• 规则 2：每个队列中可以只有一个工作，也可以有多个工作，如果有多个工作时，那这个队列中的每个工作有相同的优先级。这时对同优先级的工作进行轮转，每执行一个工作的固定的时间片然后切换到另一个工作的该固定时间片。

关键是优先级是如何设置的？MLFQ will try to learn about processes as they run, and thus use the history of the job to predict its future behavior.

如何调整优先级¶

• 规则 3：工作进入系统时，放在最高优先级（最上层队列）。

• 规则 4a：工作用完整个时间片后，优先级减一。

• 规则 4b：如果工作在其时间片内主动释放 CPU，可以维持优先级不变。-- 这种情况一般有两种可能：1）进程在一个时间片内就发出来 I/O 请求导致阻塞；说明这是交互式进程。2）进程在一个时间片内就结束工作了，说明这个进程的执行时间很短。

整体的感觉是，所有的工作一进来都默认是最高优先级，在慢慢地在下一轮时间片中放进更低的优先级。

缺点：

CPU 一直被高优先级队列中的进程所占用，而低优先级队列中的进程将无法获得 CPU，而一直处于“饥饿”状态。

流氓软件可以滥用规则 4b，game the scheduler. （举例：进程在时间片用完之前，调用一个 I/O 操作​，从而主动释放CPU，从而获得更高优先级。）

针对这种滥用的漏洞，重写规则 4：

规则 4: 一旦工作用完了其在某一层中的时间配额（无论中间主动放弃了多少次CPU）​，就降低其优先级（移入低一级队列）。

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