Longest Response Time First


Introduction

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.

Example

Let's take an example of The LRTF scheduling algorithm. In the Following schedule, there are 4 processes with process ID P1, P2, P3 and P4. P1 arrives at time 1, P2 at time 2, P3 at time 3 and P4 arrives at time 4 in the ready queue. The processes and their respective Arrival and Burst time are given in the following table.

table

Step 0) The CPU is idle for 1 second interval.

Step 1) At time = 1, Available Process : P1. So, P1 is selected and executed for 1s.

Step 2) At time = 2, Available Process : P1, P2. So, P2 is selected and executed for 1s (since BT(P1)=1 which is less than BT(P2) = 4).

Step 3) At time = 3, Available Process : P1, P2, P3. So, P3 is selected and executed for 1s (since, BT(P1) = 1 , BT(P2) = 3 , BT(P3) = 6).

Step 4) Repeat the above steps until the execution of all processes.

Step 5) Let's calculate the average waiting time for above example.


gt

The Turnaround time and the waiting time are calculated by using the following formula.

Turn Around Time = Completion Time - Arrival Time Waiting Time = Turnaround time - Burst Time
tat
cal

Advantages

  1. This algorithm is easy to implement and simple
  2. This algorithm is starvation-free because all processes get a fair share of CPU.
  3. All the processes get completed by the time the longest job reaches its completion.

Disadvantages

  1. With this algorithm, the average waiting time and turnaround time are too high, even if burst time is less for each process.
  2. In this process with less burst time(smaller processes) need to wait for CPU in order to finish processes with larger burst size.
  3. The valuable time of CPU is consumed by context switch, which can be utilized for the execution of processes.