操作系统基础26-多级反馈队列调度算法

操作系统基础26-多级反馈队列调度算法

2020-12-02 01:54·重学IT的老猫

通常在使用多级队列调度算法时,进程进入系统时被永久地分配到某个队列。例如,如果前台和后台进程分别具有单独队列,那么进程并不从一个队列移到另一个队列,这是因为进程不会改变前台或后台的性质。这种设置的优点是调度开销低,缺点是不够灵活。

相反,多级反馈队列(multievel feedback queue)调度算法允许进程在队列之间迁移。这种想法是,根据不同CPU执行的特点来区分进程。如果进程使用过多的CPU时间,那么它会被移到更低的优先级队列。这种方案将I/O密集型和交互进程放在更高优先级队列上。 此外,在较低优先级队列中等待过长的进程会被移到更高优先级队列。这种形式的优化可阻止饥饿的发生。

操作系统基础26-多级反馈队列调度算法

多级反馈队列

例如,一个多级反馈队列的调度程序有三个队列,从02(如上图)。调度程序首先执行队列0内的所有进程。只有当队列0为空时,它才能执行队列1内的进程。类似地,只有队列01都为空时,队列2的进程才能执行。到达队列1的进程会抢占队列2的进程。同样,到达队列0的进程会抢占队列1的进程。

每个进程在进入就绪队列后,就被添加到队列 0 内。队列 0 内的每个进程都有 8ms 的时间片。如果一个进程不能在这一时间片内完成,那么它就被移到队列1的尾部。如果队列0为空,队列 1 头部的进程会得到一个16ms 的时间片。如果它不能完成,那么将被抢占,并添加到队列2。只有当队列 0 和 1 为空时,队列 2 内的进程才可根据FCFS来运行。
这种调度算法将给那些 CPU 执行不超过 8ms 的进程最高优先级。这类进程可以很快得到 CPU,完成 CPU 执行,并且处理下个 I/O 执行。
所需超过 8ms 但不超过 24ms 的进程也会很快得以服务,但是它们的优先级要低一点。长进程会自动沉入队列2,队列01不用的CPU周期按 FCFS 顺序来服务。

算法思想: 对其他调度算法的折中权衡。

算法规则:

a.设置多级就绪队列,各级队列优先级从高到低,时间片从小到大。

b. 新进程到达时先进入第1级队列,按FCFS原则排队等待被分配时间片,若用完时间片进程还未结束,则进程进入下一级队列队尾。如果此时已经是在最下级的队列,则重新放回该队列队尾。

c. 只有第k级队列为空时,才会为k+1级队头的进程分配时间片

用于作业/进程调度: 用于进程调度

是否可抢占? 抢占式算法

优缺点: 对各类型进程相对公平(FCFS的优点);每个新到达的进程都可以很快就得到响应(RR优点);短进程只用较少的时间就可完成(SPF优点);不必实现估计进程的运行时间;可灵活地调整对各类进程的偏好程度,比如CPU密集型进程、I/O密集型进程(拓展:可以将因I/O而阻塞的进程重新放回原队列,这样I/O型进程就可以保持较高优先)

是否会导致饥饿:

通常,多级反馈队列调度程序可由下列参数来定义:

  1. 队列数量。
  2. 每个队列的调度算法。
  3. 用以确定何时升级到更高优先级队列的方法。
  4. 用以确定何时降级到更低优先级队列的方法。
  5. 用以确定进程在需要服务时将会进入哪个队列的方法。

多级反馈队列调度程序的定义使其成为最通用的CPU调度算法。通过配置,它能适应所设计的特定系统。但是,由于需要一些方法来选择参数以定义最佳的调度程序,所以它也是最复杂的算法。

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