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).
- 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.
- 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.
- 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.
|Process||Arrival time||Burst Time|
The order in which the CPU processes the process are (Gantt Chart) –
- At ( t =0ms ), P1 arrives. It’s the only process so CPU starts executing it.
- 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.
- 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 .
- 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.
- 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.
- At ( t = 7ms ),P4 gets executed for 3ms.
- At ( t = 10ms ), P1 gets executed till it finishes.
Waiting time = Completion time – Burst Time – Arrival Time
- P1 waiting time = (15-6-0) = 9ms
- P2 waiting time = (7-4-1) = 2ms
- P3 waiting time = (4-2-2 )=0ms
- P4 waiting time = (10-3-3)= 4ms
The average waiting time is ( 9 +2 + 0 + 4)/4 = 15/4 = 3.75
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.
- Process (Intro)
- Process Life Cycle
- Process Control Block PCB
- Process Scheduling
- Context Switching
- CPU Scheduling
- FCFS Scheduling
- Shortest Job First (or SJF) scheduling – non-preemptive
- Shortest Job First (or SJF) scheduling – preemptive (SRTF)
- Round Robin scheduling
- Priority Scheduling
- Convoy Effect
- Difference between Scheduler and Dispatcher
- Preemptive scheduling vs Non Preemptive scheduling
- Preemptive scheduling
- Non preemptive scheduling