What is shortest job next (SJN) CPU scheduling?

Operating systems use different process schedulers to schedule processes to be assigned to the CPU for further execution based on some scheduling algorithms. Following are some scheduling algorithms:

• First Come First Serve (FCFS) scheduling

• Shortest job next (SJN) scheduling

• Priority scheduling

• Shortest remaining time

• Round Robin (RR) Scheduling

• Multiple-level queues Scheduling

Note: Algorithms are either preemptivePreemptive scheduling is based on priority where a scheduler may preempt a low priority running process anytime when a high priority process enters into a ready state. or non-preemptiveNon-preemptive algorithms are designed so that once a process enters the running state, it cannot be preempted until it completes its allotted time..

In this answer, we'll discuss the SJN scheduling algorithm.

SJN scheduling

The shortest job next (SJN) scheduling algorithm is also known as the shortest job first (SJF) scheduling. In this scheduling, the algorithm selects the process in the waiting queue with the shortest burst timeBurst time is the amount of time required by a process for executing on CPU. to execute next. If two processes have the same burst time, we use the FCFS scheduling to break the tie, and the rest of the processes get scheduled using SJN again.

There are two types of SJN scheduling:

• Preemptive SJN

• Non-Preemptive SJN

Non-Preemptive SJN

In the non-preemptive SJN scheduling, if the CPU cycle is allocated to any process, the process holds the CPU until it reaches a waiting state or is terminated.

Example

Suppose we have a set of five processes whose burst time and arrival timeTime at which the process arrives in the ready queue. are given, schedule the processes using non-preemptive SJN scheduling, and calculate the average waiting time.

Solution

Let's handle this process scheduling using non-preemptive SJN scheduling. To understand it better, have a look at the figure below:

Gantt chart

Have a look at the Gantt chartA Gantt chart, commonly used in project management, is one of the most popular and useful ways of showing activities (tasks or events) displayed against unit time. of our example:

Waiting time

Let's calculate the waiting time using the Gantt chart above:

$Wait Time = Service Time - Arrival Time$

Average waiting time

Preemptive SJN

In the preemptive SJN scheduling, all the processes are put into the ready queue as they request to use the CPU. The process with the shortest burst time starts execution. If another process arrives with a shorter burst time, the current process gets preempted from execution, and a shorter process is allocated to use the CPU.

Example

Suppose we have a set of five processes whose burst time and arrival time are given, schedule the processes using preemptive SJN scheduling, and calculate the average waiting time.

Solution

Let's handle this process scheduling using preemptive SJN scheduling. To understand it better, have a look at the figure below:

Gantt chart

Have a look at the Gantt chart of our example:

Waiting time

Let's calculate the waiting time using the above Gantt chart:

Wait Time = Service Time - Arrival Time

Average waiting time

Advantages

The advantages of the SJN algorithm are as follows:

• This is the best scheduling to reduce waiting time.

• It's a straightforward approach to implement in Batch systems where the required CPU time is known.

• The optimal scheduling in terms of average turnaround time.

Disadvantages

The disadvantages of the SJN algorithm are the following:

• The processor must know in advance how much time the process will take.

• This scheduling is impossible to implement in interactive systems where the required CPU time is unknown.