# Scheduling

## 简介

![](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-Lb0zvBtHyplobYDWC6m%2F-LayADA6wDSvUI5WZO3u%2FScreen%20Shot%202019-03-27%20at%204.03.18%20PM.jpg?alt=media\&token=de3e462f-5e07-436a-bbac-ad412d757fac)

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

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

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

![](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-Lb0zvBtHyplobYDWC6m%2F-LayC_Z0DUedN4XGWbqB%2FScreen%20Shot%202019-03-27%20at%204.13.07%20PM.jpg?alt=media\&token=ea44822d-82b6-4517-9767-18f23b694cd0)

### 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) 如下图所示：

![](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-Lb0zvBtHyplobYDWC6m%2F-LayJer3Ug24uPyPqEVW%2FScreen%20Shot%202019-03-27%20at%204.44.36%20PM.jpg?alt=media\&token=be1edeb7-f79f-4820-a9eb-6febf949c363)

它们的 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     |

对应的甘特图如下所示：

![](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-Lb0zvBtHyplobYDWC6m%2F-Lb159hX5gsQn4_AzVe4%2FScreen%20Shot%202019-03-28%20at%2010.19.42%20AM.jpg?alt=media\&token=33593bae-8416-481b-a2b6-450d8b61a397)

* 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 的对比：

![](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-Lb0zvBtHyplobYDWC6m%2F-Lb19q1kaTf_-pU__nfG%2FScreen%20Shot%202019-03-28%20at%2010.40.09%20AM.jpg?alt=media\&token=717a4fcd-4c2e-4bab-a8cd-558a4690c398)

在图中可以看出，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

![](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-Lb0zvBtHyplobYDWC6m%2F-Lb1DmUMbSQJcFwEfML7%2FScreen%20Shot%202019-03-28%20at%2010.57.23%20AM.jpg?alt=media\&token=5c62f5a2-b165-4828-b37d-8375f4bfc5fb)

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

![](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-Lb0zvBtHyplobYDWC6m%2F-Lb1E4bqoN9W345OY-oj%2FScreen%20Shot%202019-03-28%20at%2010.58.41%20AM.jpg?alt=media\&token=c41367a7-df81-4554-a97a-0e77cc2fa38f)

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 短，反之亦然

![](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-Lb1pNADjbJFAOj570pt%2F-Lb2KkPCAf2kFIqlMEGZ%2FScreen%20Shot%202019-03-28%20at%204.07.26%20PM.jpg?alt=media\&token=c74466db-a553-4858-b5cf-0c47d22e90c3)

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，主要用于多媒体应用中。

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

![](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-LbBHctvNnbRe6zMnqn8%2F-LbBJd67vKNIQy1VhMwq%2FScreen%20Shot%202019-03-30%20at%209.59.09%20AM.jpg?alt=media\&token=10fbb5c4-086f-4552-a39a-14dbef74b1b0)

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

![](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-LbBHctvNnbRe6zMnqn8%2F-LbBK9pA0lv8x50Sx3HN%2FScreen%20Shot%202019-03-30%20at%2010.01.27%20AM.jpg?alt=media\&token=b8452437-0e28-469f-88f9-6dd0d0e2ff33)

*Earliest Deadline First (EDF)*

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

## A Final Word on Scheduling

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

![](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-LbBMlledh02zoPfsdrz%2F-LbBPua1m_q7VNztQtQs%2FScreen%20Shot%202019-03-30%20at%2010.26.33%20AM.jpg?alt=media\&token=20e2b4dc-a116-4e44-987f-5d7c7cf59d69)

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

## 参考

[slides](https://inst.eecs.berkeley.edu/~cs162/sp15/static/lectures/10.pdf)