优先级调度算法：抢占式、非抢占式

什么是优先级调度？

优先调度 是一种基于优先级的进程调度方法。在此算法中，调度程序根据优先级选择要执行的任务。

优先级较高的进程应首先执行，而优先级相同的作业则在循环或 FCFS 的基础上执行。 优先级取决于内存要求、时间要求等。

优先级调度的类型

优先级调度主要分为两种类型：

抢先调度

在抢占式调度中，任务大多按优先级分配。有时，在运行另一个优先级较低的任务之前运行优先级较高的任务很重要，即使优先级较低的任务仍在运行。优先级较低的任务会保留一段时间，并在优先级较高的任务完成执行后恢复。

非抢占式调度

在这种调度方法中，CPU 已被分配给特定进程。占用 CPU 的进程会通过切换上下文或终止来释放 CPU。它是唯一一种可以用于各种硬件平台的调度方法，因为它不像抢占式调度那样需要特殊的硬件（例如定时器）。

优先级调度的特点

• 根据优先级调度进程的 CPU 算法。
• 它用于 Opera用于执行批处理过程的系统。
• 如果两个具有相同优先级的作业都处于 READY 状态，则它按 先来先服务 基础。
• 在优先级调度中，每个进程都会被分配一个数字来表示其优先级。
• 数字越低，优先级越高。
• 在这种调度算法中，如果一个优先级高于当前正在运行的进程的新进程到达，则当前正在运行的进程将被抢占。

优先级调度示例

考虑以下五个进程 P1 至 P5。每个进程都有其独特的优先级、运行时间和到达时间。

工艺应用	优先	爆发时间	到达时间
P1	1	4	0
P2	2	3	0
P3	1	7	6
P4	3	4	11
P5	2	2	12

步骤0） 在时间 0 时，进程 P1 和 P2 到达。P1 的优先级高于 P2。程序从进程 P1 开始执行，其执行时间为 4。

步骤1） 在时间 1 时，没有新进程到达。程序继续执行，进程为 P1。

步骤2） 在时间 2 时，没有新进程到达，因此可以继续执行 P1。P2 处于等待队列中。

步骤3） 在第 3 个时刻，没有新的进程到达，因此您可以继续执行 P1。P2 进程仍在等待队列中。

步骤4） 在时间 4 时，P1 完成执行。P2 开始执行。

步骤5） 当时间 = 5 时，没有新的进程到达，因此我们继续执行 P2。

步骤6） 在时间 6 时，程序 P3 到达。P3 的优先级 (1) 高于优先级 (2) 的程序 P2。程序 P2 被抢占，程序 P3 开始执行。

工艺应用	优先	爆发时间	到达时间
P1	1	4	0
P2	2	1 项中有 3 项待定	0
P3	1	7	6
P4	3	4	11
P5	2	2	12

步骤7） 在第 7 时刻，没有新进程到达，所以我们继续处理 P3。P2 在等待队列中。

步骤8） 当时间 = 8 时，没有新的进程到达，因此我们可以继续执行 P3。

步骤9） 当时间 = 9 时，没有新的进程到来，因此我们可以继续执行 P3。

步骤10） 时间间隔 10 时，没有新的进程到来，因此我们继续执行 P3。

步骤11） 在时间 = 11 时，P4 到达，优先级为 4。P3 的优先级更高，因此它继续执行。

工艺应用	优先	爆发时间	到达时间
P1	1	4	0
P2	2	1 项中有 3 项待定	0
P3	1	2 项中有 7 项待定	6
P4	3	4	11
P5	2	2	12

步骤12） 在时间 12 时，程序 P5 到达。由于程序 P3 的优先级更高，因此它继续执行。

步骤13） 在时间 t = 13 时，P3 执行完毕。此时就绪队列中有 P2、P4 和 P5。P2 和 P5 优先级相同。P2 的到达时间早于 P5，因此 P2 开始执行。

工艺应用	优先	爆发时间	到达时间
P1	1	4	0
P2	2	1 项中有 3 项待定	0
P3	1	7	6
P4	3	4	11
P5	2	2	12

步骤14） 在时间 14 时，P2 进程已执行完毕。P4 和 P5 处于等待状态。P5 优先级最高，开始执行。

步骤15） 在时间 = 15 时，P5 继续执行。

步骤16） 在时间 16 时，进程 P5 执行完毕。只剩下进程 P4，它开始执行。

步骤17） 时间 = 20 时，P4 已完成执行，没有剩余进程。

步骤18） 让我们来计算一下上述例子的平均等待时间。

等待时间 = 开始时间 - 到达时间 + 等待下一次突发的时间

P1 = 0 - 0 = 0
P2 = 4 - 0 + 7 = 11
P3 = 6 - 6 = 0
P4 = 16 - 11 = 5
Average Waiting time = (0 + 11 + 0 + 5 + 2)/5 = 18/5 = 3.6

优先级调度的优点

以下是使用优先级调度方法的优势/优点：

• 简单易用的日程安排方法。
• 进程按优先级执行，因此高优先级进程无需长时间等待，从而节省时间。
• 该方法提供了一种良好的机制，可以精确地定义每个过程的相对重要性。
• 适用于时间和资源需求波动的应用程序。

优先级调度的缺点

以下是优先级调度的一些缺点/不足之处：

• 如果系统最终崩溃，所有低优先级进程都会丢失。
• 如果高优先级进程占用大量 CPU 时间，则低优先级进程可能会陷入困境，并将无限期地推迟。
• 该调度算法可能会让一些低优先级的进程无限期地等待。
• 当一个进程准备运行但由于当前正在运行其他进程而必须等待 CPU 时，它将被阻塞。
• 如果新的更高优先级的进程不断进入就绪队列，那么处于等待状态的进程可能需要等待很长时间。

常见问题