RV Institute of Technology and Management®

RV Educational Institutions®
RV Institute of Technology and Management
(Affiliated to VTU, Belagavi)

JP Nagar 8th Phase, Bengaluru - 560076

Department of
Information Science and Engineering

Course Name: OPERATING SYSTEMS

Course Code: BCS303
III Semester
2022 Scheme

Prepared By :

Dr. Latha C A, Prof & HoD, Dept of ISE, RVITM

Dr. Shruthi P, Assistant Professor, Dept of ISE, RVITM

OPERATING SYSTEM (BCS303) 1

 RV Institute of Technology and Management®

MODULE III
3.1 Process Synchronization
3.1.1 Background

Since processes frequently needs to communicate with other processes therefore, there is a need
for a well- structured communication, without using interrupts, among processes.
A situation where several processes access and manipulate the same data concurrently and the
outcome of the execution depends on the particular order in which the access takes place, is called
a race condition.
To guard against the race condition, ensure only one process at a time can be manipulating the
variable or data. To make such a guarantee process need to be synchronized in some way.

3.1.2 The Critical-Section Problem

Consider a system consisting of n processes {P0, P1, ..., Pn−1}. Each process has a segment of
code, called a critical section, in which the process may be changing common variables, updating
a table, writing a file, and so on. when one process is executing in its critical section, no other
process is allowed to execute in its critical section.
The critical-section problem is to design a protocol that the processes can use to cooperate. Each
process must request permission to enter its critical section. The section of code implementing this
request is the entry section.
The critical section may be followed by an exit section. The remaining code is the remainder
section. The general structure of a typical process Pi is shown in Fig. 3.1
A solution to the critical-section problem must satisfy the following three requirements:
Mutual exclusion. If process Pi is executing in its critical section, then no other processes can
be executing in their critical sections.
Progress. If no process is executing in its critical section and some processes wish to enter their
critical sections, then only those processes that are not executing in their remainder sections can
participate in deciding which will enter its critical section next, and this selection cannot be
postponed indefinitely.

[Link] Bounded waiting. There exists a bound, or limit, on the number of times that other processes
are allowed to enter their critical sections after a process has made a request to enter its

OPERATING SYSTEM (BCS303) 2

 RV Institute of Technology and Management®

critical section and before that request is granted.

Fig. 3.1General structure of a typical process P,.

Two general approaches are used to handle critical sections in operating systems:

Preemptive kernels: A preemptive kernel allows a process to be preempted while it is running

in kernel mode.

Non-preemptive kernels: A non-preemptive kernel does not allow a process running in kernel
mode to be preempted; a kernel-mode process will run until it exits kernel mode, blocks, or
voluntarily yields control of the CPU.

3.1.3 Peterson’s Solution

A classic software-based solution to the critical-section problem known as Peterson’s solution.

It addresses the requirements of mutual exclusion, progress, and bounded waiting. It Is two
process solution. Assume that the LOAD and STORE instructions are atomic; that is, cannot be
interrupted.

The two processes share two variables:

int turn; Boolean flag [2];

The variable turn indicates whose turn it is to enter the critical section. The flag array is used to
indicate if a process is ready to enter the critical section. flag[i] = true implies that process Pi is
ready.

OPERATING SYSTEM (BCS303) 3

 RV Institute of Technology and Management®

The structure of process Pi in Peterson’s solution: It proves that Mutual exclusion is preserved
• Progress requirement is satisfied
• Bounded-waiting requirement is met

3.1.4 Synchronization Hardware

Software-based solutions such as Peterson’s are not guaranteed to work on modern computer
architectures. Simple hardware instructions can be used effectively in solving the critical-
section problem. These solutions are based on the locking — that is, protecting critical regions
through the use of locks.

Solution to Critical Section problem using locks

Modern machines provide special atomic hardware instructions Atomic = non- interruptable
Either test memory word and set value (TestAndSet ()) Or swap contents of two memory words (Swap
()).

The definition of the test and set () instruction

Fig. 3.2 The definition of the TestAndSet () instruction.

Using test and set () instruction, mutual exclusion can be implemented by declaring a Boolean variable lock,
initialized to false. The structure of process Pi is shown in Fig. 3.2

Mutual-exclusion implementation with test and set ().

If the machine supports the TestAndSet () instruction, then we can implement mutual exclusion by declaring a Boolean
variable lock, initialized to false. The structure of process P, is shown in Fig. 3.3.

OPERATING SYSTEM (BCS303) 4

 RV Institute of Technology and Management®

Fig. 3.3 Mutual-exclusion implementation with TestAndSet ().

3.2 Semaphores

The hardware-based solutions to the critical-section problem are complicated as well as

