操作系统 - 调度算法
-
简述
进程调度器根据特定的调度算法调度不同的进程分配给 CPU。我们将在本章讨论六种流行的进程调度算法 -- 先到先服务 (FCFS) 调度
- 最短作业下一个 (SJN) 调度
- 优先调度
- 最短剩余时间
- 循环（RR）调度
- 多级队列调度
这些算法要么non-preemptive or preemptive. 非抢占式算法被设计为一旦进程进入运行状态，直到它完成分配的时间才能被抢占，而抢占式调度是基于优先级的，调度器可以在高优先级的任何时候抢占低优先级正在运行的进程进程进入就绪状态。 -
先到先得 (FCFS)
- 作业按照先到先得的原则执行。
- 它是一种非抢占式、抢占式调度算法。
- 易于理解和实施。
- 它的实现是基于先进先出队列的。
- 性能差，因为平均等待时间很长。
Wait time每个过程如下 -过程 等待时间：服务时间 - 到达时间 P0 0 - 0 = 0 P1 5 - 1 = 4 P2 8 - 2 = 6 P3 16 - 3 = 13 平均等待时间：(0+4+6+13) / 4 = 5.75 -
下一个最短作业 (SJN)
-
这也被称为shortest job first, 或 SJF
-
这是一种非抢占式、抢占式调度算法。
-
减少等待时间的最佳方法。
-
易于在预先知道所需 CPU 时间的批处理系统中实现。
-
无法在所需 CPU 时间未知的交互式系统中实现。
-
处理者应该提前知道处理需要多少时间。
给定：进程表及其到达时间、执行时间过程 到达时间 执行时间处理时间 服务时间 P0 0 5 0 P1 1 3 5 P2 2 8 14 P3 3 6 8 
Waiting time每个过程如下 -过程 等待的时间 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 
Waiting time每个过程如下 -过程 等待的时间 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 是抢占式进程调度算法。
-
每个进程都有一个固定的执行时间，称为quantum.
-
一旦一个进程在给定的时间段内执行，它就会被抢占，而其他进程在给定的时间段内执行。
-
上下文切换用于保存被抢占进程的状态。
Wait time每个过程如下 -过程 等待时间：服务时间 - 到达时间 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。