两个简单调度算法的最优性

进程调度是操作系统里面比较关注的问题。这里主要是记一下 SRTF 调度算法的一些东西。

为了简单起见，本文假设只有一个处理器，因此每时每刻只能有一个进程在运行。并且操作系统的中的进程可以随时按照需求中断，然后切换到其它进程（上下文切换）；或者是什么也不做，使处理器处于空闲状态。我们默认上下文切换的时间可以忽略不计。此外，对于进程中运行的程序，我们假设：

• 程序只会进行运算，不会有其它请求（例如读写文件）。因此每个程序在执行过程中除了退出程序外不会由其它的中断。
• 每个程序的提交时刻和所需的运行时间是已知的。

这里提交时刻是指提交给操作系统的时刻。进程提交后，操作系统要安排所有已经提交的进程的运行，完成每个进程的任务。如果一个进程在 $l_i$ 时刻提交，需要运行 $t_i$ 个单位的时间，然后在 $r_i$ 时刻完成运行，显然需要 $r_i - l_i \geqslant t_i$。我们称 $r_i - l_i$ 是这个进程的轮转时间。

显然如果不让处理器处于空闲状态（除非当前没有进程可以运行），那么在前面的假设下，运行完所有进程的时间是固定的。但是由于只有一个处理器，势必会让一些进程不得不等待其它进程完成运行后，自己才能被运行。因此调度算法的一个任务是要尽可能减少这种等待时间。前面提到的轮转时间就是每个进程的运行时间和等待时间之和，所以上述目标也就是要最小化所有进程的轮转时间之和。

SJF 算法

首先来考虑一个特殊情况：有 $n$ 个进程都在时刻 $0$ 时提交，第 $i$ 个进程的运行时间为 $t_i$（$i \in \mathbb{N}^+$），如何安排进程的运行顺序使得总轮转时间最少？这其实就是小学奥数里面的排队接水问题。策略非常简单：我们让 $t_i$ 更小的进程先运行即可。这个算法被称为 SJF 算法¹（Shortest Job First）。

考虑将 $t_i$ 按照进程的运行顺序排列，即第一个运行的进程的 $i$ 为 $1$，之后依次类推。那么我们之前的策略意思是 $t_i$ 升序排列（不下降顺序）的时候总轮转时间最少。要证明这个事情可以考虑调整法。首先我们要先确定总轮转时间该怎么算。显然第 $i$ 个进程的结束运行的时间就是 $t_i$ 序列里面前 $i$ 个数的前缀和 $S_i = \sum_{k=1}^i t_k$，而总轮转时间是所有 $S_i$ 的总和。如果最优的方案不是 $t_i$ 升序的话，那么其中必有两个位置 $i < j$ 满足 $t_i > t_j$。实际上可以假设 $i$ 和 $j$ 是相邻的，即 $j = i + 1$。那么通过交换 $t_i$ 和 $t_j$ 的值，可以使得它们之间变得有序。而这个交换不会改变 $S_i$ 之前和 $S_j$ 之后的 $S_k$。对于 $S_i$ 和 $S_j$，设它们交换后为 $S'_i$ 和 $S'_j$，则

$$ \begin{aligned} S_i &= S_{i - 1} + t_i \\ S_j &= S_{i - 1} + t_i + t_j \\ S'_i &= S_{i - 1} + t_j \\ S'_j &= S_{j - 1} + t_j + t_i \end{aligned} $$

（假设 $S_0 = 0$）

因为 $t_j < t_i$，所以 $S'_i + S'_j < S_i + S_j$，因此交换后的总轮转时间变少了，这与 $t_i$ 是最优方案的假设矛盾。因此最优方案就是 $t_i$ 升序排列的方案。

另外一种想法是考虑每个 $t_i$ 在总轮转时间中的贡献。显然第一个进程的运行时间 $t_1$ 是要被所有进程都算一遍的，然后第二个进程则只用算 $n - 1$ 遍，依次类推。所以总轮转时间就是：

$$ \sum_{k = 1}^n (n - k + 1)t_k $$

根据排序不等式²，上式在 $t_i$ 升序时取最小值。当然排序不等式本身也可以用调整法证明，所以这里只是换了一个看问题的角度。

在上面我们其实没有考虑上下文切换这种操作，就默认每个进程一启动就一直运行到结束。实际上，在进程运行中途切换到其它进程并不能优化总轮转时间。下面一节介绍的 SRTF 将解释这个事情。

SRTF 算法

上一节的 SJF 算法假设了所有进程都在时刻 $0$ 提交。现在把这个限制放开，并且令第 $i$ 个进程的提交时间为 $c_i$。如果我们不采取上下文切换，那么可能遇到下图中 (a) 的情况：

