OSTEP: Ch9: Scheduling: Proportional Share

18th November 2020 at 3:39pm
OSTEP
核心问题How to share the CPU proportionally?
解法见下文

按比例分享 CPU。采用发行彩票方式。基本理念:

  • 每个时间片都举行一场彩票发行。比如发 100 张票,然后开出一张票
  • 如果希望任务 A 运行 75% 的时间,任务 B 运行 25%,则给 A 75 张票,B 25 张票
  • 每次开票得出一个票号。此时 A 都有 75% 的概率运行,B 则是 25%;多次开票后,它们的运行时间在统计上趋近于 3:1

为什么用随机?

  1. 比 LRU 等算法更均衡,没有 worst-case
  2. 实现上轻量简单,没有太多状态
  3. 生成随机数的性能好

没有继续看了。