Shortest Job First Scheduling Non Preemptive
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
SJF Non Preemptive Example
Note – This example is given wrong on Geeks4Geeks. So make sure that you only study it on PrepInsta.
Let us try to understand SJF Non-Preemptive Scheduling with an example –
Here, processes are assumed to be arrived at the same time.
See the below Example –
|SJF Process||Burst Time ( in ms)||Arrival Time|
The order in which the CPU processes the process are(Gantt Chart) –
- 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
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.
- 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.
- 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