OS 基础教程

进程管理

同步

死锁

内存管理

文件管理

original icon
版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://www.knowledgedict.com/tutorial/os-preemptive-priority-scheduling.html

抢先式优先级调度


在抢占式优先级调度中,在进程到达就绪队列时,其优先级与就绪队列中存在的其他进程的优先级以及CPU在该点执行的优先级进行比较。 在所有可用的进程中具有最高优先级的那个将被赋予CPU。

抢先优先级调度和非抢占优先级调度之间的区别在于,在抢先优先级调度中,正在执行的作业可以在更高优先级作业到达时停止。

一旦所有作业在就绪队列中可用,算法将表现为非抢占式优先级调度,这意味着计划的作业将运行直至完成并且不会执行抢占。

示例

有7个过程P1,P2,P3,P4,P5,P6和P7给出。 下表列出了他们各自的优先级,到达时间和爆发时间。

进程Id 优先级 到达时间 爆发时间
1 2(L) 0 1
2 6 1 7
3 3 2 3
4 5 3 6
5 4 4 5
6 10(H) 5 6
7 9 15 8

甘特图制备

在时间0,P1以1单位的爆发时间和优先级2到达。由于没有其他进程可用,因此这将被安排到下一个作业到达或完成(以较小者为准)。

在时间1,P2到达。 P1已经完成执行,此时没有其他进程可用,因此操作系统必须安排它,而不管分配给它的优先级如何。

下一个进程P3在时间单元2到达,P3的优先级高于P2。 因此,P2的执行将被停止,并且P3将被安排在CPU上。

在执行P3期间,还有三个进程P4,P5和P6可用。 因为,所有这三个优先级都低于执行过程,因此PS无法抢占进程。 P3将完成其执行,然后P5将按照可用进程中的优先级排列。

同时执行P5,所有进程都可以在就绪队列中使用。 此时,算法将开始表现为非抢占式优先级调度。 因此,现在,一旦所有进程在就绪队列中都可用,操作系统就会将进程的优先级最高并执行该进程直到完成。 在这种情况下,P4将按计划执行,直至完成。

由于P4已完成,因此就绪队列中具有最高优先级的其他进程为P2。 因此P2将在下一个时间安排。

P2被给予CPU直到完成。 由于其剩余的爆发时间为6个单位,因此P7将在此之后安排。

唯一剩下的进程是P6,其优先级最低,操作系统除非执行它,否则别无选择。 这将在最后执行。

每个过程的完成时间在GANTT图表的帮助下确定。 周转时间和等待时间可以通过以下公式计算。

周转时间 = 完成时间 - 到达时间
等待时间 = 转身时间 - 爆发时间
进程Id 优先级 到达时间 爆发时间 完成时间 周转时间 等待时间
1 2 0 1 1 1 0
2 6 1 7 22 21 14
3 3 2 3 5 3 0
4 5 3 6 16 13 7
5 4 4 5 10 6 1
6 10 5 15 45 40 25
7 9 6 8 30 24 16

平均等待时间=(0 + 14 + 0 + 7 + 1 + 25 + 16)/ 7 = 63/7 = 9个单位