操作系统进程调度

[bigwolftime]

https://bigwolftime.github.io/system-process-dispatcher/

一. 调度指标

周转时间

如果任务只使用 CPU, 并且没有交互类型的进程, 那么只需要使用周转时间来衡量调度算的性能, 其定义为:

T(周转时间) = T(完成时间) - T(任务到达时间)

多个任务的平均周转时间定义为:

T(平均周转时间) = (T1(任务1周转时间) + T2(任务2周转时间) + ...) / n. n 为任务数

响应时间

由于引入了分时操作系统, 用户会坐在终端前执行交互性的进程, 所以对系统的响应时长提出了要求, 响应时间的定义:

T(响应时间) = T(首次执行时间) - T(任务到达时间)

二. 调度策略介绍

1. 先进先出(First In First Out, FIFO)

使用了队列思想, 那个任务先来便运行哪个任务. 其特点是: 逻辑简单, 易于实现

假设1: 有 A,B,C 三个任务, 几乎同时到达系统, 排队的序列为: A,B,C, 假如每个任务的执行时间是 10s, 则第 0-10s 运行任务A, 11-20s 运行
任务B, 21-30s 运行任务C.

则对于每个任务, 其周转时间为(假设: 任务几乎同时到达, 开始时间为0):

A: 10 - 0 = 10

B: 20 - 0 = 20

C: 30 - 0 = 30

其平均周转时间 = (10 + 20 + 30) / 3 = 20s

但实际上每个任务所需的执行时间是不同的, 在上面的前提下, 假设2: 我们修改任务A的运行时长为 100s. 则其周转时间为:

A: 100 - 0 = 100

B: 110 - 0 = 110

C: 120 - 0 = 120

其平均周转时间 = (100 + 110 + 120) / 3 = 110s

如果我们调换一下任务的执行顺序呢? 假设3: 任务A,B,C 的运行时间为 100s, 10s, 10s, 任务到达系统的顺序为: B, C, A, 则其周转时间:

B: 10 - 0 = 10

C: 20 - 0 = 20

A: 120 - 0 = 120

平均周转时间 = (10 + 20 + 120) / 3 = 50s

可以看到差距了, 在公平的调度策略下, 不同的任务执行顺序计算得到的平均周转时间是不同的, 这个问题通常被称为护航效应, 即耗时较少的的任
务被排在了耗时较大的任务后面.

2. 最短任务优先(Shorted Job First, SJF)

考虑到平均周转时间, 提出了 SJF(最短任务优先原则): 即先执行最短的任务, 再执行次短的任务, 以此类推.

先进先出策略的假设3部分, 就体现出了 SJF 策略, 其表现要比 FIFO 要好.

假设: 有A,B,C三个任务, 其耗时分别为: 100s, 10s, 10s, 任务A在 0s 到达, 任务B,C在 10s 到达(B 在 C 的前面), 其周转时间:

A: 100 - 0 = 100

B: 110 - 10 = 100

C: 120 - 10 = 110

平均周转时间 = (100 + 100 + 110) / 3 = 103.3s

注意: 目前并没有用考虑进程的抢占式调度, 即进程一旦开始执行, 可一直运行直到结束.

可以看出, SJF 策略同样出现了护航效应问题.

3. 最短完成时间优先(Shorted Time-to-Completion First, STCF)

上面的讨论都是非抢占式的调度策略, 在 SJF 的基础上, 假设任务可以被抢占, 即当一个新任务到达后, 如果新任务比当前正在运行的任务耗时少,
则停止正在运行的任务并保存其上下文, 转而执行新任务.

假设: A,B,C 三个任务, 其耗时分别为: 100s, 10s, 10s, 任务A在 0s 到达, 任务B,C在 10s 到达(B在C的前面), 其周转时间:

A: 120 - 0 = 120, A在第10s被B抢占, 直到第31s才继续执行

B: 20 - 10 = 10, B在10s时刻到达后直接抢占

C: 30 - 10 = 20, C在B的后面执行

平均周转时间 = (120 + 10 + 20) / 3 = 50s

4. 轮转(Round Robin, RR)

从这里开始, 引入了分时操作系统, 有了交互性较强的进程, 对任务的调度有了新的要求: 响应时间.

例如: 任务A在 0s 时刻到达, 任务B,C在 10s 时刻到达, 则响应时间为:

A: 0 - 0 = 0

B: 10 - 10 = 0

C: 20 - 10 = 10

平均响应时间 = (0 + 0 + 10) / 3 = 3.3s

假如任务C属于交互性进程, 则用户需要等待10s才能得到响应, 这是不可接受的.

