5.6 Algorithm evaluation

It will be a difficult task to choose the most suitable CPU scheduling approach for a certain system. To select an algorithm, we must first define the relative importance of the performance measures such as CPU utilization, response time, or throughput. Different evaluation methods will be described in the following subsections.

Deterministic modeling
This method takes a particular predetermined workload and defines the performance of each algorithm for that workload. The deterministic modeling gives fast results. However, its result is valid only for a given workload.

Queueing models

In queueing models, the computer system is described as a network of servers. Each server has a queue of waiting processes. The CPU is a server with its ready queue. Utilization, average queue length, and average wait time can be computed based on known arrival rates and service rates. Queueing analysis has the classes of algorithms and distributions that can be handled are limited.

Simulations
Simulations can give more accurate evaluation of scheduling algorithms. A model for a computer system is built. Statistics that indicate algorithm performance are gathered when the simulator executes. The data that run the simulations can be generated using random number generator. The data can be collected from an actual system.

5.6 Algorithm evaluation

Implementation
The most accurate way to evaluate a scheduling algorithm is to code it up, put it in the operating system. Then monitor how it is working in a real operating condition. The disadvantage of this approach is that it has high cost.