Algorithm:
The SJF scheduling algorithm works as follows:
- Find the process with the shortest CPU burst time .
- Execute the process until completion.
- Repeat steps 1 and 2 until all processes are executed.
In simpler terms, the algorithm chooses the task with the shortest duration, runs it, then moves on to the next task with the next shortest duration, and repeats. This method is non-preemptive as it allows a task to run without interruption once it has started until it finishes.
Implementation:
Now, let's explore the implementation of the Shortest Job First (SJF) scheduling algorithm in the C programming language. We'll develop a basic application that accepts inputs such as the process count, arrival time, and burst time for each process. Subsequently, the program will compute the average waiting time and turnaround time for each process by applying the SJF scheduling algorithm.
Develop a framework for a procedure that will retain its arrival time, burst duration, and latency period.
struct Process {
int arrival_time;
int burst_time;
int waiting_time;
};
Develop a function that compares two processes by their burst time. This custom function will be employed by the qsort function to arrange the processes in ascending order according to their burst time.
int compare(const void *a, const void *b) {
struct Process *p1 = (struct Process *)a;
struct Process *p2 = (struct Process *)b;
return p1->burst_time - p2->burst_time;
}
Develop a primary function that receives user input and runs the Shortest Job First (SJF) scheduling algorithm.
int main() {
int n, i, j;
float avg_waiting_time = 0, avg_turnaround_time = 0;
printf("Enter the number of processes: ");
scanf("%d", &n);
struct Process processes[n];
for (i = 0; i< n; i++) {
printf("Enter arrival time and burst time of process %d: ", i+1);
scanf("%d %d", &processes[i].arrival_time, &processes[i].burst_time);
}
qsort(processes, n, sizeof(struct Process), compare);
processes[0].waiting_time = 0;
for (i = 1; i< n; i++) {
processes[i].waiting_time = 0;
for (j = 0; j <i; j++) {
processes[i].waiting_time += processes[j].burst_time;
}
avg_waiting_time += processes[i].waiting_time;
}
avg_waiting_time /= n;
for (i = 0; i< n; i++) {
avg_turnaround_time += processes[i].burst_time + processes[i].waiting_time;
}
avg_turnaround_time /= n;
printf("\nProcess\tArrival Time\tBurst Time\tWaiting Time\tTurnaround Time\n");
for (i = 0; i< n; i) {
printf("%d\t\t%d\t\t%d\t\t%d\t\t%d\n", i+1, processes[i].arrival_time, processes[i].burst_time, processes[i].waiting_time, processes[i].burst_time+processes[i].waiting_time);
}
printf("\nAverage Waiting Time: %f\n", avg_waiting_time);
printf("Average Turnaround Time: %f\n", avg_turnaround_time);
return 0;
}
Let's go through the above code step by step:
- We first take input from the user for the number of processes, arrival time , and burst time of each process.
- We create an array of structures to store the information about each process.
- We use the qsort function to sort the processes based on their burst time.
- We calculate the waiting time of each process using the SJF scheduling algorithm.
- We calculate the average waiting time and average turnaround time of all processes.
- Finally, we print the results in tabular form.
Example:
Let's explore an instance involving four tasks along with their arrival time and execution time specified below:
Process 1: Arrival Time = 0, Burst Time = 8
Process 2: Arrival Time = 1, Burst Time = 4
Process 3: Arrival Time = 2, Burst Time = 9
Process 4: Arrival Time = 3, Burst Time = 5
Code:
struct Process {
int arrival_time;
int burst_time;
int waiting_time;
};
int compare(const void *a, const void *b) {
struct Process *p1 = (struct Process *)a;
struct Process *p2 = (struct Process *)b;
return p1->burst_time - p2->burst_time;
}
int main() {
int n, i, j;
float avg_waiting_time = 0, avg_turnaround_time = 0;
printf("Enter the number of processes: ");
scanf("%d", &n);
struct Process processes[n];
for (i = 0; i< n; i++) {
printf("Enter arrival time and burst time of process %d: ", i+1);
scanf("%d %d", &processes[i].arrival_time, &processes[i].burst_time);
}
qsort(processes, n, sizeof(struct Process), compare);
processes[0].waiting_time = 0;
for (i = 1; i< n; i++) {
processes[i].waiting_time = 0;
for (j = 0; j <i; j++)
{
processes[i].waiting_time += processes[j].burst_time;
}
avg_waiting_time += processes[i].waiting_time;
}
avg_waiting_time /= n;
for (i = 0; i< n; i++) {
avg_turnaround_time += processes[i].burst_time + processes[i].waiting_time;
}
avg_turnaround_time /= n;
printf("\nProcess\tArrival Time\tBurst Time\tWaiting Time\tTurnaround Time\n");
for (i = 0; i< n; i++) {
printf("%d\t\t%d\t\t%d\t\t%d\t\t%d\n", i+1, processes[i].arrival_time, processes[i].burst_time, processes[i].waiting_time, processes[i].burst_time+processes[i].waiting_time);
}
printf("\nAverage Waiting Time: %f\n", avg_waiting_time);
printf("Average Turnaround Time: %f\n", avg_turnaround_time);
return 0;
}
Output:
Enter the number of processes: 4
Enter arrival time and burst time of process 1: 0 8
Enter arrival time and burst time of process 2: 1 4
Enter arrival time and burst time of process 3: 2 9
Enter arrival time and burst time of process 4: 3 5
Process Arrival Time Burst Time Waiting Time Turnaround Time
1 0 8 0 8
2 1 4 8 12
4 3 5 12 17
3 2 9 17 26
Average Waiting Time: 9.250000
Average Turnaround Time: 15.750000
SJF scheduling serves as a crucial algorithm in operating systems to enhance system efficiency by reducing the average waiting time and turnaround time of processes. This algorithm is non-preemptive, indicating that a process will not face interruptions once it begins execution until it finishes. SJF scheduling picks the process with the briefest burst time for execution.
One key benefit of the Shortest Job First (SJF) scheduling algorithm is its ability to minimize the average waiting time and turnaround time for all processes. Nevertheless, a significant drawback of this algorithm is its unpredictability, particularly when the burst times of processes are not predetermined. This unpredictability arises from the fact that the SJF scheduling algorithm necessitates awareness of the burst times of all processes in order to determine the next process to execute.
The process of implementing the Shortest Job First (SJF) scheduling algorithm in C requires the creation of a structure array to hold details about each process such as arrival time, burst time, and waiting time. Subsequently, the processes are arranged in ascending order based on their burst time utilizing the qsort function. Following the sorting, the waiting time for each process is determined employing the SJF scheduling logic. To conclude, the average waiting time and average turnaround time for all processes are computed and displayed in a tabular format.
Enhancing the SJF scheduling algorithm in C involves enhancing it with error-handling mechanisms to manage input validation and edge scenarios. For instance, in cases where a process's arrival time exceeds the current time, signifying its non-arrival, the algorithm should skip it until it becomes available. Likewise, when multiple processes share identical burst times, the SJF scheduling algorithm should prioritize the one with the earliest arrival time for processing.
Another method to enhance the execution of the SJF scheduling algorithm in C is by transforming it into a preemptive approach. In a preemptive SJF scheduling system, a task with a shorter burst duration has the ability to interrupt a task with a longer burst duration if it enters the system while the longer task is already in progress. Employing preemptive SJF scheduling can result in further reduction of the average waiting time and turnaround time, particularly in scenarios where tasks with shorter burst durations are frequently introduced.
Conclusion:
In summary, Shortest Job First (SJF) scheduling stands out as a robust algorithm for enhancing the efficiency of operating systems and software applications. Its execution in the C programming language entails the creation of a structure array to hold process details, the sorting of processes based on their burst duration, and the computation of waiting and turnaround times. Despite the constraints of non-preemptive SJF scheduling, it remains a prevalent choice in scheduling algorithms due to its effectiveness in minimizing average waiting and turnaround times. Enhancements to SJF scheduling, such as incorporating preemptive features and robust error handling, can further elevate its performance. Mastering the SJF scheduling algorithm in C proves to be a valuable expertise for programmers and computer scientists striving to develop streamlined and optimized software solutions.