本章讨论的问题是如何对进程调度。

在讨论之前,现有五个假设: 1. 每个任务都执行相同的时间。 2. 所有的任务都在同一时间到达。 3. 一旦开始,每个任务都会运行至结束。 4. 所有的任务都是 CPU 密集型的。 5. 每个任务运行的时间是已知的。

首先定义一个指标 turnaround time。

First In, First Out (FIFO) or First Come, First Served (FCFS)

先来先服务,顾名思义,按照任务在队列中的先后顺序进行调度。

但是,将第一个假设去除,即每个任务执行的时间不相同,那么就会出现下面的问题。

如果长进程在队列的前面,一系列运行时间短进程在队列的后面,那么时间短的任务就需要等待。

书中的一个比喻很恰当,当在超市排队结账时,前面有一个人推着十个购物车在结账,那么后面的一些只有几件东西的顾客一定是非常绝望的。

Shortest Job First (SJF)

在队列中的几个进程,操作系统选择其中最短的进行调度,然后按照时间进行优先级排序。

但是,如果将第二个假设去除,即任务不是同时到达的,就会出现下面的问题。

如果长进程先到达,短进程后到达,就会出现同样的问题

Shortest Time-to-Completion First (STCF)

上一章说了 CPU 会有一个时钟中断。那么,在长进程运行时,短进程到达了,可以利用时钟中断的时候 OS 掌握控制权,借着这个机会调度新来的短进程执行,然后再恢复长进程的执行。

接下来再定义一个指标 response time,也就是首次响应时间,举个例子,如果用户输入一个字符,结果要等前面的一堆任务完成才能响应,那么很尴尬的是,用户需要坐在显示器前面等待这样一个事情。

如果按照这个指标来看,SJF 对这个指标完成度非常差。

Round Robin (RR)

有一个进程的队列。

在这种方式上,定义了一个 time slice。每个进程运行 time slice 时间后,OS 会切换其它的进程,如此循环,知道进程退出。这样就能做到 response time 变的很小。当然这样也存在了一定的开销,那就是相较于 SJF 和 FIFO 来说,上下文切换就会变得很频繁。

所以对于 turnaround 来说,RR 的指标是最差的。

如果碰上了 I/O,进程将会被阻塞,这是其它进程会被调度,这个进程会被 block 知道再次 ready 后放入队列中。