时间片轮转（RR）调度算法详解
时间片轮转（RR）调度算法详解
时间片轮转（RR）调度算法是专门为分时系统设计的，它通过将CPU时间划分为固定长度的时间片，并采用循环队列的方式对就绪进程进行调度，从而实现多个进程的并发执行。本文将详细介绍RR调度算法的工作原理、实现机制以及其性能特点。
时间片轮转（RR）调度算法是专门为分时系统设计的。它类似于FCFS调度，但是增加了抢占以切换进程。该算法中，将一个较小时间单元定义为时间量或时间片。时间片的大小通常为10~100ms。就绪队列作为循环队列。CPU调度程序循环整个就绪队列，为每个进程分配不超过一个时间片的CPU。
为了实现RR调度，我们再次将就绪队列视为进程的FIFO队列。新进程添加到就绪队列的尾部。CPU调度程序从就绪队列中选择第一个进程，将定时器设置在一个时间片后中断，最后分派这个进程。
接下来，有两种情况可能发生。进程可能只需少于时间片的CPU执行。对于这种情况，进程本身会自动释放CPU。调度程序接着处理就绪队列的下一个进程。否则，如果当前运行进程的CPU执行大于一个时间片，那么定时器会中断，进而中断操作系统。然后，进行上下文切换，再将进程加到就绪队列的尾部，接着CPU调度程序会选择就绪队列内的下一个进程。
不过，采用RR策略的平均等待时间通常较长。假设有如下一组进程，它们在时间0到达，其CPU执行以ms计：
如果使用4ms的时间片，那么P1会执行最初的4ms。由于它还需要20ms，所以在第一个时间片之后它会被抢占，而CPU就交给队列中的下一个进程。由于P2不需要4ms，所以在其时间片用完之前就会退出。CPU接着交给下一个进程，即进程P3。在每个进程都得到了一个时间片之后，CPU又交给了进程P1以便继续执行。因此，RR调度结果如下：
现在，我们计算这个调度的平均等待时间。P1等待10-4=6ms，P2等待4ms，而P3等待7ms。因此，平均等待时间为17/3=5.66ms。
在RR调度算法中，没有进程被连续分配超过一个时间片的CPU（除非它是唯一可运行的进程）。如果进程的CPU执行超过一个时间片，那么该进程会被抢占，并被放回到就绪队列。因此，RR调度算法是抢占的。
如果就绪队列有n个进程，并且时间片为q，那么每个进程会得到1/n的CPU时间，而且每次分得的时间不超过q个时间单元。每个进程等待获得下一个CPU时间片的时间不会超过(n-1)q个时间单元。例如，如果有5个进程，并且时间片为20ms，那么每个进程每100ms会得到不超过20ms的时间。
RR算法的性能很大程度取决于时间片的大小。在一种极端情况下，如果时间片很大，那么RR算法与FCFS算法一样。相反，如果时间片很小（如1ms），那么RR算法可以导致大量的上下文切换。
例如，假设我们只有一个需要10个时间单元的进程。如果时间片为12个时间单元，那么进程在一个时间片不到就能完成，而且没有额外开销。如果时间片为6个时间单元，那么进程需要2个时间片，并且还有一个上下文切换。如果时间片为1个时间单元，那么就会有9个上下文切换，相应地使进程执行更慢（图1）。
因此，我们希望时间片远大于上下文切换时间。如果上下文切换时间约为时间片的10%，那么约10%的CPU时间会浪费在上下文切换上。在实践中，大多数现代操作系统的时间片为10~100ms，上下文切换的时间一般少于10ms；因此，上下文切换的时间仅占时间片的一小部分。
周转时间也依赖于时间片大小。正如从图2中所看到的，随着时间片大小的增加，一组进程的平均周转时间不一定会改善。一般情况下，如果大多数进程能在一个时间片内完成，那么平均周转时间会改善。
例如，假设有三个进程，都需要10个时间单元。如果时间片为1个时间单元，那么平均周转时间为29；如果时间片为10，那么平均周转时间会降为20；如果再考虑上下文切换时间，那么平均周转时间对于较小时间片会增加，这是因为需要更多的上下文切换。
尽管时间片应该比上下文切换时间要大，但也不能太大。如果时间片太大，那么RR调度就演变成了FCFS调度。根据经验，80%的CPU执行应该小于时间片。