SJF Scheduling Program in C with Example & Explanation

Shortest Job First (SJF) scheduling is a CPU scheduling method where the process that requires the least amount of execution time runs first. It is a non-preemptive algorithm, meaning once a process starts, it cannot be interrupted until it finishes. The main advantage of SJF is that it helps reduce the average waiting time for all processes in the system.

This method is useful when dealing with multiple tasks, as it ensures that shorter processes are completed quickly, preventing them from waiting too long. However, one drawback of SJF is that longer processes may face delays if shorter ones keep arriving, which is something to consider when implementing an SJF Scheduling Program in C.

Characteristics of SJF Scheduling

• Non-preemptive: A process runs from start to finish without being interrupted.
• Efficient waiting time: This method keeps the average waiting time as low as possible.
• Risk of starvation: Long tasks might get delayed if short ones keep arriving.
• Greedy approach: Always pick the shortest available task first.

Understanding the key metrics in Shortest Job First (SJF) scheduling is essential for evaluating its efficiency and effectiveness. The most important factors include burst time, arrival time, waiting time, turnaround time, and completion time. These metrics help determine how well the scheduling algorithm performs and highlight issues such as starvation.

Burst Time

Burst time is the total time required by a process for execution on the CPU. In SJF scheduling, processes with shorter burst times are prioritized, which directly impacts the order in which jobs are selected from the queue.

Arrival Time

Arrival time refers to the moment a process enters the ready queue. It is a crucial factor in determining which processes are available for scheduling at any given time.

Waiting Time

Waiting time is the total time a process spends in the ready queue before it starts execution. SJF aims to minimize the average waiting time across all processes.

Turnaround Time

Turnaround time is the total time taken from the arrival of a process to its completion. It is calculated as: Turnaround Time = Completion Time – Arrival Time

Completion Time

Completion time is the exact moment when a process finishes its execution. It is used to compute both waiting time and turnaround time.

Average Waiting Time and Average Turnaround Time

• Average Waiting Time: The mean of the waiting times for all processes. Lower average waiting time indicates better scheduling efficiency.
• Average Turnaround Time: The mean of the turnaround times for all processes. This metric reflects how quickly processes are completed on average.

Starvation

Starvation occurs when processes with longer burst times remain in the queue for a long period, waiting for their turn as shorter jobs are repeatedly scheduled first.

Waiting Table

A waiting table is often used to keep track of each process’s burst time, arrival time, waiting time, and turnaround time during scheduling analysis.

Summary:

These key metrics, such as burst time, waiting time, and turnaround time—are essential for evaluating the performance and fairness of SJF scheduling in any operating system.

1. Get the Number of Processes

• First, ask the user how many processes need to be scheduled.

2. Collect Burst Times

• For each process, take input for its burst time (execution time). The burst time represents how long the process takes to execute.

3. Sort Processes by Burst Time

• Arrange all processes in increasing order of burst time. The process with the shortest burst time should be executed first.
• If two processes have the same burst time, the one that arrived first (or has the lowest process ID) is executed first.

4. Calculate The Waiting Time for Each Process

• The waiting time for a process is the total time it spends waiting before execution.
• The first process in the list has a waiting time of 0.
• For every other process, the waiting time is calculated as:

Waiting Time = Completion Time of Previous Process- Arrival Time of Current Process

5. Calculate Turnaround Time

• Turnaround time is the total time a process takes from arrival to completion. It is calculated as:

Turnaround Time=Waiting Time+Burst Time

6. Display the Results

• Print each process along with its burst time, waiting time, and turnaround time.
• Also, compute and display the average waiting time and average turnaround time for all processes.

Let’s understand how Shortest Job First (SJF) scheduling works using four processes: P1, P2, P3, and P4.

Given Data

SJF selects the process with the shortest burst time from the processes that have already arrived.

Step 1: Organizing by Arrival Time

Processes are first observed based on when they enter the system:

• At time 1 → P1 and P3 arrive
• At time 2 → P2 arrives
• At time 4 → P4 arrives

The scheduler can only choose from processes that have already arrived.

Step 2: CPU Idle Period

From time 0 to 1, no process is available in the ready queue.

During this period, the CPU remains idle.

Step 3: First Process Selection

At time 1, two processes are available: P1 and P3.

• P1 burst time = 3
• P3 burst time = 2

Since P3 has the shorter burst time, it is selected first and starts execution.

