Top 3 Performance Comparison Methods of CPU Scheduling Algorithms

Top 3 Performance Comparison Methods of CPU Scheduling Algorithms

The performance of the CPU scheduling algorithms depends on a variety of features including

  1. The probability distribution of service time of various processes.
  2. The efficiency of scheduling and content switching mechanism.
  3. Nature of the I/O demand and the performance of the I/O sub-system.

We will learn three main performance comparison methods:

  1. Deterministic Modeling
  2. Queuing analysis
  3. Simulators

1. Deterministic Modeling

This method takes a predetermined workload and defines the performance of each algorithm for that workload. For example, assume that we have a workload containing 5 processes arriving at time 0. The length of CPU burst time is given in milliseconds.

ProcessCPU Burst Time (in milliseconds)
P16
P212
P31
P43
P54

Consider FCFS, SJF, and RR (Quantum = 1) scheduling algorithms for this process. From the above three algorithms, which would give the minimum average time, we can say that algorithm is the best. For the above example, SJF has the least waiting time, so it is said to be the best one.

This type of algorithm execution is said to be Deterministic Modeling. It is simple and fast and it requires exact numbers for input and its answers apply to only those cases.

2. Queuing Analysis

Queuing Analysis can be useful in comparing scheduling algorithms. If we know the arrival rates and service rates, we can compute CPU utilization, Average queue length, Average wait time, and so on. This area of study is called queuing analysis.

For example, consider Little’s formula, N = λ x W
Where,
N = Average queue length
λ = Average arrival rate in the queue
W = Waiting time of the process

We can use Little’s formula to compute one of the 3 variables if we know the other 2 variables.

3. Simulators

We can get a more accurate evaluation of scheduling algorithms with simulations. Simulations involve programming a model of the computer system. Software data structures represent the major components of the system. When the simulation executes, statistics that indicate the algorithm’s performance is gathered.

For example, consider the figure:

simulators-evaluation

Leave a Comment

Your email address will not be published. Required fields are marked *

Scroll to Top