调度策略漫谈

情景

有 10 个客户要在银行窗口办业务。其中客户甲需要占用窗口 1 小时才能办好业务。其余 9 个客户，均只需要 2 分钟就能办好业务。
这种情景下，不同的调度算法，会产生截然不同的效果。

先来先服务

假设银行 8 点营业，客户甲是 8:30 来的，其余 9 个客户是 8:31 来的，按照先来先服务算法，客户甲优先办理业务，其余 9 个客户进入等待状态。由于客户甲需要办理 1 个小时，其余 9 个客户也不得不一起等待 1 个小时。这就是先来先服务。
显然，这种调度算法，对其余 9 个客户来说不太友好，他们本来可以几分钟办好业务就去忙别的事了，但偏偏要等待客户甲 1 个小时。

短进程优先

银行窗口问道：“你们 10 个人都办理什么业务啊（估计一下耗时）”？得知其中 9 个人差不多每人 2 分钟就能办完，有一个客户需要 1 个小时才能办完。“好，你们 9 个先办”。这就是短进程优先。
显然，这种调度算法，对其余 9 个客户来说很友好，基本上等个几分钟就办好了，对客户甲来说也还能接受，他本来就要花 1 小时办理业务，多等个十几分钟也还好。
这种调度算法具有最优的平均周转时间。
一个相关问题：需要预知未来（如何预估下一个进程是长进程还是短进程呢？）
答案是：用过去来预测未来

最高响应比优先

假设客户甲是 8:30 来的，其余 9 个客户是 9 点来的，9:10 分银行窗口开始为这 10 人办理业务。虽然客户甲需要占用 1 个小时，但是人家已经等了 40 分钟了呀，其它 9 人才等了 10 分钟，这时候理当先为客户甲服务。这就是最高响应比优先。
在短进程优先中，会出现一直执行短进程，而长进程一直无法得到执行，即饥饿现象。
最高响应比优先，解决了这个问题。

时间片轮转

假设银行 8 点营业，客户甲是 8:30 来的，其余 9 个客户是 8:31 来的，按照先来先服务算法，客户甲优先办理业务，其余 9 个客户进入等待状态。
这种情况下，会造成其余 9 个客户过多的等待时间，所以我们想改用短进程优先。
短进程优先又会造成客户甲饥饿，所以我们改用最高响应比优先。
最高响应比优先，又回到了先来先服务效果，造成其余 9 个客户过多的等待时间。
这时候，想出了时间片轮转算法。
时间片轮转算法，基于先来先服务，只不过给每个进程执行的时间加个限定，这个限定就是时间片。
对照我们这个例子就是，银行窗口约定，每个客户最多只能连续占用窗口 5 分钟。这样，客户甲先办理，办理 5 分钟后虽然业务没办完，但根据规则，他被迫让出窗口。这样其它 9 个客户可以紧接着办理。其它 9 个客户业务很短，相继办理完毕走人了。然后再轮到客户甲办理。
这种调度算法，解决了上面三种算法带来的弊端。
但是又带来了另外一个弊端：

• 上下文切换有开销（暂停客户甲的办理，得为客户甲保存现场，包括当前办理的进度，电脑上为客户甲打开的窗口不能关闭，只能先最小化等，等再次轮到为客户甲办理时，需要恢复现场，包括手续状态继续、电脑窗口恢复等）
• 时间片设置多少合适？
  • 时间片太大——极端情况下退化为先来先服务算法
  • 时间片太小——上下文切换开销过大
  • 经验值：维持上下文切换开销处于 1% 以内。上下文切换时间 0.1ms，时间片 10ms。

多级队列调度算法

• 就绪队列被划分成多个独立的子队列
• 每个队列拥有自己的调度算法
• 队列间的调度
  • 固定优先级
    • 先处理前台，然后处理后台
    • 可能导致饥饿
  • 时间片轮转
    • 每个队列都得到一个确定的能够调度其进程的 CPU 总时间
    • 如：80% CPU 时间用于前台，20% CPU 时间用于后台

对应上面的例子就是：10 个客户中，客户甲和客户乙办理业务均需要占用 1 小时，其余 8 个客户均需要占用 2 分钟。这时候，将客户甲和客户乙划为一组，记作后台组，其余 8 个客户划为一组，记作前台组。在一个小时中，48 分钟用来处理前台组，12 分钟用来处理后台组。这样，前台组能够得到较短的响应时间，而后台组也不至于饿死。

多级反馈队列算法

• 进程可在不同队列间移动
• 时间片大小随优先级降低而增加
• 如，进程在当前的时间片没有完成，则降到下一个优先级
  • CPU 密集型进程的优先级会逐渐降低（因为它每次都把时间片用完），并且时间片逐渐增大，这样切换开销逐渐降低。
  • I/O 密集型进程停留在高优先级

这种算法能够达到不错的效果，实际上系统中也是采用类似这种综合的调度算法。