[What]Scheduling:Introduction

理解操作系统调度策略。

轮转时间(Turnaround Time)

通过 轮转时间 来测试调度策略的优劣, 轮转时间 是指从启动进程到完成该进程所花的时间。

FIFO 策略

假设只有一个核的情况下,以 FIFO 策略调度进程。

当进程 A、B、C 同时启动(FIFO 调度器依次运行),且其完成所需时间分别为 100、10、10 秒,那么它们的平均轮转时间为:

(100 + 110 + 120) / 3 = 110
  • 从 A 启动到 A 完成花费 100 秒
  • 从 B 启动到 B 完成花费 110 秒
  • 从 C 启动到 C 完成花费 120 秒

SJF(Shortest Job First) 策略

当调度器先运行花费时间短的进程,此处是 B、C、A 顺序调度(假设可以提前预知各个进程运行时间),那么平均轮转时间为:

(10 + 20 + 120 ) / 3 = 50

下面假设当 A 先启动,10 秒以后才是 B、C 同时启动,那么即使是 SJF 策略也只能先调度 A , 那么平均轮转时间为:

  (100 + 100 + 110) / 3 = 103.333

STCF(Shortest Time-to-Completion First) 策略

要实现运行时间短的进程优先运行,就需要调度器能根据进程优先级进行上下文切换。

基于 SJF 的第二种运行方法,当 B、C 启动时, A 就会被抢占,其平均轮转时间为:

( 10 + 20 + 120 ) / 3 = 50

响应时间(Response Time)

轮转时间测测试方式是以进程启动到进程完成所花的时间,应用场景比较单一。

在时分复用机制的调度策略中,响应时间是比较重要的测量指标。

响应时间 是指从进程已进入准备状态到其真正被调度所花的时间。

虽然上面的 STCF 调度策略具有很短的轮转时间,但其响应时间极长,这导致用户体验很差。

  • 比如 C 进程需要等到 B 进程运行完了才能被调度。

RR(Round Robin) 策略

RR 策略便是以时间片的方式循环调度各个进程的调度策略, 时间片的长度是定时器粒度的整数倍。

假设有A、B、C 三个进程,每个进程需要运行 5 秒,若以响应时间为测试依据则:

//SJF
( 0 + 5 + 10 ) / 3 = 5
//RR(假设时间粒度为 1 秒)
( 0 + 1 + 2 ) / 3 = 1

毫无疑问,RR 策略的用户体验会更好。

  • 需要注意的是:调度粒度不能太小,否则上下文切换的时间将会占用太多 CPU 资源。
    • 上下文切换除了寄存器的存取,还有 cache miss、页表重载、CPU 分支预测打断等很多动作

但若以轮转时间为测试依据则:

//SJF
( 0 + 5 + 10 ) / 3 = 5
//RR(假设时间粒度为 1 秒)
( 13 + 14 + 15 ) / 3 = 14

很明显,以进程的完成时间来看,RR 策略是很差的。

这就是高吞吐量(轮转时间短)和高响应速度(响应时间短)的矛盾,实际应用中会结合二者调度策略,力求达到一个平衡。

考虑 IO 操作

当进程请求 IO 操作时,由于接下来的工作是由其他硬件(比如DMA)完成的,所以这段时间的 CPU 是空闲的。

操作系统会阻塞当前进程并调用其他进程,当 IO 操作完毕会产生一个中断,将刚才阻塞的进程状态设置为 ready 或直接调度。

基于以上理论,在进行线程优先级分配时:

  1. 根据整体任务分配出 IO 密集型和 CPU 密集型线程
  2. IO 密集型线程优先级要高于 CPU 密集型线程

这样既可以保证 IO 密集型的高响应速度,也可以保证 CPU 密集型的高吞吐量。

  • 因为 IO 密集型仅占用少部分 CPU 资源,一旦发出 IO 请求便可以立即运行 CPU 密集型线程。
Last Updated 2019-08-12 一 07:57.
Render by hexo-renderer-org with Emacs 26.1 (Org mode 9.1.14)