Question-1 Explain Round Robin scheduling algorithms with illustration.
Each selected process is assigned a time interval, called time quantum or time slice.
Process is allowed to run only for this time interval. Here, two things are possible:
- First, Process is either blocked or terminated before the quantum has elapsed. In this case the CPU switching is done and another process is scheduled to run.
- Second, Process needs CPU burst longer than time quantum. In this case, process is running at the end of the time quantum. Now, it will be preempted and moved to the end of the queue. CPU will be allocated to another process. Here, length of time quantum is critical to determine.
This strategy can be implemented by using circular FIFO queue. If any process comes, or process releases CPU, or process is preempted. It is moved to the end of the queue.
When CPU becomes free, a process from the first position in a queue is selected to run.
Consider the following set of four processes. Their arrival time and time required to complete the execution are given in the following table. All time values are in milliseconds. Consider that time quantum is of 4 ms, and context switch overhead is of 1 ms
|Process||Arrival Time (T0)||Time required for completion (∆T)(CPU Burst Time)|
At 4ms, process P0 completes its time quantum. So it preempted and another process P1 is allowed to run. At 12 ms, process P2 voluntarily releases CPU, and another process is selected to run. 1 ms is wasted on each context switch as overhead. This procedure is repeated till all process completes their execution.
|Process||Arrival Time(T0)||CPU Burst Time(∆T)||Finish Time(T1)||Turnaround Time(TAT=T1-T0)||Waiting Time (WT=TAT-∆T)|
Average Turnaround Time: (28+24+9+17)/4 = 78 / 4 = 19.5 ms
Average Waiting Time: (18+18+7+13)/4 = 56 / 4 = 14 ms
- One of the oldest, simplest, fairest and most widely used algorithms.
- Context switch overhead is there.
- Determination of time quantum is too critical. If it is too short, it causes frequent context switches and lowers CPU efficiency. If it is too long, it causes poor response for short interactive process.