在抢占式优先级调度中,在进程到达就绪队列时,其优先级与就绪队列中存在的其他进程的优先级以及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个单位