How Is Shortest Job First Scheduling Performed In Operating Systems?

Introduction

An operating system’s main task is to allocate the resources and hereby schedule the processes. So once a process has been received, the process scheduler schedules its execution. This process is later assigned to the CPU. Now, this process scheduling can be performed in many ways.

There are six well-known process scheduling algorithms, namely:

• First Come First Serve (FCFS)
• Shortest-Job-First (SJF)
• Priority Scheduling
• Shortest Remaining Time First (SRTF)
• Round Robin (RR)
• Multi-Level Queues Scheduling

Out of these, we will be discussing Shortest-Job-First (SJF) Scheduling.

Shortest Job First Scheduling

Shortest-Job-First Scheduling is said to be the best process scheduling approach as it minimises the waiting time of the other processes awaiting their execution. It is also referred to as Shortest-Job-Next owing to its characteristic, to schedule the job with the minimum time as next. It is both preemptive and non-preemptive. Let us see some of its characteristics-:

• It suits best in Batch-type Systems where the CPU time i.e Burst Time, is known beforehand and process execution is not that critical.
• It is associated with each process as a unit of time to be completed.
• It can increase output by offering a short process time, i.e the short processes are executed first.
• Since the jobs which need less time are executed first, it increases the throughput time as well.
• The algorithm works the best when the arrival time for all processes is the same.

Before moving ahead let us learn about some key factors that play a significant role in scheduling.

• Arrival Time: Time at which a process/job arrives
• Burst Time: Time needed to complete the execution
• Completion Time: Actual time is taken to complete the execution of process/job
• Turn around Time: The difference between completion time and arrival time

Turn Around Time=Completion Time-Arrival Time

• Waiting Time: The difference between turn around time and burst time.

Waiting Time=Turn around Time-Burst Time

There are two types of Shortest-Time-First scheduling algorithms, preemptive and non-preemptive. Let us see them in detail.

Shortest-Job-First Preemptive Scheduling 

In Shortest-Job-First Preemptive Scheduling, processes are put into the ready queue as soon as they arrive. Then according to the algorithm, the process with the shortest burst time will begin its execution ahead of others.

If a process with the least short time arrives, the current process in execution will be stopped and preempted from the execution, and the shortest process is allocated to the CPU cycle. However, the current state of the currently executing process will be saved, when the CPU is allocated to another process.

Let us see an example of Shortest-Job-First Preemptive Scheduling

Let us suppose this example where we have four processes, their process id, arrival time, and burst time is given to us. Now we have to fin the completion time, turn around time, and waiting time.

Solution:

Let us use the Gantt Chart for the above-given problem.

Now we know that the waiting time and turnaround time is completed using the following formulas-:

Turn Around Time=Completion Time-Arrival Time
Waiting Time=Turnaround Time-Burst Time

So now after calculating the Completion Time, Waiting Time, and Turn Around Time we get:

Average Waiting Time: (13+0+5+2)/4=20
Average Turn-Around Time: (31+4+12+4)/4=12.75

Shortest-Job-First Non-Preemptive Scheduling

In Shortest-Job-First Non-Preemptive Scheduling the process currently in execution is not preempted when a new short-time process arrives, unlike in Shortest-Time-First Preemptive Scheduling. So now suppose, there is a process currently in execution with a burst time of 16.

And a new process arrives that has a burst time of 9, still, the processor will not stop the execution. The execution-only stops when the process has either been terminated or completed. 

Now, this non-preemptive nature of scheduling sometimes creates a problem called Starvation. It is that state in which a process with a short burst time has to wait until the other process finishes its execution. This causes an unnecessary wait. 

However, this can be avoided by sending the new process only after a certain duration, i.e delaying the arrival of a process. This is called Ageing.

Now let us see a problem with Shortest-Job-First Non-Preemptive Scheduling. So here we have the processes with their process id, burst time, and arrival time is given.

Solution:

Let us use the Gantt Chart for the above-given problem.

Now we know that the waiting time and turnaround time is completed using the following formulas:

Turn Around Time=Completion Time-Arrival Time
Waiting Time=Turn around Time-Burst Time

So now after calculating the Completion Time, Waiting Time and Turn Around Time we get:

Average Waiting Time-: (8+0+3+4)=3.75
Average Turn-Around Time-: (16+5+12+6)=9.75

Algorithm & Implementation

To implement the Shortest-Job-First with Arrival Time Scheduling algorithm, we will implement the following steps:

