CPU Scheduling

Basic Concepts

In a single-processor system, only one process can run at a time; any 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. The idea is relatively simple. A process is executed until'
it must wait, typically for the completion of some I/O request. In a simple computer system, the CPU
then just sits idle. All this waiting time is wasted; no useful work is accomplished. With
multiprogramming, we try to use this time productively. 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 pattern continues. Every time one process has to wait,
another process can take over use of the CPU. Scheduling of this kind is a fundamental operating-
system function. Almost all computer resources are scheduled before use. The CPU is, of course,
one of the primary computer resources. Thus, its scheduling is central to operating-system design.

CPU-I/O Burst Cycle

Process execution consists of a cycle of CPU execution and I/O wait. Processes alternate between
these two states. Process execution begins with a CPU burst. That is followed by an I/O burst, which
is followed by another CPU burst, then another I/O burst, and so on. Eventually, the final CPU burst
ends with a system request to terminate execution (Figure 2.1).

The durations of CPU bursts have been measured extensively. Although they vary
greatly from process to process and from computer to computer, they tend to have a frequency curve
similar to that shown in Figure 2.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.
 Figure 2.1 Alternating sequence of CPU and I/O bursts.

Figure 2.2 Histogram of CPU-burst durations.

Scheduling Criteria
There are many different criteria’s to check when considering the "best" scheduling
algorithm

CPU utilization

To make out the best use of CPU and not to waste any CPU cycle, CPU would be
working most of the time (Ideally 100% of the time). Considering a real system, CPU
usage should range from 40% (lightly loaded) to 90% (heavily loaded.)

Throughput

It is the total number of processes completed per unit time or rather say total
amount of work done in a unit of time. This may range from 10/second to 1/hour
depending on the specific processes.

Turnaround time

It is the amount of time taken to execute a particular process, i.e. The interval
from time of submission of the process to the time of completion of the process(Wall
clock time).

Waiting time

The sum of the periods spent waiting in the ready queue amount of time a process
has been waiting in the ready queue to acquire get control on the CPU.

Load average

It is the average number of processes residing in the ready queue waiting for their
turn to get into the CPU.

Response time

Amount of time it takes from when a request was submitted until the first
response is produced. Remember, it is the time till the first response and not the
completion of process execution (final response).

In general CPU utilization and Throughput are maximized and other factors are reduced
for proper optimization.
 Basics of Scheduling Algorithms

Pre-emptive and Non Pre-emptive Scheduling:

Pre-emptive Scheduling:
Pre-emptive scheduling is used when a process switches from running state to ready state
or from waiting state to ready state. The resources (mainly CPU cycles) are allocated to
the process for the limited amount of time and then is taken away, and the process is
again placed back in the ready queue if that process still has CPU burst time remaining.
That process stays in ready queue till it gets next chance to execute.
Non Pre-emptive Scheduling:
Non pre-emptive Scheduling is used when a process terminates, or a process switches
from running to waiting state. In this scheduling, once the resources (CPU cycles) is
allocated to a process, the process holds the CPU till it gets terminated or it reaches a
waiting state. In case of non pre-emptive scheduling does not interrupt a process running
CPU in middle of the execution. Instead, it waits till the process complete its CPU burst
time and then it can allocate the CPU to another process.
Key differences between Preemptive and Non-Preemptive Scheduling:
1. In preemptive scheduling the CPU is allocated to the processes for the limited time
whereas in Non-preemptive scheduling, the CPU is allocated to the process till it
terminates or switches to waiting state.
2. The executing process in preemptive scheduling is interrupted in the middle of
execution when higher priority one comes whereas, the executing process in non-
preemptive scheduling is not interrupted in the middle of execution and wait till its
execution.
3. In Preemptive Scheduling, there is the overhead of switching the process from ready
state to running state, vise-verse, and maintaining the ready queue. Whereas in case
of non-preemptive scheduling has no overhead of switching the process from
running state to ready state.
4. In preemptive scheduling, if a high priority process frequently arrives in the ready
queue then the process with low priority has to wait for a long, and it may have to
starve. On the other hands, in the non-preemptive scheduling, if CPU is allocated to
the process having larger burst time then the processes with small burst time may
have to starve.
 5. Preemptive scheduling attain flexible by allowing the critical processes to access
