**Characteristics of SJF Scheduling Algorithm**

Characteristics of Shortest Job First (SJF) Scheduling Algorithm:

**Optimality**: SJF scheduling algorithm ensures optimal CPU utilization by selecting the shortest job first, minimizing average waiting time.**Non-preemptive**: Typically, SJF is implemented as a non-preemptive scheduling algorithm, meaning once a process starts executing, it continues until completion.**Dynamic**: SJF requires knowledge of the burst time of each process, making it a dynamic scheduling algorithm.**Starvation**: Long processes may suffer from starvation in SJF, as shorter processes continuously arrive, causing them to wait indefinitely.**Implementation Complexity**: Accurate prediction of process burst times is often challenging, leading to complexity in real-world implementations.**Variance Sensitivity**: SJF can be sensitive to variance in burst times; small variations may significantly affect the overall performance of the algorithm.**Limited Applicability**: SJF is not suitable for interactive or real-time systems where predictability and fairness are critical due to its inherent unpredictability and potential for process starvation.

**Algorithm of Shortest Job First Scheduling**

- Start with sorting all the processes based on their time of arrival at the processor.
- Then select the earliest arriving process with the shortest burst time.
- While executing the current process, all the waiting processes are pushed in the waiting queue, and when the current process ends, choose the process with the shortest burst time among the waiting processes.

Read More - __Time Complexity of Sorting Algorithms__

**Implementation of Shortest Job First Scheduling Algorithm**

### C++

`#include <bits/stdc++.h>`

using namespace std;

//Matrix to store the values.

int matrix[20][6];

//Function to swap.

void swap(int *x, int *y)

{

int var = *x;

*x = *y;

*y = var;

}

//Function to sort the processes by the time of arrival.

void sortbyarrival(int noofprocess, int matrix[][6])

{

for( int i=0;i<noofprocess;i++)

{

for(int j=0;j<noofprocess-i-1;j++)

{

if(matrix[j][1]>matrix[j+1][1])

{

for(int k=0;k<5;k++)

{

swap(matrix[j][k],matrix[j+1][k]);

}

}

}

}

}

//Choosing the process with minimum burst time.

void timeofcompletion(int noofprocess, int matrix[][6])

{

int var, ctr;

matrix[0][3] = matrix[0][1] + matrix[0][2];

matrix[0][5] = matrix[0][3] - matrix[0][1];

matrix[0][4] = matrix[0][5] - matrix[0][2];

for(int i=1;i<noofprocess;i++)

{

var=matrix[i-1][3];

int lower=matrix[i][2];

for(int j=i;j<noofprocess;j++)

{

if(var>= matrix[j][1]&&lower>=matrix[j][2])

{

lower=matrix[j][2];

ctr=j;

}

}

matrix[ctr][3] = var+matrix[ctr][2];

matrix[ctr][5] = matrix[ctr][3] - matrix[ctr][1];

matrix[ctr][4] = matrix[ctr][5] - matrix[ctr][2];

for(int k=0;k<6;k++)

{

swap(matrix[ctr][k],matrix[i][k]);

}

}

}

//Driver function.

int main()

{

int noofprocess=6;

matrix[0][0]=1,matrix[0][1]=2,matrix[0][2]=3;

matrix[1][0]=2,matrix[1][1]=0,matrix[1][2]=4;

matrix[2][0]=3,matrix[2][1]=4,matrix[2][2]=2;

matrix[3][0]=4,matrix[3][1]=5,matrix[3][2]=4;

matrix[4][0]=5,matrix[4][1]=6,matrix[4][2]=6;

matrix[5][0]=6,matrix[5][1]=7,matrix[5][2]=7;

sortbyarrival(noofprocess, matrix);

timeofcompletion(noofprocess, matrix);

cout<<"Process ID Arrival Time Burst Time Waiting Time Turnaround Time"<<endl;

for(int i=0; i<noofprocess; i++)

{

cout<<matrix[i][0]<<" "<<matrix[i][1]<<" "<<matrix[i][2]<<" "<<matrix[i][4]<<" "<<matrix[i][5]<<endl;

}

}

Output:

```
Process ID Arrival Time Burst Time Waiting Time Turnaround Time
2 0 4 0 4
3 4 2 0 2
1 2 3 4 7
4 5 4 4 8
5 6 6 7 13
6 7 7 12 19
```

The time complexity of this algorithm is **O(N*log(N)).**

The space complexity of this algorithm is **O(1).**

You can also read about layered structure of operating system.

Must Read: __Design and Analysis of Algorithms__

## Types of Shortest Job First

Shortest Job First (SJF) scheduling has two main types:

### Non-Preemptive SJF

In non-preemptive SJF, once a process starts executing, it continues until completion without interruption. The scheduler selects the shortest job from the ready queue and allows it to run to completion before selecting the next shortest job.

**Implementation:**

### C++

`#include <iostream>`

#include <vector>

#include <algorithm>

struct Process {

int id;

int arrivalTime;

int burstTime;

};

bool compareArrivalTime(Process a, Process b) {

return a.arrivalTime < b.arrivalTime;

}

bool compareBurstTime(Process a, Process b) {

return a.burstTime < b.burstTime;

}

void sjfNonPreemptive(std::vector<Process> processes) {

std::sort(processes.begin(), processes.end(), compareArrivalTime);

int currentTime = 0;

float totalWaitingTime = 0;

for (auto process : processes) {

if (currentTime < process.arrivalTime)

currentTime = process.arrivalTime;

currentTime += process.burstTime;

totalWaitingTime += currentTime - process.arrivalTime - process.burstTime;

}

std::cout << "Average waiting time: " << totalWaitingTime / processes.size() << std::endl;

}

