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.
|Process||Arrival Time||Burst time||Completion time||
Turn around Time
Turn Around Time = Completion Time – Arrival Time
Waiting Time = Turn Around Time – Burst 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.