 |
| Shortest Remaining Time First Scheduling Algorithm |
Shortest remaining time first (SRTF): Preemptive shortest job next (SJN) is another name for SRTF. This scheduling method uses the minimum amount of execution time left to choose which operating system task should be executed from the ready queue.
SRTF is more useful in systems wherein the response time must be low and the CPU must be utilized in an optimization manner.
The article outlines SRTF in detail, by definition, mechanism of working, benefits, drawbacks, real life examples, and comparison with similar scheduling algorithms. In addition, common questions are also dealt to give a complete understanding of this key concept.
(In some places, it is known as Shortest Time to Complete First)
What is Shortest Remaining Time First (SRTF)?
SRTF is a preemptive CPU scheduling algorithm. It may preempt the process that is running currently, if some new process arrival has a remaining time smaller than the currently executing one. The goal of SRTF is to reduce process turnaround and waiting times.
Its tasks get completed very quickly if they are very short in size. Ideally, it's being used in the interactive systems where very fast responses are needed.
SRTF
The system determines whether a newly arrived process has less time left than the one that is executing at the moment.
If it does, the currently running process is paused, and the new process takes its place.
If not, the current process continues execution.
By constantly switching to the shortest remaining job, SRTF aims to improve overall response time, although it may lead to higher context-switching costs.
How Does SRTF Work?
In SRTF, time left of running processes in comparison to other process is calculated when a new Process arrives in system. Now, let us consider an example step by step to illustrate SRTF Scheduling.
Example
Four processes arrive in a system at different times with a different burst times (total execution times). Here is the information of about each of processes
|Approach |Arrival Time |Burst Time |
|P1 | 0 | 7 |
| P2 | 2 | 4 |
| P3 | 4 | 1 |
| P4 | 5 | 4 |
1. At time 0:Process P1 arrives and gets executed since there are no other processes available.
2. At time 2: Process P2 arrives. P1's remaining execution times of five is more than P2's of four.
Thus, P1 is suspended by the system, and P2 is resumed.
3. Process P3 shows up at time 4. One is the burst time. The burst time of P3 is less than the two-second remaining duration of P2.
After that, the system goes back to P3.
4.Process P4 joins the ready queue at time 5 with a burst time of 4.
However P3 continues to run till its completion as it has the least remaining time.
5. After time 6: The algorithm will continue to select the processes in order of the remaining time till all the processes have completed their execution.
This way, short jobs have a higher preference and hence the waiting time is less.
Gantt Chart for the Above Example:
These processes have the following Gantt chart:
| Time | Process |
| 0-2 | P1 |
| 2-4 | P2 |
| 4-5 | P3 |
| 5-7 | P2 |
| 7-11 | P4 |
| 11-13| P1 |
The average waiting and turnaround times for each step are reduced by this order.
Advantages and disadvantages of SRTF
Advantages:
- Reduces Average Waiting Time: SRTF minimizes the average waiting time due to priority given to the smaller processes. That further enhances the efficiency of interactive tasks.
- Improves Turnaround Time: Quicker completion of some of the smaller processes might be crucial for such systems requiring short response time.
- Suitable for Short Jobs: SRTF is suitable in those systems, where short jobs are to be done more and more frequently in time sensitive as well as interactive applications.
Disadvantages
- High Context Switching Overhead: Higher process switch generates higher cost to the context switching, which further reduces the efficiency of the CPU: Starvation for Long Processes: If the long processes keep getting replaced by arriving shorter processes, they would wait for indefinite time and cause starvation.
- It requires precise information: the burst times of processes which, in most instances are not easy to predict.
Real-World Application of SRTF
An example of SRTF in the real world is "interactive gaming". Most games have multiple tasks running simultaneously, such as displaying updates about the background, character animations and responses to the user's inputs. The system responsible for a game will prioritize its tasks based on how soon they must be completed:
User Inputs are short tasks, and it can be done instantaneously.
Background Updates are longer tasks, which can be stopped or put on hold in case further action by the users needs processing.
With SRTF, game responds promptly to the user, or most probably gives prime preference to shorter, urgent user tasks rather than letting long background processes run for extended periods.
It should be understood that what is expected with user inputs and keeping the background updates in terms of priority, as discussed above.
The following are some important facts and figures about SRTF.
[R ou.T., ht studies have established that SRTF can support efficiency since it increases turnaround times by 15 to 20% in cases where the processes take different durations.
For a system in which processes arrive very frequently, a context switching of as high as 40 percent is witnessed due to a scheduling algorithm done by SRTF compared to non-preemptive algorithms.
In time sharing systems SRTF is normally used wherever response times are necessary in interactive environments.
Conclusion
Shortest Remaining Time First (SRTF) is a powerful distributed OS scheduling algorithm that could be very effective with the high demand for responsiveness time. SRTF will minimize waiting and turnaround times of high priority processes due to switching between processes preventively such that the first tasks that are going to be executed are the shortest ones. It does, however, have some drawbacks; high context-switching overhead and long processes would starve.
Understanding the strengths and weaknesses of SRTF might help to decide which scheduling algorithm to be opted for based upon the system requirements. For example, SRTF is very good at interactive systems where quick responses are essential but not suited for batch processing environment in which throughput is concerned.
SRTF Common Questions and Answers
Q1. What is the difference between SRTF and Shortest Job First (SJF)?
Answer: A preemptive technique called SRTF can stop the running process when a new one enters with less time left.
SJF is non-preemptive as it completes one process once it starts, whether any other processes arrive later or not.
Q2. How does SRTF handle the case if two processes have the same remaining time?
Answer: If two processes have the same remaining time, SRTF normally schedules them based on arrival order; that is, the process that arrived first gets a priority.
Q3. Why is SRTF considered a fair algorithm?
Answer: SRTF treats short processes fairly because it enables them to complete quickly. However it may suffer from long process starvation in case short tasks keep on coming, thus the algorithm is not too fair on systems containing frequently short tasks.
Q4. What is the main limitation of SRTF in real-world applications?
Answer: Its main disadvantage is starving of the longer processes and the higher overhead caused by context switchings, which may decrease the CPU efficiency in the highly loaded environments.
Q5. Is SRTF applicable for batch processing systems?
Answer: SRTF is not that appropriate for batch systems in which jobs are not so urgent and timely. Batch processing systems have greater benefits from an algorithm that ought to focus more on throughput rather than response time.
Q6. What is the effect of SRTF on CPU utilization?
Answer: SRTF improves utilization of the CPUs since it limits idle times, but excessive context switching due to preemption can make overall CPU efficiency go down.
