Operating Systems -Scheduling Algorithms Made Easy : SJF

Introduction

Shortest Job First(SJF) supports both preemptive and non-preemptive scheduling. This algorithm associates with each process the length of the process’s next CPU burst. When the CPU is available, it is assigned to the process that has the smallest next CPU burst. If the next CPU bursts of two processes are the same, FCFS scheduling is used to break the tie. Shortest Remaining time first(SRTF) is the Shortest Job First(SJF) scheduling algorithm in preemptive mode.

Explanation

The SJF scheduling algorithm is provably optimal, in that it gives the minimum average waiting time for a given set of processes. Moving a short process before a long one decreases the waiting time of the short process more than it increases the waiting time of the long process. Consequently, the average waiting time decreases.
In SRTF, the execution of the process can be stopped after certain amount of time. The short term scheduler schedules processes with least amount of burst time among available and running processes.
Once all the processes are available in the ready queue, No preemption will be done and the algorithm will work as SJF scheduling. The context of the process is saved in the Process Control Block when the process is removed from the execution and the next process is scheduled. This PCB is accessed on the next execution of this process.

• Advantages:

  • Maximum throughput
  • SJF is optimal, gives minimum average waiting time for a set of processes.
  • SRTF is faster in execution than SJF.

• Disadvantages:

  • In SJF, if there are more number of shorter jobs, then longer jobs starve.

Code

Non-preemptive SJF Scheduling

#include <stdio.h>
#include <string.h>

int main()
{
  struct SJF
  {
    char pn[100];
    int bt,wt,tat;
  }b[100];
  int sum1=0,sum2=0,i,j,temp,n;
  float avg1=0,avg2=0;
  char t1[100];
  printf("Enter number of processes:\n");
  scanf("%d",&n);
  printf("Enter process names and burst times:\n");
  for(i=0;i<n;i++)
  {
    scanf("%s",b[i].pn);
    scanf("%d",&b[i].bt);
  }
  for(j=0;j<n;j++)
  {
    for(i=0;i<n-1;i++)
    {
      if(b[i].bt>b[i+1].bt)
      {
        temp=b[i].bt;
        b[i].bt=b[i+1].bt;
        b[i+1].bt=temp;
        strcpy(t1,b[i].pn);
        strcpy(b[i].pn,b[i+1].pn);
        strcpy(b[i+1].pn,t1);
      }
    }
  }
  b[0].wt=0;
  for(i=0;i<n;i++)
    {
      b[i+1].wt=b[i].bt+b[i].wt;
      b[i].tat=b[i].wt+b[i].bt;
    }
  printf("PN\tBT\tWT\tTAT\n");
  for(i=0;i<n;i++)
    {
      sum1+=b[i].wt; 
      sum2+=b[i].tat;
      printf("%s\t%d\t%d\t%d\n",b[i].pn,b[i].bt,b[i].wt,b[i].tat);
    }
  avg1=(float)sum1/n;
  avg2=(float)sum2/n;
  printf("Average waiting time: %.2f\n",avg1);
  printf("Average turnaround time: %.2f\n",avg2);
  return 0;
}

Sample Input and Output

Input:

Enter number of processes:

4

Enter process names and burst times:

P1 6

P2 8

P3 7 

P4 3

Output:

PN  BT  WT  TAT

P4  3   0   3

P1  6   3   9

P3  7   9   16

P2  8   16  24

Average waiting time: 7.00

Average turnaround time: 13.00

SRTF: Preemptive SJF Scheduling:

#include<stdio.h>
#include<string.h>
void main()
{
    struct SJF
    {
        char pn[10];
        int bt,wt,tat,at;
    }b[100];
    int i,j,n,sum1=0,sum2=0,z=0,cnt=0;
    float avg1=0,avg2=0;
    printf("Enter the number of processes:\n");
    scanf("%d",&n);
    printf("Enter process names, burst times and arrival times:\n");
    for(i=1;i<=n;i++)
        scanf("%s %d %d",b[i].pn,&b[i].bt,&b[i].at);
    for(i=1;i<=n;i++)
    {
        for(j=i;j<=n;j++)
        {
            if(b[i].at>b[j].at)
            {

                int t=b[i].bt;
                b[i].bt=b[j].bt;
                b[j].bt=t;
                char temp[10];
                strcpy(temp,b[i].pn);
                strcpy(b[i].pn,b[j].pn);
                strcpy(b[j].pn,temp);
                t=b[i].at;
                b[i].at=b[j].at;
                b[j].at=t;
            }
        }
    }
    char temp[10];
    for(i=1;i<=n;i++)
    {
        cnt+=b[i].bt;
        for(j=i+1;j<=n;j++)
        {
            if(b[i+1].at<=cnt && b[i+1].bt>b[j].bt && b[j].at<=cnt)
            {
                //swap burst times
               int t=b[i+1].bt;
                b[i+1].bt=b[j].bt;
                b[j].bt=t;
                //swap process names
                strcpy(temp,b[i+1].pn);
                strcpy(b[i+1].pn,b[j].pn);
                strcpy(b[j].pn,temp);
                //swap arrival times
                t=b[i+1].at;
                b[i+1].at=b[j].at;
                b[j].at=t; 
            }
        }
    }
    b[1].wt=0;
    for(i=1;i<=n;i++)
    {
        b[i+1].wt=b[i].wt+b[i].bt+b[i].at-b[i+1].at;
        b[i].tat=b[i].wt+b[i].bt;
    }
    printf("PN\tBT\tAT\tWT\tTAT\n");
    for(i=1;i<=n;i++)
    {
        sum1=sum1+b[i].wt;
        sum2=sum2+b[i].tat;
        printf("%s\t%d\t%d\t%d\t%d\n",b[i].pn,b[i].bt,b[i].at,b[i].wt,b[i].tat);
    }
    avg1=(float)sum1/n;
    printf("Average waiting time: %.2f\n",avg1);
    avg2=(float)sum2/n;
    printf("Average turnaround time: %.2f\n",avg2);
}

Sample Input and Output

Input:

Enter the number of processes:

4

Enter process names, burst times and arrival times:

P1 8 0

P2 4 1

P3 9 2

P4 5 3

Output:

PN  BT  AT  WT  TAT

P1  8   0   0   8

P2  4   1   7   11

P4  5   3   9   14

P3  9   2   15  24

Average waiting time: 7.75

Average turnaround time: 14.25

Complexity Analysis

• Time Complexity:

  • Best Case : O(n)
  • Average Case : O(n²)
  • Worst Case : O(n²)

• Space Complexity : O(1)