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

7.

Shortest-Job-First Scheduling with Arrival Time in C

8.

Shortest-Job-First Scheduling with Arrival Time in JAVA

9.

Advantages of Shortest-Job-First Scheduling

10.

Disadvantages of Shortest-Job-First Scheduling

11.

Frequently Asked Questions

11.1.

How do you implement the shortest job first?

11.2.

How do you calculate waiting time for the shortest remaining first?

11.3.

Is SRTF and SJF the same?

11.4.

Which is a better shortest job first or round-robin?

11.5.

How do you solve the first preemptive shortest job?

12.

Conclusion

Table of contents

Operating system track

Free guided path14 chapters83+ problems

Earn badges and level up

Introduction

An operating systemâ€™s main task is to allocate resources and hereby schedule processes. So once a process has been received, the 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:

Shortest-Job-First Scheduling is said to be the best process scheduling approach as it minimizes the waiting time of the other processes awaiting their execution. It is also referred to as Shortest-Job-Next owing to its characteristic of scheduling 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 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 that need less time are executed first, it also increases the throughput time.

The algorithm works 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.

Get the tech career you deserve, faster!

Connect with our expert counsellors to understand how to hack your way to success

User rating 4.7/5

1:1 doubt support

95% placement record

Akash Pal

Senior Software Engineer

326% Hike After Job Bootcamp

Himanshu Gusain

Programmer Analyst

32 LPA After Job Bootcamp

After Job Bootcamp

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.

PROCESS ID

ARRIVAL TIME

BURST TIME

P0

0

18

P1

1

4

P2

2

7

P3

3

2

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:

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.

PROCESS ID

ARRIVAL TIME

BURST TIME

P0

5

8

P1

0

5

P2

4

9

P3

1

2

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:

PROCESS ID

ARRIVAL TIME

BURST TIME

COMPLETION TIME

TURN AROUND TIME

WAITING TIME

P0

5

8

21

16

8

P1

0

5

5

5

0

P2

4

9

16

12

3

P3

1

2

7

6

4

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

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.

You can implement the shortest job first scheduling by using this algorithm:

1. Sort all the processes according to their time of arrival.

2. Then sort all the processes according to their burst time and choose the one with both minimum arrival time and burst time.

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

How do you calculate waiting time for the shortest remaining first?

Waiting Time can be calculated using the difference between turn around time and burst time i.e Waiting Time=Turn around Time-Burst Time.

Is SRTF and SJF the same?

No, they are not the same but we can say that Shortest Remaining Time First (SRTF) is the preemptive version of Shortest-Job-First Scheduling(SJF). In this scheduling algorithm, the process with the smallest amount of time remaining until completion is selected to execute first. However, the jobs having the same arrival time will be converted from SRTF to Shortest Remaining Job First (SJF).

Which is a better shortest job first or round-robin?

Shortest Job First Scheduling is said to be better if the processes manage the processes simultaneously received by the processor. However, Round Robin is better to leverage the average waiting time and it is much easier to implement.

How do you solve the first preemptive shortest job?

In First Preemptive Shortest Job First Scheduling, all the jobs/processes are put into the ready queue as soon as they arrive. However, when a process with a shorter burst time arrives, the existing process is preempted from execution, and the shorter process that has just arrived is executed first.

Conclusion

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.

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.