Longest Remaining Time First Scheduling Algorithm

The Longest Remaining time First(LRTF) scheduling is the preemptive version of Longest Job First(LJF) scheduling. This scheduling algorithm is used by the operating system in order to schedule incoming processes so that they can be executed in a systematic way.

With this algorithm, the process having the maximum remaining time is processed first. In this, we will check for the maximum remaining time after an interval of time(say 1 unit) that is there another process having more Burst Time arrived up to that time.

Let us now understand the procedure followed by the LRTF scheduling algorithm;

How does LRTF Scheduling work?

• The First step is to sort the processes according to their Arrival time in increasing order

• The next step is to choose the process that least arrival time but having the most Burst Time. After that process it for 1 unit. After one unit you need to check if up to that time of execution; any other process is arrived or not

• Just repeat the above steps until the execution of all processes.

Characteristics of LRTF Scheduling

Given below are some of the characteristics of LRTF:

• It is a CPU scheduling algorithm that is used to determine the process to be executed first among all incoming processes in a systematic way.

• This algorithm follows the preemptive approach because in this CPU is allocated to any process only for a fixed slice of time.

• In this algorithm, processes are selected on the basis of the highest burst time(the one with the highest burst time is processed first) and this process runs till the fixed slice of time. After that, the selection process takes place again.

• Due to the high value of the average waiting time, this algorithm is not optimal.

Now it's time to cover an example of LRTF.

LRTF Scheduling Example

In the above example, four processes P1, P2, P3, P4 are given along with their arrival time and burst time.

With the help of the Gantt chart let us calculate completion time, waiting time, and turn around time.

Average waiting time is calculated by adding the waiting time of all processes and then dividing them by no. of processes.

average waiting time = waiting time of all processes/ no.of processes

average waiting time=8+5+11+8/4 = 4ms

Advantages of LRTF

• This algorithm is easy to implement and simple

• This algorithm is starvation-free because all processes get a fair share of CPU.

• All the processes get completed by the time the longest job reaches its completion.

Disadvantages of LRTF

• With this algorithm, the average waiting time and turnaround time are too high, even if burst time is less for each process.

• In this process with less burst time(smaller processes) need to wait for CPU in order to finish processes with larger burst size.

• The valuable time of CPU is consumed by context switch; which can be utilized for the execution of processes.