Evaluation of Process Scheduling Algorithms
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.
Deterministic Modeling
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 |
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.
Queuing Models
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 = λwWhere
n is the average queue lengthKnowing 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.
λ is the average arrival rate for new processes (e.g. five a second)
w is the average waiting time in the queue
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.
Simulations
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.
Implementation
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.