当有一堆任务要处理,但由于资源有限,这些事情没法同时处理。这就需要确定某种规则来决定处理这些任务的顺序,这就是 “调度” 研究的问题。
调度分为 3 个层级:
其中频率最高的进程调度是我们要重点研究的。
进程调度就是按照某种规则,从就绪队列中选择一个进程为其分配处理机。
那什么时候需要进行进程调度呢?
有些时候是不能进行进程调度的:
进程调度的方式
分为非抢占式和抢占式
狭义的进程调度是指仅从就绪队列中选择一个进程这个步骤;而广义的进程调度还包括进程切换这一步骤。
进程调度、切换是有代价的,并不是频率越高并发度就越高。
FCFS 算法
FCFS
算法 是一种先来先服务的的算法,根据先后顺序依次执行,它是一种非抢占式的调度算法,相对来说比较公平。
但是存在一个问题,就是如果前面有一个大作业,后面跟着一个小作业,那么小作业的带权周转时间很大,用户体验会非常不好。
比如你去排队买奶茶,你只想买一杯奶茶,但是你前面有一个要买 20
杯,你就要等很长时间,用户体验很差。
所以 FCFS
算法对长作业比较有利,但对短作业不利,它有利于 CPU
繁忙型作业,不利于 IO
繁忙型作业;所谓 CPU 繁忙型作业,是指该类作业需要大量的 CPU 时间进行计算,而很少请求 IO 操作,IO 繁忙型作业是指 CPU 处理时,需要频繁的请求 IO 操作,所以 CPU 繁忙型作业更接近于长作业。
SJF 算法
即短作业优先算法,可用于进程调度,称为短进程优先算法,SPF
,也是非抢占式算法,但是他们也有抢占式的版本:最短剩余时间算法 SRTN
。
简单地说就一句话:每次调度时选择当前已到达且运行时间最短的作业。
同样是上面的那一道题,我们使用 SJF
算法来解决:
下面来分析一下抢占式的 最短剩余时间算法:
该算法对长作业不利,因为长作业一直让着短作业,导致长作业可能永远没机会执行,形成 饥饿 现象; 但 SJF 算法的平均等待时间和平均周转时间都是最少的。
高响应比优先算法
这是一个非抢占式的算法,只有当前运行的作业主动放弃处理机时才需要调度,才需要计算响应比。
一般来说,进程优先级的设置使用以下规则:
IO 型进程
优先于 计算型进程;时间片轮转调度算法
主要适用于分时系统,即分配给进程时间片,时间到了就重新进入就绪队列,然后再轮流使用,其中时间片大小的选取很重要,如果时间片很大,那么就会退化成为先来先服务算法,如果时间片很小,频繁的切换处理机,开销很大。