在 (a) 中，由于灰色的进程运行时间长，导致另外两个进程长时间等待，因此总轮转时间非常大。而如果采取上下文切换的机制，我们可以随时切换进程的运行，让一些运行时间短的进程优先，如上图中 (b) 的情况，这样可以减少总轮转时间。

SRTF 算法（Shortest Remaining Time First）³就是利用这一思想，在任意时刻优先运行剩余运行时间最少的进程，以期望减少总轮转时间。我们可以证明，SRTF 给出的调度方案是所有利用上下文切换的调度方案中总轮转时间最少的。在证明这个结论之前，我们首先要用尽可能简单的方法来描述调度方案。我们可以用一个二值函数 $S(t, i)$ 表示在时刻 $t$，进程 $i$ 是否在运行。即如果 $S(t,i) = 1$ 表示时刻 $t$ 运行的程序为 $i$。显然对于固定的 $t$，$S(t,i) = 1$ 的进程 $i$ 最多一个。有了 $S(t,i)$ 后不难算出以下信息：

• 进程 $i$ 在时刻 $t$ 已经运行的时间 $f(t, i) = \int_{c_i}^t S(x, i)\mathrm{d}x$。
• 剩余时间 $r(t, i) = \max\{0, t_i - f(t, i)\}$。
• 终止时刻 $e_i = \min\left\{t\colon r(t,i) = 0 \right\}$。
• 时刻 $t$ 时还未完成的所有进程集合 $A(t)=\{i\colon r(t,i)>0\}$。
• 进程 $i$ 在运行的所有时段 $R(i) = \{t\colon S(t, i)=1\}$。

形式化地说，对于 SRTF 算法，其给出的调度方案 $S$ 满足 $S(t,i) = 1 \Rightarrow \forall j\in[1,n]\colon r(t,i) \leqslant r(t, j)$[^tie]。如果 SRTF 没有给出最优方案，那么设最优方案为 $S$，那么存在一个区间 $(a,b)$，在段时间区间内没有按照 SRTF 的策略进行调度。设 $j$ 是 $S$ 在 $(a,b)$ 内运行的进程，即 $S(t,j) = 1,\forall t\in(a,b)$，以及 $i\in A(t)$（$t\in(a,b)$） 表示 SRTF 会选择的进程，即 $i$ 满足 $\forall k\in[1,n],t\in(a,b),S(t,i)\leqslant S(t,k)$（如果有多个 $i$ 则任选一个）。像在 SJF 中的调整法一样，我们可以尝试交换 $i$ 和 $j$ 的运行。但是要注意这里在 $(a,b)$ 内的修改有一些小细节（如 $r(a,i) < b-a$ 的情况），以及可能会影响后续的运行。于是我们只考虑进程 $i$ 和进程 $j$ 在 $(a,∞)$ 内的运行时段 $L= (a,∞)\cap(R(i) \cup R(j))$，尝试在 $L$ 上只针对这两个进程，用 SRTF 的策略重新调度，得到调度方案 $S'$。在 $L$ 上的调整不会影响除 $i$、$j$ 外的其它进程，因此我们只用考虑 $L$ 上的总轮转时间的变化。首先，在 $L$ 上，无论谁最后结束，总时间是不变的。因此我们实际上只用最小化先结束的进程的轮转时间。而 $r(t,i)<r(t,j)$，所以先运行进程 $i$ 是更优的。这与 $S$ 是最优方案矛盾。

[^tie]：因为可能有两个进程的 $r(t,i)$ 相同，因此只能推出一个方向。

上述证明最初由 Linus Schrage⁵ 给出。后来 Donald R. Smith⁶ 给了一个不用反证法的证明。他的证明相当于考察了整个调度过程，并且验证 SRTF 算法的每一步都是最优的。在之前的证明中，我们实际上是用一个 0/1 向量来表示某个时刻 $t$ 的状态。为了能够更方便地计算总轮转时间，我们还可以直接记录所有未结束进程的剩余时间的序列作为状态。具体而言，用无穷长的序列⁴ $\{x_i\colon i \in \mathbb{N}^+\}$ 记录某个时刻所有进程的剩余时间，并且按照剩余时间降序排列，然后序列多余的部分全部填 $0$。定义后缀和为 $X_i = \sum_{k = i}^∞ x_i$。利用 SJF 算法，如果从这个时刻起，之后没有新的进程，那么运行完 $\{x_i\}$ 中所有进程的最小总轮转时间为

$$ \sum_{i=1}^∞ ix_i = \sum_{i=1}^∞\sum_{k = i}^∞ x_i = \sum_{i = 1}^∞ X_i $$