int main() {

std::vector<Process> processes = { {1, 0, 6}, {2, 1, 8}, {3, 2, 7}, {4, 3, 3} };

sjfNonPreemptive(processes);

return 0;

}

**Output**

`Average waiting time: 8.75`

### Preemptive SJF

In preemptive SJF, a running process can be interrupted if a new process arrives with a shorter burst time. The scheduler selects the shortest remaining time job from the ready queue, preempts the currently running process if necessary, and executes the selected process.

**Implementation:**

### C++

`#include <iostream>`

#include <vector>

#include <algorithm>

struct Process {

int id;

int arrivalTime;

int burstTime;

};

bool compareArrivalTime(Process a, Process b) {

return a.arrivalTime < b.arrivalTime;

}

bool compareBurstTime(Process a, Process b) {

return a.burstTime < b.burstTime;

}

void sjfPreemptive(std::vector<Process> processes) {

std::sort(processes.begin(), processes.end(), compareArrivalTime);

int currentTime = 0;

float totalWaitingTime = 0;

while (!processes.empty()) {

auto shortest = std::min_element(processes.begin(), processes.end(), compareBurstTime);

currentTime = std::max(currentTime, shortest->arrivalTime);

totalWaitingTime += currentTime - shortest->arrivalTime;

currentTime += shortest->burstTime;

processes.erase(shortest);

}

std::cout << "Average waiting time: " << totalWaitingTime / processes.size() << std::endl;

}

int main() {

std::vector<Process> processes = { {1, 0, 6}, {2, 1, 8}, {3, 2, 7}, {4, 3, 3} };

sjfPreemptive(processes);

return 0;

}

**Output**

`Average waiting time: inf`

## Advantages of SJF

The advantages of Shortest Job First (SJF) Scheduling are:

**Optimal Efficiency**: SJF scheduling algorithm minimizes average waiting time by executing shorter jobs first, leading to optimal CPU utilization.**Improved Turnaround Time**: Shorter jobs complete quickly, reducing the average turnaround time and enhancing system responsiveness.**Predictability**: SJF provides predictable performance as it selects the shortest job, making it easier to estimate job completion times.**Reduced Waiting Time**: Short jobs are prioritized, minimizing the waiting time for processes in the ready queue, thus enhancing overall system throughput.**Enhanced Resource Utilization**: By prioritizing short jobs, SJF helps in better utilization of system resources, leading to improved system efficiency.

## Disadvantages of SJF

The disadvantages of Shortest Job First (SJF) Scheduling:

**Starvation**: Longer jobs may suffer from starvation as they wait indefinitely behind short jobs, leading to potential delays in their execution.**Difficulty in Predicting Job Length**: Accurately predicting job lengths in advance can be challenging, making it hard to implement SJF effectively in practice.**Need for Accurate Burst Time Estimation**: SJF relies on precise burst time estimations, which may not always be available or accurate, impacting scheduling decisions.**Preemption Overhead**: In preemptive SJF, frequent preemptions can introduce overhead and context switch costs, reducing system efficiency.**Unfairness**: Preemptive SJF may prioritize short bursts excessively, potentially causing longer jobs to experience unfair treatment and increased waiting times.

**Important Terminologies**

As this topic belongs to the operating subject domain as well, before proceeding further, letâ€™s understand a few terminologies related to it that are used frequently in the blog-

**Burst time**â€“ It refers to the amount of time in which a process gets executed in standard conditions.**Arrival time of a process**â€“ The time at which a process is assigned to the processor to be processed.**Completion time**â€“ The time at which the execution of the process ends is known as completion time.**Turnaround time**â€“ This is the total time the processing spends at the processor, which is equal to the difference between completion time and arrival time.**Waiting time**â€“ It is the difference between the time the process spends at the processor and the time it requires to be completed in a standard condition. I.e., turnaround time â€“ burst time.

For a processor to perform this kind of scheduling algorithm, it must know the burst time of the processes beforehand. And this is effective for batch-type processing, in which the waiting time is not critical for the process. This kind of processing has a high throughput because it ensures the shorter tasks are completed as early as possible.

**Frequently Asked Questions**

**Why is shortest job first the best?**

Shortest Job First (SJF) minimizes average waiting time by executing shorter jobs first, leading to optimal CPU utilization and improved system efficiency.

**What is the shortest job first algorithm in C++?**

Shortest Job First (SJF) algorithm in C++ selects the shortest job for execution, enhancing system responsiveness and reducing average waiting time.

**What do you mean by SRTF?**

Shortest Remaining Time First (SRTF) is a preemptive version of SJF where a running process can be preempted if a shorter job arrives.

**What is a real life example of SJF scheduling?**

This algorithm is used in many real-life scenarios for example: online delivery apps always choose to deliver the nearest order first, then after delivering the first order, it searches for the next nearest delivery location thus.

## Conclusion

In this blog, we discussed the program for Shortest Job First (SJF) CPU Scheduling. We have learned what SJF is and why it is used. SJF CPU Scheduling stands as a powerful algorithm in optimizing CPU utilization and reducing average waiting time. Its ability to prioritize shorter jobs ensures efficient resource allocation and enhances system responsiveness.

In this algorithm, we always choose the process with the shortest burst time and until the current process gets executed, we maintain all incoming processes in a waiting queue. Once the current process ends, we check the waiting queue for the process with the shortest execution time, and then we begin executing that process.

This algorithm is suitable for batch type processing as to decide which process must be executed first, we must know its burst time beforehand. It works more efficiently than the naive first-come-first-serve scheduling algorithm, by focusing on executing the shortest process first.

Recommended Articles

Read more about search algorithms here, Donâ€™t forget to practice similar problems on code studio as well. If you liked this blog, share it with your friends.