CREATE OWN LIBRARY

Algorithm Evaluation for Scheduling

It is difficult we select a CPU-scheduling algorithm for a particular system because every scheduling algorithm has its own parameter.

To select an algorithm, we first decide which elements are relatively important.

Some criteria may include several measures:

a) Maximizing CPU utilization under the constraint that the maximum response time is 1 second.

b) Maximizing throughput such that turnaround time is (on average) linearly proportional to total execution time.

c) Minimize waiting time.

After deciding the selection criteria for analyzing the algorithms, we want to evaluate scheduling algorithms under consideration.

Here we define various evaluation methods:

a) Deterministic Modeling:

Analytic evaluation is a major class of evaluation methods where it’s provided a formula or number to evaluate the performance of the algorithm according to the given algorithm and the system work load.

Deterministic modeling is one type of analytic evaluation. Here this method is very simple; it takes a predetermined workload and evaluates the performance of each and every algorithm for the given workload.

It is very simple like we take a table as predetermined workload:

Now calculate the waiting time of FCFS, SJF, SRTF, Round-Robin, and according to minimize waiting time evaluate the performance of the said algorithms. 

b) Queuing Models: 

Its uses of mathematical models to evaluate the performance of various systems led to the development of a separate branch of mathematics known as queuing theory. And Performance analysis using this theory is called queuing analysis.

Queuing analysis is used to develop mathematical expressions for server efficiency, mean queue length, and mean wait time. In this method, the computer system is treated 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, and soon. This area of study is called queuing-network analysis.

As an example let,

n = average queue length (excluding the process being serviced).

W = average waiting time in the queue.

λ = average arrival rate for new processes in the queue (such as three processes per second)

We expect that during the time W that a process waits, λ×W new processes will arrive in the queue. 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. Thus,

n = λ × W

This equation, known as Little’s formula.