SJF Scheduling Program in C

In this article, we will learn what is shortest job scheduling, the Algorithm of shortest job scheduling, the characteristics of the shortest job first algorithm, the shortest job scheduling algorithm with an example, the SJF scheduling program in c., the advantages of the shortest job first scheduling, and the disadvantages of the shortest job first scheduling.

What is the shortest job scheduling?

The shortest job first is one of the CPU scheduling algorithms. It is an algorithm in which the process depends on its burst time. In short, a process that has less burst time takes first place in the execution. The shortest job first (SJF) is also known as the shortest job next (SJN). For example, we have 4 processes P1, P2, P3, and P4 with burst times of 5, 7, 6, and 2. Now, first, process P4 will be executed as it has less burst time. After that, processes P1, P3, and P2 will be executed respectively.

Shortest job first scheduling Algorithm :

Below are the steps to perform the SJF scheduling program in c.

  • Firstly, we will begin the procedure.
  • After that, we will Consider the number of elements to be inserted.
  • Then, we will choose the process with the shortest burst time and will execute the first process.
  • We will check that if both processes have the same burst time length then the FCFS scheduling algorithm is used.
  • We will make the average waiting time for the next process.
  • We will begin with the first process, make the above selection, and place the other processes in a queue.
  • We will calculate burst time.
  • We will display the values that are related.
  • In the end, we will stop the process.
  • Likewise, we will run all the steps until all the processes are executed.

Characteristics of shortest job scheduling:

  • It is a Greedy algorithm.
  • It is useful for batch processing.
  • Among all scheduling algorithms, Shortest Job First has the advantage of having the shortest average waiting time.
  • It increases job output by providing shorter jobs that should be completed first and usually have a shorter turnaround time.

Shortest job scheduling algorithm with an example:

Let’s see how the shortest job first scheduling algorithm works with an example. Here, we have taken an example to understand the working of the algorithm. We will also do a dry run to understand it better.

In the above example, we have taken 4 processes P1, P2, P3, and P4 with an arrival time of 1,2,1, and 4 respectively. They also have burst times 3, 4, 2, and 4 respectively. Now, we need to create two queues the ready queue and the running queue which is also known as the Gantt chart.

Step 1: First, we will sort all the processes according to their arrival time.

In the above image, we can see that after performing a sort on arrival time order of the processes changes to P1, P3, P2, and P4.

Step 2: We will push all the processes into the ready queue with an arrival time of 0. In this example, we do not have processes that have 0 arrival times which is why we will push processes that have an arrival time of 1. In this example, we have P1 And P3 with an arrival time of 1. For time 0-1 running queue is in the ideal mode.

This is how queues will look after the completion of the second step.

In the above image, we can see that first process P3 is pushed into the ready queue and after that, process P1 is pushed. While running queue is in the ideal condition.

Step 3: After that, we will select a process that comes at an arrival time of 1 from the ready queue which has a minimum burst time. Here, P3 has the least burst time which is 2 and it is moved into the running queue. That’s why P3 is executed first.

Step 4: During the execution of P3, we will push P2 into the ready queue that has an arrival time of 2 because P3 runs till time 3. Now, in the ready queue, there are 2 processes available: P1, P2

Step 5: P3 finishes at time 3. Again we will select a process from the ready queue that has minimum burst time. In our ready queue, we have 2 processes P1 and P2. Among them, P1 has the minimum burst time which is 3. Then P1 enters into the running queue and it is executed till time 6.

Step 6: During the execution of P1, we will push P4 into the ready queue that has an arrival time of 4 because P1 runs till time 6. Now, in the ready queue, there are 2 processes available: P2, P4

After this, we do not have any new process to add to the ready queue so we will not modify the running queue.

Step 7: P1 completes on time 6. Again, we will choose a process from the ready queue with the shortest burst time. We have two processes in our ready queue: P2 and P4. In this case, both processes (P2, P4) have equal burst time which is 4. That is why we will select a process that has a minimum arrival time. So, P2 came on time 2 and P4 came on time 4 but P2 has a minimum arrival time compared to P4. That is why P2 is then added to the running queue and executed until time 10.

After this, we do not have any new process to add to the ready queue so we will not modify the running queue.
Step 8: P2 completes on time 10. Now, we have only one process (P4) in the ready queue which has burst time 4. P4 is moved to the running queue and executed until time 14.

After performing all the operations, our running queue also known as the Gantt chart will look like the below.

Let’s calculate the other terms like Completion time, Turn Around Time (TAT), Waiting Time (WT), and Response Time (RT). Below are the equations to calculate the above terms.

Turn Around Time = Completion Time – Arrival Time
Waiting Time = Turn Around Time – Burst Time

Average waiting time = Addition of waiting time of all processes divided by the number of processes

SJF scheduling program in C:

We have already seen what is SJF scheduling and how SJF scheduling works. Now, We will see how to write the SJF scheduling program in c. We will use the above algorithm to write the SJF scheduling program in c.

// SJF scheduling program in c
#include<string.h>
int main()
{
    int bt[20],at[10],n,i,j,temp,st[10],ft[10],wt[10],ta[10];
    int totwt=0,totta=0;
    double awt,ata;
    char pn[10][10],t[10];
    //clrscr();
    printf("Enter the number of process:");
    scanf("%d",&n);
    for(i=0; i<n; i++)
    {
        printf("Enter process name, arrival time& burst time:");
        scanf("%s%d%d",pn[i],&at[i],&bt[i]);
    }
    for(i=0; i<n; i++)
        for(j=0; j<n; j++)
        {
            if(bt[i]<bt[j])
            {
                temp=at[i];
                at[i]=at[j];
                at[j]=temp;
                temp=bt[i];
                bt[i]=bt[j];
                bt[j]=temp;
                strcpy(t,pn[i]);
                strcpy(pn[i],pn[j]);
                strcpy(pn[j],t);
            }
        }
    for(i=0; i<n; i++)
    {
        if(i==0)
            st[i]=at[i];
        else
            st[i]=ft[i-1];
        wt[i]=st[i]-at[i];
        ft[i]=st[i]+bt[i];
        ta[i]=ft[i]-at[i];
        totwt+=wt[i];
        totta+=ta[i];
    }
    awt=(double)totwt/n;
    ata=(double)totta/n;
    printf("\nProcessname\tarrivaltime\tbursttime\twaitingtime\tturnaroundtime");
    for(i=0; i<n; i++)
    {
        printf("\n%s\t%5d\t\t%5d\t\t%5d\t\t%5d",pn[i],at[i],bt[i],wt[i],ta[i]);
    }
    printf("\nAverage waiting time: %f",awt);
    printf("\nAverage turnaroundtime: %f",ata);
    return 0;
}

Output

Enter the number of process:4
Enter process name, arrival time& burst time:
1
1 
3
Enter process name, arrival time& burst time:
2
2
4
Enter process name, arrival time& burst time:
3
1
2
Enter process name, arrival time& burst time:
4
4
4
Process name Arrival time Burst time Waiting time Turnaround time
3 1 2 0 2
1 1 3 2 5
2 2 4 4 8
4 4 4 6 10

Average waiting time: 3.000000
Average turnaround time: 6.250000

Advantages of the SJF scheduling algorithm:

  • Processes with the shortest burst time will be prioritized.
  • It is very effective as this algorithm produces a minimum average waiting time.

Disadvantages of the SJF scheduling algorithm:

  • If short processes come again and again they can cause starvation. We can solve this problem by aging.
  • We can not use this algorithm for the implementation of short-term CPU scheduling.

Leave a Reply

Your email address will not be published. Required fields are marked *