CONCEPT - Longest Job First (LJF)

Algorithm


Longest Job First (LJF)

Longest Job First (LJP) is a non-preemptive scheduling algorithm. Its preemptive version is called Longest Remaining Time First (LRTF) algorithm.

This algorithm is based upon the burst time of the processes. The processes are put into the ready queue based on their burst times i.e., in descending order of the burst times. As the name suggests this algorithm is based upon the fact that the process with the largest burst time is processed first. The burst time of only those processes is considered that have arrived in the system until that time.

    Advantages:

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

    • Disadvantages:

  • Processes with smaller burst time may starve for CPU.
  • It reduces the processing speed and thus reduces the efficiency and utilization of the system.
  • This algorithm gives very high average waiting time and average turn-around time for a given set of processes. This may lead to convoy effect.

Algorithm

1. First, sort the processes in increasing order of their Arrival Time.
2. Choose the process having highest Burst Time among all the processes that have arrived till that time. Then process it for its burst time. Check if any other process arrives until this process completes execution.
3. Repeat the above both steps until all the processes are executed.
Note-
If two processes have the same burst time then the tie is broken using FCFS i.e., the process that arrived first is processed first.

>> Example :

For the four processes P1, P2, P3, P4 and P5, the arrival time is 0ms, 0ms, 2ms, 3ms and 4ms respectively. And the burst time forP1, P2, P3, P4 and P5 is 2ms, 3ms, 4ms, 5ms, and 4ms respectively.

Working :
Gantt chart for this example,


Since, completion time (CT) can be directly determined by Gantt chart, and
Turn Around Time (TAT) = (Completion Time) - (Arrival Time)
Also, Waiting Time (WT) = (Turn Around Time) - (Burst Time)
Therefore, final table look like,

Total Turn Around Time = 40 ms
So, Average Turn Around Time = 40/5 = 8 ms
And, Total Waiting Time = 24 ms
So, Average Waiting Time = 24/5 = 4.8 ms = 226