Round Robin (RR)

Algorithm:

• Pre-emptive version of First Come First Served (FCFS)
• Processes are added to a queue ordered by their time of arrival
• Picks the first process in the queue and executes it for a time interval (quantum)
• If the process needs more time to complete, it is placed at the end of the queue
• If the process ends before the quantum time, move on to next process in queue Details:
• Quite simple to implement
• May also lead to long waiting times
• Performance depends heavily on the length of the time slice

Example

Given a $TQ=\tau =3$ for this system, calculate the:

• Completion Time
• Turn Around Time
• Waiting Time For the following table using round robin scheduling:

Example

At $t=0$ our only process that has arrived is P1, so we run P1 for 3 At $t=1$ P3 arrives, this means the queue is currently P3 At $t=3$ P1 is taken off the CPU, and placed at the end of the queue, (P1 has 5 left) Queue = P3,P1 So now we run P3 for 3 At $t=5$ P2 arrives, our Queue = P1, P2 At $t=6$ P3 is taken off the CPU, and placed at the end of the queue (P3 has 4 left) Queue = P1,P2,P3 P1 is now run for 3 At $t=9$ P1 is taken off the CPU, and placed at the end of the queue, (P1 has 2 left) Queue = P2,P3,P1 P2 is now run, however the remaining time, 2 is less than $\tau$ so we only run for 2 At $t=11$ P2 is finished, and therefore not placed back on the queue Queue = P3,P1 P3 is now run for 3 At $t=14$ P3 is taken off the CPU, and placed at the end of the queue (P3 has 1 left) Queue = P1,P3 P1 is now run, however the remaining time, 2 is less than $\tau$ so we only run for 2 At $t=16$ P1 is finished, and therefore not placed back on the queue Queue = P3 P3 is now run, however the remaining time, 1 is less than $\tau$ so we only run for 1 At $t=17$ P3 is finished, and therefore not placed back on the queue Therefore we can now create the following.