open-courses
Search…
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_1
P2P_2
P3P_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_2
P3P_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