所以有了新的调度算法: 轮转, 轮转是指给任务分配 CPU 时间片, 当时间片用尽, 则切换到下一个进程, 如此往复.

注意: 时间片的大小必须是时钟周期的倍数, 如时钟中断为10ms, 则时间片的分配可以是 10ms, 20ms, 30ms…

假设任务A,B,C同时到达, 且执行耗时均为 5s, 则:

在 SJF 调度策略下, 响应时间:

A: 0 - 0 = 0

B: 5 - 0 = 5

C: 10 - 0 = 10

平均响应时间 = (0 + 5 + 10) / 3 = 5s

在轮转的调度策略下, 响应时间(假如时间片大小为1s):

A: 0 - 0 = 0

B: 1 - 0 = 1

C: 2 - 0 = 2

平均响应时间 = (0 + 1 + 2) / 3 = 1s

在轮转的策略中, 时间片分配得越小, 平均响应时间就越小, 但是定义太小的话也是有问题的, 因为程序运行时, 在高速缓存, TLB, 分支预测器和其他
硬件中建立了大量的状态, 切换进程会导致旧状态被刷新, 新状态被引入, 以及寄存器数据的刷新, 因此频繁地上下文切换也会有可观的损耗,

可以看到, 不同的调度策略性能上的差距, 如果比较关心响应时间, 则轮转策略表现较好; 如果关心周转时间, 则 STCF 策略比轮转策略要好. 所以,
在公平调度策略下, 可以有效降低响应时间, 但是要以周转时间为代价; 反之, 若使用非公平调度, 可以降低周转时间, 但响应时间又会上升.

5. 多级反馈队列(Multi-level Feedback Queue, MLFQ)

1962年, Corbato 首次提出多级反馈队列, 兼容时分共享系统, 获得了 ACM 颁发的图灵奖. 该调度程序经过多年的优化, 出现在许多现代操作系统中.

多级反馈队列需要解决的问题是: 如何优化周转时间和响应时间.

MLFQ 使用了多个独立的队列, 每个队列有不同的优先级, CPU 总是先从优先级高的队列中取任务, 而队列内部的任务优先级相同(一般采用轮转的调度方式).

那么, 如何确定一个进程需要放在哪个队列中呢?

MLFQ 的思想是, 对于交互型的进程, 其 I/O 操作会比较多, 且需要控制响应时间, 所以把它放在高优先级队列; 对于计算密集型进程, 需要长时间占用
CPU, 把它放在低优先级的队列中.

问题来了, 假设有三个队列, 其优先级 Q1 > Q2 > Q3, Q1 中有任务A和B, Q2 中有任务C, Q3中有任务D, 则可能出现的情况是: 以轮转的策略执行
Q1 中的 A,B, 而任务 C,D 在 A,B 运行完成前都没有调度机会.

为了改变这种情况, 在此基础上, 我们尝试在运行时改变进程的优先级, 规则如下:

工作/任务进入系统时, 放在最高优先级
进程用完整个 CPU 时间片后, 降低优先级, 即移入次高优先级队列
如果任务在 CPU 时间片内主动放弃了 CPU, 则优先级不变

为什么这样设计呢?

对于 I/O 密集型的短工作, 基本上在分配的时间片还没用完就会主动放弃 CPU 转而去等待 I/O, 而我们恰好需要其保持较高的优先级以达到快速响应的目的,
这达到了预期; 对于 CPU 密集型的工作需要长时间占用 CPU, 基本上需要用完整个 CPU 时间片, 然后归还给操作系统, 所以我们把它降低一个优先级,
最后的结果就是 CPU 密集型的工作会在低优先级的队列中, 使用轮转的方式调度.

问题来了:

如果有太多交互型进程不断地占用 CPU, 可能会使处于低优先级队列的任务饥饿;
一个 CPU 密集型的进程可能会在某个阶段表现为交互型较强的进程;
如果程序试图愚弄调度算法, 例如: 在每个时间片即将用完之前, 都会调用一个 IO 操作以主动释放 CPU, 那么就会始终保持一个高优先级,
达到独占 CPU 的效果.

如何解决呢?

对于饥饿问题, 一个较简单的办法是: 经过一段时间, 将系统中的所有工作重新加入到最高优先级队列, 这样的话原本得不到 CPU 时间片的进程,
就会在最高优先级队列以轮转的方式得到执行; 另外, 如果一个 CPU 密集型进程在此阶段表现为交互型进程, 也会被调度算法正确处理.

对于问题3, 为了防止调度程序被恶意愚弄, 我们增加一个计算指标: 某进程在此队列中的总运行时间, 达到总运行时间后, 不论是否主动放弃 CPU,
都会降低优先级.

