Longest Job First Scheduling Algorithm
Longest Job First (LJF) scheduling comes under the category of the non-preemptive scheduling algorithm. This algorithm mainly keeps the track of Burst time of all processes that are available at the arrival time itself and then it will assign the processor to the process having the longest burst time. In this algorithm, once a process starts its execution then it cannot be interrupted in between its processing. Any other process can be executed only after the assigned process has completed its processing and has been terminated.
This scheduling is similar to the SJF scheduling algorithm. But, in this scheduling algorithm, the priority is given to the process having the longest burst time.
Although this scheduling algorithm is not considered to be an efficient way of scheduling the processes because there are many drawbacks of it:
-
The first one is the Convoy effect is displayed by it
-
The second one is this algorithm has a very large average turn-around time and average waiting time. Due to these two, the effectiveness of the system decreases and processing becomes slow.
In a situation if two processes having the same burst time then the tie is broken using FCFS i.e., the process that arrived first is processed first.
Let us take a look at the Procedure used in LJF scheduling:
-
In the First step, the algorithm sort the processes according to the increasing order of their Arrival Time.
-
In the second step, it will choose the process having the highest Burst Time among all the processes that have arrived till that time.
-
After that, it will process it for its given burst time. The LJF also checks if any other process arrives until this process completes its execution.
-
last but not least it will Repeat all the above steps until all the processes are executed.
Now its time to take a look at the example of LJF Scheduling:
Longest Job First Scheduling Example
In the above example, four processes P1, P2, P3, P4 are given along with their Burst time and arrival time.
Explanation
Let us understand the working of LJF in the Gantt chart given above;
-
At t = 0, there is one process that is available having 2 units of burst time. So, select P1 and execute it for 2 ms.
-
At t = 2 i.e. after P1 gets executed, The Available Processes are P2, P3. As you can see the burst time of P3 is more than P2. So, select P3 and execute it for 5ms.
-
At t = 7 i.e. after the execution of P3, the Available Processes are P2, P4. As you can see the burst time of P4 is more than P2. So, select P4 and execute it for 7ms.
-
Finally, after the completion of P4 execute the process P2 for 3 ms.
You can determine the completion time easily with the help of the Gantt chart. Let us calculate the waiting time and turnaround time.
| Process |
Arrival Time |
Burst Time |
Completion Time |
Turn around Time
Turn Around Time = Completion Time – Arrival Time
|
Waiting Time
Waiting Time = Turn Around Time – Burst Time
|
| P1 |
0 |
2 |
2 |
2-0=2 |
2-2=0 |
| P2 |
1 |
3 |
17 |
17-1=16 |
16-3=13 |
| P3 |
2 |
5 |
7 |
7-2=5 |
5-5=0 |
| P4 |
3 |
7 |
14 |
14-3=11 |
11-7=4 |
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 for the time of all processes/ no.of processes
average waiting time=0+13+0+4/4=17/4=4.25ms
Disadvantages of LJF Scheduling
-
This algorithm leads to the reduction of processing speed due to which there is a reduction in the efficiency and utilization of the system.
-
Due to this algorithm, for a given set of processes, the average waiting time and average turn-around time increase.
-
This algorithm leads to the convoy effect.
-
With this algorithm, there is a possibility that a short process may never get executed and the system keeps on executing the long processes.