• Sort all the processes according to their time of arrival.
• Then sort all the processes according to their burst time and choose the one with both minimum arrival time and burst time.
• After the completion of the process, make a pool of processes that execute till the completion of the previous process and then select the process from the pool having minimum Burst Time.

Now let us implement the above algorithm in C, C++, and Java.

Shortest-Job-First with Arrival Time Scheduling in C++

#include<bits/stdc++.h>

using namespace std;
 
struct Process
{
   int pid;     // process ID
   int bt;      // burst Time
};
 
/* 
    this function sorts all of the
    processes in the increasing order of their burst time
*/
bool comparison(Process a, Process b)
{
    return (a.bt < b.bt);
}
 
// this function finds waiting time for all the processes
void findWaitingTime(Process proc[], int n, int wt[])
{
    // waiting time for first process is 0
    wt[0] = 0;
 
    // calculating waiting time
    for (int i = 1; i < n ; i++)
    {
        wt[i] = proc[i-1].bt + wt[i-1] ;
    }
}
 
// function to calculate turn around time
void findTurnAroundTime(Process proc[], int n, int wt[], int tat[])
{
    // calculating turnaround time by adding bt[i] + wt[i]
    for (int i = 0; i < n ; i++)
    {
        tat[i] = proc[i].bt + wt[i];
    }
}
 
// function to calculate average time
void findAverageTime(Process proc[], int n)
{
    int wt[n], tat[n], total_wt = 0, total_tat = 0;
 
    // function finds the waiting time of all of the processes
    findWaitingTime(proc, n, wt);
 
    // this function finds the turn around time for all processes
    findTurnAroundTime(proc, n, wt, tat);
 
    // this function displays the processes along with all their details
    cout << "\nProcesses "<< " Burst time "
         << " Waiting time " << " Turn around time\n";
 
    // calculate total waiting time and total turn around time
    for (int i = 0; i < n; i++)
    {
        total_wt = total_wt + wt[i];
        total_tat = total_tat + tat[i];
        cout << " " << proc[i].pid << "\t\t"
             << proc[i].bt << "\t " << wt[i]
             << "\t\t " << tat[i] <<endl;
    }
 
    cout << "Average waiting time = "
         << (float)total_wt / (float)n;
    cout << "\nAverage turn around time = "
         << (float)total_tat / (float)n;
}
 
// main function
int main()
{
    Process proc[] = {{1, 21}, {2, 3}, {3, 6}, {4, 2}};
    int n = sizeof proc / sizeof proc[0];
 
    // sorting processes by burst time.
    sort(proc, proc + n, comparison);
 
    cout << "Order in which process gets executed\n";
    for (int i = 0 ; i < n; i++)
    {
        cout << proc[i].pid <<" ";
    }
 
    findAverageTime(proc, n);
    
    return 0;
}

Shortest-Job-First Scheduling with Arrival Time in C

#include<stdio.h>
#include<conio.h>
#include<string.h>
void main()
{
    int et[20],at[10],n,i,j,temp,st[10],ft[10],wt[10],ta[10];
    int totwt=0,totta=0;
    float 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& execution time:");
        //flushall();
        scanf("%s%d%d",pn[i],&at[i],&et[i]);
    }
    for(i=0; i<n; i++)
        for(j=0; j<n; j++)
        {
            if(et[i]<et[j])
            {
                temp=at[i];
                at[i]=at[j];
                at[j]=temp;
                temp=et[i];
                et[i]=et[j];
                et[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]+et[i];
        ta[i]=ft[i]-at[i];
        totwt+=wt[i];
        totta+=ta[i];
    }
    awt=(float)totwt/n;
    ata=(float)totta/n;
    printf("\nPname\tarrivaltime\texecutiontime\twaitingtime\ttatime");
    for(i=0; i<n; i++)
        printf("\n%s\t%5d\t\t%5d\t\t%5d\t\t%5d",pn[i],at[i],et[i],wt[i],ta[i]);
    printf("\nAverage waiting time is:%f",awt);
    printf("\nAverage turnaroundtime is:%f",ata);
    getch();
}

Shortest-Job-First Scheduling with Arrival Time in JAVA

import java.util.*;

class GFG {

	static int[][] mat = new int[10][6];

	static void arrangeArrival(int num, int[][] mat) {
		for (int i = 0; i < num; i++) {
			for (int j = 0; j < num - i - 1; j++) {
				if (mat[j][1] > mat[j + 1][1]) {
					for (int k = 0; k < 5; k++) {
						int temp = mat[j][k];
						mat[j][k] = mat[j + 1][k];
						mat[j + 1][k] = temp;
					}
				}
			}
		}
	}

