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

什么是优先级调度？

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

具有较高优先级的进程应首先执行，而具有相同优先级的作业则按轮转或先来先服务（FCFS）进行。优先级取决于内存需求、时间需求等。

优先级调度的类型

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

抢占式调度

在抢占式调度中，任务通常会分配其优先级。有时，即使较低优先级的任务仍在运行，也必须在较低优先级任务之前运行具有较高优先级的任务。较低优先级的任务会暂停一段时间，并在较高优先级的任务完成执行后恢复。

非抢占式调度

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

优先级调度的特点

一种根据优先级调度进程的 CPU 算法。
它用于操作系统执行批处理作业。
如果两个具有相同优先级的作业处于就绪状态，则它按先来先服务原则工作。
在优先级调度中，为每个进程分配一个数字，表示其优先级级别。
数字越小，优先级越高。
在此类调度算法中，如果一个新进程到达，并且其优先级高于当前正在运行的进程，则当前正在运行的进程将被抢占。

优先级调度示例

考虑以下五个进程 P1 到 P5。每个进程都有其唯一的优先级、突发时间（burst time）和到达时间。

过程	优先级	执行时间	到达时间
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）高于 P2 的优先级（2）。P2 被抢占，P3 开始执行。

过程	优先级	执行时间	到达时间
P1	1	4	0
P2	2	3 个待处理中 1 个	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	3 个待处理中 1 个	0
P3	1	7 个待处理中 2 个	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	3 个待处理中 1 个	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 时间，则低优先级进程可能会饿死，并被无限期推迟。