Shortest Job First (SJF) in Operating System

What is the Shortest Job First Scheduling in the Operating System?

Shortest Job First (SJF) algorithm is also known as Shortest Job Next (SJN) or Shortest Process Next (SPN). It is a CPU processes scheduling algorithm that sorts and executes the process with the smallest execution time first and then the subsequent processes with the increased execution time. Both preemptive and non-preemptive scheduling strategies are possible in the SJF scheduling algorithm. In SJF, there is a significant amount of reduction in the average waiting time for other processes that are waiting to be executed.

However, it can be quite challenging to estimate the burst time required for a process, making it difficult to apply this technique to the operating system scheduling process.

The burst time for a process can only be approximated or predicted. To get the most out of the SJF algorithm, our approximations must be correct. Numerous methods can be used to predict a process's CPU burst time.

1. Static Techniques:

• Process Size: We approximate the burst time of the upcoming process by using the burst time of an older process having a similar size.
• Process Type: Depending on the type of the process, we can estimate the burst time. There are several different sorts of processes, , for example,, Background Processes, User Processes, Operating System Processes, etc.

2. Dynamic Techniques:

• Simple Averaging: In simple averaging, a list of $n$ processes is provided. $P(1)$, $P(2)$,.......,$P(n)$. Let $T(i)$ represent the $ith$ process's burst time. Let $τ(n)$ be the estimated burst time for the $Pth$ process. The estimated burst time of a process $n+1$ can be determined by:

where, $0<=i<=n$ and $∑ T(i)$ is the summation of all the burst times and .

• Exponential Averaging or Aging: Let $Tn$ represents the $nth$ process's exact burst time. If the $nth$ process's estimated burst time is $τ(n)$, the subsequent process's $τ(n+1)$ CPU burst time can be determined by:

where $α$ represents the smoothing. Its value ranges from $0$ to $1$.

Characteristics of SJF Scheduling

The following are the characteristics of Shortest Job First Scheduling:

• Shortest Job First has the shortest average waiting time out of all scheduling methods.
• SJF is categorized as a Greedy algorithm.
• The Starvation problem can occur if shorter processes continue to be generated, to solve this we can use an ageing technique.
• The operating system can't calculate the burst times, so it is almost impossible to sort them. Although execution time cannot be calculated, it can be estimated using a variety of techniques, such as a weighted average of earlier execution times.
• This algorithm can be utilized in specialized environments where precise burst time (or running time of an application) estimations are available.

SJF Algorithm

The Algorithm for Shortest Job First CPU Scheduling is as follows:

1. First sort all the CPU processes in order of their arrival time to identify the one that needs to be executed first. This makes sure that the process that came first and had the shortest burst duration is the one that is executed.
2. Segment Trees are used to find the minimum burst time process from all the arriving processes rather than iterating over the entire struct array to identify the minimum burst time process among all the arrived processes.
3. After choosing a process that needs to be executed, the arrival time and burst time of the process are used to compute the different times, for example, the turnaround time of a process, the waiting time of a process, and the completion time (all the times are discussed in the next section of this article).

Example:

In the above example, we are taking the arrival time of each process to be $0$. The processes are executed in ascending order according to their burst times because their arrival times are all zero. As a result, the processes are executed in the following order:

How to Compute Below Times in SJF Using a Program?

Pre-requisites:

• CPU Scheduling
• Scheduling Algorithms in OS

Completion Time (CT)

The time in the CPU scheduling at which a process has finished running.

Formula for computing the completion time of a process:.

Turn Around Time (TAT)

The difference in time between the Completion Time of the process and the Arrival Time of the process.

Formula for computing the turnaround time of a process:.

Waiting Time (WT)

The difference in time between Turn Around Time of the process and the Burst Time of the process.

Formula for computing the waiting time of a process:.

or

Java Program for SJF Algorithm

Output:

Non-Preemptive SJF

In Non-preemptive SJF scheduling, the process retains the CPU cycle once it has been assigned to the CPU until it completes its execution or is stopped.

