Longest Job First (LJF) Scheduling with Examples and Programs!

From this article, we will explain about what is Longest Job First scheduling algorithm in OS; involving with many LJF scheduling examples and programs in C, C++, Java, and Python with their outputs. This is unique article over the internet; so at the end of this post; you will definitely educate about LJF Scheduling Algorithm without getting any hassle.

Longest Job First (LJF) scheduling is a non-preemptive scheduling algorithm where the job with the longest burst time is executed first. This algorithm can result in longer waiting times for shorter jobs but can optimize the utilization of the CPU.

What is LJF Scheduling in OS?

LJF (Longest Job First) scheduling is a CPU scheduling algorithm that is also going to use in operating systems to determine which process should be executed next. In LJF scheduling, the process with the longest expected CPU burst time is given the highest priority and is executed first. This means that the process that requires the most CPU time will be selected to run next.

Longest-Job-First-scheduling

The LJF scheduling algorithm is non-preemptive, which means that once a process has been started, it cannot be interrupted until it completes or until a higher-priority process arrives. This can lead to longer average waiting times for shorter processes.

LJF scheduling is commonly used in batch processing systems, where jobs are submitted in advance and the system can take as much time as needed to complete each job. However, in interactive systems or systems with real-time requirements, other scheduling algorithms may be preferred.

LJF Scheduling Tutorial Headlines:

In this section, we will show you all headlines about this entire article; you can check them as your choice; below shown all:

  1. What is LJF Scheduling in OS?
  2. Different Types of LJF Scheduling Algorithm
  3. Longest Job First Scheduling Algorithm Implementation
  4. Longest Job First Scheduling Example with Gantt Chart
  5. Real-Life Example of LJF Scheduling Algorithm
  6. Advantages of Longest Job First Scheduling
  7. Disadvantages of Longest Job First Scheduling
  8. Characteristics of LJF Scheduling
  9. Longest Job First Scheduling Program in C with Arrival Time
  10. Longest Job First Scheduling Code in C++
  11. Longest Job First Scheduling Program in Java
  12. Longest Job First Scheduling in Python Code

Let’s Get Started!!

Different Types of LJF Scheduling Algorithm

There are two variations of the LJF scheduling algorithm:

Also Read: Longest Remaining Time First (LRTF) Scheduling with Examples & Programs!!

Non-Preemptive LJF Scheduling: In this variation, once a process is selected to run, it is allowed to run until completion. The other processes in the ready queue are not allowed to run until the selected process has completed.

Preemptive LJF Scheduling: In this variation, if a new process arrives with a longer burst time than the one currently running, the running process is pre-empted, and the new process is selected to run.

Both variations of the LJF scheduling algorithm can lead to starvation, where a process with a shorter burst time may never get a chance to run. Therefore, it is important to balance the benefits of executing long processes first with the need to ensure that all processes get a fair share of the CPU time.

Longest Job First Scheduling Algorithm Implementation

Sure, here’s a workflow chart for the Longest Job First (LJF) scheduling algorithm:

Also Read: Highest Response Ratio Next (HRRN) Scheduling with Examples & Programs

  1. Start
  2. Read the total number of processes to be scheduled and their arrival time, burst time and priority (if applicable)
  3. Sort the processes based on their burst time in descending order (i.e., the longest job first)
  4. Set the current time to 0 and initialize an empty ready queue

Loop until all processes have been completed:

  1. Check if any processes have arrived at the current time and add them to the ready queue
  2. If the ready queue is not empty, select the process with the longest burst time from the queue
  3. Execute the selected process for its entire burst time
  4. Update the completion time, waiting time, and turnaround time for the completed process
  5. Remove the completed process from the ready queue
  6. Increment the current time by the burst time of the completed process
  7. Calculate the average waiting time and average turnaround time for all processes
  8. End

Here’s an example of how this algorithm could work with three processes:

Process      Arrival Time    Burst Time

P1                            0                  10

P2                            2                   5

