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

P1P_1

24

P2P_2

3

P3P_3

3

假设 3 个 processes 的调度顺序是: P1P_1P2P_2P3P_3 ,那么对应的甘特图 (Gantt Chart) 如下图所示:

它们的 Waiting Time 分别为: P1=0;P2=24;P3=27P_1=0;P_2=24;P_3=27 ,Average Waiting Time 为 (0+24+27)/3=17(0+24+27)/3 = 17 ,Average Completion Time 为 (24+27+30)/3=27(24+27+30)/3=27

可以看出,从 Average Waiting Time 和 Completion Time 上看, P2P_2P3P_3 前面的长任务 P1P_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

P1P_1

53

P2P_2

8

P3P_3

68

P4P_4

24

对应的甘特图如下所示:

  • Waiting Time:

    • P1=(6820)+(11288)P_1 = (68-20)+(112-88)

    • P2=(200)=20P_2 = (20-0) = 20

    • P3=(280)+(8848)+(125108)=85P_3 = (28-0)+(88-48)+(125-108) = 85

    • P4=(480)+(10868)=88P_4 = (48-0)+(108-68)=88

  • Average Waiting Time: (72+20+85+88)/4=66.25(72+20+85+88)/4 = 66.25

  • Average Completion Time: (125+28+153+112)/4=104.5(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, τn=f(tn1,tn2,tn3,...)\tau_n = f(t_{n-1}, t_{n-2}, t_{n-3}, ...) ,一个典型的例子就是 exponential averaging, τn=αtn1+(1α)τn1\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