OS 基础教程

进程管理

同步

死锁

内存管理

文件管理

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

循环调度算法示例


在以下示例中,有六个进程分别命名为P1,P2,P3,P4,P5和P6。 他们的到达时间和爆发时间如下表所示。 系统的时间量是4个单位。

进程ID 到达时间 突发时间
1 0 5
2 1 6
3 2 3
4 3 1
5 4 5
6 6 4

根据算法,我们必须保持就绪队列和甘特图。 两个数据结构的结构在每次调度后都会改变。

就绪队列:
最初,在时间0,过程P1到达,其将被安排为时间片4单位。 因此,在就绪队列中,在CPU突发时间5个单元开始时将只有一个进程P1。

P1
5

甘特图
P1将首先执行4个单位。

就绪队列

同时执行P1,另外四个进程P2,P3,P4和P5到达就绪队列。 P1还没有完成,它需要另外1个单位时间,因此它也将被添加回就绪队列。

P2 P3 P4 P5 P1
6 3 1 5 1

甘特图

在P1之后,P2将在甘特图中显示的4个单位时间内执行。

就绪队列

在执行P2期间,再有一个进程P6进入就绪队列。 由于P2尚未完成,因此P2也将被添加回就绪队列,剩余的突发时间为2个单位。

P3 P4 P5 P1 P6 P2
3 1 5 1 4 2

甘特图
在P1和P2之后,由于其CPU突发时间仅为3秒,因此P3将执行3个单位时间。

就绪队列

由于P3已经完成,因此它将被终止并且不会被添加到就绪队列中。 下一个进程将执行P4。

P4 P5 P1 P6 P2
1 5 1 4 2

甘特图

之后,P1,P2和P3,P4将被执行。 它的爆发时间只有1个单位,与时间量相比更小,因此它会完成。

就绪队列

就绪队列中的下一个进程是P5,有5个单位的突发时间。 由于P4已完成,因此它不会被添加回队列。

P5 P1 P6 P2
5 1 4 2

甘特图
P5将在整个时间片执行,因为它需要5个单位的突发时间,这比时间片更高。

就绪队列
P5尚未完成; 它将被添加回队列中,其余的突发时间为1个单位。

P1 P6 P2 P5
1 4 2 1

甘特图
进程P1将在下一个回合完成执行。 由于它只需要1单位的突发时间,因此它将被完成。

就绪队列
P1已完成并且不会被添加回就绪队列。 接下来的处理P6仅需要4个单位的突发时间,接下来将被执行。

P6 P2 P5
4 2 1

甘特图
P6将执行4个单位时间直至完成。

就绪队列
由于P6已完成,因此不会再次添加到队列中。 就绪队列中只有两个进程。 下一个进程P2只需要2个单位的时间。

P2 P5
2 1

甘特图

P2将再次执行,因为它只需要2个单位时间,因此这将会完成。

就绪队列

现在,队列中唯一可用的进程是P5,它需要1个单位的突发时间。 由于时间片是4个单位,因此它会在下一次突发中完成。

P5
1

甘特图
P5将被执行直至完成。

完成时间,周转时间和等待时间将按下表所示计算。

周转时间 = 完成时间 - 到达时间
等待时间 = 周转时间 - 爆发时间
进程ID 到达时间 爆发时间 完成时间 周转时间 等待时间
1 0 5 17 17 12
2 1 6 23 22 16
3 2 3 11 9 6
4 3 1 12 9 8
5 4 5 24 20 15
6 6 4 21 15 11

平均等待时间=(12 + 16 + 6 + 8 + 15 + 11)/ 6 = 76/6个单位