Let's consider the below example to understand non-preemptive SJF scheduling in OS:

Step 0: At $time = 0$, Process $P3$ arrives and begins execution.

Step 1: At $time = 1$, process $P4$ arrives. However, $P3$ still needs two more units to finish. $P3$ will continue to run on the CPU.

Step 2: At $time = 2$, process $P1$ arrives and joins the queue of processes waiting for execution. $P3$ will continue to run on the CPU.

Step 3: At $time = 3$, process $P3$ execution gets completed. We compare the burst times of $P4$ and $P1$. Process $P1$ goes into the CPU for execution because it has a shorter burst time than Process $P4$ does.

Step 4: At $time = 4$, process $P2$ arrives and joins the queue of processes waiting for execution. process $P1$ continues its execution on the CPU, and $P4$ remains in the queue.

Step 5: At $time = 5$, process $P1$ execution gets completed. We compare the burst times of $P4$ and $P2$. Process $P4$ goes into the CPU for execution because it has a shorter burst time than Process $P2$ does.

Step 6: At $time = 6$, process $P4$ continues execution.

Step 7: At $time = 9$, process $P4$ completes its execution and process $P2$ goes into the CPU for execution.

Step 8: At $time = 14$, process $P2$ will complete its execution.

Step 9: Let's find out the average waiting time for a process.

Preemptive SJF

In the Preemptive SJF scheduling, jobs are inserted into the queue as they are received. The process with the least burst time starts execution, and if a job with a shorter burst time enters the queue, the current process is terminated or preempted from continuing and the shorter job is given the CPU cycle for execution.

Let's consider the below example to understand preemptive SJF scheduling in OS:

Step 0: At $time = 0$, process $P1$ arrives and begins execution ($arrivaltime = 0$, $burstTime = 3$ for $P1$, see above table).

Step 1: At $time = 1$, process $P3$ arrives ($arrivalTime = 1$, $burstTime = 5$ for $P3$). However, $P1$ has a shorter burst time, so $P1$ will continue to run on the CPU, meanwhile, $P3$ will go in the process queue.

Step 2: At $time = 2$, process $P4$ arrives ($arrivalTime = 2$, $burstTime = 4$ for $P4$) and it joins the queue of processes waiting for execution as $P1$ has a shorter burst time than $P4$. $P1$ will continue to run on the CPU.

Step 3: At $time = 3$, process $P1$ completes its execution. We compare the burst times of $P3$ and $P4$. Process $P4$ goes into the CPU for execution because it has a shorter burst time than Process $P3$ does.

Step 4: At $time = 4$, process $P2$ arrives with a shorter burst time ($arrivalTime = 4$, $burstTime = 1$ for $P2$) as compared to process $P4$ which is currently executing. Process $P4$ is terminated/preempted and $P2$ starts executing.

Here, the table will look something like this:

Step 5: At $time = 5$, process $P2$ completes its execution and $P4$ again starts execution as it has a shorter burst time as compared to $P3$.

Step 6: At $time = 8$, process $P4$ completes its execution, and $P3$ starts its execution in the CPU.

Step 7: At $time = 13$, process $P3$ completes its execution.

Step 8: Let's find out the average waiting time for a process.

Advantages of SJF

These are some of the Advantages of the SJF algorithm:

• Shortest Job First (SJF) has a shorter average waiting time as compared to the First come first serve (FCFS) algorithm.
• SJF can be applied to long-term scheduling.
• SJF is ideal for jobs that run in batches and whose run times are known.
• SJF is probably the best concerning the average turnaround time of a process.

Disadvantages of SJF

These are some of the Disadvantages of the SJF algorithm:

• The Shortest Job First algorithm may result in a starvation problem with extremely long turnaround times.
• In SJF, job burst time must be predetermined, although it might be difficult to predict it.
• As we are unable to estimate the duration of the upcoming CPU process burst time, we cannot utilize SJF for short-term CPU scheduling.
• The processes cannot be given any priority in SJF scheduling.