Write an SJF scheduling program in C to determine the average waiting time and average turnaround time given n processes and their burst times.
SJF Scheduling Algorithm in C:
The CPU scheduling algorithm Shortest Job First (SJF), allocates the CPU to the processes according to the process with smallest execution time.
SJF uses both preemptive and non-preemptive scheduling. The preemptive version of SJF is called SRTF (Shortest Remaining Time First). Here we will discuss about SJF i.e., the non-preemptive scheduling.
- It has the minimum waiting time among all the scheduling algorithms.
- A process having larger burst time may get into starvation but the problem can be solved using concept of Ageing.
- It is a greedy algorithm and provides optimal scheduling.
1. Enter number of processes.
2. Enter the burst time of all the processes.
3. Sort all the processes according to their burst time.
4. Find waiting time, WT of all the processes.
5. For the smallest process, WT = 0.
6. For all the next processes i, find waiting time by adding burst time of all the previously completed process.
7. Calculate Turnaround time = WT + BT for all the processes.
8. Calculate average waiting time = total waiting time / no. of processes.
9. Calculate average turnaround time= total turnaround time / no. of processes.
SJF Example:
Process | Arrival Time | Burst Time |
---|---|---|
P1 | 0 | 5 |
P2 | 0 | 4 |
P3 | 0 | 12 |
P4 | 0 | 7 |
Gantt Chart:
Waiting Time: Time Difference between turnaround time and burst time.
Waiting Time = Turnaround Time – Burst Time
P1 waiting time: 4
P2 waiting time: 0
P3 waiting time: 16
P4 waiting time: 9
Average Waiting Time = (4 + 0 + 16 + 9)/4 = 29/4 = 7.25
Turnaround Time: Difference between completion time and arrival time.
Turnaround Time = Completion Time – Arrival Time
P1 turnaround time: 9-0 = 9
P2 turnaround time: 4-0 = 4
P3 turnaround time: 28-0 = 28
P4 turnaround time: 16-0 = 16
Average Turnaround Time = (9 + 4 + 28 + 16)/4 = 14.25
Here is the source code of the C Program to Implement SJF Scheduling. The C program is successfully compiled and run on a Linux system. The program output is also shown below.
/*
* C Program to Implement SJF Scheduling
*/
#include<stdio.h>
int main()
{
int bt[20],p[20],wt[20],tat[20],i,j,n,total=0,totalT=0,pos,temp;
float avg_wt,avg_tat;
printf("Enter number of process:");
scanf("%d",&n);
printf("\nEnter Burst Time:\n");
for(i=0;i<n;i++)
{
printf("p%d:",i+1);
scanf("%d",&bt[i]);
p[i]=i+1;
}
//sorting of burst times
for(i=0;i<n;i++)
{
pos=i;
for(j=i+1;j<n;j++)
{
if(bt[j]<bt[pos])
pos=j;
}
temp=bt[i];
bt[i]=bt[pos];
bt[pos]=temp;
temp=p[i];
p[i]=p[pos];
p[pos]=temp;
}
wt[0]=0;
//finding the waiting time of all the processes
for(i=1;i<n;i++)
{
wt[i]=0;
for(j=0;j<i;j++)
//individual WT by adding BT of all previous completed processes
wt[i]+=bt[j];
//total waiting time
total+=wt[i];
}
//average waiting time
avg_wt=(float)total/n;
printf("\nProcess\t Burst Time \tWaiting Time\tTurnaround Time");
for(i=0;i<n;i++)
{
//turnaround time of individual processes
tat[i]=bt[i]+wt[i];
//total turnaround time
totalT+=tat[i];
printf("\np%d\t\t %d\t\t %d\t\t\t%d",p[i],bt[i],wt[i],tat[i]);
}
//average turnaround time
avg_tat=(float)totalT/n;
printf("\n\nAverage Waiting Time=%f",avg_wt);
printf("\nAverage Turnaround Time=%f",avg_tat);
}
1. Initialize two array pid[] and bt[] of size 20.
2. Ask the user for number of processes n.
3. Ask the user for process id and burst time for all n processes and store them into pid[] and bt[] respectively.
4. Sort all the processes according to their burst time.
5. Assign waiting time = 0 to the smallest process.
6. Calculate waiting time of each process by using two loops and adding all the burst time of previously completed processes.
7. Print Process Id, Burst Time, waiting time and Turnaround time of each process in tabular manner.
8. Calculate and print turnaround time of each process = bt[i] + wt[i].
9. Add waiting time of all the processes and store it in the variable total.
10. Add turnaround time of all the processes and store it in the variable totalT.
11. Calculate average waiting time as avg_wt = total/n.
12. Calculate average turnaround time as avg_tat = totalT/n;
13. Print average waiting time and average turnaround time.
14. Exit.
Time Complexity: O(n2)
The above program for implementing SJF Scheduling has a time complexity of O(n2), as the for loop runs for n^2 times for calculating waiting time of each process.
Space Complexity: O(n)
In the SJF Scheduling program, space complexity is O(n) as arrays of size n have been initialized to store the values in it.
In this case, we enter “3” as the number of processes, and the burst time are “p1: 5”, “p2: 4”, “p3: 12”, and “p4: 7” to find average waiting time and average turnaround time using SJF Scheduling algorithm.
Enter number of process:4 Enter Burst Time: p1:5 p2:4 p3:12 p4:7 Process Burst Time Waiting Time Turnaround Time p2 4 0 4 p1 5 4 9 p4 7 9 16 p3 12 16 28 Average Waiting Time=7.250000 Average Turnaround Time=14.250000
To practice programs on every topic in C, please visit “Programming Examples in C”, “Data Structures in C” and “Algorithms in C”.
- Get Free Certificate of Merit in C Programming
- Participate in C Programming Certification Contest
- Become a Top Ranker in C Programming
- Take C Programming Tests
- Chapterwise Practice Tests: Chapter 1, 2, 3, 4, 5, 6, 7, 8, 9, 10
- Chapterwise Mock Tests: Chapter 1, 2, 3, 4, 5, 6, 7, 8, 9, 10
- Apply for C Internship
- Buy Computer Science Books
- Practice Computer Science MCQs
- Buy C Books
- Watch Advanced C Programming Videos