进程调度

Saturday, October 12, 2019

进程调度

我们使用一个周转时间来评估调度策略 T(周转时间)=T(完成时间)-T(到达时间) 为了简化,先假设所有任务同一时间到达,既为0

先进先出 FIFO

先进来的先执行,很容易丽姐的一种策略方式。假如有3个进程,都是10秒钟能完成,那平均周转时间就是 (10+20+30) / 3 = 20,平均周转时间为20。

但是先进先出的一个大问题是,假如先运行的进程,完成时间需要很久,比如100秒。那这次平均周转时间就变成了 (100+110+120)/ 3 = 110,效率非常低。这就是护航效应。

最短任务优先 SJF

先运行最短的任务,依次下去。这样上面的例子就会变成(10+20+130) / 3 = 50,大幅度缩短平均周转时间。

但是前面也说到,我们是假设所有任务同时到达的,现在放宽这一条件,B,C 任务在 A 任务到达10秒后到达,这样平均周转时间变为(100 + 110 - 10 + 120 - 10) / 3 = 103.33

最短完成时间优先 STCF

这种策略基于时钟中断和上下文切换,在 SJF 的基础上,添加抢占,当有新进程进来时,先判断睡的工作量最小,就去运行哪个进程。这样效率会重新变为之前的SJF 计算的50。

新度量指标:响应时间

现代操作系统,已经引入了分时系统,比如用户会坐在终端面前,系统能够实时响应交互。所以我们有一个新的指标:响应时间。 T(响应时间) = T(首次运行)- T(到达时间) 比如运行时间都为10的三个进程 ABC,A 在时间0到达,B,C 在时间10到达。那么 ABC 的响应时间为0,0,10,平均3.33

那么问题就来了,之前讨论的调度方式,在响应时间上表现都不好,比如 ABC 同时到达,那么 C 不得不等待前面两个完成才能运行。你不能让用户在终端面前输入指令,等待10s 才能看到系统的响应。

轮转 RR

  • 在一个时间片内运行一个进程,然后切换到下一个进程来运行。
  • 时间片必须为时钟周期的倍数

时间片

可以看出,时间片长度对于RR 至关重要,但是时间片太短是有问题的,突然上下文切换的成本会影响整体性能。上下文切换的成本不仅仅来自保存和恢复少量寄存器的操作系统,它们还在 CPU 高速缓存,TLB,分支预测和其他片上硬件中建立了大量的状态。

相对的,我们缩短了响应时间,周转时间就不可避免的变长了。

结合 I/O

前面的讨论,我们都没有把 I/O 放进去考虑,实际情况基本所有程序都涉及到 I/O。 调度程序要在发起 I/O 请求时做出决定,因为在 I/O 期间,不会使用 CPU,被阻塞等待I/O 完成。这时调度程序应该在 CPU 上安排其他工作。

假如A进程要频繁的请求 I/O,比如每执行10ms 就要进行一次 I/O,假设 I/O 的时间也是10ms,B 进程是一个要处理50ms 的进程。常见的方法是,基于 STCF,把每一次10ms 的处理工作当做一个独立的工作,那么在 I/O期间,会去切换到 B 来处理,I/O 结束后,又会切换到 A。系统得到了更好的利用。

OS-7.8 OS-7.9

无法预知

前面我们都假设了进程的运行时间,但实际上,这个假设很糟糕。 后面我们会利用最近的历史来预测未来,从而解决这个问题。

OS

调度:多级反馈队列

受限制直接执行