OSTEP: Ch8: Scheduling: The Multi-Level Feedback Queue

22nd September 2020 at 3:58pm
OSTEP
核心问题How to schedule without perfect knowledge?
解法见下文

OS 的调度算法有几大任务:

  • 在不确定每个进程需要多少 CPU 的情况下做调度
  • 兼顾完成时间(turnaround time)和响应时间(responsive time)(参考 OS: Process: Scheduler

多级反馈队列的核心在于:通过观察进程的行为来确定给它多少 CPU。它将进程(ABCD)分别放到不同优先级的队列(Q1 ~ Q8):

[High Priority] Q8: A => B
                Q7
                Q6
                Q5
                Q4: C
                Q3
                Q2
 [Low Priority] Q1: D

运行优先规则:

  • 高优先级的进程先运行(A 和 B 先运行,后面才轮到 C 和 D)
  • 同优先级的多个进程,轮流执行(A 和 B 轮流运行)
  • 每个进程被执行时,至少给一个时间片

那进程如何改变优先级?规则是:

  • 当进程刚开始运行,它处于最高优先级
  • 当进程使用完整个时间片时,它的优先级降低
  • 当进程没有使用完整个时间片就让出 CPU(比如触发了 I/O),则使它保持在同个队列中

为了防止有些很耗 CPU 的进程一直无法被运行(starvation),加一条规则:

  • 定时把全部进程放到最高优先级的队列中

为了防止有些进程取巧,在每次快用完它的时间片前就调用 I/O 让出 CPU,使其一直处于高优先级队列中:

  • 一旦进程使用了一定量的 CPU 时间片,则将其优先级降低

另外则是,这个调度算法的参数(比如时间片长度、多久将全部进程置为高优先级等),一般都难以直观判断。因此 OS 一般提供 配置能力。另外 OS 也提供了让使用者调整进程优先级的能力,比如 Linux 中的 nice 命令。

总结

  • Rule 1: If Priority(A) > Priority(B), A runs (B doesn’t).
  • Rule 2: If Priority(A) = Priority(B), A & B run in round-robin fashion using the time slice (quantum length) of the given queue.
  • Rule 3: When a job enters the system, it is placed at the highest priority (the topmost queue).
  • Rule 4: Once a job uses up its time allotment at a given level (regardless of how many times it has given up the CPU), its priority is reduced (i.e., it moves down one queue).
  • Rule 5: After some time period S, move all the jobs in the system to the topmost queue.