Scheduling Criteria

The goal of a scheduling algorithm is to identify the process whose selection will result in the best possible system performance.
Best performance is a subjective evaluation and depends upon the number of criteria of different relative importance.
The commonly used criteria can be grouped into two categories user oriented and system oriented criteria.
User Oriented criteria relate to the behavior of the system as perceived by the individual user or process. For example, response time, turnaround time.
System Oriented criteria relate to the effective and efficient use of processor. For example: throughput, processor utilization, fairness, priorities.
User Oriented criteria are important on all system, system oriented criteria are generally of minor importance on single-user system.

The various scheduling criteria for evaluating an algorithm are:

CPU utilization is the average fraction of time during which the processor is busy.
Being busy usually refers to the processor not being idle and includes both the time i.e. time spent in executing user program as well as the time spent in executing the operating system.
The level of CPU utilization depends on the load on the system.
CPU utilization may range from 0 to 100 percent. In a real system, it should range from 40 percent (for light loaded system) to 90 percent (for a heavily used system).

Throughput refers to the number of processes the system can execute in a period of time
For long processes, this rate may be 1 process per hour, for short processes, throughput may be 10 processes per second.
Thus evaluation of throughput depends on the average length of a process.
Throughput is also dependent on the job-mix i.e., the number of CPU bound & I/0 bound processes. If all the processes are CPU bound, throughout will be less as compared to 1/O based processes (which requires CPU for less time and hence more of them can be finished in a given time). Thus two types of jobs should be properly mixed to improve the throughput.

This is the interval of time between the submission of a process and its completion.
Thus turnaround time is an average period of time it takes a process to execute.
A process’s turnaround time includes all the time it spends in the system and can be computed by subtracting the time the process was created from the time it terminated.
Therefore, turnaround time includes actual execution time plus time spent waiting for resources (i.e. time spent waiting to get into memory, waiting in ready queue and doing I/0).
Turnaround time is inversely proportional to throughput.
It is the metrics used for batch jobs.

It is the average period of time a process spends waiting.
It is a time spent in waiting for a resource allocation. Therefore, waiting time is the penalty imposed for sharing resources with others.
Waiting time presents a more accurate measure of performance as compared to turnaround time because it does not include the time a process is executing on the CPU or performing I/O. It includes only the time a process spends waiting.
Waiting time can be expressed as turnaround time minus the actual execution time.

W(x) = T(x) – x

where x is the service time,

W(x) is the waiting time of job requiring x units of service

and T(x) is the job’s turnaround time.

Response time is defined as the time interval between the job submission and the first response produced by the job.
Thus, it is the average time it takes the system to start responding to user input. It is not the time taken to output the response.
Response time is an important metric used in the interactive system.
In order to obtain better performance response time should be low.

A given job should run in about the same amount of time and at about the same cost regardless of the load on the system.
A wide variation in response time or turnaround time is distracting to users.
For example, an interactive system that routinely responds within a second, but on occasion takes 10 sec. to respond, may be viewed more negatively than a system that consistency responds in 2 secs. Although average response time in the latter system is greater, user may prefer the system with greater predictability.

Fairness refers to the degree to which all processes are given equal opportunity to execute.
In the absence of guidance from the user or other system supplied guidance, processes should be treated the same and no process should suffer starvation.
A process is a victim of starvation if it becomes struck in a scheduling queue indefinitely.

When the processes are assigned priorities, the scheduling policy should give preference to the higher priority processes.
Higher priority processes should be given preference and the lower priority processes should be preempted.

The main purpose of scheduling is to maximize CPU utilization and throughput and to minimize turnaround time, waiting time and response time.

2 thoughts on “Scheduling Criteria”