Round Robin Scheduling Algorithm: A Detailed Example and Explanation

Understand the Round Robin (RR) CPU scheduling algorithm with this practical example. This tutorial demonstrates RR scheduling, including Gantt chart creation, calculating waiting time and turnaround time, and illustrating how RR aims for fairness in CPU allocation.



Round Robin Scheduling Algorithm Example

Understanding Round Robin Scheduling

Round Robin (RR) is a preemptive, CPU scheduling algorithm that gives each process a small, fixed burst of CPU time called a time quantum. Processes are maintained in a ready queue. The process at the head of the queue gets the CPU for one time quantum. If the process doesn't complete within its quantum, it goes back to the end of the queue. This continues until all processes are finished. RR aims for fairness, giving each process a share of CPU time.

Example: Round Robin Scheduling

Let's illustrate RR scheduling with six processes (P1-P6). The time quantum is 4 units. Arrival and burst times are shown below. We'll track the ready queue and create a Gantt chart.

Process ID Arrival Time Burst Time
P1 0 5
P2 1 6
P3 2 3
P4 3 1
P5 4 5
P6 6 4

Initial State (Time 0)

Ready Queue: P1 (burst time 5)

Initial Gantt Chart

Time 0-4: P1 executes

Ready Queue: P2(6), P3(3), P4(1), P5(5), P1(1)

Gantt Chart after P1

Time 4-8: P2 executes

Ready Queue: P3(3), P4(1), P5(5), P1(1), P6(4), P2(2)

Gantt Chart after P2

Time 8-11: P3 executes

Ready Queue: P4(1), P5(5), P1(1), P6(4), P2(2)

Gantt Chart after P3

Time 11-12: P4 executes

Ready Queue: P5(5), P1(1), P6(4), P2(2)

Gantt Chart after P4

Time 12-17: P5 executes

Ready Queue: P1(1), P6(4), P2(2), P5(1)

Gantt Chart after P5

Time 17-18: P1 executes

Ready Queue: P6(4), P2(2), P5(1)

Gantt Chart after P1 2nd

Time 18-22: P6 executes

Ready Queue: P2(2), P5(1), P6(0)

Gantt Chart after P6

Time 22-24: P2 executes

Ready Queue: P5(1), P2(0)

Gantt Chart after P2 2nd

Time 24-25: P5 executes

Ready Queue: P5(0)

Gantt Chart after P5 2nd
Process ID Arrival Time Burst Time Completion Time Turnaround Time Waiting Time
P1 0 5 18 18 13
P2 1 6 24 23 17
P3 2 3 11 9 6
P4 3 1 12 9 8
P5 4 5 25 21 16
P6 6 4 22 16 12

Average Waiting Time = (13+17+6+8+16+12)/6 = 72/6 = 12