操作系统时间片轮转调度算法

蔚落 2022-08-04 04:28 303阅读 0赞

**时间片轮转法（RR）**

算法描述：用于分时系统中的进程调度。每次调度时，总是选择就绪队列的队首进程，让其在CPU上运行一个系统预先设置好的时间片。一个时间片内没有完成运行的进程，返回到绪队列末尾重新排队，等待下一次调度。

【例】进程A、B、C、D需要运行的时间分别为20ms、10 ms、15 ms、5 ms，均在0时刻到达。到达的先后次序为A、B、C、D。如果时间片分别为1 ms和5ms，计算各个进程的带权周转时间和平均带权周转时间。

**分析**  在掌握了时间片轮转法概念的基础上，我们可以用一个执行时间图来形象地表示作进程的执行情况，帮助我们理解此题。具体如下：

![Center][]

根据执行时间图就可以计算各个进程的带权周转时间和平均带权周转时间了。这里要注意的是，要记住带权周转时间和平均带权周转时间的算术公式：

带权周转时间W，即：

W = T/R

其中T为周转时间，R为实际运行时间。

平均带权周转时间为：

![Center 1][]

**解：**采用时间片轮转法进行调度，算法的性能指标如下：

<table> 
 <tbody> 
 <tr> 
 <td> 到达时间 </td> 
 <td> 进 程 名 </td> 
 <td> 到达时间 </td> 
 <td> 运行时间 </td> 
 <td> 开始时间 </td> 
 <td> 完成时间 </td> 
 <td> 周转时间 </td> 
 <td> 带权 周转时间 </td> 
 </tr> 
 <tr> 
 <td> 时间片=1 </td> 
 <td> A </td> 
 <td> 0 </td> 
 <td> 20 </td> 
 <td> 0 </td> 
 <td> 50 </td> 
 <td> 50 </td> 
 <td> 2.5 </td> 
 </tr> 
 <tr> 
 <td> B </td> 
 <td> 0 </td> 
 <td> 10 </td> 
 <td> 1 </td> 
 <td> 34 </td> 
 <td> 34 </td> 
 <td> 3.4 </td> 
 </tr> 
 <tr> 
 <td> C </td> 
 <td> 0 </td> 
 <td> 15 </td> 
 <td> 2 </td> 
 <td> 45 </td> 
 <td> 45 </td> 
 <td> 3.0 </td> 
 </tr> 
 <tr> 
 <td> D </td> 
 <td> 0 </td> 
 <td> 5 </td> 
 <td> 3 </td> 
 <td> 20 </td> 
 <td> 20 </td> 
 <td> 4.0 </td> 
 </tr> 
 <tr> 
 <td colspan="7"> 平均周转时间=37.25&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 平均带权周转时间=3.225 </td> 
 </tr> 
 <tr> 
 <td> 时间片=5 </td> 
 <td> A </td> 
 <td> 0 </td> 
 <td> 20 </td> 
 <td> 0 </td> 
 <td> 50 </td> 
 <td> 50 </td> 
 <td> 2.5 </td> 
 </tr> 
 <tr> 
 <td> B </td> 
 <td> 0 </td> 
 <td> 10 </td> 
 <td> 5 </td> 
 <td> 30 </td> 
 <td> 30 </td> 
 <td> 3.0 </td> 
 </tr> 
 <tr> 
 <td> C </td> 
 <td> 0 </td> 
 <td> 15 </td> 
 <td> 10 </td> 
 <td> 45 </td> 
 <td> 45 </td> 
 <td> 3.0 </td> 
 </tr> 
 <tr> 
 <td> D </td> 
 <td> 0 </td> 
 <td> 5 </td> 
 <td> 15 </td> 
 <td> 20 </td> 
 <td> 20 </td> 
 <td> 4.0 </td> 
 </tr> 
 <tr> 
 <td colspan="7"> 平均周转时间=36.25&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 平均带权周转时间=3.125 </td> 
 </tr> 
 </tbody> 
</table>

感兴趣的同学还可以根据时间片从1~10的变化，多计算几次，并分析每次计算得到的平均周转时间，做一条平均周转时间随时间片变化的曲线，来体会时间片的变化对平均周转时间的影响，并分析原因。

[Center]: /images/20220731/25d0da6bf10c4f99bc37282c037066c5.png
[Center 1]: /images/20220731/e87d611f99d94a35b2ec419688c960f1.png