时间片轮转调度算法的计算

在分时系统中，最简单最常用的就是基于时间片轮转调度算法，时间片轮转调度算法是非常公平的处理机分配方式，让就绪队列的每个进程每次仅运行一个时间片。

1.时间片轮转调度算法的基本原理

   在时间片轮转调度算法中，系统根据先来先服务的原则，将所有的就绪进程排成一个就绪队列，并且每隔一段时间产生一次中断，激活系统中的进程调度程序，完成一次处理机调度，把处理机分配给就绪队列队首进程，让其执行指令。当时间片结束或进程执行结束，系统再次将cpu分配给队首进程。

2.进程切换时机

      时间片尚未结束，进程已经执行结束，立即激活调度程序，将其从就绪队列中删除，在调度就绪队列的队首进程执行，开启新的时间片（计数器置0）。

    时间片已经结束，进程尚未结束，立即激活进程调度程序，未执行完的进程放到就绪队列的队尾。

3.时间片大小的确定

   在轮转调度算法中时间片的大小对系统的性能有很大的影响。若时间片很小，将有利于短作业，其能够在这个时间片内完成。时间片过小意味着会进行频繁的进程切换，这将增大系统的开销。若时间片选择太长，时间片轮转调度算法将退化为先来先服务的进程调度算法。

下面通过一个例题来解释下如何来计算RR调度算法中的完成时间、周转时间、带权周转时间

进程名

A

B

C

D

平均

到达时间

0

1

2

3

服务时间

30

5

25

10

RR

Q=5

完成时间

 70

 10

 65

 35

周转时间

 70

 9

 63

 32

带权周转时间

 2.3

 1.8

 2.55

 3.2

RR

Q=10

完成时间

 65

 15

 70

 35

周转时间

 65

 14

 68

 32

带权周转时间

 2.2

 2.8

 2.75

 3.2

对于时间片为Q=5我们画一个坐标轴来计算他们的完成时间，那么我们从这4个进程知道这个坐标轴的大小为30+5+25+10=70

0      5     10     15     20      25    30    35   40    45     50    55     60     65     70

     A     B     C    D        A       C     D    A      C     A     C       A          C             A

(1)因为RR首先要按照FCFS算法来一次进行调度，所以首先是ABCD，由于B的服务时间是5所以在第一个时间片就可以完成，所以在第二个时间片中只有ACD三个进程在执行，由于D服务时间为10所以在第二个时间片完成的时候D也执行完成，剩下的就剩下AC二个进程，所以一次按照这个顺序下去，便可以得到它们的完成时间。

带权周转时间=周转时间/服务时间

(2)对于时间片Q=10我们同样可以算出各进程的完成时间

0    10    15     25    35   45   55   65    70

    A     B      C       D     A     C     A     C