G53OPS - Operating Systems

This course is run at the The University of Nottingham within the School of Computer Science & IT. The course is run by Graham Kendall (EMAIL : gxk@cs.nott.ac.uk)

Shortest Job First

Using the SJF algorithm, each process is tagged with the length of its next CPU burst. The processes are then scheduled by selecting the shortest job first.

Consider these processes, P1..P4. Assume they arrived in the order P1..P4.

Process Burst Time Wait Time
P1 12 0
P2 19 12
P3 4 31
P4 7 35

If we schedule the processes in the order they arrive then the average wait time is 19.5 (78/4). If we run the processes using the burst time as a priority then the wait times will be 0, 4, 11 and 23; giving an average wait time of 9.50.

In fact, the SJF algorithm is provably optimal with regard to the average waiting time. And, intuitively, this is the case as shorter jobs add less to the average time, thus giving a shorter average.

The problem is we do not know the burst time of a process before it starts.

For some systems (notably batch systems) we can make fairly accurate estimates but for interactive processes it is not so easy.
One approach is to try and estimate the length of the next CPU burst, based on the processes previous activity.

To do this we can use the following formula

Tn+1 = atn + (1 - a)Tn


a, 0 <= a <= 1
Tn, stores the past history
tn, contains the most recent information

What this formula allows us to do is weight both the history of the burst times and the most recent burst time. The weight is controlled by a.

If a = 0 then Tn+1 = Tn and recent history (the most recent burst time) has no effect. If a = 1 then the history has no effect and the guess is equal to the most recent burst time.

A value of 0.5 for a is often used so that equal weight is given to recent and past history.

This formula has been reproduced on a spreadsheet. Experiment with the various values.

Last Page Back to Main Index Next Page


 Last Updated : 13/01/2002