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)
Time 0-4: P1 executes
Ready Queue: P2(6), P3(3), P4(1), P5(5), P1(1)
Time 4-8: P2 executes
Ready Queue: P3(3), P4(1), P5(5), P1(1), P6(4), P2(2)
Time 8-11: P3 executes
Ready Queue: P4(1), P5(5), P1(1), P6(4), P2(2)
Time 11-12: P4 executes
Ready Queue: P5(5), P1(1), P6(4), P2(2)
Time 12-17: P5 executes
Ready Queue: P1(1), P6(4), P2(2), P5(1)
Time 17-18: P1 executes
Ready Queue: P6(4), P2(2), P5(1)
Time 18-22: P6 executes
Ready Queue: P2(2), P5(1), P6(0)
Time 22-24: P2 executes
Ready Queue: P5(1), P2(0)
Time 24-25: P5 executes
Ready Queue: P5(0)
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