Shortest-Job-First Scheduling

• A different approach to CPU scheduling is the shortest-job-first (SJF) scheduling algorithm. This algorithm associates with each process the length of the process's next CPU burst.
• When the CPU is available, it is assigned to the process that has the smallest next CPU burst. If the next CPU bursts of two processes are the same, FCFS scheduling is used.
• As an example of SJF scheduling, consider the following set of processes, with the length of the CPU burst given in milliseconds:
  

  	Burst	Waiting	Turnaround
  Process	Time	Time	Time
  $P_1$	6	3	9
  $P_2$	8	16	24
  $P_3$	7	9	16
  $P_4$	3	0	3
  Average	-	7	13

• Using SJF scheduling, we would schedule these processes according to the following chart:

  
• By comparison, if we were using the FCFS scheduling scheme, the average waiting time would be 10.25 milliseconds.
• The SJF scheduling algorithm gives the minimum average waiting time for a given set of processes.
  • Moving a short process before a long one decreases the waiting time of the short process more than it increases the waiting time of the long process.
  • Consequently, the average waiting time decreases.
• The real difficulty with the SJF algorithm is knowing the length of the next CPU request. For long-term (job) scheduling in a batch system, we can use as the length the process time limit that a user specifies when he submits the job.
• Although the SJF algorithm is optimal, it can not be implemented at the level of short-term CPU scheduling. There is no way to know the length of the next CPU burst.
• We may not know the length of the next CPU burst, but we may be able to predict its value. We expect that the next CPU burst will be similar in length to the previous ones.
• Also, long running jobs may starve for the CPU when there is a steady supply of short jobs.
• Example: In Fig. 5.6a, the average turnaround time is 14 minutes. Consider running these four jobs using SJF, as shown in Fig. 5.6b, the average turnaround time now becomes 11 minutes.

  Figure 5.6: An example of shortest job first scheduling. (a) Running four jobs in the original order. (b) Running them in shortest job first order.

  

  Figure 5.7: An example to Shortest Job First.

  
• The SJF algorithm can be either pre-emptive or nonpreemptive. The choice arises when a new process arrives at the ready queue while a previous process is still executing.
• The next CPU burst of the newly arrived process may be shorter than what is left of the currently executing process. A pre-emptive SJF algorithm will preempt the currently executing process, whereas a nonpreemptive SJF algorithm will allow the currently running process to finish its CPU burst.
• Pre-emptive SJF scheduling is sometimes called shortest-remaining-time-first scheduling. As an example, consider the following four processes, with the length of the CPU burst given in milliseconds:
  

  	Arrival	Burst	Waiting	Turnaround
  Process	Time	Time	Time	Time
  $P_1$	0	8	9	17
  $P_2$	1	4	0	4
  $P_3$	2	9	15	24
  $P_4$	3	5	2	7
  Average	-	6.5	13

• If the processes arrive at the ready queue at the times shown and need the indicated burst times, then the resulting pre-emptive SJF schedule is as depicted in the following chart:

  
• Nonpreemptive SJF scheduling would result in an average waiting time of 7.75 milliseconds.

  Figure 5.8: Example of non-pre-emptive SJF and pre-emptive SJF.