The round-robin scheduling algorithm is suitable for time-sharing computers which are similar to FCFS. However, preemption is added to this algorithm to switch between processes.
A time slice is defined called time quantum which is typically 10 to 100 milliseconds. The processes are allocated CPU time up to 1-time quantum. Then the process is preempted and the next process is allocated the CPU.
A first in first out (FIFO) queue is enough to implement the round-robin algorithm. The FIFO queue must be circular because the processes are added to the tail of the ready queue frequently unless it has terminated before it could complete its time quantum.
Gantt Chart for Round Robin
Consider an example, the following processes arrive at time 0.
| Process | CPU Burst |
| p1 | 20 |
| p2 | 5 |
| p3 | 4 |
| p4 | 8 |
Let the time quantum be 4 milliseconds, then
Therefore,
The waiting time for p1 = (25 – 20) + (16 – 4) = 5 + 12 = 17
The waiting time for p2 = 20 – 8 = 12
The waiting time for p3 = 8
The waiting time for p4 = 21 – 16 = 5
The average waiting time = 17 + 12 + 8 + 5 = 42/4 = 10.5 ms
Performance Analysis
The performance depends on the size of the time quantum. If the time quantum is very large the performance is same as FCFS. If the time slice is too small the processor shall take more time to do context switching.
For example, if quantum is 4 ms and context switching task takes 1 ms, then 20% of the time is lost in administrative tasks. Suppose if quantum is 100 ms, then the loss would be 1% of the time.
Now, each process takes 100 milliseconds and if 10 at least are waiting in the ready queue and each one takes 100 milliseconds then the last one takes 1 second which is slow in processor terms.
What if the quantum size is larger than CPU burst? In that case, there would not be a preemption and process will be blocked and the context switch will happen.
The size of quantum should be at least 20 – 50 milliseconds which is neither too high, nor too low.
References
- Abraham Silberschatz, Peter B. Galvin, Greg Gagne (July 29, 2008) Operating System Concepts, 8 edn., : Wiley.
- Tanenbaum, Andrew S. (March 3, 2001) Modern Operating Systems, 2nd edn., : Prentice Hall.