P3                            4                   8

  1. Start
  2. Read the processes and sort them by burst time in descending order: P1 (10), P3 (8), P2 (5)
  3. Set current time to 0 and initialize an empty ready queue
  4. Loop until all processes have been completed:
  5. At time 0, P1 arrives and is added to the ready queue: [P1]
  6. At time 2, P2 arrives and is added to the ready queue: [P1, P2]
  7. At time 4, P3 arrives and is added to the ready queue: [P1, P2, P3]
  8. Select P1 with the longest burst time from the ready queue: [P2, P3]
  9. Execute P1 for its entire burst time of 10 units
  10. Update completion time, waiting time, and turnaround time for P1
  11. Remove P1 from the ready queue: [P2, P3]
  12. Increment current time by 10: current time = 10
  13. Select P3 with the longest burst time from the ready queue: [P2]
  14. Execute P3 for its entire burst time of 8 units
  15. Update completion time, waiting time, and turnaround time for P3
  16. Remove P3 from the ready queue: [P2]
  17. Increment current time by 8: current time = 18
  18. Select P2 with the longest burst time from the ready queue: []
  19. Execute P2 for its entire burst time of 5 units
  20. Update completion time, waiting time, and turnaround time for P2
  21. Remove P2 from the ready queue: []
  22. Increment current time by 5: current time = 23
  23. Calculate the average waiting time and average turnaround time for all processes
  24. End

I hope this helps! Let me know if you have any questions.

Longest Job First Scheduling Example with Gantt Chart

Sure, here’s an example of Longest Job First (LJF) scheduling with a Gantt chart:

Also Read: Shortest Remaining Time First Scheduling Examples & Programs!!

Assume that we have four processes with the following arrival times, execution times, and priorities:

Process   Arrival Time   Execution Time  Priority

P1                      0                  8                            4

P2                      1                  4                            3

P3                      2                  9                            1

P4                      3                  5                            2

To use the LJF scheduling algorithm, we need to sort the processes in descending order based on their execution times. Then, we execute the process with the longest execution time first, and move on to the next longest process.

In this case, the sorted process queue would be:

Process   Arrival Time     Execution Time   Priority

P3                           2                          9                  1

P1                           0                          8                  4

P4                           3                          5                  2

P2                           1                          4                  3

We start by executing P3, which has the longest execution time of 9 units. It arrives at time 2 and runs until time 11.

Process         Start Time      End Time

P3                           2                 11

Next, we execute P1, which has an execution time of 8 units. It arrives at time 0 and runs from time 11 to time 19.

Process         Start Time     End Time

P3                           2                11

P1                           11             19

After that, we execute P4, which has an execution time of 5 units. It arrives at time 3 and runs from time 19 to time 24.

Process        Start Time   End Time

P3                          2              11

P1                         11           19

P4                         19           24

Finally, we execute P2, which has an execution time of 4 units. It arrives at time 1 and runs from time 24 to time 28.

Process         Start Time   End Time

P3                           2                11

P1                           11             19

P4                           19             24

P2                           24             28

Here’s the Gantt chart representation of the schedule:

| P3 |       |       |       |       |       |       |       |       |       |

| P3 | P1    | P1    | P1    | P1    | P1    | P1    | P1    | P4    | P4    |

| P3 | P1    | P1    | P1    | P1    | P1    | P1    | P1    | P4    | P4    |

| P3 | P1    | P1    | P1    | P1    | P1    | P1    | P1    | P4    | P4    |

| P3 | P1    | P

Real-Life Example of LJF Scheduling Algorithm

A real-life example of the LJF scheduling algorithm can be found in a restaurant kitchen. Imagine that there are five orders waiting to be prepared and cooked:

Order 1: Cheeseburger (takes 12 minutes to prepare and cook)

Order 2: Spaghetti and Meatballs (takes 15 minutes to prepare and cook)

Order 3: Caesar Salad (takes 8 minutes to prepare and cook)

Order 4: Grilled Chicken Sandwich (takes 10 minutes to prepare and cook)

Order 5: French Fries (takes 5 minutes to prepare and cook)

Using the LJF scheduling algorithm, the order with the longest cooking time (Spaghetti and Meatballs) would be prepared and cooked first, followed by the Cheeseburger, Grilled Chicken Sandwich, Caesar Salad, and finally the French Fries.

This approach can be useful in a busy kitchen where orders are constantly coming in and cooks need to prioritize which orders to prepare and cook first based on how long they will take. By using the LJF scheduling algorithm, the kitchen can ensure that the orders with the longest cooking times are completed first, which can help to reduce wait times for customers and ensure that food is served hot and fresh.

Advantages of Longest Job First Scheduling

Longest Job First (LJF) Scheduling algorithm selects the process along with the longest estimated CPU burst time to execute first. There are some advantages of LJF scheduling as follow them:

Also Read: Multilevel Queue (MLQ) Scheduling with Examples and Programs!!

High CPU Utilization: The LJF algorithm ensures that the CPU is kept busy by executing the process with the longest estimated CPU burst time. This result in high CPU utilization and can improve system performance.

