进程调度

Intro

过去, 我们讲了运行进程的底层机制; 下面, 我们要介绍系统调度程序采取的上层策略: 一系列调度策略.

调度指标

周转时间:
任务完成时间减去任务到达系统的时间, 即 $T_{周转时间} = T_{完成时间} - T_{到达时间}$ .
是一个性能指标.
响应时间:
任务到达系统后首次运行的时间, 即 $T_{响应时间} = T_{首次运行} - T_{到达时间}$ .
与系统的交互性息息相关, 是一个公平性指标.

”Laplace’s Strategy” without I/O

这里, 我们的调度策略就像 Laplace’s demon 一样,
一个工作到达时, 它就可以预测工作需要的总时长.

当然, 这绝不现实(至少在现在). 但是这将作为一种理想模型, 帮助我们想出一些调度策略模型.

FIFO: 先进先出

简单, 易于实现.

FIFO Simple Example

但是有护航效应, 一些耗时较少的潜在资源消费者排在重量级的资源消费者之后.

Why FIFO is not that Great

SJF: 最短任务优先

这是一个总体调度原则, 可以应用于所有系统, 只要平均客户的周转时间很重要.

策略就是: 从短到长依次运行任务.

SJF Simple example

但是, 在长任务先到达的时候, 同样会遇到护航问题.

Convey Effect of SJF

STCF: 最短完成时间优先

SJF 是一个非抢占式的调度策略, 向其添加抢占:
当新的任务到的时候, 调度程序可以抢占运行中的工作, 切换到另一个任务, 稍后继续原工作.
因此, STCF 也称为抢占式最短任务优先.

每当新工作进入系统, 它就会确定剩余工作和新工作剩余时间最少的, 然后调度该程序.

STCF Simple Example

RR: 轮转

STCF 和相关方法的周转时间虽然很好, 但是响应时间并不好.
因此如何构建响应时间优化的调度程序?

RR 就是一种这样的算法, 在一个时间片里运行一个工作, 然后切换到下一个, 反复进行, 直到完成所有任务.

Comparison Between SJF and RR

时间片长短是 RR 的一个重要权衡点: 时间片越短, 响应时间越好, 但是上下文切换开销越大.

当然, RR 的周转时间非常差.

这也是调度策略设计的一个权衡点: 公平和效率.
一个公平的策略, 如 RR, 往往周转时间这类性能指标表现不佳;
而相反, 牺牲公平性, 例如 STCF, 则会有更高的性能, 更快的周转时间.

I/O

以上我们都没有考虑 I/O. 但是显然, 所有程序都需要执行 I/O.

调度程序需要:

在工作发起 I/O 请求时做出决定, 因为当前的作业在 I/O 期间不会使用 CPU, 此时调度程序应该在 CPU 上安排另外的工作.
在工作的 I/O 完成时做出决定, 这会产生中断, 操作系统应该把发出 I/O 的进程从阻塞转移回就绪状态.

关键是实现重叠, 一个进程在等待另一个进程的 I/O 完成时使用 CPU; 而不是仅仅运行一个工作, 再去运行另一个.

Poor Use of Resources

Overlap

把 A 运行的每个子工作视为独立工作, 优先调度, 完成后(等待 I/O 时)运行 B.
也就是确保”交互”的进程经常运行, 而在它们执行 I/O 的时候, 其他 CPU 密集型作业运行, 从而更好利用 CPU.

多级反馈序列

这是我们以上所说的内容的一个集大成者, 结合以上策略的优点, 并且面对更加现实的情况.

它要:

优化周转时间, 从而提升性能.
优化响应时间, 带来更好的交互体验.
在对进程一无所知, 不知道其总运行时间的情况下, 实现上面两个目标.

MLFQ

基本规则

MLFQ 中有许多独立队列, 不同队列有不同优先级, 一个工作存在于一个队列中.
而 MLFQ 总是执行优先级高的工作, 如果相同优先级就轮转执行.
优先级会根据程序的行为动态调整.