CPU as they arrive into the ready queue, no matter what process is executing
currently. Non-preemptive scheduling is called rigid as even if a critical process
enters the ready queue the process running CPU is not disturbed.
6. The Preemptive Scheduling has to maintain the integrity of shared data that’s why it
is cost associative as it which is not the case with Non-preemptive Scheduling.

Scheduling Algorithms
1. First Come First Serve (FCFS) Scheduling:
The simplest CPU-scheduling algorithm is the first-come, first-served (FCFS)
scheduling algorithm. With this scheme, the process that requests the CPU first is
allocated the CPU first. The implementation of the FCFS policy is easily managed with a
FIFO queue. 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 p1,p2,p3,p4 that arrive at time 0, with the length
of the CPU burst given in milliseconds:

Fig2.12.1: Example of FCFS scheduling algorithm

The waiting time is 0 milliseconds for process P1, 21 milliseconds for process P2, and 24
milliseconds for process P3 and 30 milliseconds for process p4. Thus, the average waiting
time is 18.75 milliseconds as shown in the Gantt Chart.
Note: FCFS scheduling algorithm is non preemptive. Once the CPU has been allocated to
a process, that process keeps the CPU until it releases the CPU, either by terminating or
by requesting I/O. The FCFS algorithm is thus particularly troublesome for time-sharing
systems, where it is important that each user get a share of the CPU at regular intervals.
2. Shortest-Job-First(SJF) Scheduling:

A different approach to CPU scheduling is the shortest-job-first (SJF) scheduling

algorithm. This algorithm associates with each process the length of the process’s next
CPU burst. When the CPU is available, it 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 to break the tie. Note that a more appropriate term for this scheduling method would
be the shortest-next-CPU-burst algorithm, because scheduling depends on the length of
the next CPU burst of a process, rather than its total length. Consider 4 process
p1,p2,p3,p4 with their corresponding burst time as given below

Fig2.5: Example of SJF scheduling algorithm

As shown in above Gantt Chart waiting time of p1 will be 11ms, p2 waiting time will be
2ms and p3 waiting time will be 5ms and p4 waiting time will be 0ms. The average
waiting time is 4.5ms.

NOTE: The SJF algorithm can be either preemptive or non pre-emptive. 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 preempt the
 currently executing process, whereas a non pre-emptive SJF algorithm will allow the
currently running process to finish its CPU burst.
Preemptive SJF scheduling is sometimes called shortest-remaining-time-first
scheduling.
3. Round Robin (RR) Scheduling:
The round-robin (RR) scheduling algorithm is designed especially for timesharing
systems. It is similar to FCFS scheduling, but preemption is added to enable the system to
switch between processes. A small unit of time, called a time quantum or time slice, is
defined. A time quantum is generally from10 to 100 milliseconds in length. The ready
queue is treated as a circular queue. The CPU scheduler goes around the ready queue,
allocating the CPU to each process for a time interval of up to 1 time quantum.
To implement RR scheduling, we again treat the ready queue as a FIFO queue of
processes. New processes are added to the tail of the ready queue. The CPU scheduler
picks the first process from the ready queue, sets a timer to interrupt after 1 time quantum,
and dispatches the process.
 A fixed time is allotted to each process, called quantum, for execution.
 Once a process is executed for given time period that process is preempted and
other process executes for given time period.
Consider 4 processes p1,p2,p3,p4 as shown below with their corresponding burst time as
shown

Fig2.12.3: Example of RR scheduling algorithm

 Multi-Processor Scheduling

In multiple-processor scheduling multiple CPU’s are available and hence Load Sharing
becomes possible. However multiple processor scheduling is more complex as compared
to single processor scheduling. In multiple processor scheduling there are cases when the
processors are identical i.e. HOMOGENEOUS, in terms of their functionality, we can use
any processor available to run any process in the queue.
1. Approaches to Multiple-Processor Scheduling:
One approach is when all the scheduling decisions and I/O processing are handled by a
single processor which is called the Master Server and the other processors executes
only the user code. This is simple and reduces the need of data sharing. This entire
scenario is called Asymmetric Multiprocessing.
A second approach uses Symmetric Multiprocessing where each processor is self
scheduling. All processes may be in a common ready queue or each processor may have
its own private queue for ready processes. The scheduling proceeds further by having the
scheduler for each processor examine the ready queue and select a process to execute.

