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(n ^{2})**

The above program for implementing SJF Scheduling has a time complexity of O(n

^{2}), 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”.

**If you find any mistake above, kindly email to [email protected]**

**Related Posts:**

- Practice Computer Science MCQs
- Check C Books
- Apply for Computer Science Internship
- Watch Advanced C Programming Videos
- Apply for C Internship