Step 4: Handling New Arrivals During Execution

While P3 is executing (from time 1 to 3):

• P2 arrives at time 2

However, because this is non-preemptive SJF, the currently running process is not interrupted.

Step 5: Selecting the Next Process

At time 3, P3 finishes execution.

The ready queue now contains:

• P1 (burst time = 3)
• P2 (burst time = 4)

Among these, P1 has the shorter burst time, so it is selected next.

Step 6: More Processes Enter the Queue

While P1 is running (from time 3 to 6):

• P4 arrives at time 4

The ready queue now contains:

• P2
• P4

Step 7: Choosing Between Equal Burst Times

At time 6, P1 completes.

Both remaining processes:

• P2 (burst time = 4)
• P4 (burst time = 4)

Since their burst times are equal, the scheduler chooses the process that arrived earlier, which is P2.

P2 runs from time 6 to 10.

Step 8: Final Process Execution

After P2 finishes at time 10, only P4 remains.

P4 executes from time 10 to 14, completing all processes.

Performance Metrics Calculation

• Turnaround Time (TAT)
  = Completion Time − Arrival Time
• Waiting Time (WT)
  = Turnaround Time − Burst Time
• Average Waiting Time
  = Total Waiting Time ÷ Number of Processes

These metrics help evaluate how efficiently SJF schedules processes and highlight its strength in minimizing waiting time.

Bottom Line

This step-by-step flow shows how SJF prioritizes shorter jobs, reduces average waiting time, and makes decisions based only on the processes currently available, without interrupting running tasks.

Shortest Job First (SJF) scheduling is a CPU scheduling algorithm that selects the process with the shortest burst time to execute first. It is divided into two types: preemptive and non-preemptive. To understand its implementation, you can refer to an SJF Scheduling Program in C, which indicates how processes are scheduled based on their burst times.

Preemptive SJF (Shortest Remaining Time First - SRTF)

Preemptive SJF, also known as Shortest Remaining Time First (SRTF), allows a newly arriving process to interrupt the current execution if it has a shorter burst time. This ensures that the CPU always executes the process with the least remaining execution time, and it can be implemented using the SJF Preemptive Scheduling Program in C to efficiently manage task execution.

SJF Preemptive Scheduling Program in C:

#include <stdio.h>

int main() {
    int arrival_time[20], burst_time[20], remaining_time[20];
    int i, time, limit, shortest, completed = 0;
    double wait_time = 0, turnaround_time = 0;
    
    printf("Enter number of processes: ");
    scanf("%d", &limit);

    for (i = 0; i < limit; i++) {
        printf("Enter arrival time and burst time for process %d: ", i + 1);
        scanf("%d %d", &arrival_time[i], &burst_time[i]);
        remaining_time[i] = burst_time[i];
    }

    for (time = 0; completed != limit; time++) {
        shortest = -1;
        for (i = 0; i < limit; i++) {
            if (arrival_time[i] <= time && remaining_time[i] > 0) {
                if (shortest == -1 || remaining_time[i] < remaining_time[shortest]) {
                    shortest = i;
                }
            }
        }

        if (shortest != -1) {
            remaining_time[shortest]--;
            if (remaining_time[shortest] == 0) {
                completed++;
                wait_time += (time + 1 - arrival_time[shortest] - burst_time[shortest]);
                turnaround_time += (time + 1 - arrival_time[shortest]);
            }
        }
    }

    printf("\nAverage Waiting Time: %.2lf", wait_time / limit);
    printf("\nAverage Turnaround Time: %.2lf\n", turnaround_time / limit);

    return 0;
}

Explanation:

This Shortest Job First Scheduling Program in C simulates preemptive SJF by continuously checking for the process with the shortest remaining burst time at each time unit. If a process with a smaller burst time arrives, it preempts the currently running process. After execution, the program calculates the average waiting and turnaround times.

Output:

Enter number of processes: 3  
Enter arrival time and burst time for process 1: 0 5  
Enter arrival time and burst time for process 2: 1 3  
Enter arrival time and burst time for process 3: 2 2  

Average Waiting Time: 2.33  
Average Turnaround Time: 5.33 

Time and Space Complexity:

• Time Complexity: O(n²) (due to the nested loop checking for the shortest process)
• Space Complexity: O(n) (for storing process details)

Non-Preemptive Shortest Job First (SJF) Scheduling

