Shortest Job First – Preemptive Scheduling with Example (SJF)

Shortest Job First - Preemptive Scheduling with Example (SJF)

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.

Shortest Job First – Preemptive Scheduling with Example (SJF)

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

[table id=254 /]

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

Shortest Job First (SJF) Preemptive Algorithm
  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.

Prime Course Trailer

Related Banners

Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription

Get over 200+ course One Subscription

Courses like AI/ML, Cloud Computing, Ethical Hacking, C, C++, Java, Python, DSA (All Languages), Competitive Coding (All Languages), TCS, Infosys, Wipro, Amazon, DBMS, SQL and others

Checkout list of all the video courses in PrepInsta Prime Subscription

Checkout list of all the video courses in PrepInsta Prime Subscription