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)
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
Where
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