Page 81 - DCAP403_Operating System

Operating System

Notes process needs to wait (does IO, is interrupted, etc.) the operating system picks a process from
the ready queue and assigns the CPU to that process. The cycle then continues. There are many
scheduling algorithms, ranging in complexity and robustness: First-come, First-serve scheduling,
Shortest Job First scheduling, Round-Robin scheduling, etc.
A major task of an operating system is to manage a collection of processes. In some cases, a single
process may consist of a set of individual threads.

In both situations, a system with a single CPU or a multi-processor system with fewer CPU’s than
processes has to divide CPU time among the different processes/threads that are competing to
use it. This process is called CPU scheduling.

There are many scheduling algorithms and various criteria to judge their performance. Different
algorithms may favor different types of processes. Some criteria are as follows:
1. CPU utilization: CPU must be as busy as possible in performing different tasks. CPU
utilization is more important in real-time system and multi-programmed systems.
2. Throughput: The number of processes executed in a specified time period is called

throughput. The throughput increases .for short processes. It decreases if the size of
processes is huge.
3. Turnaround Time: The amount of time that is needed to execute a process is called
turnaround time. It is the actual job time plus the waiting time.
4. Waiting Time: The amount of time the process has waited is called waiting time. It is the
turnaround time minus actual job time.
5. Response Time: The amount of time between a request is Submitted and the fi rst response
is produced is called response time.

5.3 Scheduling Algorithms

Most Operating Systems today use very similar CPU time scheduling algorithms, all based on the
same basic ideas, but with Operating System-specific adaptations and extensions. What follows

is a description of those rough basic ideas.
What should be remarked is that this algorithm is not the best algorithm that you can imagine,
but it is, proven mathematically and by experience in the early days of OS programming (sixties
and seventies), the algorithm that is the closest to the ‘best’ algorithm. Perhaps when computers
get more powerful some day then we might implement the ideal CPU time scheduler.
Another remark is that this algorithm is designed for general-purpose computers. Special-purpose
Operating Systems or systems, and some real-time systems will use a very different algorithm.

CPU scheduling is the task of selecting a waiting process from the ready queue and allocating the
CPU to it. The CPU is allocated to the selected process by the dispatcher.
A CPU scheduling algorithm should try to maximize the following:

1. CPU utilization
2. Throughput
A CPU scheduling algorithm should try to minimize the following:
1. Turnaround time

2. Waiting time
3. Response time
Different algorithms are used for CPU scheduling.

74 LOVELY PROFESSIONAL UNIVERSITY