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 按先来后到的顺序执行程序，每个程序执行完毕后才进入下一个。如：

Process	Burst Time
$P_1$	24
$P_2$	3
$P_3$	3

假设 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 也无法设定地太小

举例如下：

Process	Burst Time
$P_1$	53
$P_2$	8
$P_3$	68
$P_4$	24

对应的甘特图如下所示：

• 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 永远选择优先级最高的任务运行。

A Final Word on Scheduling

Scheduling 策略解决的是资源稀缺条件下的资源分配最优化问题，若资源充足，则一切 Scheduling 策略都没有用处。解决资源不足的方式除了采用更合适、更高效的 Scheduling 策略，还可以通过提高单机资源，纵向扩展的方式来解决问题。不论用各种方式解决问题，有一个准则是通用的：

在资源利用率低的时候，系统的相应时间随着资源利用率的增加而线性增加；当资源利用率到达一定阈值之后，二者的关系逐渐转化成指数关系。大到 OS 资源调度，小到 Hash Table，无一例外。

参考

slides