Shortest Job First Scheduling Algorithm (SJF)
- SJF is also known as Shortest-Job-Next (SJN) algorithm and is faster than FCFS.
- When the CPU is available, it is assigned to the process that has the smallest next CPU For this, SJF algorithm associates with each process, the length of its next CPU burst.
- In SJF, the process with the least estimated execution time is selected from the ready queue for execution. burst.
- If two processes have the same length of next CPU burst. FCFS scheduling algorithm used to break the tie.
- SJF algorithm can be preemptive or non-preemptive.
Non-Preemptive SJF Algorithm
- In Non-preemptive SJF, scheduling, CPU is always assigned to the process with least CPU burst time and the process keeps CPU with it until it terminates.
- The main advantage of SJF scheduling is that it gives minimum average waiting time for a given set of processes. By moving a short process before a long process, the waiting time of the short process decreases more than it increases the waiting time of the long process.
- The main disadvantage of SJF scheduling is that it requires precise knowledge of how long a job or process will run and this information is usually not available. However a prediction formula can be used to predict the amount of time for which CPU may be required by a process.
- Another disadvantage of SJF scheduling is that the processes with high estimated execution time may have to wait for a long time if there are a large number of processes with short estimated execution time.
Preemptive SJF Algorithm
- The preemptive version of SJF scheduling is known Shortest Remaining Time (SRT) scheduling.
- SRT scheduling is useful in timesharing system.
- In SRT, the process with the smallest estimated run-time to completion is run next. This rule is applied even for new arrival processes.
- Any time a new process enters the pool of processes to be scheduled, the scheduler compare the expected value for its remaining processing time with that of the process currently running. If the new process’s time is less, then currently running process is preempted and CPU is allocated to new process.
The disadvantages of SRT scheduling are :
- The execution time of processes must be known in advance. Calculating execution time of a process without executing it is difficult.
- SRT has higher overhead than SJF. It must keep the track of the elapsed service-time of the running job and must handle occasional preemptions.
- As SRT favors short jobs, the mean waiting time for longer processes or jobs is no longer and long jobs can be victim of starvation.
Example of Non-preemptive SJF Algorithm
Consider the set of following processes having CPU burst time in milliseconds and having arrived at almost same time
| Process | Burst Time |
| P1 | 6 |
| P2 | 8 |
| P3 | 7 |
| P4 | 3 |
The scheduling of various processes is shown in the following Gantt chart:
How to Calculate Completion Time?
Completion time is the time taken by a process for its execution. It is calculated by subtracting initial time from time of its completion.
How to calculate Turn Around Time (T.A.T.)?
Turn Around Time (T.A.T.) = Completion Time – Arrival Time (0 if not given in question).
How to calculate Waiting Time?
Waiting time (W.T.) = Turn Around Time (T.A.T.) – Burst Time (B.T.)
| Process | Arrival Time (A.T.) | Burst Time (B.T.) | Completion Time (C.T.) | Turn Around Time (T.A.T.) | Waiting Time (W.T.) |
| P1 | 0 | 6 | 6 | 6 | 3 |
| P2 | 0 | 8 | 8 | 8 | 16 |
| P3 | 0 | 7 | 7 | 7 | 9 |
| P4 | 0 | 3 | 3 | 3 | 0 |
Waiting time for P1 = 3 milliseconds
Waiting time for P2 = 16 milliseconds
Waiting time for P3 = 9 milliseconds
Waiting time for P4 = 0 milliseconds
Average waiting time = (3+16 +9+0)/4 = 7 milliseconds
Example of preemptive SJF Scheduling:
Consider the following 4 processes with burst time in milliseconds. These 4 processes arrived in the ready queue at the times shown in the table below:
| Process | Arrive Time | Burst Time |
| P1 | 0 | 8 |
| P2 | 1 | 4 |
| P3 | 2 | 9 |
| P4 | 3 | 5 |
The scheduling of various processes is shown in the following Gantt chart:
| Process | Arrival Time (A.T.) | Burst Time (B.T.) | Waiting Time (W.T.) |
| P1 | 0 | 8 | 9 |
| P2 | 1 | 4 | 0 |
| P3 | 2 | 9 | 15 |
| P4 | 3 | 5 | 2 |
- Process P1 is started at time 0, as it is the only process in the queue.
- Process P2 arrives at time 1 and its burst time is 4 milliseconds. This burst time than the remaining time for process P1 (7 milliseconds), so process P1 is preempted and P2 is scheduled.
- The process P3 arrives at time 2. Its burst time is 9 milliseconds which is larger than remaining time for process P2 (3 milliseconds). So P2 is not preempted.
- The process P4 arrives at time 3. Its burst time is 5 milliseconds. Again it is larger than the remaining time for process P2 (2 milliseconds). Hence P2 is not preempted.
- After the termination of P2 the process with shortest next CPU burst i.e. process P4 scheduled.
- After process P4 processes P1 (7 milliseconds) and then process P9 (9 milliseconds) are scheduled.
Calculating the average waiting time :
Waiting time for P1 = 10 -1 =9 milliseconds
Waiting time for P2 = 1-1=0 milliseconds
Waiting time for P3 = 17 -2 = 15 milliseconds
Waiting time for P4 = 5-3 = 2 milliseconds
Average waiting time = {(10-1) + (1-1) + (17-2) + (5-3)}/ 4
= (9+0+15 +2)/4 = 26/4
= 6.5 milliseconds