Shortest Job First (SJF) Scheduling in Operating System

In case of Shortest Job First scheduling algorithm, the process with the smallest execution time gets executed next. Shortest Job First (SJF) reduces the average waiting time for other processes significantly.

Types of Shortest Job First Algorithms

Following are the two types of SJF algorithms:

1. Non-preemptive: The CPU is held by a process until the process reaches the waiting state or terminates.

EXAMPLE: Consider the following five processes:

Step 1: At time = 0, P4 arrives and starts executing.

Step 2: At time = 1, process P3 arrives in the waiting queue but P4 continues executing as it only needs to complete 2 units.

Step 3: At time = 2, P1 arrives in the waiting queue and P4 continues executing.

Step 4: At time = 3, P4 finishes executing and P1 starts executing as it has the least burst time.

Step 5: At time = 4, P5 arrives in the waiting queue while P1 executes.

Step 6: At time = 5, process P2 arrives and enters the waiting queue. P1 will continue execution.

Step 7: At time = 9, P1 finishes execution and after comparing the burst time of P3, P5, and P2, P2 with the least burst time starts executing.

Step 8: At time = 10, P2 continues executing while P3 and P5 are in the waiting queue.

Step 9: At time = 11, P2 finishes execution, and P5 starts executing.

Step 10: At time = 15, P5 finishes execution.

Step 11: At time = 23, P3 finishes execution.

Step 12: The average waiting time is:
P4 = 0 – 0 = 0
P1 = 3 – 2 = 1
P2 = 9 – 5 = 4
P5 = 11 – 4 = 7
P3 = 15 – 1 = 14

Thus, the average waiting time is: (0 + 1 + 4 + 7 + 14)/5 = 26/5 = 5.2

2. Preemptive: Jobs first enter the ready queue as they come. Then the process with the shortest burst time starts executing. The running process enters a waiting state when a process with shorter burst time than the one currently running arrives. It replaces the running process and starts executing.

EXAMPLE: Consider the following five processes:

Step 1: At time = 0, P4 arrives and starts executing.

Step 2: At time = 1, P3 arrives but P4 continues executing as it has a shorter burst time.

Step 3: At time = 2, P1 arrives but P4 continues executing as it has a shorter burst time.

Step 4: At time = 3, P4 finishes execution. After comparing the burst time of P3 and P1, P1 starts executing.

Step 5: At time = 4, P5 arrives and starts executing as it has the lowest burst time amongst all the processes. P1 preempts.

Step 6: At time = 5, P2 arrives and starts executing as it has the lowest burst time amongst all the processes. P5 preempts.

Step 7: At time = 6, P2 is executing.

Step 8: At time = 7, P2 finishes execution. After comparing the burst time of P1, P3, and P5, P5 resumes execution.

Step 9: At time = 10, P5 finishes execution. After comparing the burst time of P1 and P3, P1 starts executing.

Step 10: At time = 15, P1 finishes execution, and P3 starts executing.

Step 11: At time = 23, P3 finishes execution.

Step 12: The average waiting time is:
P4 = 0 – 0 = 0
P1 = 3 – 2 + 6 = 7
P2 = 5 – 5 = 0
P5 = 4 – 4 + 2 = 2
P3 = 15 – 1 = 14
The average waiting time is: (0 + 7 + 0 + 2 + 14)/5 = 23/5 = 4.6

Characteristics of SJF Scheduling

Following are some characteristics of SJF:

• Associated with every job as it requires a unit of time for a job to complete.
• Helpful for batch-type processing.
• Improves process throughput as shorter jobs execute first, further reducing the turnaround time.
• Offers shorter jobs that improve job output.

Advantages of SJF

Following are the advantages of SJF:

• Used for long-term scheduling.
• Reduces average waiting time.
• Helpful for batch-type processing where runtimes are known in advance.
• For long-term scheduling, we can obtain a burst time estimate from the job description.
• It is necessary to predict the value of the next burst time for Short-Term Scheduling.
• Optimal with regard to average turnaround time.

Disadvantages of SJF

Following are the disadvantages of SJF:

• It is necessary to know the job completion time beforehand as it is hard to predict.
• Used for long-term scheduling in a batch system.
• Can’t implement this algorithm for CPU scheduling for the short term as we can’t predict the length of the upcoming CPU burst.
• Cause extremely long turnaround times or starvation.
• Knowledge about the runtime length of a process is necessary.
• The length of the upcoming CPU request is hard to predict.
• Recording the elapsed time results in increased overhead on the processor.

Summary

In case of Shortest Job First scheduling algorithm, the process with the smallest execution time gets executed next. There are two types of SJF: preemptive and non-preemptive. IT offers shorter jobs, this can improve job output. It is a greedy algorithm that can cause starvation if only shorter jobs keep executing.