Introduction to shortest remaining time first (SRTF) algorithm

Operating systems use different process schedulers to schedule processes to be assigned to the CPU for further execution based on some scheduling algorithms. Some scheduling algorithms are as follows:

• First-come, first-served (FCFS) scheduling

• Shortest-job-next (SJN) scheduling

• Priority scheduling

• Shortest remaining time first scheduling

• Round robin(RR) scheduling

• Multiple-level queues scheduling

Note: Algorithms are either preemptivePreemptive scheduling is based on priority where a scheduler may preempt a low priority running process anytime when a high priority process enters into a ready state. or non-preemptiveNon-preemptive algorithms are designed so that once a process enters the running state, it cannot be preempted until it completes its allotted time..

In this answer, we'll discuss the shortest remaining time first scheduling algorithm.

Shortest remaining time first scheduling

This algorithm is the preemptive version of the shortest job first (SJF) scheduling or the shortest job next (SJN). In this SRTF scheduling, the process with the least burst time remaining is executed first. So, in this scheduling, the processes are scheduled based on their remaining execution time.

Note: To learn more about SJF scheduling, click here.

Let's understand preemptive SJN scheduling through an example.

Example

Suppose we have a set of five processes whose burst timeBurst time is the total time taken by the process for its execution on the CPU. and arrival time Time at which the process arrives in the ready queue.are given. Schedule the processes using the shortest remaining time first scheduling, and calculate the average waiting time.

Solution

Let's handle this process scheduling using preemptive SJN scheduling or the shortest remaining time first scheduling. To understand it better, look at the figure below:

Gantt chart

Let's look at the Gantt chartA Gantt chart, commonly used in project management, is one of the most popular and useful ways of showing activities (tasks or events) displayed against unit time. of our example:

Waiting time

Let's calculate the waiting time using the above Gantt chartA Gantt chart, commonly used in project management, is one of the most popular and useful ways of showing activities (tasks or events) displayed against unit time.:

Wait Time = Service Time - Arrival Time

Average waiting time

Advantages

The advantages of the shortest remaining time first scheduling are as follows:

• Processes with a shorter burst time are executed quickly.

• The system overhead is minimal since the system only needs to make a choice when a process completes its execution, or a new process is added to the queue.

• Since it's a preemptive algorithm, whenever a new process is added to the queue, it just has to compare the presently executing process and the new one.

Disadvantages

The advantages of the shortest remaining time first scheduling are the following:

• The context switch is done a lot more times significantly in SRTF than in SJN and consumes the CPU's important time for handling. This amounts to its handling time and decreases its benefit of quick handling.

• It has the potential for process starvationStarvation or indefinite blocking is a phenomenon associated with the Preemptive scheduling algorithms. since it always selects the shortest jobs first.

• If the shorter process is continuously added, the longer processes may be held off indefinitely.