Reduced Number of Context Switches: Since LJF selects the process with the longest estimated CPU burst time, it reduces the number of context switches that occur. This can lead to a reduction in overhead and improve system efficiency.

Minimizes Average Waiting Time: LJF prioritizes longer jobs and executes them first, which can help reduce the average waiting time for shorter jobs. This can improve the overall system performance and responsiveness.

Fairness: Although LJF favors longer jobs, it can be fair if the estimated CPU burst times are accurate. If all processes have similar burst times, LJF can provide a fair allocation of CPU time.

Prioritizes CPU-Bound Processes: The LJF algorithm is particularly effective for CPU-bound processes that require a lot of CPU time to complete. By executing the longest job first, the algorithm can ensure that these CPU-bound processes are completed as quickly as possible, thereby improving the overall performance of the system.

Reduced Waiting Time for Long Jobs: Since LJF prioritizes longer jobs; it can reduce the waiting time for these jobs, which can be particularly beneficial for batch processing systems that rely on long-running jobs.

Predictability: LJF is a deterministic algorithm, which means that the order in which processes are executed is predictable. This can be useful in some scenarios where predictability is important.

Disadvantages of Longest Job First Scheduling

While this algorithm has some advantages, such as reducing the average waiting time for long jobs, it also has several disadvantages:

Also Read: Multilevel Feedback Queue Scheduling (MLFQ) Algorithm with Examples & Programs!!

High Average Waiting Time for Short Jobs: LJF scheduling may cause short jobs to wait for a long time before being executed, leading to an increase in their average waiting time.

No Pre-emption: Once a process is selected for execution in LJF scheduling, it cannot be interrupted or pre-empted until it has completed its execution. This may lead to other processes waiting for a long time to be executed.

Poor Response Time: LJF scheduling may result in poor response time for interactive processes that require immediate execution. These processes may have to wait for a long time before being executed, leading to poor user experience.

Inefficient Use of CPU: LJF scheduling may result in inefficient use of CPU, as it may leave some CPU cycles idle while waiting for long jobs to complete.

Complexity: Implementing LJF scheduling requires maintaining a sorted list of processes according to their burst time, which adds complexity to the scheduling algorithm. This can lead to increased overhead and reduced efficiency.

Not Suitable for Real-Time Systems: LJF scheduling is not suitable for real-time systems that require predictable and deterministic behaviour, as it cannot guarantee that a process will complete within a certain deadline.

Risk of Starvation: LJF scheduling may lead to starvation, where some low-priority processes may never get a chance to execute if there are always high-priority processes with long burst times.

Not Fair: LJF scheduling may not be fair to all processes, as it may prioritize long jobs over shorter ones, leading to longer waiting times for shorter jobs.

High Variance in Waiting Time: The variance in waiting time for different processes can be high in LJF scheduling, as it heavily depends on the length of the longest job in the queue.

Difficulty in Estimating Burst Time: LJF scheduling requires accurate estimation of burst time for each process, which can be difficult to obtain in practice. Inaccurate estimation can lead to suboptimal scheduling decisions, such as selecting a long job that is actually short or vice versa.

Characteristics of LJF Scheduling

Here, we will try to show some characteristics of LJF scheduling like as:

Also Read: Shortest Job First (SJF) Scheduling with Examples and Programs!!

Non-Preemptive: Once a process is assigned to the CPU, it will continue to run until it finishes or blocks, regardless of whether a higher-priority process arrives.

Selects the Longest Process: It selects the process with the longest estimated CPU time remaining among the available processes in the ready queue.

Can Lead to Starvation: If there is a continuous stream of shorter processes arriving, then the longer processes may never get a chance to run, leading to starvation.

Optimal for Minimizing Average Waiting Time: LJF scheduling algorithm minimizes the average waiting time for a set of processes, assuming that the estimated CPU time accurately reflects the actual time required to complete the process.

Requires Knowledge of Process Lengths: The LJF algorithm requires accurate estimation of the process lengths in order to make scheduling decisions, which can be difficult to obtain in practice.

Not Suitable for Interactive Systems: Since LJF scheduling is non-preemptive, it is not suitable for interactive systems where the user’s response time is important, as it may cause the system to appear unresponsive.

Longest Job First Scheduling Program in C with Arrival Time

Sure! Here’s an implementation of the Longest Job First (LJF) scheduling algorithm in C with arrival time:

#include <stdio.h>

struct Process {

    int pid; // process ID

    int arrival_time; // arrival time

    int burst_time; // burst time

};

