Chapter 6 (CPU Scheduling)

CPU scheduling is the basis of multi-programmed operating systems. By switching the CPU among
processes, the operating system can make the computer more productive.

Objectives
 To introduce CPU scheduling.
 To describe various CPU-Scheduling algorithms.
 To discuss evaluation criteria for selecting a CPU-Scheduling algorithm for a particular
system.
6.1 Basic Concepts
In a single-processor system, only one process can run at a time. Others must wait until the CPU is
free and can be rescheduled. The objective of multiprogramming is to have some process running at
all times, to maximize CPU utilization.

A process is executed until it must wait, typically for the completion of some I/O request. In a
multiprogramming system, several processes are kept in memory at one time. When one process
has to wait, the operating system takes the CPU away from that process and gives the CPU to
another process. This is called CPU scheduling.

6.1.1 CPU – I/O Burst Cycle

The success of CPU scheduling depends on an observed property of processes:
Process execution consists of a cycle of CPU execution and I/O wait. Process execution begins with
a CPU burst, followed by an I/O burst, alternating between these two states. Eventually, the final
CPU burst ends with a system request to terminate execution (Figure 6.1).

CPU bursts vary greatly from process to process and from computer to computer, they tend to have
a frequency curve similar to that shown in Figure 6.2. The curve is generally characterized as
exponential or hyper exponential, with a large number of short CPU bursts and a small number of
long CPU bursts.

An I/O-bound program typically has many short CPU bursts. A CPU-bound program might have a
few long CPU bursts. This distribution can be important in the selection of an appropriate CPU-
scheduling algorithm.

6.1.2 CPU Scheduler

Whenever the CPU becomes idle, the operating system must select one of the processes in the ready
queue to be executed. The selection process is carried out by the short-term scheduler, or CPU
scheduler.

A ready queue can be implemented as a FIFO queue, a priority queue, a tree, or simply an unordered
linked list. The records in the queues are generally process control blocks (PCBs) of the processes.

6.1.3 Preemptive Scheduling

CPU-scheduling decisions may take place under the following four circumstances:
1. When a process switches from the running state to the waiting state (for eg, as the result of an
I/O request or an invocation of wait() for the termination of a child process)
2. When a process switches from the running state to the ready state (for eg, when an interrupt
occurs)
3. When a process switches from the waiting state to the ready state (for eg, at completion of I/O)
4. When a process terminates

For situations 1 and 4, there is no choice in terms of scheduling. A new process (if one exists in the
ready queue) must be selected for execution. There is a choice, however, for situations 2 and 3.

When scheduling takes place only under circumstances 1 and 4, we say that the scheduling scheme
is non-preemptive or cooperative. Otherwise, it is preemptive.

Non-preemptive Vs. Preemptive Scheduling

Def - Once the CPU has been allocated to Def - Once the CPU has been allocated to
a process, it keeps the CPU (no choice) a process, it can be forcibly taken away
until it releases the CPU either by (choice), for eg when time quantum
terminating or by switching to the expires
waiting state.
It does not require the special hardware. It requires special hardware (for eg, a
timer).
It simple It is complex because it affects design of
OS kernel*.
It is not expensive It is expensive because it can result in
race conditions** when data is shared
among several processes.

**Consider the case of two processes that share data. While one process is updating the data, it is
preempted so that the second process can run. The second process then tries to read the data, which
are in an inconsistent state. This is referred to as race condition.

*Preemption also affects the design of the operating-system kernel. During the processing of a
system call, the kernel may be busy with an activity on behalf of a process. Such activities may
involve changing important kernel data (for instance, I/O queues). What happens if the process is
preempted in the middle of these changes and the kernel needs to read or modify the same
structure? Certain operating systems, including most versions of UNIX, deal with this problem by
waiting either for a system call to complete or for an I/O block to take place before doing a context
switch. This scheme ensures that the kernel structure is simple, since the kernel will not pre-empt
a process while the kernel data structures are in an inconsistent state. Unfortunately, this kernel-
execution model is a poor one for supporting real-time computing where tasks must complete
execution within a given time frame.

6.1.4 Dispatcher
Another component involved in the CPU-scheduling function is the dispatcher. The dispatcher is
the module that gives control of the CPU to the process selected by the short-term scheduler. This
function involves the following:

• Switching context
• Switching to user mode
• Jumping to the proper location in the user program to restart that program

