操作系统基础24-轮转调度

操作系统基础24-轮转调度(RR)算法

2020-11-30 11:05·重学IT的老猫

时间片轮转(RR)调度算法是专门为分时系统设计的。它类似于FCFS调度,但是增加了抢占以切换进程。也称为时间片技术(time slicing,SL)。
该算法中,将一个较小时间单元定义为时间量时间片。时间片的大小通常为10~100ms。就绪队列作为循环队列。CPU调度程序循环整个就绪队列,为每个进程分配不超过一个时间片的CPU
为了实现RR调度,我们再次将就绪队列视为进程的FIFO 队列。新进程添加到就绪队列的尾部。CPU调度程序从就绪队列中选择第一个进程,将定时器设置在一个时间片后中断,最后分派这个进程。

有两种情况可能发生。进程可能只需少于时间片的CPU执行。对于这种情况,进程本身会自动释放CPU。调度程序接着处理就绪队列的下一个进程。否则,如果当前运行进程的CPU执行大于一个时间片,那么定时器会中断,进而中断操作系统。然后,进行上下文切换,再将进程加到就绪队列的尾部,接着CPU调度程序会选择就绪队列内的下一个进程。
不过,采用RR策略的平均等待时间通常较长。假设有如下一组进程,它们在时间0到达,其CPU 执行以ms计:

操作系统基础24-轮转调度(RR)算法

如果使用4ms的时间片,那么P1会执行最初的 4ms。由于它还需要 20ms,所以在第一个时间片之后它会被抢占,而CPU就交给队列中的下一个进程。由于P2不需要 4ms,所以在其时间片用完之前就会退出。CPU接着交给下一个进程,即进程 P3。在每个进程都得到了一个时间片之后,CPU又交给了进程 P1以便继续执行。因此,RR 调度结果如下:

操作系统基础24-轮转调度(RR)算法

现在,我们计算这个调度的平均等待时间。P1 等待 10-4 = 6msP2 等待 4ms,而 P3 等待 7ms。因此,平均等待时间为 17/3 = 5.66ms。

RR调度算法中,没有进程被连续分配超过一个时间片的CPU(除非它是唯一可运行的进程)。如果进程的CPU执行超过一个时间片,那么该进程会被抢占,并被放回到就绪队列。因此,RR调度算法是抢占的

如果就绪队列有n个进程,并且时间片为 q,那么每个进程会得到 1/nCPU时间,而且每次分得的时间不超过 q 个时间单元。每个进程等待获得下一个CPU时间片的时间不会超过 (n-1)q 个时间单元。例如,如果有5个进程,并且时间片为 20ms,那么每个进程每100ms 会得到不超过 20ms 的时间。
算法思想:公平地、轮流地为各个进程服务,让每个进程在一定时间间隔内都可以得到响应
算法规则:按照各进程到达就绪队列的顺序,轮流让各个进程执行一个时间片(如100ms)。各进程未在一个时间片内执行完,则剥夺处理机,将进程重新放到就绪队列队尾重新排队。
用于作业/进程调度:用于进程调度(只有作业放入内存建立了相应的进程后,才能被分配处理机时间片)
优缺点
  优点:公平;响应快,适用于分时操作系统。
  缺点:由于高频率的进程切换,因此有一定开销;不区分任务的紧急程度。

是否会导致饥饿:不会

RR 算法的性能很大程度取决于时间片的大小。在一种极端情况下,如果时间片很大,那么RR算法会导致变成先来先服务FCFS,时间片太小(如 1ms)会导致切换过于频繁,时间都用于切换进程。

时间片大小为2

操作系统基础24-轮转调度(RR)算法

0到5时刻

操作系统基础24-轮转调度(RR)算法

操作系统基础24-轮转调度(RR)算法

6-16时刻

时间片大小为5

操作系统基础24-轮转调度(RR)算法

-------------本文结束 感谢阅读-------------