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

什么是优先级调度?

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

优先级较高的进程应首先执行,而优先级相同的作业则在循环或 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 时间,则低优先级进程可能会陷入困境,并将无限期地推迟。

每日Guru99新闻简报

通过立即获取最新、最重要的人工智能新闻报道来开始您的一天。