The dispatcher should be as fast as possible, since it is invoked during every process switch. The
time it takes for the dispatcher to stop one process and start another running is known as the
dispatch latency.

6.2 Scheduling Criteria

Different CPU-scheduling algorithms have different properties, and the choice of a particular
algorithm may favour one class of processes over another (SJF favours short processes). In
choosing which algorithm to use in a particular situation, we must consider the properties of the
various algorithms.

Following criteria have been suggested for comparing CPU-scheduling algorithms:

FIFO, SJF

• CPU utilization (maximise) - CPU must be as busy as possible. In a real system, it should range
from 40 percent (lightly loaded system) to 90 percent (heavily loaded system).

• Throughput (maximise) - It is the measure of work, i.e., number of processes completed per time
unit. For long processes, this rate may be one process per hour; for short transactions, it may be ten
processes per second.

• Turnaround time (minimise) - The interval from the time of submission of a process to the time of
completion is the turnaround time. Turnaround time is the sum of the periods spent waiting to get
into memory, waiting in the ready queue, executing on the CPU, and doing I/O.
• Waiting time (minimise) - The CPU-scheduling algorithm does not affect the amount of time
during which a process executes or does I/O. It affects only the amount of time that a process
spends waiting in the ready queue. Waiting time is the sum of the periods spent waiting in the
ready queue.

• Response time (minimise) - In an interactive system, turnaround time may not be the best
criterion. Often, a process can produce some output fairly early and can continue computing new
results while previous results are being output to the user. Thus, another measure is the time from
the submission of a request until the first response is produced. This measure, called response time,
is the time it takes to start responding, not the time it takes to output the response. The turnaround
time is generally limited by the speed of the output device.

6.3 Scheduling Algorithms

CPU scheduling deals with the problem of deciding which of the processes in the ready queue is to
be allocated the CPU.

6.3.1 First-Come, First-Served Scheduling (FCFS)

It is a scheme where the process that requests the CPU first is allocated the CPU first. When a
process enters the ready queue, its PCB is linked onto the tail of the queue. When the CPU is free, it
is allocated to the process at the head of the queue. The running process is then removed from the
queue.

Consider the following set of processes that arrive at time 0, with the length of the CPU burst given
in milliseconds:
Process Burst Time
P1 24
P2 3
P3 3

The following Gantt chart illustrates FCFS schedule, including the start and finish times of each of
the participating processes:

P1 P2 P3
0 24 27 30

Waiting Time:
P1 – 0
P2 – 24
P3 – 27
Average waiting Time = (0+24+27)/3 = 17 milliseconds

If the processes arrive in the order P2, P3, P1, however, the results will be as shown in the following
Gantt chart:

P2 P3 P1
0 3 6 30

Waiting Time:
P1 – 6
P2 – 0
P3 – 3
Average waiting Time = (6+0+3)/3 = 3 milliseconds (this reduction is substantial).

Assume there is one CPU-bound process (A) and many I/O-bound processes (Bs). A will get and hold
the CPU while Bs will finish their I/O and move into the ready queue, waiting for the CPU. All I/O
devices are idle. Eventually, A finishes its CPU burst and moves to an I/O device. Bs, which have
short CPU bursts, execute quickly and move back to the I/O queues. Here, the CPU sits idle. A will
then get CPU back. Again, Bs end up waiting in the ready queue until A is done. There is a convoy
effect as all other processes wait for one big process to get off the CPU. This effect results in lower
CPU and device utilization than might be possible if the shorter processes were allowed to go first.

Advantages -
 The code for FCFS scheduling is simple to write and understand.
 The implementation of the FCFS policy is easily managed with a FIFO queue.
Disadvantages -
 The average waiting time is often quite long. It may also vary substantially if the processes’
CPU burst times vary greatly (we can see from above eg).
 It suffers from convoy effect.
 It is non-preemptive algorithm and thus not suitable for time-sharing systems.

6.3.2 Shortest-Job-First Scheduling (SJF)

This algorithm associates with each process the length of the process’s next CPU burst. CPU is
assigned to the process that has the smallest next CPU burst. If the next CPU bursts of two
processes are the same, FCFS scheduling is used.

As an example of SJF scheduling, consider the following set of processes, with the length of the
CPU burst given in milliseconds:

Process Burst Time

P1 6
P2 8
P3 7
P4 3

Using SJF scheduling, we would schedule these processes according to the following Gantt chart:

P4 P1 P3 P2
0 3 9 16 24

Waiting Time:
P1 – 3
P2 – 16
P3 – 9
P4 – 0
Average waiting Time – (3+16+9+0)/4 – 7 milliseconds
With FCFS, AWT - 10.25 milliseconds

The SJF algorithm can be either preemptive or non-preemptive. The choice arises when a new
process arrives at the ready queue while a previous process is still executing. The next CPU burst of
the newly arrived process may be shorter than what is left of the currently executing process. A
preemptive SJF algorithm will pre-empt the currently executing process, whereas a non-
preemptive SJF algorithm will allow the currently running process to finish its CPU burst.
Preemptive SJF scheduling is sometimes called shortest-remaining-time-first scheduling.

As an example, consider the following four processes, with the length of the CPU burst given in
milliseconds:

Process Arrival Time Burst Time

P1 0 8
P2 1 4
P3 2 9
 P4 3 5

If the processes arrive at the ready queue at the times shown and need the indicated burst times,
then the resulting preemptive SJF schedule is as depicted in the following Gantt chart:

P1 P2 P4 P1 P3
0 1 5 10 17
26
Waiting Time:
P1 – (10 – 1) = 9
P2 – (1 – 1) – 0
P3 – (17 – 2) - 15
P4 – (5 – 3) - 2
Average waiting Time – (9+0+15+2)/4 – 6.5 milliseconds
Non-preemptive SJF AWT - 7.75 milliseconds

Advantages -
 It is optimal, in that it gives the minimum average waiting time for a given set of processes.
Disadvantages -
 It is difficult to know the length of the next CPU request. Hence, it is mostly used in long-term
scheduling where user estimates the process time limit accurately.
 Cost of preemption is added.

6.3.3 Priority Scheduling

The SJF algorithm is a special case of the general priority-scheduling algorithm. A priority is
associated with each process, and the CPU is allocated to the process with the highest priority.
Equal-priority processes are scheduled in FCFS order.

In this text, we assume that low numbers represent high priority. As an example, consider the
following set of processes, assumed to have arrived at time 0:

Process Burst Time Priority

P1 10 3
P2 1 1
P3 2 4
P4 1 5
P5 5 2

Using priority scheduling, we would schedule these processes according to the following Gantt
chart:

P2 P5 P1 P3 P4
0 1 6
16 18 19

Waiting Time:
P1 – 6
P2 – 0
P3 – 16
P4 – 18
P5 – 1
Average waiting Time – (6+0+16+18+1)/5 – 8.2 milliseconds

Priorities can be defined either internally or externally:

 Internally defined priorities use some measurable quantities like number of open files, and
the ratio of average I/O burst to average CPU burst, to compute the priority of a process.
 External priorities are set by criteria outside the operating system, such as the importance of
 the process, the type and amount of funds being paid for computer use, the department
sponsoring the work, and other, often political, factors.

Preemptive priority scheduling If the priority of a new process is higher than that of currently
running process, CPU is preempted and the new process is given to it.

Non-preemptive priority scheduling algorithm puts the new process according to its priority in the
ready queue.

Disadvantages -
 Indefinite blocking or starvation - A process that is ready to run but waiting for the CPU can
be considered blocked. A priority scheduling algorithm can leave some low-priority
processes waiting indefinitely. In a heavily loaded computer system, a steady stream of
higher-priority processes can prevent a low-priority process from ever getting the CPU.

A solution to the problem of indefinite blockage of low-priority processes is aging. Aging involves
gradually increasing the priority of processes that wait in the system for a long time. For example,
increasing the priority by 1 every 15 minutes. Eventually, the process will have the highest priority
in the system and would be executed.

6.3.4 Round-Robin Scheduling

It is preemptive (for switching between processes) FCFS (FIFO) designed for time-sharing systems.
The CPU scheduler goes around the ready queue, allocating the CPU to each process for a time
interval of up to 1 time quantum (10 to 100 milliseconds). The ready queue is treated as a circular
queue as the process which finishes its time quantum with CPU goes to the tail of ready queue.

Two cases:
 CPU burst is less than 1 time quantum - process will voluntarily release CPU.
 CPU burst is longer than 1 time quantum - the timer will go off and will cause an interrupt to
the OS. A context switch will be executed, and the process will be put at the tail of the ready
queue.