generally inaccessible to application programmers. So operating-system designers build
software tools to solve the critical-section problem, and this synchronization tool called as
Semaphore. Semaphore S is an integer variable.
Two standard operations modify S: wait() and signal(). Originally called P() and V().Can only be
accessed via two indivisible (atomic) operations.
Must guarantee that no two processes can execute wait () and signal () on the same semaphore
at the same time.

Usage:
Semaphore classified into:
Counting semaphore: Value can range over an unrestricted domain.
Binary semaphore (Mutex locks): Value can range only between from 0 & 1. It provides mutual
exclusion.
Consider 2 concurrently running processes:

S1;
signal(synch);
In process P1, and the statements wait(synch); S2;

Because synch is initialized to 0, P2 will execute S2 only after P1 has invoked signal(synch), which

OPERATING SYSTEM (BCS303) 5

 RV Institute of Technology and Management®

is after statement S1 has been executed.

Implementation:

The disadvantage of the semaphore is busy waiting i.e While a process is in critical section, any
other process that tries to enter its critical section must loop continuously in the entry code.
Busy waiting wastes CPU cycles that some other process might be able to use productively.
This type of semaphore is also called a spin lock because the process spins while waiting for
the lock.

Solution for Busy Waiting problem:

Modify the definition of the wait() and signal()operations as follows: When a process executes
the wait() operation and finds that the semaphore value is not positive, it must wait. Rather than
engaging in busy waiting, the process can block itself. The block operation places a process into
a waiting queue associated with the semaphore, and the state of the process is switched to the
waiting state. Then control is transferred to the CPU scheduler, which selects another process
to execute.

A process that is blocked, waiting on a semaphore S, should be restarted when some other
process executes a signal() operation. The process is restarted by a wakeup() operation, which
changes the process from the waiting state to the ready state. The process is then placed in the
ready queue. To implement semaphores under this definition, define a semaphore as follows:

typedef struct {int value; struct

process *list;
} semaphore;

Each semaphore has an integer value and a list of processes list. When a process must wait on
a semaphore, it is added to the list of processes. A signal () operation removes one process from
the list of waiting processes and awakens that process. Now, the wait () semaphore operation
can be defined as:

wait (semaphore *S) { S->value--

;
if (S->value < 0) {
add this process to S->list; block ();

OPERATING SYSTEM (BCS303) 6

 RV Institute of Technology and Management®

}
}

and the signal () semaphore operation can be defined as

