Home » Operating System – Shortest Job First Scheduling

Operating System

Chapter 1: Introduction to Operating System 

— Definition of Operating System.

— Evolution of operating systems – simple batch systems, multi-programmed batch systems, time sharing systems.

— Functions of an operating system

— Characteristics of Operating System

— Single user and multi-user operating systems

Open-source and closed-source operating systems.

Important Questions with their Answers of “Introduction to operating system”

— MCQs and Fill in Blanks

— Short term Questions

— Long Term Questions


Chapter 2: Process Overview

Definition of process, process states, process life cycle,

Process Control Block (PCB),

Process Scheduling – Scheduling queues,

Schedulers (short term, medium term and long term).

Dispatcher.

Context Switch.

Important Questions with their Answers of “Process Overview”

— MCQs and Fill in blanks

Short term Questions

Long Term Questions


Chapter 3: CPU Scheduling

  • CPU Scheduler,
  • Preemptive and non-preemptive scheduling.
  • Scheduling criteria – CPU utilization, Throughput, Turnaround time, Waiting time, Response time.
  • Scheduling Algorithms: First-Come-First-Serve, Shortest-Job-First, Priority Scheduling, Round-Robin.

Important Questions with their Answers of “CPU Scheduling”

  • MCQs and Fill in blanks
  • Short term Questions
  • Long Term Questions

Operating System – Shortest Job First Scheduling


In SJF scheduling, the process with the lowest burst time, among the list of available processes in the ready queue, is going to be scheduled next.

However, it is very difficult to predict the burst time needed for a process hence this algorithm is very difficult to implement in the system.

  • This is the best approach to minimize waiting time.
  • This is used in Batch Systems.
  • It is of two types:
    1. Non Pre-emptive
    2. Pre-emptive

Advantages of SJF

  1. Maximum throughput
  2. Minimum average waiting and turnaround time

Disadvantages of SJF

  1. May suffer with the problem of starvation
  2. It is not implementable because the exact Burst time for a process can’t be known in advance.

Non Pre-emptive Shortest Job First

Consider the below processes available in the ready queue for execution, with arrival time as 0 for all and given burst times.

As you can see in the GANTT chart above, the process P4 will be picked up first as it has the shortest burst time, then P2,followed by P3 and at last P1.

We scheduled the same set of processes using the First come first serve algorithm in the previous tutorial, and got average waiting time to be 14.5 ms, whereas with SJF, the average waiting time comes out 4 ms.

Problem with Non Pre-emptive SJF

If the arrival time for processes are different, which means all the processes are not available in the ready queue at time 0, and some jobs arrive after some time, in such situation, sometimes process with short burst time have to wait for the current process’s execution to finish, because in Non Pre-emptive SJF, on arrival of a process with short duration, the existing job/process’s execution is not halted/stopped to execute the short job first.

This leads to the problem of Starvation, where a shorter process has to wait for a long time until the current longer process gets executed. This happens if shorter jobs keep coming, but this can be solved using the concept of aging.


Pre-emptive Shortest Job First

In Preemptive Shortest Job First Scheduling, jobs are put into ready queue as they arrive, but as a process with short burst time arrives, the existing process is preempted or removed from execution, and the shorter job is executed first.

The average waiting time for preemptive Shortest Job First Scheduling is less than both, Non-preemptive SJF Scheduling and FCFS Scheduling.

As you can see in the GANTT chart above, as P1 arrives first, hence it’s execution starts immediately, but just after 1 ms, process P2 arrives with a burst time of 4 ms which is less than the burst time of P1, hence the process P1(1 ms done, 14 ms left) is preemptied and process P2 is executed.

As P2 is getting executed, after 1 msP3 arrives, but it has a burst time greater than that of P2, hence execution of P2 continues. But after another millisecond, P4 arrives with a burst time of 1 ms, as a result P2(2 ms done, 2 ms left) is preemptied and P4 is executed.

After the completion of P4, process P2 is picked up and finishes, then P2 will get executed and after that P3 is executed and at last P1.

The Pre-emptive SJF is also known as Shortest Remaining Time First, because at any given point of time, the job with the shortest remaining time is executed first.


Leave a comment

Your email address will not be published. Required fields are marked *

‘Operating System’ Practical

  1. To install and configure MS Windows 7/8/10 on a computer
  2. To get familiar with general Windows commands – ECHO, CLS, DIR, TREE, MD, CD, TYPE, RD, DEL, MOVE, COPY , REN, ATTRIB, COLOR, DATE, TIME, ERASE, FIND, FC, MORE, CMD, PATH, SYSTEMINFO, SHUTDOWN, TASKLIST, TASKKILL, VER, VOL, CHKDSK
  3. To use wildcard characters for copying, moving, renaming, and deleting files and directories in a given hierarchical directory structure under Windows’s command prompt.
  4. To get familiar with windows control panel components.
  5. To use Windows backup and restore features.
  6. To get familiar with commonly used Windows PowerShell cmdlets like Get-ChildItem, GetContent, Get-Command, Get-Help, Clear-Host, Copy-Item, Move-Item, Remove-Item, Rename-Item, Get-Location, Set-Location, Write-Output, Get-Process, Stop-Process.
  7. To write scripts in Windows PowerShell to automate tasks.