操作系统基础25-多级队列调度算法

操作系统基础25-多级队列调度算法

2020-12-01 13:30·重学IT的老猫

进程容易分成不同组的情况下,可以有另一类调度算法。例如,进程通常分为前台进程(foreground process)(或交互进程)和后台进程(background process)(或批处理进程)。这两种类型的进程具有不同的响应时间要求,进而也有不同调度需要。另外,与后台进程相比,前台进程可能要有更高的优先级(外部定义)。

多级队列(multilevel queue)调度算法将就绪队列分成多个单独队列(图1)。根据进程属性,如内存大小、进程优先级、进程类型等,一个进程永久分到一个队列,每个队列有自己的调度算法。

例如,可有两个队列分别用于前台进程后台进程。前台队列可以采用RR调度算法,而后台队列可以采用FCFS调度算法。
此外,队列之间应有调度,通常采用固定优先级抢占调度。例如,前台队列可以比后台队列具有绝对的优先。
现在,我们看一个多级队列调度算法的实例,这里有五个队列,它们的优先级由高到低:

操作系统基础25-多级队列调度算法

图1 多级队列调度

每个队列与更低层队列相比具有绝对的优先。例如,只有系统进程、交互进程和交互编辑进程队列都为空,批处理队列内的进程才可运行。如果在一个批处理进程运行时有一个交互进程进入就绪队列,那么该批处理进程会被抢占。

另一种可能是,在队列之间划分时间片

每个队列都有一定比例的CPU时间,可用于调度队列内的进程。例如,对于前台-后台队列的例子,前台队列可以有80%CPU时间,用于在进程之间进行RR调度,而后台队列可以有20%CPU时间,用于按FCFS算法来调度进程。

队列之间划分时间片

  • 最高优先级上进程运行一个时间片,次高优先级上进程运行两个时间片,再下级运行四个时间片,依次类推。
  • 每次从队列头开始运行进程,每当一个进程在一个优先级队列中用完它时间片后就移到队列尾部;只有当高优先级队列为空时,才会从不为空的低优先级队列中选择进程运行;在低优先队列中等待时间过长进程将会移动高优先级队列

参考:《操作系统概念》

-------------本文结束 感谢阅读-------------