This technique is associated with the length of the next CPU burst of a process. When the CPU is available, it is assigned to the process that has smallest next CPU burst. If the next bursts of two processes are the same, FCFS scheduling is used.

The SJF algorithm is optimal i.e. it gives the minimum average waiting time for a given set of processes.

The real difficulty with this algorithm knows the length of next CPU request.

Let us consider following set of process with the length of the CPU burst given in milliseconds.

Examples

Q1. Consider the following set of processes that arrives at time 0, with the length of the CPU burst given in milliseconds:

Process Burst Time
P1 6
P2 8
P3 7
P4 3

SJF scheduling chart

The waiting time for process P1= 3, P2 = 16, P3 = 9 and P4 = 0 milliseconds, Thus

Average waiting time

= (3 + 16 + 9 + 0) / 4

= 7 milliseconds

A preemptive SJF algorithm will preempt the currently executing, where as a non-preemptive SJF algorithm will allow the currently running process to finish its CPU burst. Preemptive SJF scheduling is also known Shortest-Remaining-time (SRT) First Scheduling.

Let us consider following four processes with the length of the CPU burst given in milliseconds.

Process Arrival Time Burst Time
P1 0 8
P2 1 4
P3 2 9
P4 3 5

Gantt chart is:

P1 P2 P4 P1 P3

 0                         1                          5                           10                        17                      26

Process P1 is started at time 0, since it is the only process in the queue. Process P2 arrives at time

  1. The remaining time for process P1 (7 milliseconds) is larger than the time required by process P2 (4 milliseconds), so process P1 is preempted, and process P2 is scheduled.
  • The average waiting time is: = (P1 + P2 + P3 + P4) / 4

                  = [(10 - 1) + (1 - 1) + (17 - 2) + (5 - 3) ]/4

                  = (9 + 0 + 15 + 2)/4

                  =  26 / 4

                  =  6.5 milliseconds

Example: Non-Preemptive SJF

Process Arrival Time Burst Time
P1 0.0 7
P2 2.0 4
P3 4.0 1
P4 5.0 4

SJF (non-preemptive) Gant Chart

Average waiting time

=    (P1 + P2 + P3 + P4) / 4

=    [(0 – 0) + (8 – 2) + (7 – 4) + (12 – 5)] / 4

=    (0 + 6 + 3 + 7) / 4

=    4 milliseconds

Example: Preemptive SJF

Process Arrival Time Burst Time
P1 0.0 7
P2 2.0 4
P3 4.0 1
P4 5.0 4

SJF (preemptive) (Shortest Remaining Time First, SRTF) Gantt chart

Average waiting time

=    [(11 – 2) + (5 – 4) + (4 – 4) + (7 – 5)] / 4

=    (9 + 1 + 0 +2) / 4

=    3 milliseconds