Performance Comparison or Algorithm Evaluation:

· How do we select CPU scheduling algorithm for a particular system?

· First problem is defining the criteria to be used in selecting an algorithm.

· These criteria are often defined in terms of CPU utilization, response time, and throughput.

· Criteria may include several measures like:

Maximize CPU utilization under constraint that maximum response time is 1 second.
Maximize throughput such that turnaround time is on average linearly proportional to total execution time.

Different Evaluation Methods:

Analytic evaluation uses given algorithm and the system workload to produce formula or a number that evaluates performance of algorithm for that workload.
Deterministic modeling is one type of analytic evaluation.
This method takes particular pre-determined workload and defines performance of each algorithm for that workload.
For example, assume we have following workload. All five processes arrive at time 0, in the order given, with the length of CPU burst in milliseconds:

Consider FCFS, SJF and RR (Quantum = 10 millisecond) for this set of processes. Which algorithm would give minimum average waiting time?

For FCFS algorithm,

Average waiting time = (0 + 10 + 39 + 42 + 49)/5 = 28 milliseconds

With non-preemptive SJF algorithm,

Average waiting time = (10 + 32 + 0 + 3 +20)/5 = 13 milliseconds

With Round Robin algorithm,

Average waiting time = (0 + 32 + 20 + 23 + 40)/5 = 23 milliseconds

The deterministic modeling is simple and faster technique.
It gives exact numbers, allowing algorithms to be compared.
The drawback of deterministic modeling is that, it requires exact numbers of inputs, and its answers apply to only those cases.
Main uses of deterministic modeling are in describing a scheduling algorithms and providing examples.

A computer system is described as a network of servers.
Each server has a queue of waiting processes.
CPU is a server with its ready queue, as is IO system with its device queues.
Knowing arrival rates and service rates, we can compute utilization, average queue length, average waiting time, etc.
This area of study is called queuing network analysis.
For example, let ‘n’ be average queue length, ‘W’ be average waiting time in queue, ‘λ’ be average arrival rate for new processes in a queue.
If the system is in steady state, then number of processes leaving the queue must be equal to the number of processes that arrive.
So, n=λ x W, this formula is called as Little's formula.
It is useful because it is valid for any scheduling algorithm and arrival distribution.
We can use this formula to compute one of the three variables, if we know the other two variables.
Queuing analysis can be useful in comparing scheduling algorithms but it also has certain limitations.
Mathematics of complicated algorithms or distribution can be difficult to work with.

To get a more accurate evaluation of scheduling algorithms we can use simulations.
Simulations involve programming a model of a computer system.
Software data structures represent major components of a system.
Simulator has a variable representing a clock. As its value is increased or decreased, simulator modifies system state to reflect activities of devices, processes and scheduler.
As simulation executes, statistics that indicate algorithm performance are gathered and printed.
Data to drive simulation can be generated in several ways. Most common method used is random number generator which is programmed to generate processes, CPU burst time, arrivals, departures, etc. according to probability distributions.
Distributions may be defined mathematically or empirically.
For empirical distribution, measurements of actual system under study are taken.
Distribution driven simulation may be inaccurate due to relationships between successive events in the system.
Trace tapes are used to correct this problem. A trace tape is created by monitoring real system, recording sequence of actual events.
This sequence is then used to drive simulation.
Trace tapes provides excellent way to compare two algorithms on exactly the same set of real inputs.
Accurate results are produced with this method.

Drawbacks of simulations are as follows:

It can be expensive; requires hours of computer time.
Most detailed simulation provides more accurate results but also requires more computer time.
Trace tapes can require large amounts of storage space.
Designing, coding, debugging of simulator can be a major task.