此外还有一些其他问题: 配置多少个优先级队列? 每层的队列时间片分配多少? 需要多久整体改变一次进程的优先级? 这些都需要实际的测试和调优.

总结一下, 多级反馈队列的调度思路:

如果 A 的优先级 > B 的优先级, 运行 A;
A 的优先级 = B 的优先级, 轮转调度;
工作提交到系统时, 默认进入最高优先级队列;
某进程一旦用完了整个队列的时间份额, 则会降低优先级;
经过一段时间, 将所有任务放在最高优先级.

三. 多处理器调度

截至目前, 我们讨论的都是单核处理器的调度策略, 如何扩展到多处理器呢?

1. 处理器架构

首先讨论单处理器情况: 处理器为了更快地处理程序, 设计了多级的硬件缓存, 用来协调 CPU 和 内存之间的读写速率不一致的问题(内存读写速率在数
十或数百纳秒, CPU 只需几纳秒).

举例: 程序第一次读取数据, 数据在内存中, 因此需要花费较长的时间, 如果处理器认为该数据可能会被再次使用, 则会将该数据放入 CPU 缓存, 当再次
读取时, 查询缓存后直接命中, 因此省去了大部分时间.

缓存是基于局部性的概念, 局部性有两种:

时间局部性: 一个数据被访问后, 近期有可能会被再次访问, 比如循环中的代码指令或者数据;
空间局部性: 当访问地址为 addr 的数据时, addr 地址周围的数据有可能会被访问到, 例如: 遍历数组

缓存正是基于局部性原理被设计出来.

在多处理器的情况下, 缓存是如何设计和使用呢?

多处理器情况下的 CPU 缓存如图:

假设: 一个程序在 CPU1 上执行, 读取地址 A 的数据, 假如数据并不在 CPU 缓存中, 则需要访问内存, 得到数据 D 后将其更改为 D’, 通常情况下,
出于系统性能考虑, 数据 D’ 并不会立即被回写到内存中; 假如此时系统中断了该程序的运行, 并将其分配给 CPU2 来继续执行, 重新读取地址 A 处的
数据, 由于 CPU2 中没有地址 A 对应的数据, 所以需要到内存读取, 此时可能会得到一个旧值 D, 而不是最新值 D’. 即出现了缓存的一致性问题.

为了处理这个问题, 硬件提供了解决方案: 在基于总线的系统中, 使用总线窥探协议(例如 MESI 协议), 其做法是将 CPU 的每个缓存之间通过总线
相连接, 因此哪个 CPU 读取了哪些数据, 缓存了哪些数据, 都能被其他 CPU 知悉, 进而对 CPU 缓存进行标记, 达到缓存一致性的效果.

2. 缓存亲和度

举例: 一个进程在 CPU1 上执行, 那么 CPU1 的缓存中会维护许多状态, 如果该程序在下次调度时仍然由 CPU1 来执行, 由于 CPU1 缓存中已有了相关
的状态或数据, 所以执行会很快; 如果被分配给其他 CPU 的话, 其数据需要重新加载, 所以会浪费一些时间. 因此多处理器调度也许考虑此问题.

3. 多处理器 + 单队列调度

将系统的所有任务放在一个任务队列中, 有多个处理器取任务. 其优点是实现简单, 各个 CPU 即用即取, 负载均衡较好, 但缺点也很明显:

缺乏扩展性: 多处理器共享一个任务队列, 要考虑并发问题, 需要通过互斥原语来保证原子性操作, 一旦加了锁, 就得考虑性能上的损耗, 大部分的

时间都浪费在上锁, 释放锁, 锁的争抢问题上.

缓存亲和度: 对于每个 CPU, 都是简单地读取队列中的任务并执行, 这个过程无法保证一个程序被分配在同一个 CPU 上, 不符合缓存亲和度的思想.

4. 多处理器 + 多队列调度

为每个 CPU 分配一个队列, 队列之间相互独立, 且队列的数量可以随着 CPU 的增加而增加, 这样可以避免数据同步的处理, 与单队列调度相比,
没有扩展性问题, 而且具有良好的缓存亲和度.

此时还有一个问题: 如何确定一个任务该分配到哪个队列中? 如果分配不均, 就会出现负载失衡的情况.

为了应对负载失衡, 可以使用工作窃取的思想, 即工作量少的队列会偷看其他队列是不是比自己的工作多, 如果是则将一部分任务”窃取”给自己, 从
而实现负载均衡.

四. 参考

《操作系统导论》 雷姆兹·H.阿帕希杜塞尔 安德莉亚·C.阿帕希杜塞尔