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)
In the section above we looked at various scheduling algorithms. But how do
we decide which one to use?
The first thing we need to decide is how we will evaluate the algorithms. To do this we need to decide on the relative importance of the factors we listed above (Fairness, Efficiency, Response Times, Turnaround and Throughput). Only once we have decided on our evaluation method can we carry out the evaluation.
This evaluation method takes a predetermined workload and evaluates each algorithm
using that workload.
Assume we are presented with the following processes, which all arrive at time zero.
| Process | Burst Time |
| P1 | 9 |
| P2 | 33 |
| P3 | 2 |
| P4 | 5 |
| P5 | 14 |
Which of the following algorithms will perform best on this workload?
First Come First Served (FCFS), Non Preemptive Shortest Job First (SJF) and
Round Robin (RR). Assume a quantum of 8 milliseconds.
Before looking at the answers, try to calculate the figures for each algorithm.
The advantages of deterministic modeling is that it is exact and fast to compute.
The disadvantage is that it is only applicable to the workload that you use
to test. As an example, use the above workload but assume P1 only has a burst
time of 8 milliseconds. What does this do to the average waiting time?
Of course, the workload might be typical and scale up but generally deterministic modeling is too specific and requires too much knowledge about the workload.
Another method of evaluating scheduling algorithms is to use queuing theory.
Using data from real processes we can arrive at a probability distribution for
the length of a burst time and the I/O times for a process. We can now generate
these times with a certain distribution.
We can also generate arrival times for processes (arrival time distribution).
If we define a queue for the CPU and a queue for each I/O device we can test the various scheduling algorithms using queuing theory.
Knowing the arrival rates and the service rates we can calculate various figures such as average queue length, average wait time, CPU utilization etc.
One useful formula is Little's Formula.
n = λw
Where
n is the average queue length
λ is the average arrival rate for new processes (e.g. five a second)
w is the average waiting time in the queue
Knowing two of these values we can, obviously, calculate the third. For example, if we know that eight processes arrive every second and there are normally sixteen processes in the queue we can compute that the average waiting time per process is two seconds.
The main disadvantage of using queuing models is that it is not always easy to define realistic distribution times and we have to make assumptions. This results in the model only being an approximation of what actually happens.
Rather than using queuing models we simulate a computer. A Variable, representing a clock is incremented. At each increment the state of the simulation is updated.
Statistics are gathered at each clock tick so that the system performance can
be analysed.
The data to drive the simulation can be generated in the same way as the queuing
model, although this leads to similar problems.
Alternatively, we can use trace data. This is data collected from real processes
on real machines and is fed into the simulation. This can often provide good
results and good comparisons over a range of scheduling algorithms.
However, simulations can take a long time to run, can take a long time to implement and the trace data may be difficult to collect and require large amounts of storage.
The best way to compare algorithms is to implement them on real machines. This
will give the best results but does have a number of disadvantages.
· It is expensive as the algorithm has to be written and then implemented on real hardware.
· If typical workloads are to be monitored, the scheduling algorithm must be used in a live situation. Users may not be happy with an environment that is constantly changing.
· If we find a scheduling algorithm that performs well there is no guarantee that this state will continue if the workload or environment changes.
Last Page Back to Main Index Next Page
Last Updated : 23/01/2002