SJF Scheduling Program in C

Problem Description:

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.

Advantages of SJF:

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.

Problem Solution

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:

Sanfoundry Certification Contest of the Month is Live. 100+ Subjects. Participate Now!

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

Check this: Computer Science Books | BCA MCQs

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

Program/Source Code

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);

```
}
```

Program Explanation

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²)
The above program for implementing SJF Scheduling has a time complexity of O(n²), 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.

Run Time Testcases

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”.

« Prev - Round Robin Scheduling Program in C

» Next - Pyramid Patterns in C

Next Steps: