Shortest Job First – Preemptive Scheduling with Example (SJF)

June 3, 2022

Shortest Job First Scheduling (SJF) – Preemptive Algorithm​

 

Shortest Job First – Preemptive Scheduling Algorithm is an algorithm in which the processor is allocated to the job having minimum CPU burst time, but the job can be preempted (Replaced) by a newer job with shorter burst time. 

What is SJF Preemptive Scheduling Algorithm in OS

Shortest Job First Preemptive Scheduling is also known as Shortest remaining Time(SRT) or Shortest Next Time(SNT).

  1. The choice of preemptive and non preemptive arises when a new process arrives at the ready queue and a previous process is not finished and is being executed. If the next CPU burst of new process is shorter than current executing process, then in preemptive version , it will stop that process and will start executing the newly arrived process.
  2. While, in non preemptive version of SJF, even if the arriving process is shorter than currently executing process, current process is not stopped . After the current process finishes , then the new process gets in the queue. This is the key difference between preemptive and preemptive version of SJF.
  3. The current state of the process is saved by the context switch and the CPU is given to another process.

Note – If 2 processes have same execution time, then jobs are based on First Come First Serve Basis.

SJF Preemptive Example

Let’s understand SJF Scheduling with the help of an example.

ProcessArrival timeBurst Time
P106
P214
P322
P433

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

Shortest Job First Scheduling Algo
  1. At ( t =0ms ), P1 arrives. It’s the only process so CPU starts executing it.
  2.  At ( t = 1ms ), P2 has arrived . At this time, P1 (remaining time ) = 5 ms . P2 has 4ms ,  so as P2  is shorter, P1 is preempted and P2 process starts executing.
  3.  At ( t = 2ms ), P3 process has arrived. At this time, P1(remaining time) = 5ms, P2(remaining time ) = 3 ms , P3 = 2ms. Since P3 is having least burst time, P3 is executed .
  4. At ( t = 3ms ), P4 comes , At this time, P1 = 5ms, P2 = 3ms, P3 = 1ms, P4 = 3ms. Since P4 does not have short burst time, so P3 continues to execute.
  5. At ( t= 4ms ),P3 is finished . Now, remaining tasks are P1 = 5ms, P2 = 3ms, P4 = 3ms. As ,P2 and P4 have same time, so the task which came first will be executed first. So, P2 gets executed first.
  6. At ( t =  7ms ),P4 gets executed for 3ms.
  7. At ( t = 10ms ), P1 gets executed till it finishes.

Waiting time = Completion time –  Burst Time – Arrival Time

  1. P1 waiting time = (15-6-0) = 9ms
  2. P2 waiting time = (7-4-1) = 2ms
  3. P3 waiting time = (4-2-2 )=0ms
  4. P4 waiting time = (10-3-3)= 4ms

The average waiting time is ( 9 +2 + 0 + 4)/4 = 15/4 = 3.75

Disadvantages

It has the same disadvantages as non-preemptive version of SJF.  Here also process with larger burst time may experience process starvation, which could be prevented with aging.

Operating System CPU Scheduling in

      Read More

  1. Process (Intro)
  2. Process Life Cycle
  3. Process Control Block PCB
  4. Process Scheduling
  5. Context Switching
  6. CPU Scheduling
  7. FCFS Scheduling
  8. Shortest Job First (or SJF) scheduling – non-preemptive
  9. Shortest Job First (or SJF) scheduling – preemptive (SRTF)
  10. Round Robin scheduling
  11. Priority Scheduling
  12. Convoy Effect
  13. Difference between Scheduler and Dispatcher
  14. Preemptive scheduling vs Non Preemptive scheduling
  15. Preemptive scheduling
  16. Non preemptive scheduling
Go to Operating System Tutorials Main Page