接下来我们需要明确什么是“更优”。现在我们需要对比两个序列 $\{x_i\}$ 和 $\{y_i\}$，对应的后缀和分别为 $\{X_i\}$ 和 $\{Y_i\}$，考虑什么情况下可以认为 $\{x_i\}$ 比 $\{y_i\}$ 更优。首先，好的调度算法不会有无意义的空闲时间，因此在同一时刻，剩下的任务总量 $X_1$ 应该是不超过 $Y_1$ 的。此外，我们可以以总轮转时间作为判据，即 $\sum_{i=1}^∞ X_i \leqslant \sum_{i=1}^∞ Y_i$。

现在的问题在于加入新的进程。而实际上加入新的进程后，上述两个不等式可能会不成立。例如：

$$ \begin{aligned} \{x_i\} &= 3, 1, 1, 1, 0, 0, ... \\ \{y_i\} &= 2, 2, 2, 0, 0, 0,... \end{aligned} $$

这个例子满足 $X_1 = Y_1 = 6$，并且 $\sum_{i=1}^∞ X_i = 3+2+3+4 = 12 = 2(1+2+3) = \sum_{i=1}^∞ Y_i$。如果加入一个运行时间为 $1$ 的进程，将不满足第二个不等式。

实际上 Smith 采用的是更加强的判据：当

$$ X_i \leqslant Y_i,\quad \forall i\in\mathbb{N}^+ $$

时，才认为 $\{x_i\}$ 优于 $\{y_i\}$。相比于 $\sum_{i=1}^∞ X_i \leqslant \sum_{i=1}^∞ Y_i$，加入一个新的进程对不等式两边的变化要简单很多。这个条件虽然比之前的条件更强，但是在一开始没有进程的时候还是可以满足的。接下来主要是要验证，当加入一个运行时间为 $t$ 的进程后，得到的 $\{x'_i\}$ 和 $\{y'_i\}$ 依然满足上述不等式。设新进程的插入位置为 $i$ 和 $j$，即 $x'_i = t$ 以及 $y'_j = t$。考虑 $k \in \mathbb{N}^+$，若

(1) $i, j < k$：

$$ X'_k = X_{k-1} \leqslant Y_{k-1} = Y'_k $$

(2) $i < k \leqslant j$：此时 $t = x'_i \geqslant x'_k = x_{k - 1}$。

$$ X'_k = X_{k-1} = x_{k-1} + X_k\leqslant t + X_k \leqslant t + Y_k = Y'_k $$

(3) $j < k \leqslant i$：此时 $x_{k-1}=x'_{k-1}\geqslant x'_i = t$

$$ X'_k = t + X_k \leqslant x_{k-1} + X_k = X_{k-1} \leqslant Y_{k-1} = Y'_k $$

(4) $k \leqslant i, j$：

$$ X'_k = t + X_k \leqslant t + Y_k = Y'_k $$

因此加入一个新的进程后，所有不等式依然满足。

有了这一点后，后面的事情就简单了。考虑在一段 $Δt$ 的时间内没有新的进程，某个调度算法将某个 $y_i$ 对应的进程运行 $Δt$ 单位的时间，使其剩余时间减少 $Δt$，并且移动到了位置 $j$ 上，即 $y'_j = y_i - Δt$，而 SRTF 会选择将 $x_i$ 最后一个非零元素 $x_l$ 减 $Δt$，得到 $\{x'_i\}$（可以假设 $Δt \leqslant \min\{y_i,x_k\}$）。考虑 $k \in \mathbb{N}^+$，若

(1) $l < k$：$X'_k = X_k = 0 \leqslant Y'_k$。下令 $k \leqslant l$。

(2) $i \leqslant j < k$：

$$ X'_k = X_k - Δt \leqslant Y_k - Δt \leqslant Y_k = Y'_k $$

(3) $i \leqslant k \leqslant j$：

$$ \begin{aligned} X'_k = X_k - Δt \leqslant Y_k - Δt &= Y_{k+1} + y_k - Δt \\ &\leqslant Y_{k+1} + y_i - Δt \\ &= Y_{k + 1} + y'_j \\ &= Y'_k \end{aligned} $$

(4) $k < i \leqslant j$：

$$ X'_k = X_k - Δt \leqslant Y_k - Δt = Y'_k $$

因此 SRTF 算法每次选择剩余时间最少的进程来运行确实是更优的。综合以上内容，从初始全 $0$ 序列开始，无论是运行进程还是加入新进程，每一步都保证处于最优的状态，不难看出 SRTF 算法确实实现了最小的总轮转时间。