[OS]Three Easy Pieces Chapter 7

Scheduling: Introduction

1 Workload Assumptions

1. Each job runs for the same amount of time.
2. All jobs arrive at the same time.
3. Once started, each job runs to completion.
4. All jobs only use the CPU (i.e., they perform no I/O)
5. The run-time of each job is known.

2 Scheduling Metrics

• 周转时间（turnaround time）：$T_{turnaround} = T_{completion} - T_{arrival}$
• 公平性
• 响应时间（response time）：$T_{response} = T_{fisrtrun} - T_{arrival}$

3 First In, First Out (FIFO)

最基本的调度算法，先到来的任务先执行，也称为先来先服务（FCFS）。

优点

• 实现简单
• 无饥饿现象

缺点

• 存在护航效应（convoy effect），即短作业排在长作业之后，导致系统平均周转时间边长。

4 Shortest Job First (SJF)

每次选择调度当前最短的任务。传统上是不可抢占的。

优点

• 平均周转时间较短
• 简单

缺点

• 当任务到达时间不同的时候，仍然存在护航效应

5 Shortest Time-to-Completion First (STCF)

最短完成时间，也称为抢占式短作业优先（PSJF）。

该调度策略是对短作业优先的改进，每当有新的任务到来的时候，就抢占当前进程，让调度器根据目前所需最短完成时间来进行调度。

优点

• 解决了SJF的护航效应

缺点

• 响应时间长，交互性差

6 Round Robin

将CPU划分为时间片，平均分配给各个进程，每个进程轮流得到时间片。

优点

• 公平
• 响应时间低

缺点

• 平均周转时间差（最差之一）

时间片过长会导致响应时间变差，最坏情况下会退化成FCFS。时间片过短虽然会提升响应时间，但是会导致上下文切换开销过大。需要注意的是，这种开销不单单是切换寄存器的值，当程序运转的时候，会在CPU缓存，TLB，分支预测等硬件建立很多状态来提升效率，当切换进程的时候，这些状态全部需要替换，造成一定的开销。

7 Incorporating I/O

将任务分为CPU密集型和IO密集型，IO密集型的优先级更高，这样可以更好的利用资源。