Abstract

It is a preemptive version of the LJF algorithm. In LRTF(Longest Remaining Time First) scheduling, priority is given to the process that has the largest remaining burst time.

Scope

This article talks about LRTF scheduling in detail.

Definition

In the LRTF(Longest Remaining Time First) algorithm, the process that has maximum remaining time is scheduled. It is a preemptive version of the LJF(Longest Job First) algorithm. In this, we first sort the process in increasing order of their arrival time then execute the process which has the least arrival time but the most burst time for 1 unit. If another process arrives by this time we compare the remaining time after 1 unit of execution with the burst time of the newly arrived process. The process which has the maximum burst time is scheduled. If the burst time of both the processes is the same then arrival time is considered to break the tie.

Lets consider an example 

PROCESS	ARRIVAL TIME	BURST TIME
P1	1	2
P2	2	4
P3	3	6
P4	4	8

Execution:

1. The available process for t=1 is P1, so we execute P1 for 1 unit.
2. The available processes for t=2 are P1 and P2. Since the burst time of P1 is 1 which is less than the burst time of P2 which is 4, we select P2 and execute it for 1 unit.
3. The available processes at t=3 are P1, P2, and P3. The burst time of P1 is 1, P2 is 3 and P3 is 6. Since the burst time of P3 is maximum, we select P3 and execute it for 1 unit.
4. Now we repeat the above steps until the execution of all processes.

Here the CPU is idle for 0 to 1 unit time since there is no process available in the given interval.

Gnatt chart:

WAITING TIME(WT)	TURN AROUND TIME(TAT)	COMPLETION TIME (CT)	P. NO.	ARRIVAL TIME	BURST TIME
15	17	18	P1	1	2
13	17	19	P2	2	4
11	17	20	P3	3	6
9	17	21	P4	4	8

Average turn around time = (17+17+17+17)/4 = 17

Average waiting time = (15+13+11+9)/4 = 12

Note: In this process, the average waiting time and turnaround time are too high, even burst time is less for each process

Summary

In LRTF the process with the largest remaining burst time is scheduled first. This is a preemptive version of LJF. This process is simple and easy to implement. 

Special thanks to Ami Jangid for contributing to this article on takeUforward. If you also wish to share your knowledge with the takeUforward fam, please check out this article