MLFQ Example

如果 A 的优先级 > B 的优先级，运行 A(不运行 B).
如果 A 的优先级 = B 的优先级，轮转运行 A 和 B.
工作进入系统时, 放在最高优先级(最上层队列).
一旦工作用完了其在某一层中的时间配额(无论中间主动放弃了多少次CPU), 就降低其优先级(移入低一级队列).
经过一段时间 S, 就将系统中所有工作重新加入最高优先级队列.

优先级改变

时间长短

Long-running Job

这个算法的主要目标就是, 如果不知道工作时间长短, 那么就默认其是个短工作, 并赋予高优先级.
如果确实是短工作, 很快就会执行完毕, 如果是长工作, 那么会逐渐移入低优先级队列, 也就是被当作长工作对待.

有 I/O

Along with a Interactive Job

A Mixed I/O-intensive and CPU-intensive Workload

交互性工作会有大量 I/O 行为, 会在时间片内主动放弃 CPU, 因此我们不惩罚他, 从而让交互程序保持在高优先级.
从而优化了响应时间.

比例份额调度

这是和我们之前提到的的调度策略不同的一种策略.

它的思想是: 确保每个工作获得一定比例的 CPU 时间, 而不是优化周转时间和响应时间.

基本概念: 彩票

一个进程占有总彩票数的百分比, 代表该进程占有资源的份额.

通过不断定时抽取彩票, 从 0~彩票数之前抽取一个数字, 拥有这个数字对应的彩票的进程中奖, 从而被执行.

彩票调度利用随机性, 从而在概率上满足运行期望为占有彩票的比例.

彩票机制

彩票调度还提供了一些机制, 以各种方式调度彩票.

彩票货币: 允许拥有一组彩票的进程, 以他们自己需要的形式, 将局部彩票分给自己的不同工作,
而操作系统负责将其兑换为相应数目的全局彩票.
彩票转让: 一个进程可以把自己的彩票临时转让给另一个进程.
在客户端/服务端交互的场景中尤为有用, 可以让客户端转让彩票给服务端, 从而加快其执行自己请求的速度.
彩票通胀: 一个进程可以临时提升或是降低自己的拥有的彩票数量.
在进程相互信任的环境, 一个程序可以在必要时, 不需要和其他进程通信, 增加自己的彩票数, 获得更多 CPU 时间.

实现

这个调度策略实现极为简单:

一个随机数生成器
一个记录系统中所有进程的列表(包括记住他们的彩票数), 如果按照彩票数倒序排列会更快
记录彩票总数

int counter = 0;
int winner = getrandom(0, totaltickets);
node_t *current = head;
 
while (current) {
  counter += current->tickets;
  if (counter > winner) {
    break; // The winner is found
  }
  current = current->next;
}

不足与修正

随机过程偶尔并不能产生正确的比例. 或者说, 只有运行时间比较长, 经过多次抽奖, 才能使得平均运行时间接近期望.

可以使用步长调度, 这是一个确定性的公平分配算法.

每个工作都有自己的步长, 和彩票数量成反比, 用一个大数处以其票数来获得步长.
每次运行都会让进程的计数器(行程值)增加一个步长, 以记录其运行进展.
调度程序会选择拥有最小行程值的进程运行, 并且给其行程值增加一个步长.

current = remove_min(queue);
schedule(current);
current->pass += current->stride;
insert(queue, current);

不过相比较于彩票调度策略, 步长调度还需要记录全局状态, 例如新加入的进程不能行程设为 0, 不然会独占 CPU.
因此就处理新加入的进程而言, 彩票调度策略会更加合理.

彩票数如何分配?

对于给定的一组工作, 并没有最佳的特定分配方案, 这也是该策略面对的最大问题之一, 也是其没有广泛应用的主要原因.
只有一些容易确定比例的领域有用, 例如虚拟机, 给不同系统分配 CPU.

此外, 这种策略并不能很好地适合 I/O.

シリウスの砂

探索