	static void completionTime(int num, int[][] mat) {
		int temp, val = -1;
		mat[0][3] = mat[0][1] + mat[0][2];
		mat[0][5] = mat[0][3] - mat[0][1];
		mat[0][4] = mat[0][5] - mat[0][2];

		for (int i = 1; i < num; i++) {
			temp = mat[i - 1][3];
			int low = mat[i][2];
			for (int j = i; j < num; j++) {
				if (temp >= mat[j][1] && low >= mat[j][2]) {
					low = mat[j][2];
					val = j;
				}
			}
			mat[val][3] = temp + mat[val][2];
			mat[val][5] = mat[val][3] - mat[val][1];
			mat[val][4] = mat[val][5] - mat[val][2];
			for (int k = 0; k < 6; k++) {
				int tem = mat[val][k];
				mat[val][k] = mat[i][k];
				mat[i][k] = tem;
			}
		}
	}

	// Driver Code
	public static void main(String[] args) {
		int num;

		Scanner sc = new Scanner(System.in);

		System.out.println("Enter number of Process: ");
		num = sc.nextInt();

		System.out.println("...Enter the process ID...");
		for (int i = 0; i < num; i++) {
			System.out.println("...Process " + (i + 1) + "...");
			System.out.println("Enter Process Id: ");
			mat[i][0] = sc.nextInt();
			System.out.println("Enter Arrival Time: ");
			mat[i][1] = sc.nextInt();
			System.out.println("Enter Burst Time: ");
			mat[i][2] = sc.nextInt();
		}

		System.out.println("Before Arrange...");
		System.out.println("Process ID\tArrival Time\tBurst Time");
		for (int i = 0; i < num; i++) {
			System.out.printf("%d\t\t%d\t\t%d\n",
				mat[i][0], mat[i][1], mat[i][2]);
		}

		arrangeArrival(num, mat);
		completionTime(num, mat);
		System.out.println("Final Result...");
		System.out.println("Process ID\tArrival Time\tBurst" +
						" Time\tWaiting Time\tTurnaround Time");
		for (int i = 0; i < num; i++) {
			System.out.printf("%d\t\t%d\t\t%d\t\t%d\t\t%d\n",
			mat[i][0], mat[i][1], mat[i][2], mat[i][4], mat[i][5]);
		}
		sc.close();
	}
}

So now you know about Shortest-Time-First Scheduling, let us discuss some of its advantages and disadvantages.

Advantages of Shortest-Job-First Scheduling

So the advantages of Shortest-Time-First Scheduling are:

• It is frequently used for long term scheduling.
• Shortest-Time-First Scheduling reducing the average waiting time.
• It gives the average waiting time for some specific processes.
• It is beneficial for the processes running in batches, where the running times are known in advance.
• For short-term scheduling, the value of the next burst time needs to be predicted.
• Shortest-Time-First Scheduling is optimal about the average turnaround time.

Disadvantages of Shortest-Job-First Scheduling

So the disadvantages of Shortest-Time-First Scheduling are:

• In the Shortest-Time-First Scheduling job, scheduling should be known from before, but it’s quite difficult to predict.
• Shortest-Time-First Scheduling is often used for long-term scheduling in batch systems.
• Shortest-Time-First Scheduling cannot be implemented for short-term CPU scheduling. It is because there is no such defined method for predicting Burst Time.
• It may cause starvation and does not reduce the average turnaround time more often.
• In Shortest-Time-First Scheduling, elapsed time should be recorded, which results in more overhead on the processor.

Frequently Asked Questions

Key Takeaways

Since operating systems is one of the most popular topics among the interviewers students generally have a weak hand when coming to OS. So if you are preparing for any company’s interview then Coding Ninjas’ short-term course on Operating Systems will gonna benefit you for sure.

It is a two-month course and here you will be taught the core concepts of the operating systems that will help you ace the interviews. And this is not enough, you will be working on 150+ practice problems of operating systems that have been previously asked during the interviews of some tech giants.

If you are interested to know more about operating systems you can check out Coding Ninjas’s Operating System Guide To know more about the different kinds of operating systems available checkout out Coding Ninjas’s blog on Types of Operating Systems.

You may also find the below-mentioned links useful if you are looking for some exclusive content on operating systems:

• Operating Systems Tutorials with code explained
• How to choose a good OS?
• Top operating systems for programmers

This was all you needed to quench your thirst to know about the operating systems. Hope this helps you out in preparing for tech giants. You can also check out some exclusive in-demand courses offered by Coding Ninjas.

By Shivi Srivastava