-
多级反馈队列(MLFQ, Multi-Level Feedback Queue)的思想
- 在系统中维护多个等级（优先级）不同的独立队列，一个进程在某一时刻存在且仅存在于其中一个队列中，利用反馈信息决定某个工作的优先级，优先级较高的进程优先执行，优先级相同的进程轮转（RR）执行
-
多级反馈队列的问题以及如何解决这些问题
-
MLFQ - Version 1
- 策略
- 如果A的优先级>B的优先级，则运行A
- 如果A的优先优先级==B的优先级，则轮转运行A和B
- 进程进入系统时，放在最高优先级队列
- 进程用完整个时间片后，降低其优先级（移至下一个队列）
- 如果工作在其时间片内主动释放CPU，则优先级不变
- 结果
- 对于单个工作，MLFQ会优先认为它是一个短工作，也就是在它刚进入系统时给它最高的优先级；如果它确实是短工作，那么它很快就会执行完毕；如果它其实是长工作，那么它的优先级也会慢慢变低。这实现了SJF的目标。
- 对于一个有IO的工作，它一般就会是交互型工作，也就是它需要快速运行以让用户及时得到响应。这个工作在IO操作时必然会释放CPU，此时即使它的时间片流逝，系统也不会降低它的优先级，这保证了交互型工作始终可以快速运行
- 存在的问题
- 这种策略会有饥饿(Starvation) 问题，如果系统的交互型工作太多了，那后台的CPU密集型工作就难以得到CPU，但是我们仍然希望这些工作可以得到进展
- 程序会有手段调戏调度程序(Game the Scheduler)，例如每次在时间片用完之前都进行莫名其妙的IO操作，让CPU以为它是交互型工作，这样可以一直独占CPU
- 策略
-
MLFQ - Version 2
- 策略
- 如果A的优先级>B的优先级，则运行A
- 如果A的优先级==B的优先级，则轮转运行A和B
- 进程进入系统时，放在最高优先级队列
- 进程用完整个时间片后，降低其优先级（移至下一个队列）
- 如果工作在其时间片内主动释放CPU，则优先级不变
- 针对饥饿问题：每经过一段时间S，就将系统中的所有工作重新加入最高优先级队列（周期性提高所有进程的优先级）
- 结果
- 由此，CPU密集型工作也总有机会得到执行，不至于承受饥饿
- 注意
- 这个时间S（巫毒常量(voo-doo constant)）的设置仍然是个问题，如果设置得太高那长工作又有可能饥饿，如果设置得太低那交互型工作又得不到合适的CPU时间比例
- 策略
-
MLFQ - Version 3
- 策略
- 如果A的优先级>B的优先级，则运行A
- 如果A的优先级==B的优先级，则轮转运行A和B
- 进程进入系统时，放在最高优先级队列
- 针对饥饿问题：每经过一段时间S，就将系统中的所有工作重新加入最高优先级队列（周期性提高所有进程的优先级）
- 针对独占问题：当一个工作用完了它在当前层的时间配额时，不管它放弃了多少次CPU，它的优先级都会被降低
- 结果
- 由于每一层都有一个固定的时间配额，所以系统只认这个时间配额而不认程序有没有放弃CPU。一个进程只要达到了它的时间配额，那它的优先级就会被下调。每一层的时间配额可能不同，一般会自上而下逐级减少。这样可以让狡猾的程序无法再通过定期释放CPU来独占CPU
- 策略
-
MLFQ的其它改进
- 有的MLFQ（如FreeBSD）不使用上述规则，而是通过数学公式调整优先级
- 有的MLFQ会将操作系统永远设置为最高优先级，其它工作无法达到此优先级
- 有的系统可以让用户指示是否要上调/下调某个进程的优先级
-
-
最终的MLFQ策略
- 如果A的优先级>B的优先级，则运行A
- 如果A的优先级==B的优先级，则轮转运行A和B
- 进程进入系统时，放在最高优先级队列
- 当一个工作用完了它在当前层的时间配额时，不管它放弃了多少次CPU，它的优先级都会被降低
- 每经过一段时间S，就将系统中的所有工作重新加入最高优先级队列（周期性提高所有进程的优先级）
操作系统 - Operating System
/
Chapter II 虚拟化
/
Section 1 CPU虚拟化
/
1-3 策略：进程调度