The average waiting time under the RR policy is often long. Consider the following set of processes
that arrive at time 0, with the length of the CPU burst given in milliseconds:

Process Burst Time

P1 24
P2 3
P3 3

Time Quantum – 4 milliseconds

P1 P2 P3 P1 P1 P1 P1 P1
0 4 7 10 14 18 22 26
30

In the end only P1 is run without any context switch because it is the only runnable process.
Waiting Time:

P1 – (10 – 4) = 6
P2 – 4
P3 – 7

Average waiting Time – (6+4+7)/3 – 5.66 milliseconds

Process Time = 10 Quantum Context Switches

0 10 12 0

0 6 10 6 1

0 1 2 3 4 5 6 7 8 9 10 1
9

Figure 6.4 - Smaller time quantum increases context switches.

The performance of RR algorithm depends heavily on the size of time quantum:

 Extremely large time quantum (12 milliseconds) - The RR policy is the same as the FCFS
policy.
 Extremely small (1 millisecond) - The RR approach can result in a large number of context
switches resulting in overhead, slowing the execution of the process accordingly (Figure 6.4).
Hence, time quantum (10 to 100 milliseconds) should be large with respect to the context-
switch time (10 microseconds).

6.3.5 Multilevel Queue Scheduling

A class of scheduling algorithms for processes which are easily classified into different groups. For
example, foreground (interactive) processes and background (batch) processes. These two types of
processes have different response-time requirements and so may have different scheduling needs.
In addition, foreground processes may have priority (externally defined) over background processes.

Features:
 Ready queue partitioned into several separate queues (Figure 6.6).
 The processes are permanently assigned to one queue, based on process property like
memory size, process priority, or process type.
 Each queue has its own scheduling algorithm. For example, RR for foreground queue & FCFS
for background processes.
 Scheduling among the queues - Fixed-priority pre-emptive scheduling. For eg, foreground
queue may have absolute priority over background queue.
An example of a multilevel queue scheduling algorithm with five queues, listed below in order of
priority:
1. System processes
2. Interactive processes
3. Interactive editing processes
4. Batch processes
5. Student processes

Features:
 Each queue has absolute priority over lower-priority queues.
 No process in lower queue could run unless higher queues were empty.
 If a higher priority process entered the ready queue and lower priority process was running,
the lower priority process would be pre-empted.

Another possibility is to time-slice among the queues. Here, each queue gets a certain portion of the
CPU time, which it can then schedule among its various processes. For instance, in the
foreground–background queue example, the foreground queue can be given 80 percent of the CPU
time for RR scheduling among its processes, while the background queue receives 20 percent of the
CPU to give to its processes on an FCFS basis.

Processes are permanently assigned to a queue when they enter the system:
Advantage:
 Low scheduling overhead
Disadvantage:
 Inflexible

6.3.6 Multilevel Feedback Queue Scheduling

Features:
 Processes are separated according to the characteristics of their CPU bursts, so they can move
between queues.
 A process which uses too much CPU time, is moved to a lower-priority queue. It leaves I/O -
bound and interactive processes in the higher-priority queues.

Features:
 No process in lower queue could run unless higher queues were empty.
 If a higher priority process entered the ready queue and lower priority process was running,
the lower priority process would be preempted.

A process entering the ready queue is put in queue 0. A process in queue 0 is given a time quantum
of 8 milliseconds (shorter processes given higher priority). If it does not finish within this time, it is
moved to the tail of queue 1. If queue 0 is empty, the process at the head of queue 1 is given a
quantum of 16 milliseconds. If it does not complete, it is preempted and is put into queue 2.
Processes in queue 2 are run on an FCFS (non-preemptive) basis but are run only when queues 0
and 1 are empty.

In general, a multilevel feedback queue scheduler is defined by the following parameters:

• The number of queues
• The scheduling algorithm for each queue
• The method used to determine when to upgrade a process to a higher-priority queue
• The method used to determine when to demote a process to a lower-priority queue
• The method used to determine which queue a process will enter when that process needs service

Advantages:
 A process waiting too long in a lower-priority queue may be moved to a higher-priority
queue. This is a form of aging and prevents starvation.
 The definition of a multilevel feedback queue scheduler makes it the most general CPU-
scheduling algorithm. It can be configured to match a specific system under design.
Disadvantage:
 Unfortunately, it is also the most complex algorithm, since defining the best scheduler
requires some means by which to select values for all the parameters.