In Non-Preemptive SJF, once a process starts execution, it cannot be interrupted until it finishes. The CPU selects the process with the shortest burst time from the available processes and runs it to completion before choosing the next one. This approach is commonly used in an SJF Scheduling Program in C, where processes are sorted by burst time to optimize execution order.

Code Example:

#include <stdio.h>

int main() {
    int n, i, j, process[10], burst_time[10], wait_time[10], turnaround_time[10], total_wait = 0, total_turnaround = 0;
    float avg_wait_time, avg_turnaround_time;

    printf("Enter number of processes: ");
    scanf("%d", &n);

    printf("Enter Burst Time for each process:\n");
    for (i = 0; i < n; i++) {
        printf("P%d: ", i + 1);
        scanf("%d", &burst_time[i]);
        process[i] = i + 1;
    }

    // Sorting processes based on burst time (Non-Preemptive SJF)
    for (i = 0; i < n - 1; i++) {
        for (j = i + 1; j < n; j++) {
            if (burst_time[i] > burst_time[j]) {
                // Swap burst times
                int temp = burst_time[i];
                burst_time[i] = burst_time[j];
                burst_time[j] = temp;

                // Swap process numbers
                temp = process[i];
                process[i] = process[j];
                process[j] = temp;
            }
        }
    }

    // Calculating waiting time
    wait_time[0] = 0;
    for (i = 1; i < n; i++) {
        wait_time[i] = wait_time[i - 1] + burst_time[i - 1];
        total_wait += wait_time[i];
    }

    // Calculating turnaround time
    for (i = 0; i < n; i++) {
        turnaround_time[i] = wait_time[i] + burst_time[i];
        total_turnaround += turnaround_time[i];
    }

    avg_wait_time = (float)total_wait / n;
    avg_turnaround_time = (float)total_turnaround / n;

    printf("\nAverage Waiting Time: %.2f", avg_wait_time);
    printf("\nAverage Turnaround Time: %.2f\n", avg_turnaround_time);

    return 0;
}

Explanation:

The Shortest Job First Scheduling Program in C first sorts the processes based on their burst times to ensure the shortest job executes first. Then, it calculates the waiting time for each process by summing up the burst times of previous processes. Turnaround time is derived by adding burst time to waiting time. Finally, the program computes and prints the average waiting and turnaround times.

Output:

Enter number of processes: 3  
Enter Burst Time for each process:  
P1: 5  
P2: 3  
P3: 2  

Average Waiting Time: 2.33  
Average Turnaround Time: 5.33 

Time and Space Complexity:

• Time Complexity: O(n²) (due to sorting)
• Space Complexity: O(n) (for storing process details)

The Shortest Job First (SJF) scheduling method prioritizes processes with the least burst time, ensuring they execute first. This ensures minimal waiting time and improves overall efficiency. Below is a simple SJF Scheduling Program in C that implements SJF scheduling in a non-preemptive manner.

Code Example:

#include <stdio.h>

int main() {
    int n, i, j, process[20], burst_time[20], wait_time[20], turnaround_time[20], total_wait = 0, total_turnaround = 0;
    float avg_wait_time, avg_turnaround_time;

    printf("Enter number of processes: ");
    scanf("%d", &n);

    printf("\nEnter Burst Time for each process:\n");
    for (i = 0; i < n; i++) {
        printf("P%d: ", i + 1);
        scanf("%d", &burst_time[i]);
        process[i] = i + 1; // Assign process numbers
    }

    // Sorting processes based on burst time (Selection Sort)
    for (i = 0; i < n - 1; i++) {
        int min_index = i;
        for (j = i + 1; j < n; j++) {
            if (burst_time[j] < burst_time[min_index]) {
                min_index = j;
            }
        }
        // Swap burst times
        int temp = burst_time[i];
        burst_time[i] = burst_time[min_index];
        burst_time[min_index] = temp;

        // Swap process numbers
        temp = process[i];
        process[i] = process[min_index];
        process[min_index] = temp;
    }

    // Calculating waiting time
    wait_time[0] = 0;
    for (i = 1; i < n; i++) {
        wait_time[i] = wait_time[i - 1] + burst_time[i - 1];
        total_wait += wait_time[i];
    }

    // Calculating turnaround time
    printf("\nProcess\tBurst Time\tWaiting Time\tTurnaround Time");
    for (i = 0; i < n; i++) {
        turnaround_time[i] = wait_time[i] + burst_time[i];
        total_turnaround += turnaround_time[i];
        printf("\nP%d\t\t%d\t\t%d\t\t%d", process[i], burst_time[i], wait_time[i], turnaround_time[i]);
    }

    avg_wait_time = (float)total_wait / n;
    avg_turnaround_time = (float)total_turnaround / n;

    printf("\n\nAverage Waiting Time: %.2f", avg_wait_time);
    printf("\nAverage Turnaround Time: %.2f\n", avg_turnaround_time);

    return 0;
}

