Shortest Job First Scheduling Program in C

Shortest Job First (SJF) is an algorithm for process scheduling that selects the waiting process with the smallest execution time to run next. This helps optimize average wait time and response times. This post discusses in detail how to write the Shortest Job First Scheduling Program in C.

Some key properties of SJF scheduling:

• It is a non-preemptive algorithm. Once a process starts executing, it runs until completion.
• Processes are scheduled based on the shortest next CPU burst.
• SJF is optimal in terms of minimizing average waiting time.
• It requires precise knowledge of the next CPU burst, which is difficult to predict perfectly.

How Shortest Job First (SJF) Works ?

Shortest Job First (SJF) is a scheduling algorithm that selects the waiting process with the smallest execution time from the ready queue for execution next. The underlying principle behind SJF is simple by executing the shortest jobs first, the average waiting time and average turnaround time for processes can be minimized.

Let’s delve deeper into how it works:

1. Ready Queue: When processes arrive, they are placed in the ready queue.
2. Selection for Execution: The process with the shortest burst time in the ready queue is selected next. If two processes have the same burst time, then the one which arrived first will be chosen.
3. Completion and Waiting: Once a process starts execution, it continues until it’s completed. Other processes wait in the ready queue during this time.
4. Non-Preemptive vs. Preemptive:
   • Non-Preemptive SJF: Once a process begins its execution, it runs until completion. New processes, even if they have shorter burst times, will have to wait.
   • Preemptive SJF (also known as Shortest Remaining Time First – SRTF): If a new process arrives with a burst time shorter than the remaining time of the currently executing process, the current process is preempted, and the new process takes over.

Formulas Used in SJF

1. Completion Time (CT): The time when a process completes its execution.
2. Turn-around Time (TAT): The time difference between the completion time and the arrival time. TAT=CT−AT
3. Waiting Time (WT): The time difference between the turn-around time and the burst time. WT=TAT−BT (Burst Time)

Shortest Job First Scheduling Program in C

Here is an algorithm for Shortest Job First Scheduling Program in C:

C Code

#include <stdio.h>
#include <string.h>

#define MAX_PROCESSES 10  // Defines maximum number of processes

int main() {
    int et[MAX_PROCESSES], at[MAX_PROCESSES], n;
    int st[MAX_PROCESSES], ft[MAX_PROCESSES], wt[MAX_PROCESSES], ta[MAX_PROCESSES];
    int totwt = 0, totta = 0;
    float awt, ata;
    char pn[MAX_PROCESSES][10], t[10];

    // Taking input for the number of processes
    printf("Enter the number of process: ");
    scanf("%d", &n);

    // Input process details
    for(int i = 0; i < n; i++) {
        printf("Enter process name, arrival time & execution time: ");
        scanf("%s%d%d", pn[i], &at[i], &et[i]);
    }

    // Sorting based on execution time
    for(int i = 0; i < n; i++) {
        for(int j = i+1; j < n; j++) {
            if(et[i] > et[j]) {
                // Swapping arrival times
                int temp = at[i];
                at[i] = at[j];
                at[j] = temp;

                // Swapping execution times
                temp = et[i];
                et[i] = et[j];
                et[j] = temp;

                // Swapping process names
                strcpy(t, pn[i]);
                strcpy(pn[i], pn[j]);
                strcpy(pn[j], t);
            }
        }
    }

    // Computing start, finish, wait and turnaround times
    for(int i = 0; i < n; i++) {
        if(i == 0) {
            st[i] = at[i];
        } else {
            st[i] = ft[i - 1];
        }

        wt[i] = st[i] - at[i];
        ft[i] = st[i] + et[i];
        ta[i] = ft[i] - at[i];
        totwt += wt[i];
        totta += ta[i];
    }

    awt = (float) totwt / n;
    ata = (float) totta / n;

    // Displaying the results with improved formatting
    printf("\n%-10s %-12s %-14s %-12s %-12s", "Pname", "Arrival Time", "Execution Time", "Waiting Time", "Turnaround Time");
    for(int i = 0; i < n; i++) {
        printf("\n%-10s %-12d %-14d %-12d %-12d", pn[i], at[i], et[i], wt[i], ta[i]);
    }
    printf("\n\nAverage waiting time is: %.2f", awt);
    printf("\nAverage turnaround time is: %.2f\n", ata);

    return 0;
}

Shortest Job First (SJF) Scheduling – Dry Run Example

Given Processes:

Execution Sequence:

1. Time 0-4: No processes have arrived yet.
2. Time 5: P2 arrives and starts executing as it’s the only process in the system.
3. Time 6: P3 arrives but P2 continues executing.
4. Time 7: P4 arrives. P2, P3, and P4 are now in the system, but P2 continues its execution since it started first.
5. Time 12: P2 finishes. P4, having the shortest burst time among the remaining processes (12 compared to P3’s 14), starts executing.
6. Time 24: P4 finishes. P3, being the only remaining process, starts executing.
7. Time 38: P3 finishes.

Gantt Chart:

Calculations:

• P2:
  • Waiting Time = 5 – 5 = 0
  • Turnaround Time = 12 – 5 = 7
• P3:
  • Waiting Time = 24 – 6 = 18
  • Turnaround Time = 38 – 6 = 32
• P4:
  • Waiting Time = 12 – 7 = 5
  • Turnaround Time = 24 – 7 = 17

Averages:

• Average Waiting Time: (0 + 18 + 5) / 3 = 7.67
• Average Turnaround Time: (7 + 32 + 17) / 3 = 18.67

Final Results:

Let’s delve deeper into the advantages and disadvantages of SJF Scheduling Algorithm:

Real-World Applications of SJF Scheduling Algorithm:

1. Batch Systems: In environments where jobs are processed in batches and not interactively, like some financial or data processing systems, SJF can be used to minimize the total processing time.
2. Database Systems: When queries to a database are expected to have vastly different execution times, a variation of SJF can help in optimizing the average response time.
3. Web Servers: For serving web requests where certain lightweight requests can be processed faster than heavy computational requests, an SJF-inspired approach can improve server responsiveness.
4. Cloud Computing: In cloud environments where tasks can be scheduled for execution based on their predicted completion times, SJF concepts can be applied to optimize resource utilization and costs.
5. Job Scheduling in Big Data: Platforms like Hadoop might employ SJF-like strategies when dealing with jobs of varied complexities to ensure quicker jobs don’t get stuck behind longer ones, thus improving system throughput To read about this in more depth I have attached a link.
6. Telecommunication Networks: In packet-switched networks, packets can be seen as “jobs” with varying processing times. SJF concepts can be applied to optimize packet handling in scenarios where processing times can be predicted.

Conclusion

In this blog we discussed the Shortest Job First scheduling program in c. This algorithm is effective when the primary goal is to achieve the minimum average waiting time. However, its practical application can be limited by the challenges of predicting accurate burst times and the potential for process starvation. Despite its drawbacks, SJF remains a fundamental scheduling algorithm, offering insights into the trade-offs between efficiency and fairness in process scheduling.

I hope You liked the post ?. For more such posts, ? subscribe to our newsletter. Check out more C tutorials.

FAQ