Apply For Jobs
Get Hiring UpdatesShortest Job First Scheduling Non Preemptive
Shortest Job First Scheduling Non Preemptive Scheduling Algorithm
Shortest Job First Scheduling Non Preemptive – When it comes to CPU scheduling algorithms in operating systems, Shortest Job First (SJF) Scheduling stands out as one of the most efficient strategies for minimizing waiting time and improving overall performance.
Especially in its Non-Preemptive form, SJF is straightforward yet powerful. In this blog, we’ll walk you through everything you need to know about SJF Non-Preemptive scheduling, including its definition, working mechanism, characteristics, advantages, disadvantages, real-world applications, and examples.
What is CPU Scheduling?
Before diving into SJF, it’s essential to understand CPU Scheduling. In a multiprogramming environment, when multiple processes are waiting for CPU time, the operating system decides the order in which they access the CPU. This decision-making process is known as CPU Scheduling, and the algorithm used to make the decision can significantly impact system performance.
Introduction to SJF Scheduling
Shortest Job First (SJF) is a scheduling algorithm that selects the process with the smallest CPU burst time for execution next. In simpler terms, the process that needs the least amount of time to complete is given priority.
There are two types of SJF scheduling:
- Preemptive SJF (also called Shortest Remaining Time First – SRTF)
- Non-Preemptive SJF
In this blog, we’ll focus on the Non-Preemptive variant.
Shortest Job First (SJF) – Non Preemptive
Shortest Job First Scheduling (Non Preemptive Algorithm) in Operating System
- Shortest Job First (SJF) is a Scheduling Algorithm where the process are executed in ascending order of their burst time, that is, the process having the shortest burst time is executed first and so on.
- The processor knows burst time of each process in advance.
- It can be thought of as shortest-next-cpu-burst algorithm, as Scheduling depends on length of the next CPU burst of a process. ( The duration for which a process gets control of the CPU, is the Burst time for a process.)
- SJF can be Pre-emptive or Non- preemptive. Under Non-preemptive Scheduling , once a process has been allocated to CPU, the process keeps the CPU until the process has finished its execution.
Read more – SJF Preemptive Scheduling here
Steps –
- Since Burst time for P3 (Burst = 1 sec) is lowest it is executed first.
- Then Burst time for P1 is lowest in order thus it gets executed the 2nd time.
- Similarly P4 and then P2
Waiting time –
- P1 waiting time = 1
- P2 waiting time = 7
- P3 waiting time = 0
- P4 waiting time = 3
The average waiting time is = ( 1+ 7 + 0 + 3 )/ 4 = 2.75
Prepare for Interview with us:
Features of SJF
- SJF is a greedy Algorithm
- It has Minimum average waiting time among all scheduling algorithms.
- Difficulty of SJF is knowing the length of next CPU request.
- It’s used frequently in Long-term scheduling in Batch System as in this, the time limit is provided by the user specifying the process. We presume that user provides accurate time limit as lower accurate value means faster response.
- SJF can’t be implemented in Short-term scheduling as one can’t know the exact length of next CPU burst. It can be Approximated by doing an exponential average of already measured length of previous CPU burst.
Drawback
- in SJF Scheduling, a process with high burst time may suffer starvation. Starvation is the process in which a process with higer burst time is kept on waiting and waiting , but is not allocated to the CPU. It’s prevented by aging.
- Total execution time must be known beforehand of a process.
What is aging?
- Aging is a technique which is used to reduce starvation of the processes.
- Aging takes into account the waiting time of the process in the ready queue and gradually increases the priority of the process.
- Hence, as the priority of a process gets increased this ensures that all process get completed eventually.
Final Thoughts:
Shortest Job First (SJF) Non-Preemptive Scheduling is one of the most effective scheduling algorithms when average waiting time and turnaround time are the primary metrics. However, it comes with challenges such as starvation and the requirement for prior knowledge of burst times. It’s best suited for batch systems and scenarios where process durations are known in advance.
By understanding its mechanism, advantages, limitations, and applications, developers and system administrators can use SJF strategically to optimize resource allocation and system efficiency.
FAQs
The main difference is that in Preemptive SJF (Shortest Remaining Time First), a currently running process can be interrupted if a new process with a shorter burst time arrives. In Non-Preemptive SJF, once a process starts execution, it runs till completion, regardless of the arrival of shorter jobs.
SJF always selects the shortest available job, which minimizes the waiting time for subsequent processes. Since shorter jobs finish earlier, they reduce the queue length faster, lowering the overall average waiting time compared to algorithms like FCFS or Round Robin.
The biggest challenge is accurately predicting the CPU burst time of each process in advance. In many real-time or unpredictable environments, it’s difficult to know how long a process will take before execution.
Starvation occurs when longer processes keep getting postponed due to continuous arrival of shorter ones. To prevent this, techniques like aging are used, where the priority of waiting processes increases over time, ensuring even long jobs eventually get CPU time.
Login/Signup to comment