Explanation:

This Shortest Job First Scheduling Program in C sorts the processes by burst time using selection sort. It then calculates the waiting time for each process by summing up previous burst times. Turnaround time is determined by adding burst time to waiting time. Finally, it computes and prints the average waiting and turnaround times.

Output:

Enter number of processes: 3  
Enter Burst Time for each process:  
P1: 6  
P2: 2  
P3: 4  

Process   Burst Time   Waiting Time   Turnaround Time  
   P2               2                    0                       2  
   P3               4                    2                       6  
   P1               6                    6                      12  
 
Average Waiting Time: 2.67  
Average Turnaround Time: 6.67  

Time and Space Complexity:

• Time Complexity: O(n²) (due to sorting)
• Space Complexity: O(n) (for storing process data)

To truly understand how the Shortest Job First (SJF) scheduling algorithm works, let's walk through a practical scenario with step-by-step explanations. This will help you visualize how processes are selected and executed in real time.

Example Scenario: Staggered Arrival Times

Suppose we have five processes with the following burst and arrival times:

Process Arrival Time (ms) Burst Time (ms) P1 2 6 P2 5 2 P3 1 8 P4 0 3 P5 4 4

Let’s see how SJF schedules these processes step by step:

Step 1: Initial State (Time = 0)

• Only P4 has arrived (Arrival Time = 0).
• P4 starts execution.

Step 2: Time Progression

• Time 0–3: P4 runs and completes at time 3.
• At time 1, P3 arrives, but P4 is still running.
• At time 2, P1 arrives, but P4 is still running.

Step 3: After P4 Completes (Time = 3)

• Ready Queue: P1 (Burst 6), P3 (Burst 8)
• At time 4, P5 arrives (Burst 4).
• At time 5, P2 arrives (Burst 2).

Step 4: Choosing the Next Process

• At time 3, among the available processes, P1 (Burst 6) and P3 (Burst 8) are in the queue.
• P1 has the shortest burst at this point, so it runs next.

Step 5: Dynamic Ready Queue

• As new processes arrive, the scheduler always picks the process with the shortest burst time from those that have already arrived and are not yet completed.

Gantt Chart Representation

Below is a simple Gantt chart illustrating execution order and timing:

Time Process Running 0–3 P4 3–9 P1 9–11 P2 11–15 P5 15–23 P3

Calculating Waiting and Turnaround Times

Let’s calculate the waiting and turnaround times for each process:

• Waiting Time: Time spent in the ready queue before execution.
• Turnaround Time: Time from arrival to completion.

Process Arrival Burst Start Finish Waiting Turnaround P4 0 3 0 3 0 3 P1 2 6 3 9 1 7 P2 5 2 9 11 4 6 P5 4 4 11 15 7 11 P3 1 8 15 23 14 22

• Average Waiting Time = (0 + 1 + 4 + 7 + 14) / 5 = 5.2 ms
• Average Turnaround Time = (3 + 7 + 6 + 11 + 22) / 5 = 9.8 ms

Key Takeaways

• SJF always selects the process with the shortest burst time among those that have arrived.
• The ready queue changes dynamically as new processes arrive.
• SJF is optimal for minimizing average waiting time, especially in batch processing systems where burst times are predictable.

Real-World Context

Batch processing systems and automated job queues often use SJF or similar strategies to maximize throughput and minimize the time jobs spend waiting. For example, print servers or data processing pipelines may schedule short jobs first to keep the system responsive and efficient.

Bottom Line: This example provides a clear, step-by-step illustration of SJF scheduling in practice, helping readers grasp how the algorithm works in real scenarios.

The Shortest Job First (SJF) scheduling algorithm is a widely studied scheduling algorithm in operating systems. It selects the process with the shortest burst time from the queue, aiming to optimize certain performance metrics. However, its use comes with both notable benefits and significant limitations.

Advantages of SJF Scheduling