signal (semaphore *S) { S-

>value++;
if (S->value <= 0) {
remove a process P from S->list; wakeup(P);
}

The block () operation suspends the process that invokes it. The wakeup(P) operation resumes
the execution of a blocked process P.

3.2.1 Deadlocks and Starvation

The implementation of a semaphore is as shown in fig 3.4 with a waiting queue may result in a
situation where two or more processes are waiting indefinitely for an event that can be caused
by only one of the waiting processes, these processes are said to be deadlocked. Consider below
example: a system consisting of two processes, P0 and P1, each accessing two semaphores, S
and Q, set to the value 1:

Fig 3. 4 Implementation of Semaphore

Suppose that P0 executes wait(S) and then P1 executes wait(Q). When P0 executes wait(Q), it must
wait until P1 executes signal(Q). Similarly, when P1 executes wait(S), it must wait until P0 executes
signal(S). Since these signal () operations cannot be executed, P0 and P1 are deadlocked.

Another problem related to deadlocks is indefinite blocking, or starvation, a situation in which

processes wait indefinitely within the semaphore. Indefinite blocking may occur if we add and
remove processes from the list associated with a semaphore in LIFO (last-in, first-out) order.

OPERATING SYSTEM (BCS303) 7

 RV Institute of Technology and Management®

3.3 Classic Problems of Synchronization

3.3.1 The Bounded-Buffer Problem:

N buffers, each can hold one item Semaphore mutex
initialized to the value 1 Semaphore full initialized to the
value 0

Semaphore empty initialized to the value N Code for producer is given below
The structure of the consumer process and producer process is as shown in fig 3.5 and fig 3.6
respectively.

Fig. 3.5 The structure of the consumer process.

Fig. 3.6 The structure of the producer process.

OPERATING SYSTEM (BCS303) 8

 RV Institute of Technology and Management®

3.3.2 The Readers–Writers Problem

A data set is shared among a number of concurrent processes Readers– only
read the data set; they do not perform any updates Writers– can both read and
write
Problem – allow multiple readers to read at the same time. Only one single
writer can access the shared data at the same time
Several variations of how readers and writers are treated – all involve priorities.

First variation – no reader kept waiting unless writer has permission to use shared object
In the solution to the first readers-writers problem, the reader processes share the following data
structures:
semaphore mutex,
wrt; int readcount;

The semaphores mutex and wrt are initialized to 1; readcount is initialized to 0. The semaphore wrt is
common to both reader and writer processes. The mutex semaphore is used to ensure mutual exclusion
when the variable readcount is updated.
The readcount variable keeps track of how many processes are currently reading the object. The
semaphore wrt functions as a mutual-exclusion semaphore for the writers. It is also used by the first or
last.

Fig. 3.7 The structure of a writer process

The code for a writer process is shown in Fig. 3.7. The code for a reader process is shown in Fig. 3.8

Fig. 3.8 The structure of a reader process

OPERATING SYSTEM (BCS303) 9

 RV Institute of Technology and Management®

Second variation- Once writer is ready, it performs the operation.

3.3.3 Shared Data

he readers-writers problem and its solutions has been generalized to provide reader- writer locks
on some systems. Acquiring a reader-writer lock requires specifying the mode of the lock: either
read or write access. When a process only wishes to read shared data, it requests the reader-
writer lock in read mode; a process wishing to modify the shared data must request the lock in
write mode.

Multiple processes are permitted to concurrently acquire a reader-writer lock in read mode; only
one process may acquire the lock for writing as exclusive access is required for writers. Reader-
writer locks are most useful in the following situations:

• In applications where it is easy to identify which processes only read shared data and which
threads only write shared data.
• In applications that have more readers than writers.

This is because reader-writer locks generally require more overhead to establish than
semaphores or mutual exclusion locks, and the overhead for setting up a reader- writer lock is
compensated by the increased concurrency of allowing multiple readers.

3.3.4 Dining-Philosophers Problem

Consider five philosophers who spend their lives thinking and eating. The philosophers share a
circular table surrounded by five chairs, each belonging to one philosopher. In the center of the
table is a bowl of rice, and the table is laid with five single chopsticks (Fig. 3.9).
A philosopher gets hungry and tries to pick up the two chopsticks that are closest to her (the
chopsticks that are between her and her left and right neighbors). A philosopher may pick up
only one chopstick at a time. When a hungry philosopher has both her chopsticks at the same
time, she eats without releasing the chopsticks. When she is finished eating, she puts down both
chopsticks and starts thinking again.
It is a simple representation of the need to allocate several resources among several processes
in a deadlock-free and starvation-free manner.
Solution: One simple solution is to represent each chopstick with a semaphore. A philosopher
tries to grab a chopstick by executing a wait () operation on that semaphore. She releases her
chopsticks by executing the signal () operation on the appropriate semaphores. Thus, the shared

OPERATING SYSTEM (BCS303) 10

 RV Institute of Technology and Management®

data are semaphore chopstick [5] where all the elements of chopstick are initialized to 1.

Fig. 3.9 The situation of the dining philosophers

The structure of philosopher i is shown in Fig. 3.9

Fig. 3.10 The structure of philosopher i.

Although this solution guarantees that no two neighbors are eating simultaneously, it nevertheless
must be rejected because it could create a deadlock. Suppose that all five philosophers become
hungry simultaneously and each grabs her left chopstick. All the elements of chopstick will now be
equal to 0. When each philosopher tries to grab her right chopstick, she will be delayed forever.
Several possible remedies to the deadlock problem are replaced by:

1. Allow at most four philosophers to be sitting simultaneously at the table.

OPERATING SYSTEM (BCS303) 11

 RV Institute of Technology and Management®

2. Allow a philosopher to pick up her chopsticks only if both chopsticks are available.
3. Use an asymmetric solution—that is, an odd-numbered philosopher picks up first her left
chopstick and then her right chopstick, whereas an even numbered philosopher picks up her
right chopstick and then her left chopstick.

3.4 Monitors
Incorrect use of semaphore operations:

Suppose that a process interchanges the order in which the wait () and signal () operations
on the semaphore mutex are executed, resulting in the following execution:

signal(mutex);
...
critical section
...
wait(mutex);
Suppose that a process replaces signal(mutex) with wait(mutex). That is, it executes

wait(mutex);
...
critical section
...
wait(mutex);

In this case, a deadlock will occur.

Suppose that a process omits the wait(mutex), or the signal(mutex), or both. In this case,
either mutual exclusion is violated or a deadlock will occur.

Solution:

Monitor: An abstract data type—or ADT—encapsulates data with a set of functions to operate
on that data that are independent of any specific implementation of the ADT.

A monitor type is an ADT that includes a set of programmers defined operations that are
provided with mutual exclusion within the monitor. The monitor type also declares the variables
whose values define the state of an instance of that type, along with the bodies of functions that

OPERATING SYSTEM (BCS303) 12

 RV Institute of Technology and Management®

operate on those variables. The monitor construct ensures that only one process at a time is
active within the monitor.
The syntax of a monitor type is shown in Fig.3.11. To have a powerful Synchronization schemes a
condition construct is added to the Monitor. So, synchronization scheme can be defined with one or
more variables of type condition. condition x, y

Fig. 3.11 Schematic view of a monitor

The only operations that can be invoked on a condition variable are wait ( ) and signal ( ). The
operation [Link]( ); means that the process invoking this operation is suspended until another
process invokes [Link]( ); The [Link]( ) operation resumes exactly one suspended process. If no
process is suspended, then the signal ( ) operation has no effect; that is, the state of x is the same as
if the operation had never been executed. Contrast this operation with the signal ( ) operation
associated with semaphores, which always affects the state of the semaphore.

Fig. 3.12 Monitor with condition variables.

OPERATING SYSTEM (BCS303) 13

 RV Institute of Technology and Management®

3.4.1 Dining-Philosophers Solution Using Monitors

A deadlock-free solution to the dining-philosophers problem using monitor as shown fig 3.13
concepts. This solution imposes the restriction that a philosopher may pick up her chopsticks
only if both of them are available.
Consider following data structure:
enum {THINKING, HUNGRY, EATING} state[5];

Fig. 3.13 A monitor solution to the dining-philosopher problem

3.4.2 Implementing a Monitor Using Semaphores

For each monitor, a semaphore mutex (initialized to 1) is provided. A process must execute
wait(mutex) before entering the monitor and must execute signal(mutex) after leaving the
monitor.

OPERATING SYSTEM (BCS303) 14

 RV Institute of Technology and Management®

Since a signaling process must wait until the resumed process either leaves or waits, an
additional semaphore, next, is introduced, initialized to 0. The signaling processes can use next
to suspend themselves. An integer variable next count is also provided to count the number of
processes suspended on next. Thus, each external function F is replaced by

Mutual exclusion within a monitor is ensured.

For each condition x, we introduce a semaphore x sem and an integer variable x count, both
initialized to 0. The operation x. wait() can now be implemented as

x_count++;
if (next_count > 0) signal(next);
else signal(mutex);
wait(x_sem); x_count--; The

operation [Link]() can be implemented as

3.4.3 Resuming Processes within a Monitor

If several processes are suspended on condition x, and an [Link]() operation is executed by

some process, then to determine which of the suspended processes should be resumed next, one
simple solution is to use a first-come, first-served (FCFS) ordering, so that the process that has
been waiting the longest is resumed first. For this purpose, the conditional-wait construct can

OPERATING SYSTEM (BCS303) 15

 RV Institute of Technology and Management®

be used. This construct has the form

[Link](c);

where c is an integer expression that is evaluated when the wait() operation is executed. The
value of c, which is called a priority number, is then stored with the name of the process that is
suspended. When [Link]() is executed, the process with the smallest priority number is
resumed next.

Fig. 3.14 A monitor to allocate a single resource.

The Resource Allocator monitor shown in the above Fig3.14., which controls the
allocation of a single resource among competing processes. A process that needs to access the
resource in question must observe the following sequence:
[Link](t);
...
access the resource;
...
[Link]();
where R is an instance of type Resource Allocator.

The monitor concept cannot guarantee that the preceding access sequence will be
observed. In particular, the following problems can occur:

OPERATING SYSTEM (BCS303) 16

 RV Institute of Technology and Management®

1. A process might access a resource without first gaining access permission to the resource.
2. A process might never release a resource once it has been granted access to the resource.
3. A process might attempt to release a resource that it never requested.
4. A process might request the same resource twice (without first releasing the resource).

3.5 Dead Locks

In a multiprogramming environment, several processes may compete for a finite number
of resources. A process requests resources; and if the resources are not available at that
time, the process enters a waiting state. Sometimes, a waiting 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.

3.5.1 System Model

For the purposes of deadlock discussion, a system can be modeled as a collection of

limited resources, which can be partitioned into different categories, to be allocated to a
number of processes, each having different needs.

Resource categories may include memory, printers, CPUs, open files, tape drives, CD-
ROMS, etc.

By definition, all the resources within a category are equivalent, and a request of this
category can be equally satisfied by any one of the resources in that category. If this is
not the case ( i.e. if there is some difference between the resources within a category ),
then that category needs to be further divided into separate categories. For example,
"printers" may need to be separated into "laser printers" and "color inkjet printers".

Some categories may have a single resource.

In normal operation a process must request a resource before using it, and release it when
it is done, in the following sequence:

1. Request - If the request cannot be immediately granted, then the process must wait
until the resource(s) it needs become available. Example: system calls open( ),
malloc( ), new( ), and request( ).
2. Use - The process uses the resource. Example: prints to the printer or reads from the
file.

OPERATING SYSTEM (BCS303) 17

 RV Institute of Technology and Management®

3. Release - The process relinquishes the resource. so that it becomes available for other
processes. Example: close(), free( ), delete( ), and release( ).

For all kernel-managed resources, the kernel keeps track of what resources are free and which
are allocated, to which process they are allocated, and a queue of processes waiting for this
resource to become available. Application-managed resources can be controlled using
mutexes or wait( ) and signal( ) calls, ( i.e. binary or counting semaphores. )

A set of processes is deadlocked when every process in the set is waiting for a resource that
is currently allocated to another process in the set (and which can only be released when that
other waiting process makes progress).

3.6 Deadlock Characterization

3.6.1 Necessary Conditions:

There are four conditions that are necessary to achieve deadlock:

• Mutual Exclusion - At least one resource must be held in a non-sharable mode; If any
other process requests this resource, then that process must wait for the resource to be
released.
• Hold and Wait - A process must be simultaneously holding at least one resource and
waiting for at least one resource that is currently being held by some other process.
• No preemption - Once a process is holding a resource ( i.e. once its request has been
granted ), then that resource cannot be taken away from that process until the process
voluntarily releases it.
• Circular Wait - A set of processes { P0, P1, P2, . . ., PN } must exist such that every P[ i
] is waiting for P[ ( i + 1 ) % ( N + 1 ) ]. ( Note that this condition implies the hold- and-
wait condition, but it is easier to deal with the conditions if the four are considered
separately. )
3.6.2 Resource-Allocation Graph

In some cases deadlocks can be understood more clearly through the use of Resource-
Allocation Graphs, having the following properties:

*A set of resource categories, { R1, R2, R3, . . ., RN }, which appear as square nodes on the

OPERATING SYSTEM (BCS303) 18

 RV Institute of Technology and Management®

graph. Dots inside the resource nodes indicate specific instances of the resource. ( E.g. two
dots might represent two laser printers. )
*A set of processes, { P1, P2, P3, . . ., PN }
*Request Edges - A set of directed arcs from Pi to Rj, indicating that process Pi has requested
Rj, and is currently waiting for that resource to become available.
*Assignment Edges - A set of directed arcs from Rj to Pi indicating that resource Rj has been
allocated to process Pi, and that Pi is currently holding resource Rj.
Note that a request edge can be converted into an assignment edge by reversing the direction
of the arc when the request is granted. (However, note also that request edges point to the
category box, whereas assignment edges emanate from a particular instance dot within the
box.)

Fig. 3.15 Resource-allocation graph.

*If a resource-allocation graph contains no cycles, then the system is not deadlocked. (When
looking for cycles, remember that these are directed graphs.) See the example in Fig. 3.15 above.

*If a resource-allocation graph does contain cycles and each resource category contains only a
singleinstance, then a deadlock exists.
*If a resource category contains more than one instance, then the presence of a cycle in the
resource-allocation graph indicates the possibility of a deadlock, but does not guarantee one.
Consider, for example, Fig. 3.16 and 3.17 below:

OPERATING SYSTEM (BCS303) 19

 RV Institute of Technology and Management®

Fig. 3.16 Resource-allocation graph with a deadlock

Fig. 3.17 Resource-allocation graph with a cycle but no deadlock.

3.7 Methods for Handling Deadlocks

Generally speaking there are three ways of handling deadlocks:

Deadlock prevention or avoidance - Do not allow the system to get into a deadlocked state.
Deadlock detection and recovery - Abort a process or preempt some resources when deadlocks are
detected.

OPERATING SYSTEM (BCS303) 20

 RV Institute of Technology and Management®

Ignore the problem all together - If deadlocks only occur once a year or so, it may be better
to simply let them happen and reboot as necessary than to incur the constant overhead and
system performance penalties associated with deadlock prevention or detection. This is the
approach that both Windows and UNIX take.

In order to avoid deadlocks, the system must have additional information about all
processes. In particular, the system must know what resources a process will or may request in
the future. ( Ranging from a simple worst-case maximum to a complete resource request and
release plan for each process, depending on the particular algorithm. )

Deadlock detection is fairly straightforward, but deadlock recovery requires either

aborting processes or preempting resources, neither of which is an attractive alternative.

If deadlocks are neither prevented nor detected, then when a deadlock occurs the system
will gradually slow down, as more and more processes become stuck waiting for resources
currently held by
the deadlock and by other waiting processes. Unfortunately, this slowdown can be
indistinguishable from a general system slowdown when a real-time process has heavy computing
needs.

3.8 Deadlock Prevention

Deadlocks can be prevented by preventing at least one of the four required conditions:
• Mutual Exclusion: Shared resources such as read-only files do not lead to deadlocks. Unfortunately,
some resources, such as printers and tape drives, require exclusive access by a single process.

• Hold and Wait : To prevent this condition processes must be prevented from holding one or more
resources while simultaneously waiting for one or more others. There are several possibilities for this:

o Require that all processes request all resources at one time. This can be wasteful of system
resources if a process needs one resource early in its execution and doesn't need some other
resource until much later.
o Require that processes holding resources must release them before requesting new resources,
and then re-acquire the released resources along with the new ones in a single new request. This

OPERATING SYSTEM (BCS303) 21

 RV Institute of Technology and Management®

can be a problem if a process has partially completed an operation using a resource and then
fails to get it re-allocated after releasing it. Either of the methods described above can lead to
starvation if a process requires one or more popular resources.
• No Preemption: Preemption of process resource allocations can prevent this condition of deadlocks,
when it is possible.
o One approach is that if a process is forced to wait when requesting a new resource, then all
other resources previously held by this process are implicitly released, (preempted), forcing this
process to re- acquire the old resources along with the new resources in a single request, similar
to the previous discussion.
o Another approach is that when a resource is requested and not available, then the system looks
to see what other processes currently have those resources and are themselves blocked waiting
for some other resource. If such a process is found, then some of their resources may get
preempted and added to the list of resources for which the process is [Link] of these
approaches may be applicable for resources whose states are easily saved and restored, such as
registers and memory, but are generally not applicable to other devices such as printers and
tape drives.
• Circular Wait: One way to avoid circular wait is to number all resources, and to require that processes
request resources only in strictly increasing ( or decreasing ) order.
In other words, in order to request resource Rj, a process must first release all Ri such that i
>= j.
● One big challenge in this scheme is determining the relative ordering of the different resources

3.9 Deadlock Avoidance

● The general idea behind deadlock avoidance is to prevent deadlocks from ever happening, by
preventing at least one of the aforementioned conditions.
● This requires more information about each process, AND tends to lead to low device utilization.
( i. e. it is a conservative approach. )
● In some algorithms the scheduler only needs to know the maximum number of each resource
that a process might potentially use. In more complex algorithms the scheduler can also take
advantage of the schedule of exactly what resources may be needed in what order.
● When a scheduler sees that starting a process or granting resource requests may lead to future
deadlocks, then that process is just not started or the request is not granted.
● A resource allocation state is defined by the number of available and allocated resources, and

OPERATING SYSTEM (BCS303) 22

 RV Institute of Technology and Management®

the maximum requirements of all processes in the system.

3.9.1 Safe State

● A state is safe if the system can allocate all resources requested by all processes ( up to their
stated maximums ) without entering a deadlock state.
● More formally, a state is safe if there exists a safe sequence of processes { P0, P1, P2, ..., PN
} such that all of the resource requests for Pi can be granted using the resources currently
allocated to Pi and all processes Pj where j < i. ( I.e. if all the processes prior to Pi finish and then
free up their Pi will be able to finish also, using the resources that they have resources, freed up).

Fig. 3.5: Safe, unsafe, and deadlocked state spaces

● If a safe sequence does not exist, then the system is in an unsafe state, which MAY lead to
deadlock (Fig. 3.5). (All safe states are deadlock free, but not all unsafe states lead to
deadlocks).
For example, consider a system with 12 tape drives, allocated as follows. Is this a safe state?
What is the safe sequence?

Maximum Current
Needs Allocation
P0 10 5
P1 4 2
P2 9 2

i: What happens to the above table if process P2 requests and is granted one more tape drive?

OPERATING SYSTEM (BCS303) 23

 RV Institute of Technology and Management®

Key to the safe state approach is that when a request is made for resources, the request is granted
only if the resulting allocation state is a safe one.

At time for, the system is in a safe state. The sequence < P0, P1, P2> satisfies the safety condition.
Process P1 can immediately be allocated all its tape drives and then return them (the system will
then have 5 available tape drives); then process P0 can get all its tape drives and return them (the
system will then have 10 available tape drives); and finally process P2 can get all its tape drives
and return them (the system will then have all 12 tape drives available).

A system can go from a safe state to an unsafe state. Suppose that, at time t1, process P2 requests
and is allocated one more tape drive. The system is no longer in a safe state. At this point, only
process P1, can be allocated all its tape drives. When it returns them, the system will have only
4 available tape drives. Since process P0, is allocated 5 tape drives but has a maximum of 10, it
may request 5 more tape drives. Since they are unavailable, process P1 must wait. Similarly,
process P2 may request an additional 6 tape drives and have to wait, resulting in a deadlock. Our
mistake was in granting the request from process Pi for one more tape drive. If we had made P2
wait until either of the other.

3.9.2 Resource-Allocation Graph Algorithm

If resource categories have only single instances of their resources, then deadlock states can be
detected by cycles in the resource-allocation graphs.
In this case, unsafe states can be recognized and avoided by augmenting the resource-allocation
graph with claim edges, noted by dashed lines, which point from a process to a resource that it
may request in the future.
In order for this technique to work, all claim edges must be added to the graph for any particular
process before that process is allowed to request any resources. (Alternatively, processes may
only make requests for resources for which they have already established claim edges, and claim
edges cannot be added to any process that is currently holding resources ).
When a process makes a request, the claim edge Pi->Rj is converted to a request edge. Similarly,
when a resource is released, the assignment reverts back to a claim edge.

OPERATING SYSTEM (BCS303) 24

 RV Institute of Technology and Management®

This approach works by denying requests that would produce cycles in the resource-allocation
graph, taking claim edges into effect.

Consider for example (Fig. 3.6) what happens when process P2 requests resource R2:

Fig. 3.6 Resource allocation graph for dead lock avoidance

The resulting resource-allocation graph would have a cycle in it, and so the request cannot be granted
(Fig. 3.7).

Fig. 3.7 An Unsafe State in a Resource Allocation Graph

3.9.3 Banker's Algorithm

● For resource categories that contain more than one instance the resource-allocation graph
method does not work, and more complex (and less efficient) methods must be chosen.
● The Banker's Algorithm gets its name because it is a method that bankers could use to
assure that when they lend out resources they will still be able to satisfy all their clients. (

OPERATING SYSTEM (BCS303) 25

 RV Institute of Technology and Management®

A banker won't loan out a little money to start building a house unless they are assured that
they will later be able to loan out the rest of the money to finish the house. )
● When a process starts up, it must state in advance the maximum allocation of resources it
may request, up to the amount available on the system.
● When a request is made, the scheduler determines whether granting the request would leave
the system in a safe state. If not, then the process must wait until the request can be granted
safely.

[Link] Data Structures for the Banker’s Algorithm

Let n = number of processes, and m = number of resources types. N

Available: Vector of length m. If available [j] = k, there are k instances of resource type Rj
available n

Max: n x m matrix. If Max [i,j] = k, then process Pi may request at most k instances of
resourcetype Rjn

Allocation: n x m matrix. If Allocation[i,j] = k then Pi is currently allocated k instances of Rjn

Need: n x m matrix. If Need[i,j] = k, then Pi may need k more instances of Rj to complete its

taskNeed [i,j] = Max[i,j] – Allocation [i,j]

[Link] 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 and i such that both:

(a) Finish [i] = false

(b) Needi <= Work

If no such i exists, go to step 4

OPERATING SYSTEM (BCS303) 26

 RV Institute of Technology and Management®

3. Work=Work+Allocation

i Finish[i] = true go to step

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

[Link] Resource-Request Algorithm for Process Pi

Request = request vector for process Pi . If Requesti [j] = k then process Pi wants k instances of
resourcetype 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 – Request;

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

[Link] An Illustrative Example

Consider the following situation:

OPERATING SYSTEM (BCS303) 27

 RV Institute of Technology and Management®

The system is in a safe state since the sequence < P1, P3, P4, P2, P0> satisfies safety criteria.

Example: P1 Request (1,0,2) Check that Request £ Available (that is, (1,0,2) <= (3,3,2) Þ true

Executing safety algorithm shows that sequence < P1, P3, P4, P0, P2> satisfies safety requirement.
3.10 Deadlock Detection
If deadlocks are not avoided, then another approach is to detect when they have occurred and
recover somehow.
In addition to the performance hit of constantly checking for deadlocks, a policy / algorithm must
be in place for recovering from deadlocks, and there is potential for lost work when processes
must be aborted or have their resources preempted.
3.10.1 Single Instance of Each Resource Type
i. If each resource category has a single instance, then we can use a variation of the resource-
allocationgraph known as a wait-for graph.
ii. A wait-for graph can be constructed from a resource-allocation graph by eliminating the resources
andcollapsing the associated edges, as shown in the Fig. 3.8 below.

OPERATING SYSTEM (BCS303) 28

 RV Institute of Technology and Management®

iii. An arc from Pi to Pj in a wait-for graph indicates that process Pi is waiting for a resource that
processPj is currently holding.

Fig. 3.8 (a) Resource Allocation Graph Fig. 3.8(b) Corresponding Wait for Graph
As before, cycles in the wait-for graph indicate deadlocks. This algorithm must maintain the
wait-for graph, and periodically search it for cycles.

3.10.2 Several Instances of a Resource Type Available:

A vector of length m indicates the number of available resources of each type.
Allocation: An n x m matrix defines the number of resources of each type currently allocated
to each process.
Request: An n x m matrix indicates the current request of each process. If Request [ij] = k, then process
Pi is requesting k more instances of resource type. Rj .

3.10.3 Detection Algorithm

1. Let Work and Finish be vectors of length m and n, respectively Initialize:

(a) Work = Available(b) For i = 1,2,

…, n,if Allocationi != 0, then

(a) Finish[i]=false; otherwise, Finish[i] = true

2. Find an index i such that both:

OPERATING SYSTEM (BCS303) 29

 RV Institute of Technology and Management®

(b) Finish[i] == false

(c) Requesti <=Work

If no such i exists, go to step 4

3. 3. Work = Work +

Allocationi Finish[i] = true

go to step 2

4. If Finish[i] == false, for some i, 1 <= i <=n, then the system is in

deadlock [Link], if Finish[i] == false, then Pi is deadlocked

Algorithm requires an order of O(m x n2) operations to detect whether the system is in
deadlockedstate.

3.10.4 Example of Detection Algorithm

Five processes P0 through P4; three resource types A (7 instances), B (2 instances), and C (6 instances)
Snapshot at time T0:

OPERATING SYSTEM (BCS303) 30

 RV Institute of Technology and Management®

Now suppose that process P2 makes a request for an additional instance of type C, yielding
the state shown below. Is the system now deadlocked?

3.10.5 Detection-Algorithm Usage

i. When should the deadlock detection be done? Frequently, or infrequently?

The answer may depend on how frequently deadlocks are expected to occur, as well as the
possible consequences of not catching them immediately. ( If deadlocks are not removed
immediately when they occur, then more and more processes can "back up" behind the deadlock,
making the eventual task of unblocking the system more difficult and possibly damaging to more
processes. )

ii. There are two obvious approaches, each with trade-offs:

1. Do deadlock detection after every resource allocation which cannot be immediately granted.
This has the advantage of detecting the deadlock right away, while the minimum number of
processes are involved in the deadlock. ( One might consider that the process whose request
triggered the deadlock condition is the "cause" of the deadlock, but realistically all of the processes
in the cycle are equally responsible for the resulting deadlock. ) The down side of this approach is
the extensive overhead and performance hit caused by checking for deadlocks so frequently.

OPERATING SYSTEM (BCS303) 31

 RV Institute of Technology and Management®

[Link] deadlock detection only when there is some clue that a deadlock may have occurred, such
as when CPU utilization reduces to 40% or some other magic number. The advantage is that
deadlock detection isdone much less frequently, but the down side is that it becomes impossible
to detect the processes involved in the original deadlock, and so deadlock recovery can be more
complicated and damaging to more processes.

3. As I write this, a third alternative comes to mind: Keep a historical log of resource allocations,
since that last known time of no deadlocks. Do deadlock checks periodically ( once an hour or
when CPU usage is low?), and then use the historical log to trace through and determine when
the deadlock occurred and what processes caused the initial deadlock.

Unfortunately I'm not certain that breaking the original deadlock would then free up the resulting
log jam. )

3.11 Recovery from Deadlock

There are three basic approaches to recovery from deadlock:

● Inform the system operator, and allow him/her to take manual intervention.
● Terminate one or more processes involved in the deadlock
● Preempt resources.

3.11.1 Process Termination

Two basic approaches, both of which recover resources allocated to terminated processes:
o Terminate all processes involved in the deadlock. This definitely solves the deadlock,
but at the expense of terminating more processes than would be absolutely necessary.
o Terminate processes one by one until the deadlock is broken. This is more conservative,
but requires doing deadlock detection after each step.
In the latter case there are many factors that can go into deciding which processes to terminate
next:
• Process priorities

OPERATING SYSTEM (BCS303) 32

 RV Institute of Technology and Management®

• How long the process has been running, and how close it is to finishing.
• How many and what type of resources is the process holding. (Are they easy to preempt
and restore?)
• How many more resources does the process need to complete.
• How many processes will need to be terminated.
• Whether the process is interactive or batch.

3.11.2 Resource Preemption

When preempting resources to relieve deadlock, there are three important issues to be addressed:
• Selecting a victim - Deciding which resources to preempt from which processes involves many
of the same decision criteria outlined above.
• Rollback - Ideally one would like to roll back a preempted process to a safe state prior to the
point at which that resource was originally allocated to the process. Unfortunately, it can be
difficult or impossible to determine what such a safe state is, and so the only safe rollback is to
roll back all the way back to the beginning. (I.e. abort the process and make it start over.)
• Starvation - How do you guarantee that a process won't starve because its resources are
constantly being preempted? One option would be to use a priority system, and increase the
priority of a process every time its resources get preempted. Eventually it should get a high
enough priority that it won't get preempted any more.

OPERATING SYSTEM (BCS303) 33