DEADLOCKS

In a multiprogramming environment, several processes may compete for a finite

number of resources. A process requests resources; if the resources are not available at
that time, the process enters a waiting state. Sometimes, awaiting process is never again
able to change state, because the resources it has requested are held by other waiting

processes. This situation is called a deadlock.

Fig3.14: Resource-allocation graph with a deadlock

 Necessary and Sufficient Conditions for Deadlock

A deadlock situation can arise if the following four conditions hold simultaneously in a
system:
1. Mutual exclusion. At least one resource must be held in a non sharable mode; that is,
only one process at a time can use the resource. If another process requests that resource,
the requesting process must be delayed until the resource has been released.
2. Hold and wait. A process must be holding at least one resource and waiting to acquire
additional resources that are currently being held by other processes.
3. No pre-emption. Resources cannot be pre-empted; that is, a resource can be released
only voluntarily by the process holding it, after that process has completed its task.
[Link] wait. A set {P0, P1, ..., Pn} of waiting processes must exist such that P0 is
waiting for a resource held by P1, P1 is waiting for a resource held by P2, ..., Pn−1 is
waiting for a resource held by Pn, and Pn is waiting for a resource held by P0.

Fig3.15 Deadlock

Deadlock Prevention
For a deadlock to occur, each of the four necessary conditions must hold. By ensuring
that at least one of these conditions cannot hold, we can prevent the occurrence of a
deadlock.
1. Mutual Exclusion:

The mutual exclusion condition must hold. That is, at least one resource must be non
sharable. Sharable resources, in contrast, do not require mutually exclusive access and
thus cannot be involved in a deadlock. Read-only files are a good example of a sharable
resource. If several processes attempt to open a read-only file at the same time, they can
be granted simultaneous access to the file. A process never needs to wait for a sharable
resource. In general, however, we cannot prevent deadlocks by denying the mutual-
exclusion condition, because some resources are intrinsically non sharable. For example,
a mutex lock cannot be simultaneously shared by several processes.
2. Hold and Wait:

To ensure that the hold-and-wait condition never occurs in the system, we must
guarantee that, whenever a process requests a resource, it does not hold any other
resources.
One protocol that we can use requires each process to request and be allocated all its
resources before it begins execution.
An alternative protocol allows a process to request resources only when it has none. A
process may request some resources and use them. Before it can request any additional
resources, it must release all the resources that it is currently allocated.
To illustrate the difference between these two protocols, we consider a process that
copies data from a DVD drive to a file on disk, sorts the file, and then prints the results to
a printer.
If all resources must be requested at the beginning of the process, then the process
must initially request the DVD drive, disk file, and printer. It will hold the printer for its
entire execution, even though it needs the printer only at the end.
The second method allows the process to request initially only the DVD drive and disk
file. It copies from the DVD drive to the disk and then releases both the DVD drive and
the disk file. The process must then request the disk file and the printer. After copying the
disk file to the printer, it releases these two resources and terminates.
Both these protocols have main disadvantage.
First, resource utilization may be low, since resources may be allocated but unused for a
long period. In the example given, for instance, we can release the DVD drive and disk
file, and then request the disk file and printer, only if we can be sure that our data will
remain on the disk file.
3. No Pre-emption:
The third necessary condition for deadlocks is that there be no pre-emption of resources
that have already been allocated. To ensure that this condition does not hold, we can use
the following protocol. If a process is holding some resources and requests another
resource that cannot be immediately allocated to it (that is, the process must wait), then
all resources the process is currently holding are pre-empted. In other words, these
resources are implicitly released. The pre-empted resources are added to the list of
resources for which the process is waiting. The process will be restarted only when it can
regain it sold resources, as well as the new ones that it is requesting.
Alternatively, if a process requests some resources, we first check whether they are
available. If they are, we allocate them. If they are not, we check whether they are
allocated to some other process that is waiting for additional resources. If so, we preempt
the desired resources from the waiting process and allocate them to the requesting
process. If the resources are neither available nor held by a waiting process, the
requesting process must wait.
4. Circular Wait:

The fourth and final condition for deadlocks is the circular-wait condition. To
illustrate, we let R = {R1, R2, ..., Rm} be the set of resource types. We assign to each
resource type a unique integer number,
For example, if the set of resource types R includes tape drives, disk drives, and printers,
then the function F might be defined as follows:
F(tape drive) = 1
F(disk drive) = 5
F(printer) = 12
We can now consider the following protocol to prevent deadlocks: Each process can
request resources only in an increasing order of enumeration. That is, a process can
initially request any number of instances of a resource type —say, Ri. After that, the
process can request instances of resource type Rj if and only if F(Rj ) > F(Ri ).
For example, using the function defined previously, a process that wants to use the tape
drive and printer at the same time must first request the tape drive and then request the
printer.
We can demonstrate this fact by assuming that a circular wait exists (proof by
contradiction). Let the set of processes involved in the circular wait be {P0, P1, ..., Pn},
where Pi is waiting for a resource Ri, which is held by process Pi+1. Then, since process
Pi+1 is holding resource Ri while requesting resource Ri+1, we must have F(Ri ) <
F(Ri+1) for all i. But this condition means that F(R0) < F(R1) < ... < F(Rn) < F(R0). By
transitivity, F(R0) < F(R0), which is impossible. Therefore, there can be no circular wait.
 Deadlock Avoidance

An alternative method for avoiding deadlocks is to require additional information

about how resources are to be requested.
For example, in a system with one tape drive and one printer, the system might need to
know that process P will request first the tape drive and then the printer before releasing
both resources, whereas process Q will request first the printer and then the tape drive.
With this knowledge of the complete sequence of requests and releases for each process,
the system can decide for each request whether or not the process should wait in order to
avoid a possible future deadlock.
 The simplest and most useful model requires that each process declare the maximum
number of resources of each type that it may need. Given this a priori information, it is
possible to construct an algorithm that ensures that the system will never enter a
deadlocked state.
1. Safe State:

A state is safe if the system can allocate resources to each process (up to its maximum) in
some order and still avoid a deadlock. More formally, a system is in a safe state only if
there exists a safe sequence. A sequence of processes<P1, P2, ..., Pn> is a safe sequence
for the current allocation state
A safe state is not a deadlocked state. Conversely, a deadlocked state is an unsafe state.
Not all unsafe states are deadlocks, however an unsafe state may lead to a deadlock. As
long as the state is safe, the operating system can avoid unsafe (and deadlocked) states. In
an unsafe state, the operating system cannot prevent processes from requesting resources
in such a way that a deadlock occurs. The behaviour of the processes controls unsafe
states.

Fig3.17: Safe, unsafe, and deadlocked state spaces

2. Banker’s Algorithm:

The resource-allocation-graph algorithm is not applicable to a resource allocation system

with multiple instances of each resource type. The deadlock avoidance algorithm that we
describe next is applicable to such a system but is less efficient than the resource-
allocation graph scheme. This algorithm is commonly known as the banker’s algorithm.
When a new process enters the system, it must declare the maximum number of
instances of each resource type that it may need. This number may not exceed the total
number of resources in the system. When a user requests a set of resources, the system
must determine whether the allocation of these resources will leave the system in a safe
state. If it will, the resources are allocated; otherwise, the process must wait until some
other process releases enough resources.
Several data structures must be maintained to implement the banker’s algorithm. These
data structures encode the state of the resource-allocation system. We need the following
data structures, where n is the number of processes in the system and m is the number of
resource types:
• Available :A vector of length m indicates the number of available resources of each
type.
• Max. An n × m matrix defines the maximum demand of each process.
If Max[i][j] equals k, then process Pi may request at most k instances of resource type Rj.
• Allocation. An n × m matrix defines the number of resources of each type currently
allocated to each process
• Need. An n × m matrix indicates the remaining resource need of each process. Note that
Need[i][j] equals Max[i][j]− Allocation[i][j].
Safety Algorithm
1. Let Work and Finish be vectors of length m and n, respectively. Initialize: Work
= Available Finish [i] = false for i = 0, 1, …,n- 1
2. Find an i such that both:
(a) Finish [i] = = false
(b) Need i <= Work
If no such i exists, go to step 4

3. Work = Work + Allocation i

Finish[i] = true
go to step 2
 4. If Finish [i] == true for all i, then the system is in a safe state

Resource-Request Algorithm for Process Pi

Let Requesti be the request vector for process Pi. If Requesti [j] = = k then process Pi

wants k instances of resource type Rj

