Shortest Job First (SJF) Scheduling algorithm Program in C | non-preemptive

Shortest Job First (SJF) is a CPU Scheduling algorithm in which allocation of CPU is based on burst time. The job having less burst time will get scheduled first.

Formula for computing SJF

  1. Completion time:(CT)  The completion time is a time when a process completes its execution.
  2. waiting time(WT): it is a time difference between turn-around time and burst time. Waiting Time (WT)=Turn-around time (TAT) - burst time (BT)
  3. Turn-around time(TAT): It is the time difference between completion time and arrival time. Turn-around time (TAT)= Completion time (CT) - Arrival Time (AT)

shortage Job First (SJF) Algorithm

  1. Take process, arrival time, burst time input from the user.
  2. Sort the process according to arrival time and if the process has the same arrival time then sort them having less burst time.
  3. Swap the process one above one in the order of execution.
  4. Find the turnaround time (tat) and waiting time (wt).
  5. Find average tat and average wt.

Shortest Job First (SJF) program with arrival time and completion time


#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
void swap(int *x, int *y)
{
    int temp=*x;
    *x=*y;
    *y=temp;
}
void sortat(int p[], int at[], int bt[], int n)
{
  int i, j;
  for(i=0;i<n;i++)
  {
      for(j=i+1;j<n;j++)
      {   /* sort the process having less arrival*/
	  if(at[i]>at[j])
	  { 
	        swap(&p[i], &p[j]);
		swap(&at[i], &at[j]);
		swap(&bt[i], &bt[j]);
	   }
           /* if two processes have the same arrival time than sort them having less burst time */
	   else if(at[i]==at[j])
	   {
	      if(bt[i]>bt[j])
                 swap(&p[i], &p[j]);
                 swap(&at[i], &at[j]);
                 swap(&bt[i], &bt[j]);
	   }
       }
  }
}
/* calculate turnaround time and waiting time */
void tatwt( int ct[], int at[], int bt[], int tat[], int wt[], int n)
{
   int i;
   for(i=0;i<n;i++)
   {
	tat[i]=ct[i]-at[i];
	wt[i]=tat[i]-bt[I];
   }
}
int main()
{
  int *p, *at, *bt, *tat, *wt, *ct, pos, i, j, min=1000, n;
  float awt=0, atat=0;
  printf("\nenter the number of process:");
  scanf("%d", &n);
  p=(int*)malloc(n*sizeof(int));
  at=(int*)malloc(n*sizeof(int));
  bt=(int*)malloc(n*sizeof(int));
  ct=(int*)malloc(n*sizeof(int));
  wt=(int*)malloc(n*sizeof(int));
  tat=(int*)malloc(n*sizeof(int));
  printf("enter the process");
  for(i=0;i<n;i++)
  {
	scanf("%d",&p[i]);
  }
  printf("enter the arrival time");
  for(i=0;i<n;i++)
  {
	scanf("%d",&at[i]);
  }
  printf("enter the burst time");
  for(i=0;i<n;i++)
  {
	scanf("%d",&bt[i]);
  }
  sortat(p, at, bt, n);
  ct[0]=at[0] + bt[0];
  for(i=1; i<n; i++)
  {
	for(j=i; j<n; j++)
	{
	    if(at[j]<=ct[i-1])
	   {
              if(bt[j]<min)
              {
                 min=bt[j];
                 pos=j;
              }
	   }
	}
   /*  when you get less burst time process, swap p, at, bt at position 2,
    and when getting 2nd less burst time swap at position 3rd and so on.  */
    swap(&p[i], &p[pos]);
    swap(&at[i], &at[pos]);
    swap(&bt[i], &bt[pos]);
    min=1000;
    ct[i]=ct[i-1]+bt[i];
  }
  tatwt(ct, at, bt, tat, wt, n);
  printf("\np\t at\t bt\t ct\t tat\t wt"); 
  for(i=0;i<n;i++)
  {
    printf("\n%d\t %d\t %d\t %d\t %d\t %d",p[i], at[i], bt[i], ct[i], tat[i], wt[i]);
  }
  for(i=0;i<n;i++)
  { 
    atat+=tat[i];
    awt+=wt[i];
  }
  // average turnaround time and average waiting time
  atat=atat/n;
  awt=awt/n;
  printf("\n avg tat=%.2f and avg wt=%.2f",atat, awt); 
  return 0;
}

output

enter the number of process:4
enter the process 1 2 3 4
enter the arrival time 0 2 2 0
enter the burst time 5 3 1 3

p        at      bt      ct      tat     wt
4        0       3       3       3       0
3        2       1       4       2       1
2        2       3       7       5       2
1        0       5       12      12      7
avg tat=5.50 and avg wt=2.50
Shortest Job First (SJF) Scheduling algorithm program in C

Gantt Chart

Gantt chart of above output

Gantt Chart of Shortest Job First (SJF) Scheduling algorithm

explanation of Shortest Job First (SJF) program 

  1. Take p, at, bt input from the user and store it in our dynamic declare array size pointer i.e *p, *at, *bt.
  2. Sort the p, at, bt according to arrival time (at) and if a process has the same arrival time then you will sort them which has less burst time.
  3. After sorting, calculate the first completion time. For example, if the first completion time is 3 and two processes come for scheduling then check which process has less burst time and swap them at position 2nd, now find the next min burst time and swap them at position 3rd do the same for other processes.
  4. after swapping, call tatwt() function, it will find the turn-around time ( TAT) time and waiting time (WT).
  5. calculate average tat and average wt.