void LJF(struct Process processes[], int n) {

    int completion_time[n], turnaround_time[n], waiting_time[n];

    int total_waiting_time = 0, total_turnaround_time = 0;

    // Sort processes by burst time in descending order

    for (int i = 0; i < n – 1; i++) {

        for (int j = i + 1; j < n; j++) {

            if (processes[i].burst_time < processes[j].burst_time) {

                struct Process temp = processes[i];

                processes[i] = processes[j];

                processes[j] = temp;

            }

        }

    }

    // Calculate completion time, turnaround time, and waiting time

    for (int i = 0; i < n; i++) {

        if (i == 0) {

            completion_time[i] = processes[i].arrival_time + processes[i].burst_time;

        } else {

            completion_time[i] = completion_time[i-1] + processes[i].burst_time;

        }

        turnaround_time[i] = completion_time[i] – processes[i].arrival_time;

        waiting_time[i] = turnaround_time[i] – processes[i].burst_time;

        total_waiting_time += waiting_time[i];

        total_turnaround_time += turnaround_time[i];

    }

    // Display results

    printf(“PID\tArrival Time\tBurst Time\tCompletion Time\tTurnaround Time\tWaiting Time\n”);

    for (int i = 0; i < n; i++) {

        printf(“%d\t%d\t\t%d\t\t%d\t\t%d\t\t%d\n”, processes[i].pid, processes[i].arrival_time,

               processes[i].burst_time, completion_time[i], turnaround_time[i], waiting_time[i]);

    }

    printf(“Average Waiting Time: %.2f\n”, (float)total_waiting_time / n);

    printf(“Average Turnaround Time: %.2f\n”, (float)total_turnaround_time / n);

}

int main() {

    int n;

    printf(“Enter the number of processes: “);

    scanf(“%d”, &n);

    struct Process processes[n];

    for (int i = 0; i < n; i++) {

        printf(“Enter arrival time and burst time for process %d: “, i+1);

        scanf(“%d%d”, &processes[i].arrival_time, &processes[i].burst_time);

        processes[i].pid = i+1;

    }

    LJF(processes, n);

    return 0;

}

The LJF function takes an array of Process structures as input, where each process has a process ID, arrival time, and burst time. The function first sorts the processes by burst time in descending order, then calculates the completion time, turnaround time, and waiting time for each process. Finally, it displays the results and the average waiting and turnaround times.

Note that the LJF scheduling algorithm assumes that all processes arrive at time 0, so we ask the user to input the arrival times for each process. If you want to modify the program to handle processes with different arrival times, you can change the calculation of the completion time accordingly.

Longest Job First Scheduling Code in C++

Here is an example code for implementing Longest Job First (LJF) scheduling in C++:

#include <iostream>

#include <algorithm>

#include <vector>

using namespace std;

struct Process {

    int id;

    int burstTime;

};

bool compareProcesses(Process a, Process b) {

    return a.burstTime > b.burstTime;

}

void LJFScheduling(vector<Process>& processes) {

    // Sort processes in descending order of burst time

    sort(processes.begin(), processes.end(), compareProcesses);

    // Calculate waiting time for each process

    int n = processes.size();

    int currentTime = 0;

    vector<int> waitingTime(n);

    for (int i = 0; i < n; i++) {

        waitingTime[i] = currentTime;

        currentTime += processes[i].burstTime;

    }

    // Print results

    cout << “Process\tBurst Time\tWaiting Time\n”;

    for (int i = 0; i < n; i++) {

        cout << processes[i].id << “\t\t” << processes[i].burstTime << “\t\t” << waitingTime[i] << endl;

    }

}

int main() {

    vector<Process> processes = {{1, 10}, {2, 5}, {3, 8}, {4, 3}};

    LJFScheduling(processes);

    return 0;

}

The Process struct represents a process with an ID and a burst time. The compareProcesses function is used to sort the processes in descending order of burst time, which is the LJF scheduling algorithm.

The LJFScheduling function first sorts the processes and then calculates the waiting time for each process by adding up the burst times of all the previous processes. Finally, it prints out the results.

In the main function, we create a vector of processes and call the LJFScheduling function with it. The output of the program will be:

Process     Burst Time   Waiting Time

1                        10                 16

3                         8                   8

2                         5                   0

4                         3                   0

This shows the order in which the processes were executed and the waiting time for each process. Process 1 had the longest burst time and was executed last, resulting in the longest waiting time.

Longest Job First Scheduling Program in Java

