Scheduling

简介

OS 中等待资源的 threads 通常会被放入 queue 中，如：

CPU：ready queue
I/O: I/O queue (这里可以进一步细分)

scheduling 指的就是将资源分配给具体哪个 thread 的策略问题。本节主要讨论的就是如何通过调整 threads 获得 CPU 的顺序使得系统在某些运行指标 (如 Wait Time, Completion Time, ) 上得到优化：

Scheduling Policy Goals/Criteria

Minimize Response Time (让交互性应用尽快得到反馈)
- Minimize elapsed time to do an operation (or job)
- Response time is what the user sees:
  - Time to echo a keystroke in editor
  - Time to compile a program
  - Real-time Tasks: Must meet deadlines imposed by World
Maximize Throughput (尽可能地使用 CPU)
- Maximize operations (or jobs) per second
- Minimizing response time will lead to more context switching than if you only maximized throughput
- Two parts to maximizing throughput
  - Minimize overhead (for example: context-switching)
  - Efficient use of resources (CPU, disk, memory, etc)
Fairness (尽可能地对各个 threads 做到公平)
- Share CPU among users in some equitable way
- Fairness is not minimizing average response time

以上是 Scheduling Policy 的主要目标，但这三个目标之间存在明显的 trade-off：

Minimize Response Time 会增加 context switch 的频度，同时也会增加 cache 的 miss rate，从而导致 CPU 利用率下降，与 Maximize Throughput 的目的相悖
Minimize Response Time 会增加短任务的优先级，降低长任务的优先级，但这与 Fairness 相悖
Fairness 更希望资源被公平地分配给各个 threads，这会增加 context switch 的频度，同时也会增加 cache 的 miss rate，从而导致 CPU 利用率下降，与 Maximize Throughput 的目的相悖

Scheduling Policies

First-Come, First-Served (FCFS) Scheduling

FCFS 也称为 FIFO 或者 Run until done，FCFS 按先来后到的顺序执行程序，每个程序执行完毕后才进入下一个。如：

假设 3 个 processes 的调度顺序是： $P_1$ 、 $P_2$ 、 $P_3$ ，那么对应的甘特图 (Gantt Chart) 如下图所示：

它们的 Waiting Time 分别为： $P_1=0;P_2=24;P_3=27$ ，Average Waiting Time 为 $(0+24+27)/3 = 17$ ，Average Completion Time 为 $(24+27+30)/3=27$

可以看出，从 Average Waiting Time 和 Completion Time 上看， $P_2$ 、 $P_3$ 前面的长任务 $P_1$ 拖累，这种现象被称为 Convoy Effect。

Round Robin (RR)

FCFS 对短时任务并不友好，调度结果随着任务提交的顺序变化，如果刚好在一个短时任务之前启动一个长时任务，那个短时任务心里肯定不好受。

Round Robin 策略：

每个 process 轮流获取一段 CPU 时间，通常为 10-100 ms
process 使用时间到后，就被剥夺使用权，重新放回 ready queue

假设有 n 个 processes，每段 CPU 时长 (quantum) 为 q：

每个 process 获得 1/n 的 CPU 时间，每次获得 q 的使用时间
每个 process 最多等待 (n-1)q 后就能使用 CPU
当 q 很大时 => FCFS，当 q 很小时 => 所有 processes 的执行过程相互交织，考虑到 context-switch 的固定开销，q 也无法设定地太小

举例如下：

对应的甘特图如下所示：

Waiting Time:
- $P_1 = (68-20)+(112-88)$
- $P_2 = (20-0) = 20$
- $P_3 = (28-0)+(88-48)+(125-108) = 85$
- $P_4 = (48-0)+(108-68)=88$
Average Waiting Time: $(72+20+85+88)/4 = 66.25$
Average Completion Time: $(125+28+153+112)/4 = 104.5$

下表展示不同 quantum 设定下的 RR 与 FCFS 的对比：

在图中可以看出，quantum 取值适中的 RR 策略在 Wait/Completion Time 指标上表现地最好，但仍然不如最好的 FCFS。

小结：RR 策略克服了 FCFS 策略在短时任务调度场景上的缺陷，但增加了 context-switch 的成本，以及 cache miss rate，对于长时任务有一定的影响，因此 RR 策略实际使用时长大于 FCFS。值得一提的是：最早期的 UNIX 系统中 q = 1s，现代系统中 q = 10-100ms，context-switch 的时间在 0.1ms - 1ms，因此 context-switch 的成本大约占 1%。

Strict Priority Scheduling

每个 process 都被赋予重要性等级，同属于一个等级的任务被放入相同的队列中，队列内部的任务按 FCFS 策略调度，只有较高优先级的任务全部制定完毕后，才能执行较低优先级的任务。这种方案的问题在于：

Starvation：低优先级任务可能被饿死
Deadlock：当低优先级任务拿着高优先级任务需要的锁，就可能出现死锁问题，于是高、低优先级的任务都无法推进，而中优先级的任务一直被执行。

要解决这两个问题，可以使用 dynamic properties，动态地调节任务优先级的策略，在后续章节中会介绍。

Lottery Scheduling

前面几种调度策略，都没有考虑到 Fairness 问题

