本篇主要谈谈多久反馈队列，Multi-Level Feed-back Queue(MLFQ)。MLFQ试图解决的问题主要在两个方面。第一个需要优化“周转时间”，通过运行短任务优先的策略，但是操作系统并不是一开始就知道任务的长度，这个信息是上篇提到的SJF以及STCF运行的先决条件。其次，MLFQ需要让系统对交互性的程序也有较好的响应时间，RR类的调度策略减少了响应时间，但是周转时间大大提高了。因此，我们面对的问题是：给出我们一无所知的任务，如何构建一个调度器去达成这些目标？随着系统的运行，调度器如何去感知这些任务的性格（cpu密集型还是交互型），因此才能做一个更好的调度决策？
MLFQ：基本规则
MLFQ有一些相互独立的队列，每个队列都有不同的优先级。任何给定的时刻，一个任务运行在其中一个队列里。在某个时间点上MLFQ选择高优先级的任务。
同一个队列中存在多个任务时，任务们有相同的优先级。针对本队列任务会采用RR调度策略。因此我们提炼出MLFQ的两个基本规则。
- 规则1：如果A的优先级大于B的优先级，运行A（B不运行）
- 规则2：如果A，B优先级相同，那么A和B都轮流运行，采用RR调度策略。
MLFQ调度的关键点是调度器如何设定任务的优先级。MLFQ并不固定给每个任务一个优先级，而是随着任务的运行动态的调整优先级。举个例子，如果一个任务不停的放弃cpu，比如在等待I/O完成，MLFQ会保持它的高优先级，因为它是个交互式任务。相反如果一个任务占用cpu很长时间，MLFQ会减小它的优先级。通过这种方式MLFQ会随着任务的运行，不停的学习，进而预测任务的未来可能的运行方式。
如何改变优先级
在任务的生命周期中我们必须要决定MLFQ如何改变它的优先级。首先我们关注下我们考量的场景：一个交互式程序和cpu密集型的程序一起运行。交互式程序对响应时间敏感，而cpu密集程序对周转时间敏感。下列我们尝试着列举两条规则来调整优先级
- 规则3：当任务到达系统时，把它放在最高优先级队列中
- 规则4 ：如果任务用完整个时间片，把它从高优先队列往下移动一级，如果任务没用完时间片就放弃了，它仍然在之前的队列上。
当一个长任务和交互式任务同时运行时，交互式任务一直在最高优先级队列中，长任务不停的运行到最低优先级队列中，交互式任务仿佛穿插运行在长任务中一样。这样交互式任务获得了良好的响应时间，而长任务也获得了良好的周转时间。
当前MLFQ的问题
我们现在有了基本的MLFQ，似乎看起来是公平的，对长任务来说也会公平的分享cpu，对短任务或者IO敏感的交互式任务能更快的运行的。然而，这种实现方式还有严重的问题。
- 就是饿死的问题，如果系统中有太多的交互式任务运行，他们加起来会消耗掉所有的cpu时间，于是乎长任务不可能获得任何的cpu时间（饿死）。
- 有人甚至能根据这个调度策略编写程序来戏耍调度器。他们会想办法通过戏耍调度器的方式以谋取更多的cpu资源，当时间片快要用完的时候，立马放弃cpu，然后在申请的方式。这样使得任务一直保持在当前队列中以获得更多的cpu资源，这种方式几乎能独占cpu。
- 任务可能随着时间的改变，任务的性格也会发生改变。cpu密集型的程序可能后面在会变成交互型的程序，按照这种策略，到了最低优先级后无法在往上移动了，就无法重新被系统当做是交互式的任务。
优先级提升
有了上面的三个问题，这里有个基本的想法就是周期性的提升系统中任务的优先级。有很多方法去达成这个目标，这里说个最简单的办法，把任务放到最高优先级队列中，因此，产生了一条新规则。
- 规则5：在一段时间S后，把所有的任务移动到最高优先级队列中。
引用新规则后解决了两个问题，保证不会有任务被饿死。当cpu密集型的程序变成交互式程序时，能再次获得调度器的信任。
这个S的大小值得我们去关注，如果S值设置过大，长任务饿死的时间就会变长，如果S值设置过小，交互式程序就不会获得本该公平的cpu资源。
更好的统计方式
现在我们还剩一个问题去解决了，如何去避免有恶意程序戏耍调度器。在每个MLFQ等级的队列中，通过统计每个任务消耗的cpu时间，调度器会跟踪这些值。一旦一个程序用完他的分配量，它就会被降级到下一个队列。不管是否多次还是单次用完整个时间片，我们编写的新的规则4来描述。
-
规则4：一旦任务用完时间分配在给定队列中（不管中途多少次放弃cpu），它的优先级会被降低。
这个规则应用后，所有的任务都会下降优先级，只是交互式下降速度慢一点。同时这个规则也避免了有人能可以戏耍调度器的行为发生了。
MLFQ的其他问题
最大的问题如何参数化MLFQ，比如需要多少个队列，每个队列分配的时间片长度应该多少，多久该提升一次任务的优先级？这个没有个明确的答案，这里需要经验去权衡利弊。
大部分MLFQ都会允许不同队列不同的时间片长度。最高优先级队列通常用短的时间片，因为它们通常都有交互式的任务组成，它们之间能快速切换变得比较重要了（通常10ms或者更小），低等级的队列通常都是长任务组成，长时间片会更合适（通常100ms）。上图8.7中就时高优先级队列时间片更短，低优先级时间片更长。
Solaris的MLFQ的实现中，这些参数都是比较容易配置的，提供了一些列的表去配置，程序在生命周期中如何改变性格，时间片应该多长，多久应该提升一次优先级。系统管理员可以通过配置这些表使得调度器可以以不同方式去工作。表中默认值为有60条队列，缓慢的增加时间片长度从20ms到几百ms，每隔1s提升一次优先级。
其他的MLFQ调度器并不使用表来描述，他们调整优先级通过一个数学表达式。FressBSD调度器使用一个表达式来计算当前任务的优先级。表达式基于进程使用了多少cpu，随此之外，随着时间推移通过不同方式来提供优先级提升。
最后，许多调度器还有其他的一些特性。比如一些调度器会把系统程序一直保留在最高优先队列中，因此用户程序在系统中不能获取到最高优先级。其他一些系统中，允许用户建议帮助去调度器去提高优先级，比如通过nice指令可以提高或者降低任务的优先级。
MLFQ规则总结
- 规则1：当任务优先级A大于任务优先级B时，运行A
- 规则2：当任务优先级相同时，采用RR运行方式。
- 规则3：当任务刚到达系统时，会把放置到最高优先级队列中
- 规则4：一个任务用完了时间片，会降低优先级，不论是否间歇性的很多次用完的
- 规则5：每个周期性的时间S，会把系统中所有的任务移动到最高优先级队列中
MLFQ是自我学习式的调度方式，对长任务以及交互式任务都是友好的。因为这个原因，BSD UNIX以及Slolaris以及WindowsNT的调度器都是以MLFQ。Linux除外，Linux调度方式下篇我们会谈到。
网友评论