Sjf Scheduling Program In C With Gantt Chart
Introduction
Shortest Job First (SJF) scheduling algorithm is a well-known and widely used algorithm in operating systems. It is a non-preemptive algorithm that schedules processes based on their burst time. In this article, we will discuss how to implement the SJF scheduling algorithm in C programming language and how to visualize the schedule using a Gantt chart.
SJF Scheduling Algorithm
The SJF scheduling algorithm works on the principle of selecting the process with the shortest burst time among the available processes. It is a non-preemptive algorithm, which means that once a process starts executing, it cannot be interrupted until it completes its execution.
The SJF scheduling algorithm can be implemented using an array of structures, where each structure represents a process and contains the process ID, arrival time, burst time, and completion time. The processes are sorted in ascending order based on their burst time, and the algorithm executes the processes in that order.
SJF Scheduling Program in C
Let's take a look at how to implement the SJF scheduling algorithm in C programming language.
#include <stdio.h>struct process {int pid;int arrival_time;int burst_time;int completion_time;};void swap(struct process *a, struct process *b) {struct process temp = *a;*a = *b;*b = temp;}void sort(struct process p[], int n) {for (int i = 0; i < n - 1; i++) {for (int j = i + 1; j < n; j++) {if (p[i].burst_time > p[j].burst_time) {swap(&p[i], &p[j]);}}}}void sjf(struct process p[], int n) {sort(p, n);int time = 0;for (int i = 0; i < n; i++) {p[i].completion_time = time + p[i].burst_time;time = p[i].completion_time;}}int main() {struct process p[5] = {{1, 0, 3, 0},{2, 1, 5, 0},{3, 2, 1, 0},{4, 3, 2, 0},{5, 4, 4, 0}};sjf(p, 5);printf("PID\tAT\tBT\tCT\n");for (int i = 0; i < 5; i++) {printf("%d\t%d\t%d\t%d\n", p[i].pid, p[i].arrival_time, p[i].burst_time, p[i].completion_time);}return 0;}In this program, we have defined a structure named "process" that stores the process ID, arrival time, burst time, and completion time. We have also defined a swap function and a sort function that sorts the processes based on their burst time in ascending order.
The main function initializes an array of five processes and calls the sjf function, which sorts the processes using the sort function and calculates the completion time for each process. Finally, the program prints the process ID, arrival time, burst time, and completion time for each process.
Gantt Chart
A Gantt chart is a popular tool used to visualize the schedule of processes in a system. It is a horizontal bar chart that shows the start and end times of each process.
In order to create a Gantt chart for the SJF scheduling algorithm, we need to calculate the start and end times of each process. We can use the completion time of each process to calculate the start time of the next process.
Let's take a look at how to create a Gantt chart for the example we used in the previous section.
#include <stdio.h>struct process {int pid;int arrival_time;int burst_time;int completion_time;};void swap(struct process *a, struct process *b) {struct process temp = *a;*a = *b;*b = temp;}void sort(struct process p[], int n) {for (int i = 0; i < n - 1; i++) {for (int j = i + 1; j < n; j++) {if (p[i].burst_time > p[j].burst_time) {swap(&p[i], &p[j]);}}}}void sjf(struct process p[], int n) {sort(p, n);int time = 0;for (int i = 0; i < n; i++) {p[i].completion_time = time + p[i].burst_time;time = p[i].completion_time;}}void gantt(struct process p[], int n) {printf(" ");for (int i = 0; i < n; i++) {for (int j = 0; j < p[i].burst_time; j++) {printf("--");}printf(" ");}printf("\n|");for (int i = 0; i < n; i++) {for (int j = 0; j < p[i].burst_time - 1; j++) {printf(" ");}printf("P%d", p[i].pid);for (int j = 0; j < p[i].burst_time - 1; j++) {printf(" ");}printf("|");}printf("\n ");for (int i = 0; i < n; i++) {for (int j = 0; j < p[i].burst_time; j++) {printf("--");}printf(" ");}printf("\n");}int main() {struct process p[5] = {{1, 0, 3, 0},{2, 1, 5, 0},{3, 2, 1, 0},{4, 3, 2, 0},{5, 4, 4, 0}};sjf(p, 5);printf("PID\tAT\tBT\tCT\n");for (int i = 0; i < 5; i++) {printf("%d\t%d\t%d\t%d\n", p[i].pid, p[i].arrival_time, p[i].burst_time, p[i].completion_time);}gantt(p, 5);return 0;}In this program, we have defined a gantt function that creates a Gantt chart for the processes. The function uses two for loops to print the horizontal bars and process IDs, and calculates the start and end times based on the completion time of each process.
The main function calls the sjf function to calculate the completion time for each process, and then calls the gantt function to create the Gantt chart.
Conclusion
In this article, we have discussed the SJF scheduling algorithm and how to implement it in C programming language. We have also discussed how to create a Gantt chart to visualize the schedule of processes. The SJF scheduling algorithm is a popular algorithm used in operating systems, and understanding how it works is essential for any computer science student or professional.