《Operatring System：Three Easy Pieces》第七章进程调度: 介绍

type

status

date

slug

summary

假设

为了方便概念的描述，对操作系统中运行的进程（有时也叫工作任务）做出如下的假设：

工作负载

每一个工作运行相同的时间。

所有的工作同时到达。

一旦开始，每个工作保持运行直到完成。

所有的工作只是用 CPU（即它们不执行 IO 操作）。

每个工作的运行时间是已知的。

调度指标：

周转时间：定义为任务完成时间减去任务到达系统的时间

定义为

响应时间： 从任务到达系统到首次运行的时间

定义为：

还有一些指标，例如公平等

FSFS先来先服务：

也被称为FIFO

从公平的角度考虑，按照作业/进程到达的先后顺序进行服务

😍优点：简单，易于实现（这可能是最没用的优点了，难道不是吗？），公平（确实很公平，但是这个公平真的公平吗？）

🥲缺点：带权周转时间很大，对短作业来说体验不友好（想想你超市排队结账的例子，看到前边的人推着三购物车的食品并掏出了记账本），可以根据例子很清晰的得出FIFO对长作业有利，对短作业不利

两者的平均周转周期

左：(10 + 20 + 30)/3 = 20

右：(100 + 110 + 120)/3 = 110

SJF短作业优先

对于进程调度来说，也可以称为SPF短进程优先

先运行最短的任务，再运行次短的任务

🤩优点：优秀的平均等待时间表现！

🤔缺点：不公平，对短作业有利，对长作业不利；可能会产生饥饿的现象（想想看当源源不断的短作业在一个长作业执行之前到来，那对于短作业来说是多么可怕的一件事情。。。）；进程的时间由用户提供，不一定真实，不一定真的能做到短作业优先

两者的平均周转周期

左：(10 + 20 + 120)/3 = 50

右：(100+(110−10)+(120−10))/3 = 103.33

STCF最短完成时间优先

SRNT，抢占式的SJF

保证每个时刻，cpu正在运行已经到达的进程中剩余时间完成最短的进程

🤤优点：优于SJF

😔缺点：不公平，产生饥饿，产生饥饿！

平均周转周期为：

(120 + 10 + 20)/3 = 50

轮转RR

RR在一个时间片（调度量子）内内运行一个工作，然后切换到队列中的下一个任务

tips: 时间切片必须是时钟周期的整数倍

如果切片太大，RR就会退化成FCFS（退化这个词是不是很形象？这也反映了笔者在对各种算法的态度hhh），如果切片过小，频繁的切片会导致系统开销增大（不难理解，毕竟“切换”这个过程系统是需要开销的！）

时间片长度对于 RR 是至关重要的。时间片长度越短，RR 在响应时间上表现越好。然而，时间片太短是有问题的：突然上下文切换的成本将影响整体性能。因此，系统设计者需要权衡时间片的长度，使其足够长，以便摊销（amortize）上下文切换成本，而又不会使系统不及时响应

请注意，上下文切换的成本不仅仅来自保存和恢复少量寄存器的操作系统操作。程序运行时，它们在CPU 高速缓存、TLB、分支预测器和其他片上硬件中建立了大量的状态。切换到另一个工作会导致此状态被刷新，且与当前运行的作业相关的新状态被引入，这可能导致显著的性能成本。

🧐优点：公平，响应快，适用于分时OS（不会导致饥饿！）

👿缺点：由于高频率的进程切换，系统会增加一部分开销；不区分任务的紧急程度

平均响应时间：

SJF：(0 + 5 + 10)/ 3 = 5

RR：(0 + 1 + 2)/3 = 1

一些耗时较少的潜在资源消费者被安排在了重量级的资源消费者之后，这种问题通常被成为护航效应 （convey effect）

结合I/O

我们假设有两个进程A和B，每项运行50ms，不同的是，A运行10ms然后发出I/O请求，即放宽假设 4：所有程序都不执行 I/O。

假设我们正在构建STFC调度程序，这样的调度程序该如何考虑到这样的事实，即A分解成5个10ms子工作，而B仅仅是单个50msCPU需求？显然，仅仅运行一个工作，然后运行另一个，不考虑I/O是没有意义的

一种常见的方法是将 A 的每个 10ms 的子工作视为一项独立的工作。因此，当系统启动时，它的选择是调度 10ms 的 A，还是 50ms 的 B。对于 STFC，选择是明确的：选择较短的一个，在这种情况下是 A。然后，A 的工作已完成，只剩下 B，并开始运行。然后提交 A 的一个新子工作，它抢占 B 并运行 10ms。这样做可以实现重叠（overlap），一个进程在等待另一个进程的 I/O 完成时使用 CPU，系统因此得到更好的利用

小结

我们介绍了进程调度的基本思想，并开发了两类方法：

第一种类型（SJF、STCF）优化周转时间，但对响应时间不利。

第二种类型（RR）优化响应时间，但对周转时间不利。

参考

https://pages.cs.wisc.edu/~remzi/OSTEP/Chinese/07.pdf

假设