核心问题 | How to develop scheduling policy? |
---|---|
解法 | 见下文 |
多个进程同时运行时,需要考虑如何对他们进行调度。调度器(scheduler)即是实现这套逻辑的 OS 组件。
对于调度系统,
常见的 度量方式 有几种:
这其中会涉及到一个问题,调度过程是 抢占式的(preemptive) 还是 非抢占式的(non-preemptive)。抢占式的,表示调度器可以暂停一个任务(process)的运行,而切换到另外一个任务。现代操作系统是抢占式的。抢占式意味着 CPU 运行需要有固定的时间片(time slice),即每次运行一个进程至少一个时间片长度的时间。
有几种简单的调度算法。
这种算法实现是不考虑抢占的。显然很容易有 bad case 影响整体的性能。
这种算法能实现最优的效率。但是它是非抢占式的,如果新任务进入的时间点不合适,会影响其性能。
总是运行当前任务列表中,最快可以完成的任务。这种算法可以说是 SJF 的抢占式版本。效率是最优的,但是是非常不公平的。
轮转执行各任务。这种算法是平均响应时间(看上述 response time 定义)最短的,是最公平的,但相对地 turnaround time 不是最优。
而且需要考虑 频繁的上下文切换(context switch)带来的性能损失。不仅包含存取寄存器的开销,还有 CPU 缓存、页表缓存、分支判断上的损耗。
这一章在研究方法上是个非常好的范例。
虽然书中并不是按我上面这样 top-bottom 行文的,而是 bottom-top,但是思考这类问题的思路是一致的。