Longest Job First Algorithm | LRTF Scheduling

Longest Job First Algorithm-

 

In LJF Scheduling,

  • Out of all the available processes, CPU is assigned to the process having largest burst time.
  • In case of a tie, it is broken by FCFS Scheduling.

 

 

  • LJF Scheduling can be used in both preemptive and non-preemptive mode.
  • Preemptive mode of Longest Job First is called as Longest Remaining Time First (LRTF).

 

Advantages-

 

  • No process can complete until the longest job also reaches its completion.
  • All the processes approximately finishes at the same time.

 

Disadvantages-

 

  • The waiting time is high.
  • Processes with smaller burst time may starve for CPU.

 

PRACTICE PROBLEMS BASED ON LJF SCHEDULING-

 

Problem-01:

 

Consider the set of 5 processes whose arrival time and burst time are given below-

 

Process IdArrival timeBurst time
P103
P212
P324
P435
P546

 

If the CPU scheduling policy is LJF non-preemptive, calculate the average waiting time and average turn around time.

 

Solution-

 

Gantt Chart-

 

 

Now, we know-

  • Turn Around time = Exit time – Arrival time
  • Waiting time = Turn Around time – Burst time

 

Also read- Various Times of Process

 

Process IdExit timeTurn Around timeWaiting time
P133 – 0 = 33 – 3 = 0
P22020 – 1 = 1919 – 2 = 17
P31818 – 2 = 1616 – 4 = 12
P488 – 3 = 55 – 5 = 0
P51414 – 4 = 1010 – 6 = 4

 

Now,

  • Average Turn Around time = (3 + 19 + 16 + 5 + 10) / 5 = 53 / 5 = 10.6 unit
  • Average waiting time = (0 + 17 + 12 + 0 + 4) / 5 = 33 / 5 = 6.6 unit

 

Problem-02:

 

Consider the set of 4 processes whose arrival time and burst time are given below-

 

Process IdArrival timeBurst time
P112
P224
P336
P448

 

If the CPU scheduling policy is LJF preemptive, calculate the average waiting time and average turn around time.

 

Solution-

 

Gantt Chart-

 

 

Now, we know-

  • Turn Around time = Exit time – Arrival time
  • Waiting time = Turn Around time – Burst time

 

Process IdExit timeTurn Around timeWaiting time
P11818 – 1 = 1717 – 2 = 15
P21919 – 2 = 1717 – 4 = 13
P32020 – 3 = 1717 – 6 = 11
P42121 – 4 = 1717 – 8 = 9

 

Now,

  • Average Turn Around time = (17 + 17 + 17 + 17) / 4 = 68 / 4 = 17 unit
  • Average waiting time = (15 + 13 + 11 + 9) / 4 = 48 / 4 = 12 unit

 

Problem-03:

 

Consider three processes (process id 0, 1, 2 respectively) with compute time bursts 2, 4 and 8 time units. All processes arrive at time zero. Consider the longest remaining time first (LRTF) scheduling algorithm. In LRTF, ties are broken by giving priority to the process with the lowest process id. The average turn around time is-

  1. 13 unit
  2. 14 unit
  3. 15 unit
  4. 16 unit

 

Solution-

 

We have the set of 3 processes whose arrival time and burst time are given below-

 

Process IdArrival timeBurst time
P102
P204
P308

 

Gantt Chart-

 

 

Now, we know-

Turn Around time = Exit time – Arrival time

 

Process IdExit timeTurn Around time
P11212 – 0 = 12
P21313 – 0 = 13
P32414 – 0 = 14

 

Now,

Average Turn Around time = (12 + 13 + 14) / 3 = 39 / 3 = 13 unit

Thus, Option (A) is correct.

 

To gain better understanding about LJF Scheduling,

Watch this Video Lecture

 

To gain better understanding about LRTF Scheduling,

Watch this Video Lecture

 

Next Article- Highest Response Ratio Next Scheduling

 

Get more notes and other study material of Operating System.

Watch video lectures by visiting our YouTube channel LearnVidFun.

Summary
Longest Job First Algorithm | LRTF Scheduling
Article Name
Longest Job First Algorithm | LRTF Scheduling
Description
Longest Job First Algorithm is a CPU Scheduling Algorithm that assigns CPU to the process with longest burst time. Longest Remaining Time First or LRTF is the preemptive mode of Longest Job First Scheduling Algorithm.
Author
Publisher Name
Gate Vidyalay
Publisher Logo
Liked this article? Share it with your friends and classmates now-