操作系统Round Robin时间片轮转调度算法详解

操作系统Round Robin时间片轮转调度算法详解

引用

CSDN

1.

https://blog.csdn.net/weixin_74830736/article/details/142930894

Round Robin调度算法是操作系统中一种重要的进程调度算法，通过为每个进程分配固定时间片的方式实现公平调度。本文将详细介绍该算法的基本原理，并通过一个具体实例帮助读者深入理解其工作流程。

Round Robin算法简介

1. 每个进程被分配一个时间片，周期性产生时钟中断，当发生中断的时候将该进程置于就绪队列末尾，并基于先来先服务（FCFS）选择一个进程运行。
2. 如果进程在时间片内阻塞或结束，则立即切换。

下面通过一个具体例题来说明Round Robin调度算法的工作流程：

如上图所示，进程A、B、C、D、E的产生时间分别为0、2、4、6、8，服务时间分别为3、6、4、5、2。这里时间片以1为例。

• 当t=0时，进程A产生，就绪队列为A，则在1个时间片的时间以内运行进程A。
• 当t=1时，进程A的执行时间结束（1个时间片），然而进程A并没有结束，故将进程A置于就绪队列末尾，此时就绪队列为A，则在1个时间片的时间以内运行进程A。
• 当t=2时，进程B产生，基于FCFS算法将进程B置于就绪队列末尾，此时进程A的执行时间结束，然而进程A并没有结束，故将进程A置于就绪队列末尾，此时就绪队列为AB，则在1个时间片的时间以内运行进程B。
• 当t=3时，进程B的执行时间结束，然而进程B并没有结束，故将进程B置于就绪队列末尾，此时就绪队列为BA，则在1个时间片的时间以内运行进程A。
• 当t=4时，进程C产生，基于FCFS算法将进程C置于就绪队列末尾，同时进程A的执行时间结束，进程A的服务时长为3，故进程A结束。此时就绪队列为CB，则在1个时间片的时间以内运行进程B。
• 当t=5时，将进程B置于就绪队列末尾，此时就绪队列为BC，执行进程C。（由于步骤重复，不过多重复描述）
• 当t=6时，进程D产生，将D置于就绪队列末尾，此时再将C置于就绪队列末尾。就绪队列为CDB，执行进程B
• 当t=7时，将进程B置于就绪队列末尾，此时就绪队列为BCD，执行进程D。
• 当t=8时，进程E产生，将E置于就绪队列末尾，此时再将D置于就绪队列末尾。就绪队列为DEBC，执行进程C
• 当t=9时，将进程C置于就绪队列末尾，此时就绪队列为CDEB，执行进程B。
• ……中间为重复步骤。
• 当t=15时，进程E的执行时间结束，进程E的服务时长为2，故进程E结束，就绪队列为BCD，执行进程D。
• 同理当t=17和t=18时，进程C和进程B相继结束，此时就绪队列只剩下D，故执行D至进程D结束。

通过这个详细的例子，我们可以清晰地看到Round Robin调度算法的工作流程：每个进程在获得时间片后运行，时间片结束后被放入就绪队列末尾等待下一轮调度。这种机制确保了所有进程都能得到公平的CPU使用机会，避免了某些进程长时间占用CPU资源的情况。