Shortest Job First Scheduling Non Preemptive

Shortest Job First (SJF) – Non Preemptive

Shortest Job First Scheduling (Non Preemptive Algorithm) in Operating System

  • Shortest Job First  (SJF) is a Scheduling Algorithm where the process are executed  in ascending order of their burst time, that is, the process having the shortest burst time is executed first and so on.
  • The processor knows burst time of each process in advance.
  • It can be thought of as shortest-next-cpu-burst algorithm, as Scheduling depends on length of the next CPU burst of a process. ( The duration for which a process gets control of the CPU, is the Burst time for a process.)
  • SJF can be Pre-emptive or Non- preemptive. Under Non-preemptive Scheduling , once a process has been allocated to CPU, the process keeps the CPU until the process has finished its execution.

Read more – SJF Preemptive Scheduling here

SJF Non Preemptive Example

Note – This example is given wrong on Geeks4Geeks. So make sure that you only study it on PrepInsta.

Let us try to understand SJF Non-Preemptive Scheduling with an example –

Here, processes are assumed to be arrived at the same time.

See the below Example –

SJF ProcessBurst Time ( in ms)Arrival Time
P120
P280
P310
P440

The order in which the CPU processes the process are(Gantt Chart) –

Steps –

  1. Since Burst time for P3 (Burst = 1 sec) is lowest it is executed first.
  2. Then Burst time for P1 is lowest in order thus it gets executed the 2nd time.
  3. Similarly P4 and then P2

Waiting time –

  1. P1 waiting time = 1
  2. P2 waiting time = 7
  3. P3 waiting time = 0
  4. P4 waiting time = 3

The average waiting time is = ( 1+ 7 + 0 + 3 )/ 4 = 2.75

Features of SJF

  • SJF is a greedy Algorithm
  • It has Minimum average waiting time among all scheduling algorithms.
  • Difficulty of SJF is knowing the length of next CPU request.
  • It’s used frequently in Long-term scheduling in Batch System as in this, the time limit is provided by the user specifying the process. We presume that user provides accurate time limit as lower accurate value means faster response.
  • SJF can’t be implemented in Short-term scheduling as one can’t know the exact length of next CPU burst. It can be Approximated by doing an exponential average of already measured length of previous CPU burst.

Drawback

  • in SJF Scheduling, a process with high burst time may suffer starvation. Starvation is the process in which a process with higer burst time is kept on waiting and waiting , but is not allocated to the CPU. It’s prevented by aging.
  • Total execution time must be known beforehand of a process.

What is aging?

  • Aging is a technique which is used to reduce starvation of the processes.
  • Aging takes into account the waiting time of the process in the ready queue and gradually increases the priority of the process.
  • Hence, as the priority of a process gets increased this ensures that all process get completed eventually.
Summary
Review Date
Reviewed Item
Shortest Job First Scheduling Non Preemptive
Author Rating
51star1star1star1star1star

Please Login/Signup to comment