严格地按优先级调度，对低优先级任务不公平。在 Multics 计算机中，当机器最终退休时，运维人员发现有一个十年前的任务还未被执行
为了实现公平，即使短时任务存在，也需要将 CPU 分配一部分给长时任务。但这里的 trade-off 在于牺牲 Average Response Time
- 给每个优先级队列一定比例的 CPU 时间
- 提高没有执行的任务的优先级

这其中一种选择就是 Lottery Scheduling，Lottery Scheduling 和北京买车摇号的策略一模一样

给每个任务赋予一定数量的 lottery tickets，就是摇号池里的号码
在每次分配 CPU 资源时，随机选取一个 winning ticket，中奖的任务就能够获得一段 CPU 资源
平均来看，每个任务所获取的 CPU 时间与它所持有的 lottery tickets 占比正相关

可以想象，Lottery Scheduling 的关键在于如何分配 tickets：

为了达到 SRTF 的调度效果，可以给短时任务分配更多的 tickets
为了避免长时任务饿死，每个任务都会获得至少 1 张 ticket

与 Strict Priority Scheduling 相比，Lottery Scheduling 在负载发生变化时处理地更优雅，增加或者删除任务将按比例地修正其它任务获取的资源量。

What if we Knew the Future?

在不考虑实现的情况下，是否有某种策略让我们能够在任意场景下都能获取最佳 FCFS 的调度效果？

Shortest Job First (SJF)
- Run whatever job has the least amount of computation to do
- Sometimes called "Shortest Time to Completion First" (STCF)
Shortest Remaining Time First (SRTF)
- Preemptive version of SJF: if job arrives and has a shorter time to completion than the remaining time on the current job, immediately preempt CPU
- Sometimes called "Shortest Remaining Time to Completion First" (SRTCF)

核心思想就是，谁最快结束谁先用，将短时任务快速清出，对长时任务的影响较小，达到减小 average response time 的目的。因此 SJF 与 SRTF 通常也是在 Response Time 指标上的能做到的极致。如果所有任务的长度相同，SRTF 就与 FCFS 相同；如果所有任务的长度各异，SRTF 和 RR 对短时任务更有帮助。

假设有三个任务：

A，B：都是 CPU bound 任务，每次执行一周
C：I/O bound 任务，需要 1ms CPU，9ms disk I/O

若使用 FCFS 策略，一旦 A 或 B 在 C 之前启动，C 就必须至少等待一周；若用 RR 或者 SRTF：

SRTF 的其它方面：

Starvation：SRTF 可能因为不断涌入短时任务，导致长时任务饿死
Need to predict future：在实现 SRTF，我们需要准确地知道每个任务所需的执行时间
Bottom line：虽然我们无法做到准确的 SRTF，但可以通过研究它来作为其它策略的衡量标准
SRTF Pros & Cons：
- Pros
  - Optimal (average response time)
- Cons
  - Hard to predict future
  - Unfair

Adaptive SRTF

理论上同一个个体使用资源的行为是相似的，利用个体过去的行为预测其将来的行为，在多数情形下适用。如 SRTF with estimated burst length， $\tau_n = f(t_{n-1}, t_{n-2}, t_{n-3}, ...)$ ，一个典型的例子就是 exponential averaging, $\tau_n = \alpha t_{n-1} + (1-\alpha)\tau_{n-1}$ 。

Multi-Level Feedback Scheduling

使用多个 queues 来保存不同优先级的任务，每个 queue 使用各自的 scheduling 策略，如 foreground - RR，background - FCFS，具体规则如下：

每个任务从最高优先级队列开始
如果任务使用完一段 CPU 资源，则降一级
如果任务未使用完本段 CPU 资源，则升一级
每个队列的优先级与 cpu quantum 成反比，优先级高的 quantum 短，反之亦然

Multi-Level Feedback Scheduling 的调度策略接近 SRTF，长时任务很容易沉底，短时任务通常在高优先级队列中，Scheduling 通过将任务在不同固定优先级的队列之前切换实现，队列获得的 CPU 时间与优先级成正比，优先级越高获得越多的 CPU 时间。但用户进程如果知道这种调度策略，可以利用它的特性来攫取更多的 CPU 时间。

Real-Time Scheduling (RTS)

尽管资源利用效率是调度策略的核心目标，但在实时场景下，进程被调度的可预测性 (predictability) 也很重要。根据实时性的要求，可将 RTS 进一步分为 Hard Real-Time 和 Soft Real-Time。Hard Real-Time 的目标是满足所有 deadlines，具体的策略包括 EDF (Earliest Deadline First)、LLF (Least Laxity First)、RMS (Rate-Monotonic Scheduling) 以及 DM (Deadline Monotonic Scheduling)；Sort Real-Time 的目标是在大多数情况下或大概率下能满足所有 deadlines，主要用于多媒体应用中。

现实负载特征如下图所示：

每个任务启动时间相互独立，可以被抢占，且 deadline (D) 与 computation time (C) 已知，这时候 RR 策略不符合要求：

Earliest Deadline First (EDF)

根据每个任务距离 Deadline 的时间来动态地调整其优先级，scheduler 永远选择优先级最高的任务运行。