优先级调度算法：抢占式、非抢占式示例
纳撒尼尔·布鲁克斯
什么是优先级调度？
优先调度 是一种基于优先级的进程调度方法。在此算法中，调度程序根据优先级选择要执行的任务。
优先级较高的进程应首先执行，而优先级相同的作业则在循环或 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 到达。与优先级为 (3) 的 P1 相比，P2 的优先级更高 (2)。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） 在时间=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时，P5已完成执行，没有剩余进程。
步骤18） 让我们计算一下上述例子的平均等待时间。
等待时间 = 开始时间 - 到达时间 + 等待下一次突发的时间
P1 = o - o = o P2 =4 - o + 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 时，它将被阻塞。
- 如果新的更高优先级的进程不断进入就绪队列，那么处于等待状态的进程可能需要等待很长时间。
总结
- 优先级调度是一种基于优先级的进程调度方法。在此算法中，调度程序根据优先级选择要执行的任务。
- 在优先级抢占式调度中，任务大多按其优先级分配。
- 在优先级非抢占式调度方法中，CPU 已分配给特定进程。
- 进程根据优先级执行，因此高优先级不需要等待很长时间，从而节省时间
- 如果高优先级进程占用大量 CPU 时间，则低优先级进程可能会陷入困境，并将无限期地推迟。