我终于看懂了什么是RR调度

作者 | 风中纸鹞

出品 | 脚本之家（ID：jb51net）

前不久,新来的1个同事在技术沙龙中给我们分享了Celery如何在实际项目中应用的场景。而在这个过程,突然觉得有必要写一篇关于RR调度的文章。

虽然有不少人说RR调度算法是个非常简单的调度算法,但是却没找到几篇值的推荐的,只好自己亲自动手了。

1个简单的例子

在Javascript中,对于定时器常常有类似如下的代码:

1. function say(){

2. console.log('Hello...');

3. }

5. setInterval(say,5000);

上述代码每隔5秒中就会执行一次,并一直循环下去。而这里要介绍的RR算法,其过程与之类似。

什么是RR算法

RR算法中的RR是round robin的缩写,它是1种基于时间片的调度算法,常用于分时系统中。
而所谓的时间片可以将其理解为将时间切分成多个片段后的其中一片,简单的说就是1个度量单位。
而在计算机操作系统的CPU调度过程中,1个算法的好坏主要从如下几个方面进行评估:

• 资源利用率是否高效

• 进程获取的CPU时间是否合理

• 系统资源是否平衡

而RR算法主要是基于第2个方面的目标提出的,它采用了非常公平的处理机分配方法,它让需要运行的每个进程每次仅运行1个时间片。换句话说,如果有n个需要执行的进程,则每个进程每次大约可获得1/n的CPU执行时间。

RR基本原理

在RR算法中,系统根据进程提交的先后顺序进行排列,使用1个队列的数据结构进行存储(而这个队列常常称为就绪队列),并为其设置每隔一定时间间隔(如10ms)即产生1次中断,激活操作系统中的进程调度程序,从而完成一次调度,之后将CPU分配给队首进程,令其执行。
而当该进程的时间片耗尽或运行完毕时,系统再次将CPU分配给新的队首进程(或新到达的紧迫进程)。由此,从而保证队列中的所有进程在1个确定的时间段内,都能够获得1次CPU执行。

RR算法的关键

在RR算法中,系统资源利用效率是否高效的关键在于时间片大小的选择。对于调度过程中进程的切换问题,主要存在如下2种策略:

1、如果在1个时间片尚未用完的情况下,正在运行的进程已经完成,此时就需要立即激活调度程序,将它从队列中删除,接着调度就绪队列中队首的进程运行,并启动1个新的时间片2、如果1个时间片已经用完时,但是进程仍尚未运行完毕,此时调度程序需要将它送往就绪队列的末尾

对于时间较短的作业,适合选择很小的时间片。但是时间片小,意味着会频繁地执行进程调度和进程上下文的切换,从而会增加系统的开销。反之,若时间片选择得太长,从而确保每个进程都能在1个时间片内完成,但是不利于短作业的运行。
因此1个较为可取的时间片大小是略大于一次典型的交互所需要的时间,使大多数交互式进程能在1个时间片内完成,从而可以获得很小的响应时间。

1个RR算法优劣例子

下面我们通过1个实例,来说明时间片对平均周转时间的影响。对于不同的场景,由于直接使用周转时间很难评估1个算法的好坏,因此使用平均周转时间更为合适些。
首先给出5个进程的到达时间及服务时间的信息,如下图所示:

从上表可以轻松的看到,进程A在时间0时刻到达,而要运行的时间为4。而进程C在时间2时刻到达,要运行的时间也为4。

接着我们希望根据给出了时间片分别为q=1和q=4时的计算其平均周转时间。

首先是q=1时,如下表所示:

由于时间片q=1,因此在时间0时系统让进程A执行,而在时间1时系统进行中断,此时进程A仍未完成任务,只能等待下一次的调度,因此进程B到达,于是系统让进程B运行1个时间片的任务。
于是,我们可以得到各个进程的完成时间为:

A = 1 + 4 + 1 + 4 + 1 + 3 + 1 = 15
B = 1 + 1 + 3 + 1 + 1 + 3 + 1 + 1 = 12
C = 3 + 2 + 3 + 2 + 3 + 1 + 2 = 16
D = 3 + 2 + 4 = 9
E = 4 + 1 + 5 + 4 + 3 = 17

对于进程A而言,其到达时间为0,因此第1次服务花费的时间为1,而到第2次服务时间间隔了4个进程,因此到第2次服务结束间隔了5个时间片。同理,第3次服务的时候也花费了5个时间片,此时进程D服务时间达到2次,从而退出调度。而到第4次时只花费了4个时间片,因此其总完成时间为1+5+5+4=15。

对于进程B而言,其到达时间为1,因此第1次服务花费的时间为2,而到第2次服务时间结束花费了5个时间片。同理,第3次服务的时候也花费了5个时间片,此时进程D服务时间达到2次,从而退出调度,但是对进程B并不造成影响,因此其总完成时间为2+5+5=12。

对于进程C而言,其第1次服务时间花费了3个时间片,而第2次时间片时花费时间片为5,而第3次服务的时间仍为5个时间片,此时进程D退出调度,最后1次服务时由于有2个进程在其前面,加上自身服务1个时间片,因此总完成时间为3+5+5+2+1=16。

同理,求得进程D的总完成时间为9,而进程E的总完成时间为17。

而周转时间是指从作业被提交到系统开始,到作业完成为止的这段时间间隔,又称作业周转时间。对于上表而言有:

A = 15 - 0 = 15
B = 12 - 1 = 11
C = 16 - 2 = 14
D = 9 - 3 = 6
E = 17 - 4 = 13

我们直接用总完成时间减去到达时间即可得到对应的周转时间。
接着是q=4时的情况:

由于此时时间片q=4,因此各进程的总完成时间为:

A = 4
B = 4 + 3 = 7
C = 4 + 3 + 4 = 11
D = 4 + 3 + 4 + 2 = 13
E = 4 + 3 + 4 + 2 + 4 = 17

由于进程B的服务时间只有3,小于时间片的长度,因此调度会提前中断,从而进入下1个进程的调度。
而对应各进程的周转时间为:

A = 4
B = 7 - 1 = 6
C = 11 - 2 = 9
D = 13 - 3 = 10
E = 17 - 4 = 13

从平均周转结果可以看到,RR调度法中q=4时系统利用率要比q=1时要好。

参考书籍:

《计算机操作系统(第4版)》

本文作者：风中纸鹞,1个多年滚打于Web开发的研发工程师。熟悉PHP、Java、C++等编程语言,以编程作为乐趣。