操作系统调度算法

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

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

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

先到先得 (FCFS)

• 作业以先到先得的方式执行。
• 它是一种非抢占式、抢占式调度算法。
• 易于理解和实施。
• 它的实现是基于先进先出队列的。
• 性能不佳，因为平均等待时间很长。

各进程的等待时间如下 −

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

最短作业优先 (SJN)

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

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

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

• 易于在预先知道所需 CPU 时间的 Batch 系统中实施。

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

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

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

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

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

基于优先级的调度

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

• 每个进程都被分配了一个优先级。 优先级最高的进程先执行，以此类推。

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

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

给定：进程表，以及它们的到达时间、执行时间和优先级。 这里我们认为 1 是最低优先级。

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

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

最短剩余时间

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

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

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

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

循环调度

• 循环调度是抢占式进程调度算法。

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

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

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

各进程的等待时间如下 −

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

多级队列调度

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

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

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