1. If Requesti <= Needi go to step 2. Otherwise, raise error condition, since process has
exceeded its maximum claim

2. If Requesti <= Available, go to step 3. Otherwise Pi must wait, since resources are
not available

3. Pretend to allocate requested resources to Pi by modifying the state as follows:

Available = Available –Requesti;

Allocationi =Allocationi + Requesti;

Needi =Needi – Requesti;

 If safe the resources are allocated to Pi
 If unsafe Pi must wait, and the old resource-allocation state is restored
If the resulting resource-allocation state is safe, the transaction is completed, and process
Pi is allocated its resources.

Deadlock Detection

If a system does not employ either a deadlock-prevention or a deadlock avoidance

algorithm, then a deadlock situation may occur. In this environment, the system may
provide:
• An algorithm that examines the state of the system to determine whether a deadlock has
occurred
• An algorithm to recover from the deadlock

1. Single Instance of Each Resource Type:

If all resources have only a single instance, then we can define a deadlock
detection algorithm that uses a variant of the resource-allocation graph, called a wait-for
graph. We obtain this graph from the resource-allocation graph by removing the resource
nodes and collapsing the appropriate edges.
More precisely, an edge from Pi to Pj in a wait-for graph implies that process Pi is
waiting for process Pj to release a resource that Pi needs.

Fig3.18: (a) Resource-allocation graph. (b) Corresponding wait-for graph

2. Several Instances of a Resource Type:

The wait-for graph scheme is not applicable to a resource-allocation system with
multiple instances of each resource type. We turn now to a deadlock detection algorithm
that is applicable to such a system.
• Available: A vector of length m indicates the number of available resources of each
type.
• Allocation. An n × m matrix defines the number of resources of each type currently
allocated to each process.
• Request. An n × m matrix indicates the current request of each process .If Request[i][j]
equals k, then process Pi is requesting k more instances of resource type Rj.
3. Detection-Algorithm Usage:

When should we invoke the detection algorithm? The answer depends on two factors:
1. How often is a deadlock likely to occur?
2. How many processes will be affected by deadlock when it happens? If deadlocks occur
frequently, then the detection algorithm should be invoked frequently. Resources
allocated to deadlocked processes will be idle until the deadlock can be broken. In
addition, the number of processes involved in the deadlock cycle may grow.
Deadlocks occur only when some process makes a request that cannot be granted
immediately.
If there are many different resource types, one request may create many cycles in the
resource graph, each cycle completed by the most recent request and “caused” by the one
identifiable process.

Recovery from Deadlock

When a detection algorithm determines that a deadlock exists, several alternatives

are available. One possibility is to inform the operator that a deadlock has occurred and to
let the operator deal with the deadlock manually. Another possibility is to let the system
recover from the deadlock automatically. There are two options for breaking a deadlock.
One is simply to abort one or more processes to break the circular wait. The other is to
pre-empt some resources from one or more of the deadlocked processes.
1. Process Termination:

To eliminate deadlocks by aborting a process, we use one of two methods. In both

methods, the system reclaims all resources allocated to the terminated processes.

• Abort all deadlocked processes. This method clearly will break the deadlock cycle, but
at great expense. The deadlocked processes may have computed for a long time, and the
results of these partial computations must be discarded and probably will have to be
recomputed later.
• Abort one process at a time until the deadlock cycle is eliminated. This method
incurs considerable overhead, since after each process is aborted, a deadlock-detection
algorithm must be invoked to determine whether any processes are still deadlocked.
2. Resource Pre-emption:

To eliminate deadlocks using resource pre-emption, we successively preempt some

resources from processes and give these resources to other processes until the deadlock
cycle is broken.
If pre-emption is required to deal with deadlocks, then three issues need to be addressed:
1. Selecting a victim: Which resources and which processes are to be pre-empted? As in
process termination, we must determine the order of pre-emption to minimize cost. Cost
factors may include such parameters as the number of resources a deadlocked process is
holding and the amount of time the process has thus far consumed.
OPERATING SYSTEMS MREC

2. Rollback. If we preempt a resource from a process, what should be done with

that process? Clearly, it cannot continue with its normal execution; it is missing
some needed resource. We must roll back the process to some safe state and restart
it from that state.
3. Starvation. How do we ensure that starvation will not occur? That is, how can
we guarantee that resources will not always be pre-empted from the same process?