OS: Process: Scheduler

21st September 2020 at 10:13pm
OS: Process

多个进程同时运行时,需要考虑如何对他们进行调度。调度器(scheduler)即是实现这套逻辑的 OS 组件。

对于调度系统,

  1. 需要考虑的 维度效率公平
  2. 如何体现上述的维度,则需要设计 度量方式(metrics),用来衡量不同的算法在不同情况下的表现

常见的 度量方式 有几种:

  • turnaround time,即任务开始排队到完成的平均时间。这个指标越低则越高效
  • response time,即任务开始排队到被执行的平均时间。这个指标越低则(往往)越公平

这其中会涉及到一个问题,调度过程是 抢占式的(preemptive) 还是 非抢占式的(non-preemptive)。抢占式的,表示调度器可以暂停一个任务(process)的运行,而切换到另外一个任务。现代操作系统是抢占式的。抢占式意味着 CPU 运行需要有固定的时间片(time slice),即每次运行一个进程至少一个时间片长度的时间。

有几种简单的调度算法。

调度算法

First In, First Out (FIFO)

这种算法实现是不考虑抢占的。显然很容易有 bad case 影响整体的性能。

Shortest Job First (SJF)

这种算法能实现最优的效率。但是它是非抢占式的,如果新任务进入的时间点不合适,会影响其性能。

Shortest Time-to-Completion First (STCF)

总是运行当前任务列表中,最快可以完成的任务。这种算法可以说是 SJF 的抢占式版本。效率是最优的,但是是非常不公平的。

Round Robin

轮转执行各任务。这种算法是平均响应时间(看上述 response time 定义)最短的,是最公平的,但相对地 turnaround time 不是最优。

而且需要考虑 频繁的上下文切换(context switch)带来的性能损失。不仅包含存取寄存器的开销,还有 CPU 缓存、页表缓存、分支判断上的损耗。