进程调度

操作系统的调度器决定哪个就绪进程获得CPU，以及获得多久。按能否打断正在运行的进程，调度分为两类：

• 非抢占式调度：进程一旦获得CPU，就一直运行到结束或主动进入阻塞，中途不会被换下。
• 抢占式调度：进程可以在运行途中被打断，例如时间片用完，或有更紧迫的进程变为就绪；被打断的进程回到就绪队列等待下一次调度。

一次调度决策通常出现在四种时机：进程从运行转为阻塞、时间片用完或进程被抢占、阻塞的进程转为就绪、进程终止。是否在这些时机立刻切换进程，取决于系统采用抢占式还是非抢占式调度。

最简单的调度算法，采用非抢占式策略。CPU按进程请求的顺序分配，像超市排队结账：一旦进程获得CPU，它就一直运行到完成或发生I/O阻塞。

• 优点：算法简单，容易理解和实现；对到达时间相同的进程按先后顺序处理，是公平的。
• 缺点：如果先运行的是一个长进程，后面的短进程都必须等待，平均等待时间变长，CPU和I/O设备的利用率下降，这种现象称为护航效应。FCFS也无法保证分时系统需要的响应时间。

优先调度下一个CPU执行周期最短的进程。CPU执行周期指进程一次连续占用CPU的时间，下文也直接称为CPU执行时间。SJF可以是抢占式的，此时称为最短剩余时间优先；也可以是非抢占式的。

• 优点：在所有进程同时到达的情况下，SJF能给出最小的平均等待时间。
• 缺点：下一个CPU执行周期的长度难以准确预知，通常只能根据历史数据做指数平均预测；如果系统中不断有短进程到来，长进程可能永远得不到执行，形成饥饿。

为分时系统设计的抢占式算法。系统定义一个时间片，即CPU一次分配给进程连续运行的时间，通常为10–100 ms；就绪队列被视为循环队列，CPU轮流为每个进程服务一个时间片。

• 优点：每个进程都能在有限时间内获得CPU，响应时间短，适合交互式系统；没有进程会连续占用CPU太久。
• 缺点：时间片太短会让上下文切换过于频繁，切换开销吃掉大量CPU时间；时间片长到超过大多数进程的CPU执行时间时，进程在一次时间片内就运行完毕，算法退化为FCFS。

为每个进程分配一个优先级，CPU总是分配给优先级最高的进程。优先级可以在创建时静态确定，也可以在运行时动态调整。

• 优点：可以根据任务的重要性、紧迫程度灵活安排执行顺序。
• 缺点：低优先级的进程可能无限期等待，形成饥饿。常用的缓解办法是老化：随着等待时间增加，逐步提高进程的优先级。

比较同一组进程在先来先服务和轮转调度下的执行顺序与等待时间。