Apply For Jobs
Get Hiring UpdatesShortest Job First – Preemptive Scheduling with Example (SJF)
Shortest Job First Scheduling (SJF) - Preemptive Algorithm
Shortest Job First Scheduling (SJF) - Preemptive Algorithm
Shortest Job First Preemptive Scheduling with Example (SJF) In the world of operating systems, process scheduling plays a critical role in ensuring smooth and efficient execution of multiple processes. Among various CPU scheduling algorithms, Shortest Job First (SJF) stands out due to its optimality in minimizing average waiting time. In this blog, we will explore Shortest Job First Preemptive Scheduling, also known as Shortest Remaining Time First (SRTF), in detail.
Good scheduling algorithms aim to:
- Maximize CPU utilization
- Minimize waiting and turnaround time
- Ensure fairness among processes
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.
Features of Shortest Job First (SJF) Preemptive Algorithm:
- Preemptive Nature
- The CPU is allocated to the process with the shortest remaining burst time.
- If a new process arrives with a shorter burst time than the current running process, the current process is preempted.
- Optimal for Average Waiting Time
- SJF (especially in its preemptive form) gives the lowest average waiting time among all scheduling algorithms.
- Based on Burst Time
- Scheduling decisions are made based on the estimated burst time (CPU time) of processes.
- Requires Prior Knowledge
- The algorithm needs knowledge of the burst time in advance, which may not always be feasible.
- Dynamic Scheduling
- As new processes arrive, the scheduler re-evaluates and may switch the running process if the newcomer has a shorter remaining time.
Example:
- 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
Advantages
- Minimizes Average Waiting Time: One of the most optimal algorithms in terms of waiting time.
- Responsive to Short Processes: Prioritizes short jobs, improving responsiveness.
- Better for Time-sharing Systems: Suitable for interactive environments.
Disadvantages
- High Overhead: Requires continuous tracking of burst times.
- Starvation: Long processes may wait indefinitely if shorter jobs keep arriving.
- Complex Implementation: Real-time estimation of remaining burst time is challenging.
- Needs Accurate Predictions: Burst time must be known in advance, which isn’t always possible.
Final Thoughts
Preemptive Shortest Job First (SJF), or Shortest Remaining Time First (SRTF), is a powerful scheduling algorithm known for minimizing average waiting time. It’s a theoretically optimal algorithm but comes with practical challenges in implementation.
It works best in environments where burst times can be predicted accurately, and short tasks dominate the workload. However, if not implemented carefully, it can lead to starvation for longer tasks.
Prepare for Interview with us:
Prime Course Trailer
FAQs
In Preemptive SJF, a running process can be interrupted if a new process arrives with a shorter burst time. In contrast, Non-Preemptive SJF allows a process to run to completion once it starts, regardless of whether a shorter job arrives afterward.
The primary advantages include:
- Lower average waiting time
- Better responsiveness to short processes
- Efficient CPU utilization in systems with frequent short jobs
Some key challenges include:
- Starvation of longer processes if shorter jobs keep arriving
- High overhead due to frequent context switching
- Requires accurate burst time estimation, which may not always be available
While Preemptive SJF is optimal in theory, it’s rarely used in pure form in modern OS due to its complexity and risk of starvation. However, its concept is integrated into hybrid scheduling algorithms that combine priority scheduling, round-robin, and time slicing to balance efficiency and fairness.
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
Login/Signup to comment