Shortest Job First (SJF) Scheduling in OS

In an operating system, the shortest job first (SJF) scheduling is a CPU scheduling algorithm that selects a process that has the shortest CPU burst time for execution first. Key points of shortest job first (SJF) scheduling are

• The process that contains the shortest CPU execution (CPU Burst) time will be executed first
• Shortest job first (SJF) can be a preemptive or non-preemptive scheduling algorithm
  • Preemptive scheduling is known as shortest remaining time first (SRTF), where a running process can be interrupted.
  • Non-Preemptive scheduling is known as shortest job first (SJF), where a running process cannot be interrupted.
• It’s mainly used to minimize the average waiting time among all other CPU scheduling algorithms
• It’s only helpful when we already know the burst time of each process
• Starvation may occur because the process which contains longer burst time may wait behind a lot of short-burst-time process arrivals

Working of shortest job first (SJF) scheduling

The shortest job first (SJF) scheduling follows the following steps

• Step 01: As the process arrives, it is placed in the ready queue by the OS, and it waits for CPU allocation
• Step 02: The CPU scheduler compares the burst time of all processes in the ready queue
• Step 03: The CPU scheduler selects the process which contains shortest burst time and assigns the CPU to this process for execution
• Step 04: Steps 02 and 3 are repeated until all processes in the ready queue are executed successfully.

Example of SJF Scheduling

Consider there are four processes (P1, P2, P3, and P4 ); their arrival times and burst times are shown in the following diagram

Solution

The execution order of the processes is given below

P4 → P2 → P3 → P1

Gantt Chart

Gantt chart of shortest job first (SJF) scheduling example is given below

Explaination

• At time 0, all four processes (P1, P2, P3, and P4) arrive in the ready queue.
• P4 has the shortest burst time (2 ms), so it executes first from 0 to 2.
• After P4 finishes, P2 has the next shortest burst time (4 ms), so it executes from 2 to 6.
• Next, P3 has the shortest remaining burst time (7 ms), so it executes from 6 to 13.
• Finally, P1 executes because it has the longest burst time (10 ms), running from 13 to 23.
• The Gantt chart shows that the CPU always selects the ready process with the shortest burst time, which is the main principle of Shortest Job First (SJF) Scheduling.

Advantages of Shortest Job First (SJF) Scheduling

The main advantages of shortest job first (SJF) scheduling are given below

• Shorter processes (having smaller CPU burst time) are executed quickly
• Average waiting time in SJF is reduced because shorter processes are completed quickly without facing too many delays.
• As shorter processes are executed quickly, their turnaround time is also minimized
• Suitable for batch systems where CPU time can be estimated for each process
• As Shorter processes are executed more quickly, it increases the system’s overall performance

Disadvantages of Shortest Job First (SJF) Scheduling

The main disadvantages of shortest job first (SJF) scheduling are given below

• Starvation of Long Processes: Long processes may wait for a long time if shorter processes keep arriving.
• Burst Time Must Be Known: SJF requires the CPU burst time of each process to be known or estimated before scheduling.
• Difficult to Estimate Burst Time: In many systems, it is hard to predict the exact CPU burst time of a process.
• Not Suitable for Interactive Systems: SJF is less effective for interactive and real-time systems where quick response is important.
• Higher Scheduling Complexity: The scheduler must continuously compare burst times to select the shortest process.
• Preemptive Version Has More Context Switching: In Shortest Remaining Time First (SRTF), frequent process switching increases context switching overhead.

Starvation in SJF Scheduling

Starvation in Shortest Job First (SJF) Scheduling occurs when a long process waits for a very long time because the CPU keeps selecting shorter processes first. If new short processes continue to arrive, the long process may never get a chance to execute.

Example

Suppose P1 has a burst time of 20 ms and is waiting in the ready queue. Before it gets the CPU, new processes with burst times of 2 ms, 3 ms, and 4 ms keep arriving. The scheduler always selects the shorter processes first, so P1 continues waiting. This situation is called starvation.

Performance Measures of SJF Scheduling

The performance of Shortest Job First (SJF) Scheduling is evaluated using the following measures:

• Gantt Chart: Shows the order in which processes are executed on the CPU.
• Completion Time (CT): The time at which a process finishes its execution.
• Turnaround Time (TAT): The total time taken by a process from arrival to completion.
  • Formula: TAT = Completion Time − Arrival Time
• Waiting Time (WT): The total time a process spends waiting in the ready queue.
  • Formula: WT = Turnaround Time − Burst Time
• Response Time (RT): The time from a process’s arrival until it gets the CPU for the first time.
  • Formula: RT = First Start Time − Arrival Time
• Average Waiting Time (AWT): The average waiting time of all processes.
  • Formula: AWT = Total Waiting Time ÷ Number of Processes
• Average Turnaround Time (ATAT): The average turnaround time of all processes.
  • Formula: ATAT = Total Turnaround Time ÷ Number of Processes

Difference Between FCFS and SJF Scheduling

The difference between FCFS and SJF Scheduling is given in the following table