Lecture 4. 进程调度 2：抢占式调度（25 页）

使用 RR 的抢占式调度

不同量子长度的 RR 分析

多级反馈队列

示例

轮转调度 RR

是 Round Robin 的缩写。RR 调度算法其实就是加上了抢占机制的 FCFS 调度算法，它可以让所有进程的响应时间都比较优，在分时系统和多任务系统上很重要。

定义一个较小的时间单元为 时间量（time quantum），或称 时间片（time slice），通常是 10~100ms。所有进程都是轮流调用的。如果进程运行超过了时间片还没结束，那么就中断它，重新放回就绪队列的尾部，进行上下文切换。

还是刚刚 P1 P2 P3 三个进程，在 0 时刻同时到达，加入使用 RR 算法调度（时间片 4ms），那么对应的 Gantt 图将是：

三项平均时间是：

等待：$\frac{1}{3}(6+5+6) = 5.667\text{ms}$
响应：$\frac{1}{3}(0+4+7) = 3.667\text{ms}$
周转：$\frac{1}{3}(30+7+10) = 15.667\text{ms}$

由于像 RR 这样的抢占式调度需要多次的上下文切换，我们希望上下文切换的次数不要太多，因为他也是需要花费时间的！所以，时间片不能设置的太小，要不然可能用于上下文切换的时间比进程真正执行的时间还多；也不能设置太大，要不然 RR 就变成了 FCFS。

多级反馈队列调度

根据不同 CPU 执行的特点来区分进程。如果进程使用较多的 CPU 时间（计算型），那么它就是低优先级的，放在低优先级队列里；而 IO 密集和交互型进程则是高优先级的，放在高优先级队列里。同时为了防止饥饿，在低优先级队列当中等待较久的进程，会移动到高优先级队列当中去。

例子：UNIX 进程调度策略

UNIX 进程调度策略是多级反馈队列调度，队列中使用 RR 算法，时间片 100ms。

具有 0~127 共 128 个优先级。数字越低，优先级越高。其中，0~49 是给内核进程用的，50~127 是给用户进程用的。

优先级的计算是根据 usage 和 nice value 来确定的，id 是 $j$ 的进程在第 $i$ 个时间段上的优先级公式是：$$P_j(i) = \text{Base}_j + \frac{\text{CPU}_j(i)}{2} + \text{nice}_j$$，其中 $\text{CPU}_j(i) = \frac{\text{CPU}_j(i-1)}{2}$。

解释：

$P_j(i)$ 表示进程在第 $i$ 个时间段的优先级，数值越低，优先级越高
$\text{CPU}_j(i)$ 顾名思义，就是根据前 $i$ 段时间内使用的时间计算出来的一个值，用于判断是否是 CPU 密集型进程
$\text{Base}_j$ 表示进程的基础优先级
$\text{nice}_j$ 是用户来进行自主调整的一个因素

观察这个式子得知，占用 CPU 越久，就会导致计算出来的优先级数越大，从而导致更低的优先级。而 $\text{CPU}_j(i)$ 的衰减也给了它以后再次被调度的机会。

如果持续使用 CPU，一秒后会发生抢占。对于用户进程来说，被抢占后会进入最高优先级队列。

如图，设一秒内有 60 个时钟周期，共 ABC 三个进程，蓝色表示调度，灰色表示等待。

公平共享调度

英文：Fair Share Scheduling，与多用户有关。

$$P_j(i) = \text{Base}_j + \frac{\text{CPU}_j(i)}{2} + \frac{\text{GCPU}_k(i)}{4 \times W_k}$$，其中 $\text{GCPU}_k(i) = \frac{\text{GCPU}_k(i-1)}{2}$。

解释：

$P_j(i)$ 表示进程在第 $i$ 个时间段的优先级，数值越低，优先级越高
$\text{CPU}_j(i)$ 顾名思义，就是根据前 $i$ 段时间内使用的时间计算出来的一个值，用于判断是否是 CPU 密集型进程
$\text{Base}_j$ 表示进程的基础优先级
$W_k$ 表示第 $k$ 组进程（可能一个用户的进程就是一个组）的权重。$0 < W_k \leq 1$，$\sum W_k = 1$。
$\text{GCPU}_k(i)$，其中 G 是 group 的意思，不难猜到，是指根据前 $i$ 段时间内第 $k$ 组进程使用的时间计算出来的一个值

例如，ABC 三个进程，A 独自一组，BC 一组：