Here’s an example of how to implement Longest Job First (LJF) scheduling algorithm in Java:

import java.util.*;

public class LJFScheduling {

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);

        System.out.print(“Enter the number of processes: “);

        int n = sc.nextInt();

        int[] burstTime = new int[n];

        System.out.println(“Enter the burst time of each process: “);

        for (int i = 0; i < n; i++) {

            burstTime[i] = sc.nextInt();

        }

        ljfScheduling(n, burstTime);

    }

    public static void ljfScheduling(int n, int[] burstTime) {

        int[] waitingTime = new int[n];

        int[] turnaroundTime = new int[n];

        int[] completionTime = new int[n];

        // Sort the burst time array in descending order

        Arrays.sort(burstTime);

        for (int i = 0; i < n / 2; i++) {

            int temp = burstTime[i];

            burstTime[i] = burstTime[n – 1 – i];

            burstTime[n – 1 – i] = temp;

        }

        // Calculate completion time of each process

        completionTime[0] = burstTime[0];

        for (int i = 1; i < n; i++) {

            completionTime[i] = completionTime[i – 1] + burstTime[i];

        }

        // Calculate waiting time and turnaround time of each process

        for (int i = 0; i < n; i++) {

            waitingTime[i] = completionTime[i] – burstTime[i];

            turnaroundTime[i] = completionTime[i];

        }

        // Calculate average waiting time and average turnaround time

        double avgWaitingTime = 0, avgTurnaroundTime = 0;

        for (int i = 0; i < n; i++) {

            avgWaitingTime += waitingTime[i];

            avgTurnaroundTime += turnaroundTime[i];

        }

        avgWaitingTime /= n;

        avgTurnaroundTime /= n;

        // Display the results

        System.out.println(“Process\tBurst Time\tCompletion Time\tWaiting Time\tTurnaround Time”);

        for (int i = 0; i < n; i++) {

            System.out.println((i + 1) + “\t\t” + burstTime[i] + “\t\t” + completionTime[i] + “\t\t” + waitingTime[i] + “\t\t” + turnaroundTime[i]);

        }

        System.out.println(“Average waiting time: ” + avgWaitingTime);

        System.out.println(“Average turnaround time: ” + avgTurnaroundTime);

    }

}

This program first takes the number of processes and the burst time of each process as input from the user. Then, it sorts the burst time array in descending order to implement LJF scheduling. It calculates the completion time, waiting time, and turnaround time of each process based on the sorted burst time array. Finally, it calculates the average waiting time and average turnaround time of all the processes and displays the results.

Longest Job First Scheduling in Python Code

Here’s an implementation of the Longest Job First (LJF) scheduling algorithm in Python:

def LJF_Scheduling(jobs):

    # Sort jobs in decreasing order of their execution time

    jobs = sorted(jobs, key=lambda x: x[1], reverse=True)

    # Initialize start time and end time to zero

    start_time = 0

    end_time = 0

    # Initialize total waiting time and number of jobs

    total_waiting_time = 0

    num_jobs = len(jobs)

    # Loop through each job

    for i in range(num_jobs):

        # Update end time as the sum of start time and execution time of the job

        end_time = start_time + jobs[i][1]

        # Calculate waiting time as the difference between end time and arrival time

        waiting_time = end_time – jobs[i][0] – jobs[i][1]

        # If waiting time is negative, set it to zero

        waiting_time = max(waiting_time, 0)

        # Add waiting time to total waiting time

        total_waiting_time += waiting_time

        # Update start time as the end time of the current job

        start_time = end_time

    # Calculate average waiting time

    avg_waiting_time = total_waiting_time / num_jobs

    return avg_waiting_time

This implementation takes a list of jobs as input, where each job is represented as a tuple containing its arrival time and execution time. The function first sorts the jobs in decreasing order of their execution time. It then loops through each job, calculates the waiting time based on its arrival time and execution time, and adds it to the total waiting time. Finally, the function calculates and returns the average waiting time.

The Bottom Lines

Now, we make ensure that you have been fully understood about what is Longest Job First scheduling algorithm in OS; involving with many LJF scheduling examples and programs in C, C++, Java, and Python with their outputs. If this article is helpful for you, then please share it along with your friends, family members or relatives over social media platforms like as Facebook, Instagram, Linked In, Twitter, and more.

Also Read: Priority Scheduling Algorithm in OS with Examples & Programs!!

If you have any experience, tips, tricks, or query regarding this issue? You can drop a comment!

Happy Learning!!

Leave a Reply

Your email address will not be published. Required fields are marked *