Shortest Job First Scheduling Preemptive 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 P2 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 –
- P1 waiting time = (10 -1) = 9ms
- P2 waiting time = (4-1) = 3ms
- P3 waiting time = 2ms
- P4 waiting time = 7ms
The average waiting time is ( 9 +1 + 2 + 7)/4 = 4.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