Q2Operating System
Question
Describe the Round Robin Scheduling algorithm with an example.
Answer
Round Robin is a preemptive CPU scheduling algorithm where each process is given a fixed time quantum in cyclic order, ideal for time-sharing systems.
Round Robin (RR) scheduling is designed especially for time-sharing systems. The ready queue is treated as a circular queue. The CPU scheduler assigns the CPU to each process for a time interval (time quantum or time slice), typically 10–100 milliseconds.
Algorithm: (1) Processes are arranged in a circular ready queue. (2) The scheduler picks the first process and sets a timer for one quantum. (3) If the process finishes before the quantum expires, it releases the CPU voluntarily. (4) If the process does not finish, the timer interrupts, the process is preempted, and it is placed at the end of the ready queue.
Example: Processes P1(Burst=24ms), P2(Burst=3ms), P3(Burst=3ms), all arrive at t=0. Time Quantum = 4ms.
- Gantt Chart: [P1(0-4) | P2(4-7) | P3(7-10) | P1(10-14) | P1(14-18) | P1(18-22) | P1(22-26) | P1(26-30)]
- Completion times: P1=30, P2=7, P3=10
- Waiting times: P1=(30-24)=6, P2=(7-3)=4, P3=(10-3)=7 — Wait = Completion - Burst
- Average Waiting Time = (6+4+7)/3 = 5.67 ms
- Average Turnaround Time = (30+7+10)/3 = 15.67 ms
Performance of RR heavily depends on the size of the time quantum. A very large quantum makes RR behave like FCFS. A very small quantum (approaching 0) provides the effect of processor sharing but context switching overhead becomes prohibitive. An appropriate quantum is typically slightly larger than the duration of a typical CPU burst. RR gives good response time for all processes and is fair, making it the default algorithm for most time-sharing OS.