1. Minimizes Average Waiting Time
   SJF is optimal for reducing the average waiting time in a queue. By always selecting the process with the shortest burst time, it ensures that shorter processes are completed quickly, improving overall system efficiency.
2. Maximizes Throughput
   Since shorter jobs are completed first, more processes can be finished in less time. This increases the throughput of the scheduling algorithm, making it well-suited for batch-type processing where efficiency is a priority.
3. Effective for Predictable Workloads
   SJF works best when the burst time of each process is known in advance, such as in batch processing environments. In these scenarios, it can make scheduling straightforward and highly effective.

Disadvantages of SJF Scheduling

1. Requires Accurate Burst Time Estimation
   A significant limitation of SJF is the need to know the burst time of each process beforehand. In practice, it is difficult for the operating system to predict how long a process will take, especially for interactive or unpredictable workloads.
2. Starvation of Longer Processes
   SJF can lead to starvation, particularly for longer processes. If shorter processes continue to arrive, longer ones may remain in the queue indefinitely without getting CPU time.
3. Not Suitable for All Systems
   SJF is generally unsuitable for interactive systems or environments with frequent input-output requests, as these jobs often have unpredictable burst times.
4. Complexity with Input-Output Requests
   Processes that frequently request input-output operations may disrupt the queue, making it harder to maintain the optimal order and further complicating scheduling.

By weighing these advantages and disadvantages, it becomes clear that while SJF can be highly efficient in specific scenarios, its limitations, such as starvation and the need for precise burst time prediction, can make it unsuitable for many real-world operating system workloads.

SJF scheduling is used in different fields where efficient task management is crucial. Some key applications include:

1. Batch Processing Systems: In environments where multiple tasks need to be completed, such as data processing or report generation, SJF helps prioritize shorter tasks first. This reduces the overall waiting time and improves system efficiency.
2. Online Delivery Services: Food delivery and courier services prioritize orders based on estimated preparation or travel time. SJF ensures that quicker deliveries are completed first, leading to better customer satisfaction.
3. Operating System Task Scheduling: Modern operating systems use SJF to allocate CPU time efficiently. By running shorter processes first, the system minimizes idle time and enhances overall performance.

Shortest Job First scheduling remains one of the most efficient CPU scheduling strategies for minimizing average waiting time. Through its C implementation, it becomes clear how process ordering directly affects system performance. While SJF excels in controlled or batch environments, its limitations, especially starvation and burst-time estimation, make it unsuitable for all workloads. Understanding SJF deeply provides a strong foundation for mastering advanced scheduling algorithms used in modern operating systems.

Key Takeaways 

1. SJF optimizes average waiting time but not fairness, making starvation a real concern.
2. Accurate burst-time estimation is critical, without it, SJF loses effectiveness.
3. Preemptive and non-preemptive SJF behave very differently under dynamic arrivals.
4. Scheduling decisions shape CPU utilization, not just execution order.
5. SJF concepts directly influence modern schedulers, even when not used directly.

1. What is SJF scheduling in C, and how does it work?

SJF (Shortest Job First) scheduling in C is a method where the CPU selects the process with the shortest burst time first. This approach improves efficiency by reducing waiting times and prioritizing faster tasks.

2. What are the types of SJF scheduling?

SJF scheduling has two types: preemptive and non-preemptive. Preemptive SJF allows interruption if a shorter job arrives, while non-preemptive SJF lets a process run until it finishes.

3. Can SJF scheduling lead to the starvation of longer processes?

Yes, longer processes may face starvation if shorter ones keep arriving, causing delays. This issue can be reduced using ageing, which gradually increases a process’s priority over time.

4. How is average waiting time calculated in SJF scheduling?

The average waiting time is found by adding up all process waiting times and dividing by the total number of processes. A process’s waiting time is its turnaround time minus its burst time.

5. What are the advantages of using SJF scheduling?

SJF minimizes waiting and turnaround times, making it efficient for batch processing. It improves CPU utilization by quickly executing smaller tasks before longer ones.

6. How do you implement SJF scheduling in C?

To implement SJF in C, take input for arrival and burst times, sort processes by burst time, compute completion times, and derive waiting and turnaround times using arrays and loops.

7. What is the significance of burst time in SJF scheduling?

Burst time is the execution time a process needs. SJF scheduling prioritizes shorter burst times to boost efficiency, reduce delays, and improve overall system performance.