Lists of Long Descriptive type Questions that may be asked in Written Exams.
- (1) Explain Shortest Remaining Time Next (SRTN) scheduling algorithms with illustration.
Question-1 Explain Shortest Remaining Time Next (SRTN) scheduling algorithms with illustration.
Selection Criteria:
The process, whose remaining run time is shortest, is served first. This is a preemptive version of SJF scheduling.
Decision Mode:
Preemptive: When a new process arrives, its total time is compared to the current process remaining run time. If the new job needs less time to finish than the current process, the current process is suspended and the new job is started.
Implementation:
This strategy can also be implemented by using sorted FIFO queue. All processes in a queue are sorted in ascending order on their remaining run time. When CPU becomes free, a process from the first position in a queue is selected to run.
Example:
Consider the following set of four processes. Their arrival time and time required to complete the execution are given in following table. Consider all time values in milliseconds.
Process | Arrival Time (T0) | Time required for completion (∆T)(CPU Burst Time) |
P0 | 0 | 10 |
P1 | 1 | 6 |
P2 | 3 | 2 |
P3 | 5 | 4 |
Gantt Chart:
P0 | P1 | P2 | P3 | P0 |
01 | 3 | 5 | 13 | 22 |
Initially only process P0 is present and it is allowed to run. But, when P1 comes, it has shortest remaining run time. So, P0 is preempted and P1 is allowed to run. Whenever new process comes or current process blocks, such type of decision is taken. This procedure is repeated till all processes complete their execution
Statistics:
Process | Arrival Time(T0) | CPU Burst Time(∆T) | Finish Time(T1) | Turnaround Time(TAT=T1-T0) | Waiting Time (WT=TAT-∆T) |
P0 | 0 | 10 | 22 | 22 | 12 |
P1 | 1 | 6 | 9 | 8 | 2 |
P2 | 3 | 2 | 5 | 2 | 0 |
P3 | 5 | 4 | 13 | 8 | 4 |
Average Turnaround Time: (22+8+2+8) / 4 = 40/4 = 10 ms.
Average Waiting Time: (12+2+0+4)/4 = 18 / 4 = 4.5 ms.
Advantages:
- Less waiting time.
- Quite good response for short processes.
Disadvantages:
- Again it is difficult to estimate remaining time necessary to complete execution.
- Starvation is possible for long process. Long process may wait forever.
- Context switch overhead is there.