• 操作系统视频教程

操作系统调度算法

进程调度器根据特定的调度算法调度不同的进程分配给CPU。我们将在本章中讨论六种流行的进程调度算法 -

  • 先到先服务 (FCFS) 调度
  • 最短作业下一个 (SJN) 调度
  • 优先级调度
  • 最短剩余时间
  • 循环(RR)调度
  • 多级队列调度

这些算法要么是非抢占式的，要么是抢占式的。非抢占式算法的设计使得一旦进程进入运行状态，它就不能被抢占，直到它完成分配的时间，而抢占式调度基于优先级，调度程序可以在高优先级时随时抢占低优先级正在运行的进程。进程进入就绪状态。

先到先得 (FCFS)

  • 作业按照先到先得的原则执行。
  • 它是一种非抢占式、抢占式的调度算法。
  • 易于理解和实施。
  • 它的实现是基于FIFO队列的。
  • 由于平均等待时间较长，因此性能较差。
先来先服务调度算法

每个进程的等待时间如下 -

过程 等待时间：服务时间-到达时间
P0 0 - 0 = 0
P1 5 - 1 = 4
P2 8 - 2 = 6
P3 16 - 3 = 13

平均等待时间：(0+4+6+13) / 4 = 5.75

接下来最短的工作 (SJN)

  • 这也称为最短作业优先，或 SJF

  • 这是一种非抢占式、抢占式的调度算法。

  • 减少等待时间的最佳方法。

  • 易于在预先知道所需 CPU 时间的批处理系统中实现。

  • 无法在所需 CPU 时间未知的交互式系统中实现。

  • 处理者应该提前知道处理需要多长时间。

给定：进程表及其到达时间、执行时间

过程 到达时间 执行时间处理时间 服务时间
P0 0 5 0
P1 1 3 5
P2 2 8 14
P3 3 6 8
最短作业优先调度算法

每个进程的等待时间如下 -

过程 等待的时间
P0 0 - 0 = 0
P1 5 - 1 = 4
P2 14 - 2 = 12
P3 8 - 3 = 5

平均等待时间：(0 + 4 + 12 + 5)/4 = 21 / 4 = 5.25

基于优先级的调度

  • 优先级调度是一种非抢占式算法，也是批处理系统中最常见的调度算法之一。

  • 每个进程都被分配一个优先级。具有最高优先级的进程将首先执行，依此类推。

  • 具有相同优先级的进程按照先到先得的原则执行。

  • 可以根据内存需求、时间需求或任何其他资源需求来决定优先级。

给定：进程表及其到达时间、执行时间和优先级。这里我们考虑 1 是最低优先级。

过程 到达时间 执行时间处理时间 优先事项 服务时间
P0 0 5 1 0
P1 1 3 2 11
P2 2 8 1 14
P3 3 6 3 5
优先级调度算法

每个进程的等待时间如下 -

过程 等待的时间
P0 0 - 0 = 0
P1 11 - 1 = 10
P2 14 - 2 = 12
P3 5 - 3 = 2

平均等待时间：(0 + 10 + 12 + 2)/4 = 24 / 4 = 6

最短剩余时间

  • 最短剩余时间 (SRT) 是 SJN 算法的抢占式版本。

  • 处理器被分配给最接近完成的作业，但它可以被完成时间更短的较新的就绪作业抢占。

  • 无法在所需 CPU 时间未知的交互式系统中实现。

  • 它常用于短作业需要优先考虑的批处理环境中。

循环调度

  • Round Robin 是抢占式进程调度算法。

  • 每个进程都有一个固定的执行时间，称为量子。

  • 一旦一个进程在给定的时间段内执行，它就会被抢占，并且其他进程在给定的时间段内执行。

  • 上下文切换用于保存被抢占进程的状态。

循环调度算法

每个进程的等待时间如下 -

过程 等待时间：服务时间-到达时间
P0 (0 - 0) + (12 - 3) = 9
P1 (3 - 1) = 2
P2 (6 - 2) + (14 - 9) + (20 - 17) = 12
P3 (9 - 3) + (17 - 12) = 11

平均等待时间：(9+2+12+11) / 4 = 8.5

多级队列调度

多级队列并不是一种独立的调度算法。他们利用其他现有算法来对具有共同特征的作业进行分组和调度。

  • 为具有共同特征的进程维护多个队列。
  • 每个队列可以有自己的调度算法。
  • 优先级被分配给每个队列。

例如，CPU 密集型作业可以安排在一个队列中，而所有 I/O 密集型作业则安排在另一队列中。然后，进程调度程序从每个队列中交替选择作业，并根据分配给队列的算法将它们分配给 CPU。