OS1: Process Management – Unit 5: Algorithm Evaluation

Deterministic Modelling

Deterministic modelling is a type of analytical evaluation. Analytical evaluation uses the given algorithm and the system workload to produce a formula or number that evaluates the performance of the algorithm for that workload.

Deterministic modelling takes a particular predetermined workload and defines the performance of each algorithm for that workload.

Example 1:

Assume we have the workload shown. All five processes arrive at time 0, in the order given, with the length of the CPU-burst time given in milliseconds:

Consider the FCFS, SJF, and RR (quantum = 10milliseconds) scheduling algorithms for this set of processes. Which algorithm would give the minimum average waiting time?

For the FCFS algorithm, we would execute the processes as:

The waiting time is 10 milliseconds for process P1, 32 milliseconds for process P2, 0 milliseconds for P3, 3 milliseconds for process P4 and 20 milliseconds for process P5.

Therefore, the average waiting time is (10 + 32 + 0 + 3 + 20)/5 = 13 milliseconds.

With RR algorithm, we execute the processes as:

The waiting time is 0 milliseconds for process P1, 32 milliseconds for process P2, 20 milliseconds for P3, 23 milliseconds for process P4 and 40 milliseconds for process P5.

Therefore, the average waiting time is (0 + 32 + 20 + 23 + 40)/5 = 13 milliseconds.

You can see that in this case, the SJF results in less than one-half the average waiting time obtained with FCFS scheduling; the RR algorithm gives us an intermediate value.

• Advantages of Deterministic Modelling:
• It is simple and fast.
• It gives exact numbers, allowing the algorithms to be compared.

Disadvantages of Deterministic Modelling:

• It requires exact numbers for input and its answers apply to only those cases.
• It is too specific.
• It requires too much knowledge to be useful.

3.2

Queuing Models

Queuing models employ probabilistic distributions for CPU and I/O bursts 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, as is the I/O system with its device queues. Knowing arrival rates and service rates, we can compute utilization, average queue length, average wait time, etc. This area of study is called queuing-network analysis.

For instance, let n be the average queue length (excluding the process being serviced), let

W be the average waiting time in the queue, and let λ be the average arrival rate for new processes in the queue (such as three processes per second). Then we expect that during the time W that a process waits, λ × W new processes will arrive in the q. if the system is in a steady state, then the number of processes leaving the queue must be equal to the number of processes that arrive. Therefore,

n = λ × W.

120

This equation is known as Little’s formula. The formula is particularly useful because it is valid for any scheduling algorithm and arrival distribution. It can be used to compute one of the three variables once the other two are known.

Advantages of Queuing Analysis:

• It can be useful in comparing scheduling algorithms.

Limitations:

• The classes of algorithms and distribution that can be handled is presently limited
• It is hard to express a system of complex algorithms and distributions.
• Queuing models are often an approximation of a real system. As a result, the accuracy of the computed results may be questionable.

3.3

Simulations

This is used to get a more accurate evaluation of scheduling algorithms. Simulations involve programming a model of the computer system. Software data structures represent the major components of the system. The simulator has a variable representing a clock; as this variable’s value is increased, the simulator modifies the system state to reflect the activities of the devices, the processes and the scheduler. As the simulation executes, statistics that indicate algorithm performance are gathered and printed.

Figure 3.1: Evaluation of CPU scheduler by Simulation.

Advantages:

• It produces accurate results for its inputs.

Disadvantages:

• It can be expensive
• Trace tapes can require large amounts of storage space.
• The design, coding and debugging of the simulator can be a major task.

3.4

Implementation

Even a simulator is of limited accuracy. The only completely accurate way to evaluate a scheduling algorithm is to code it, put it in the operating system, and see how it works.

This approach puts the actual algorithm in the real system for evaluation under real operating conditions.

Limitations:

• This approach is very expensive. The expense is incurred not only in coding the algorithm and modifying the operating system to support it as well as its required data structure, but also in the reaction of the users to a constantly changing operating system.

4.0

Conclusion

This unit has taken you through the various scheduling evaluation algorithms. However, as you have seen there is no perfect evaluation algorithm. There are always difficulties to be encountered when evaluating scheduling algorithms. One of the major difficulties with any algorithm evaluation is that the environment in which the algorithm is used will change. The environment will change not only in the usual way, as new programs are written and the types of problems change, but also as a result of the performance of the scheduler. If short processes are given priority, then users may break larger processes into sets of small processes. If interactive processes are given priority over non-interactive processes, then users may switch to interactive use.