处理机调度及常用的几个调度算法

调度的基本概念

当有一堆任务要处理，但由于资源有限，这些事情没法同时处理。这就需要确定某种规则来决定处理这些任务的顺序，这就是 “调度” 研究的问题。

调度分为 3 个层级：

• 作业调度：创建新的进程；
• 内存调度：恢复旧的进程；
• 进程调度：选择就绪进程；

其中频率最高的进程调度是我们要重点研究的。

进程调度的时机、方式

进程调度就是按照某种规则，从就绪队列中选择一个进程为其分配处理机。

那什么时候需要进行进程调度呢？

有些时候是不能进行进程调度的：

• 中断的时候；
• 进程在操作系统内核程序临界区中，但是在普通临界区中是可以进行调度或者切换的；
• 原子操作时；

进程调度的方式

分为非抢占式和抢占式

狭义的进程调度是指仅从就绪队列中选择一个进程这个步骤；而广义的进程调度还包括进程切换这一步骤。

进程调度、切换是有代价的，并不是频率越高并发度就越高。

调度算法

FCFS 算法

FCFS 算法 是一种先来先服务的的算法，根据先后顺序依次执行，它是一种非抢占式的调度算法，相对来说比较公平。

但是存在一个问题，就是如果前面有一个大作业，后面跟着一个小作业，那么小作业的带权周转时间很大，用户体验会非常不好。

比如你去排队买奶茶，你只想买一杯奶茶，但是你前面有一个要买 20 杯，你就要等很长时间，用户体验很差。

所以 FCFS 算法对长作业比较有利，但对短作业不利，它有利于 CPU 繁忙型作业，不利于 IO 繁忙型作业；所谓 CPU 繁忙型作业，是指该类作业需要大量的 CPU 时间进行计算，而很少请求 IO 操作，IO 繁忙型作业是指 CPU 处理时，需要频繁的请求 IO 操作，所以 CPU 繁忙型作业更接近于长作业。

SJF 算法

即短作业优先算法，可用于进程调度，称为短进程优先算法，SPF，也是非抢占式算法，但是他们也有抢占式的版本：最短剩余时间算法 SRTN。

简单地说就一句话：每次调度时选择当前已到达且运行时间最短的作业。

同样是上面的那一道题，我们使用 SJF 算法来解决：

下面来分析一下抢占式的 最短剩余时间算法：

该算法对长作业不利，因为长作业一直让着短作业，导致长作业可能永远没机会执行，形成 饥饿 现象； 但 SJF 算法的平均等待时间和平均周转时间都是最少的。

高响应比优先算法

这是一个非抢占式的算法，只有当前运行的作业主动放弃处理机时才需要调度，才需要计算响应比。

一般来说，进程优先级的设置使用以下规则：

• 系统进程 优先于 用户进程；
• 交互型进程 优先于 非交互型进程；
• IO 型进程 优先于 计算型进程；

时间片轮转调度算法

主要适用于分时系统，即分配给进程时间片，时间到了就重新进入就绪队列，然后再轮流使用，其中时间片大小的选取很重要，如果时间片很大，那么就会退化成为先来先服务算法，如果时间片很小，频繁的切换处理机，开销很大。