BCA Sem 2 Operating Systems - Module 3

PROCESS SYNCHRONIZATION

Inter process Communication

Processes executing concurrently in the operating system may be either independent processes or
cooperating processes. A process is independent if it cannot affect or be affected by the other
processes executing in the system. Any process that does not share data with any other process is
independent. A process is cooperating if it can affect or be affected by the other processes executing
in the system. Clearly, any process that shares data with other processes is a cooperating process.

There are several reasons for providing an environment that allows process cooperation:

 Information sharing: Since several users may be interested in the same piece of information (for
instance, a shared file), we must provide an environment to allow concurrent access to such
information.

 Computation speedup: If we want a particular task to run faster, we must break it into subtasks, each
of which will be executing in parallel with the others. Notice that such a speedup can be achieved
only if the computer has multiple processing elements (such as CPUs or I/O channels).

 Modularity: It has to construct the system in a modular fashion, dividing the system functions into
separate processes or threads.

 Convenience: Even an individual user may work on many tasks at the same time. For instance, a
user may be editing, printing, and compiling in parallel.

Cooperating processes require an Inter Process Communication (IPC) mechanism that will allow them
to exchange data and information. There are two fundamental models of inter process communication:
(1) shared memory and (2) message passing. In the shared-memory model, a region of memory that
is shared by cooperating processes is established. Processes can then exchange information by reading
and writing data to the shared region. In the message passing model, communication takes place by
means of messages exchanged between the cooperating processes.
The two communications models are contrasted in the figure below

Page 1 of 29
 BCA Sem 2 Operating Systems - Module 3

Message passing is useful for exchanging smaller amounts of data, because no conflicts need be
avoided. Message passing is also easier to implement than is shared memory for inter-computer
communication. Shared memory allows maximum speed and convenience of communication. Shared
memory is faster than message passing, as message passing systems are typically implemented using
system calls and thus require the more time-consuming task of kernel intervention. In contrast, in
shared memory systems, system calls are required only to establish shared-memory regions. Once
shared memory is established, all accesses are treated as routine memory accesses, and no assistance
from the kernel is required

Race Condition
A situation in which 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, we need to ensure that only one process at a time can manipulate
the shared variable.
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. The important feature of the system is that, when
one process is executing in its critical section, no other process is allowed to execute in its critical
section. Thus the execution of critical sections by the processes is mutually exclusive in time.
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.

Fig : General structure of a typical process Pi

A solution to the critical-section problem must satisfy the following three requirements:
1. Mutual exclusion. If process Pi is executing in its critical section, then no other processes can be
executing in their critical sections.
2. 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

Page 2 of 29
 BCA Sem 2 Operating Systems - Module 3

participate in deciding which will enter its critical section next, and this selection cannot be postponed
indefinitely.
3. 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 critical section
and before that request is granted.

Peterson's Solution

 Peterson's Solution is a classic software-based solution to the critical section problem. It is

unfortunately not guaranteed to work on modern hardware, due to vagaries of load and store
operations, but it illustrates a number of important concepts.
 Peterson's solution is based on two processes, P0 and P1, which alternate between their critical
sections and remainder sections. For convenience of discussion, "this" process is Pi, and the
"other" process is Pj. ( i.e. j = 1 - i )
 Peterson's solution requires two shared data items:
o int turn :- indicates whose turn it is to enter into the critical section.
o If turn = = i, then process i is allowed into their critical section.
o boolean flag[ 2 ] :- indicates when a process wants to enter into their critical section.
When process i wants to enter their critical section, it sets flag[ i ] to true.
 In the following diagram, the entry and exit sections are enclosed in boxes.
o In the entry section, process i first raises a flag indicating a desire to enter the critical
section.
o Then turn is set to j to allow the other process to enter their critical section if process
j so desires.
o The while loop is a busy loop, which makes process i wait as long as process j has the
turn and wants to enter the critical section.
o Process i lowers the flag[ i ] in the exit section, allowing process j to continue if it has
been waiting.

Page 3 of 29
 BCA Sem 2 Operating Systems - Module 3

Figure - The structure of process Pi in Peterson's solution.

 To prove that the solution is correct, we must examine the three conditions listed above:
1. Mutual exclusion - If one process is executing their critical section when the other
wishes to do so, the second process will become blocked by the flag of the first process.
If both processes attempt to enter at the same time, the last process to execute "turn =
j" will be blocked.
2. Progress - Each process can only be blocked at the while if the other process wants to
use the critical section ( flag[ j ] = = true ), and it is the other process's turn to use the
critical section ( turn = = j ). If both of those conditions are true, then the other process
( j ) will be allowed to enter the critical section, and upon exiting the critical section,
will set flag[ j ] to false, releasing process i. The shared variable turn assures that only
one process at a time can be blocked, and the flag variable allows one process to release
the other when exiting their critical section.
3. Bounded Waiting - As each process enters their entry section, they set the turn
variable to be the other processes turn. Since no process ever sets it back to their own
turn, this ensures that each process will have to let the other process go first at most
one time before it becomes their turn again.
 Note that the instruction "turn = j" is atomic, that is it is a single machine instruction which
cannot be interrupted.

Semaphore

Semaphore is a synchronization tool. A semaphore S is an integer variable that, apart from

initialization, is accessed only through two standard atomic operations: wait() and signal().
The definition of wait() is as follows:
wait(S) {
while (S <= 0)

Page 4 of 29
 BCA Sem 2 Operating Systems - Module 3

; // busy wait
S--;
}
The definition of signal() is as follows:
signal(S) {
S++;
}
 wait(s) : - Decrements the value of its argument semaphore, as soon as it becomes non-
negative.
 signal(s) :- Increments the value of its argument semaphore

Semaphore Usage

Two common types of semaphores are:

Binary Semaphore : - it has two states, 0 and 1
Counting Semaphore :- it takes multiple integer values
Binary semaphores can take on one of two values, 0 or 1. They can be used to solve the critical
section problem .
Example for Mutual-exclusion implementation with semaphores.
do {
wait (mutex);
critical section
signal (mutex);
remainder section
} while(1);

Semaphores can also be used to synchronize certain operations between processes. For example,
suppose it is important that process P1 execute statement S1 before process P2 executes statement S2.

 First we create a semaphore named synch that is shared by the two

processes, and initialize it to zero.
 Then in process P1 we insert the code:

S1;
signal(synch);

 and in process P2 we insert the code:

wait(synch);
S2;

 Because synch was initialized to 0, process P2 will block on the wait

until after P1 executes the call to signal.

Page 5 of 29
 BCA Sem 2 Operating Systems - Module 3

Disadvantages

Busy waiting: When a process is in its critical section only other process that tries to enter its critical
section must loop continuously in its entry code.

Deadlocks and Starvation

One important problem that can arise when using semaphores to block processes waiting for a limited
resource is the problem of deadlocks, which occur when multiple processes are blocked, each waiting
for a resource that can only be freed by one of the other ( blocked ) processes,

Classic Problems of Semaphore (Synchronization)

The main three classical problems are:

 The Bounded- Buffer problem (Producer – Consumer problem)
 The Readers- Writers Problem
 The Dining -Philosophers Problem

The Bounded- Buffer problem (Producer – Consumer problem)

 Here the access is controlled to a shared group of buffer of limited size (n)
 A producer tries to insert data into empty slots of buffer
 A consumer tries to remove data from the filled slots of the buffer
 In this solution, three types of semaphore are used
o (mutex or S) S = 1 [only one process is in the critical region]
o (empty) E = n [ n is the size of buffer]
o F = 0 [ Full is set to 0]
 Two atomic operations wait ( ) and signal ( ) are used.

The structure of the producer process

do

wait(E) //producer will wait on the empty slot. Wait until E > 0 and decrement E

wait(S) //requires the critical section (C.S)

//add the item

signal(S) //Release (C.S)

signal(F) //
Page 6 of 29
 BCA Sem 2 Operating Systems - Module 3

The structure of the consumer process

do
{
wait(full) ; //wait until F > 0 and decrement F
wait(S) ; //require the C.S
//remove an item from buffer
signal(S); //release C.S
signal(empty); //increment E
} while(true);

The Readers–Writers Problem

Suppose that a database is to be shared among several concurrent processes. Some of these processes
may want only to read the database, whereas others may want to update (that is, to read and write) the
database. We distinguish between these two types of processes by referring to the former as readers
and to the latter as writers. Obviously, if two readers access the shared data simultaneously, no adverse
effects will result. If a writer and some other process (either a reader or a writer) access the database
simultaneously, chaos may ensue.
To ensure that these difficulties do not arise, we require that the writers have exclusive access to the
shared database while writing to the database. This synchronization problem is referred to as the
readers–writers problem.
The readers–writers problem has several variations, all involving priorities.
The simplest one, referred to as the first readers–writers problem, requires that no reader be kept
waiting unless a writer has already obtained permission to use the shared object. In other words, no
reader should wait for other readers to finish simply because a writer is waiting. The second readers
–writers problem requires that, once a writer is ready, that writer perform its write as soon as possible.
In other words, if a writer is waiting to access the object, no new readers may start reading.
A solution to either problem may result in starvation. In the first case, writers may starve; in the second
case, readers may starve. For this reason, other variants of the problem have been proposed.
In the solution to the first readers–writers problem, the reader processes share the following data
structures:
semaphore rw mutex = 1;
semaphore mutex = 1;
int read count = 0;
The semaphores mutex and rw mutex are initialized to 1; read count is initialized to 0. The semaphore
rw mutex is common to both reader and writer processes. The mutex semaphore is used to ensure
mutual exclusion when the variable read count is updated. The read count variable keeps track of how
many processes are currently reading the object. The semaphore rw mutex functions as a mutual
exclusion semaphore for the writers. It is also used by the first or last reader that enters or exits the

Page 7 of 29
 BCA Sem 2 Operating Systems - Module 3

critical section. It is not used by readers who enter or exit while other readers are in their critical
sections.

Figure :- The structure of a reader process

do {
wait(mutex);
read count++;
if (read count == 1)
wait(rw mutex);
signal(mutex);
...
/* reading is performed */
...
wait(mutex);
read count--;
if (read count == 0)
signal(rw mutex);
signal(mutex);
} while (true);

Figure :- The structure of a reader process.

The 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 centre of the table

is a bowl of rice, and the table is laid with five single chopsticks.

Page 8 of 29
 BCA Sem 2 Operating Systems - Module 3

Figure 5.13 The situation of the dining philosophers.

When a philosopher thinks, she does not interact with her colleagues. From time to time, 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 neighbours). A philosopher may pick up only one chopstick at a
time. She cannot pick up a chopstick that is already in the hand of a neighbour. 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.
The dining-philosophers problem is considered a classic synchronization problem neither because
of its practical importance nor because computer scientists dislike philosophers but because it is an
example of a large class of concurrency-control problems. It is a simple representation of the need to
allocate several resources among several processes in a deadlock-free and starvation-free manner.
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 data are
semaphore chopstick[5];
where all the elements of chopstick are initialized to 1.

The structure of philosopher i is shown in figure.

do {
wait(chopstick[i]);
wait(chopstick[(i+1) % 5]);
...
/* eat for awhile */
...
signal(chopstick[i]);
signal(chopstick[(i+1) % 5]);
...

Page 9 of 29
 BCA Sem 2 Operating Systems - Module 3

/* think for awhile */

...
} while (true);

Figure 5.14 The structure of philosopher i.

Although this solution guarantees that no two neighbours are eating simultaneously, it nevertheless
must be rejected because it could create a deadlock. Suppose that all five philosophers become hungry
at the same time 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:
• Allow at most four philosophers to be sitting simultaneously at the table.
• Allow a philosopher to pick up her chopsticks only if both chopsticks are available (to do this, she
must pick them up in a critical section).
• 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.
Any satisfactory solution to the dining-philosophers problem must guard against the possibility that
one of the philosophers will starve to death. A deadlock-free solution does not necessarily eliminate
the possibility of starvation.

Monitors

 Semaphores can be very useful for solving concurrency problems, but only if programmers
use them properly. If even one process fails to abide by the proper use of semaphores, either
accidentally or deliberately, then the whole system breaks down.
 For this reason a higher-level language construct has been developed, called monitors.

Monitor Usage

A monitor is essentially a class, in which all data is private, and with the special restriction that only
one method within any given monitor object may be active at the same time. An additional
restriction is that monitor methods may only access the shared data within the monitor and any data
passed to them as parameters. i.e. they cannot access any data external to the monitor.

monitor monitor name

{
/* shared variable declarations */
function P1 ( . . . ) {
...
}
function P2 ( . . . ) {
...
}
.
.
Page 10 of 29
 BCA Sem 2 Operating Systems - Module 3

.
function Pn ( . . . ) {
...
}
initialization code ( . . . ) {
...
}
}
Figure Syntax of a monitor.

The following figure shows a schematic of a monitor, with an entry queue of processes waiting their
turn to execute monitor operations.

Fig: Schematic view of a monitor

In order to fully realize the potential of monitors, we need to introduce one additional new data type,
known as condition.
A variable of type condition has only two legal operations, wait and signal. ie, if X was defined as
type condition, then legal operations would be [Link]( ) and [Link]( )

Page 11 of 29
 BCA Sem 2 Operating Systems - Module 3

The wait operation blocks a process until some other process calls signal, and adds the blocked process
onto a list associated with that condition.
The signal operation does nothing if there are no processes waiting on that condition. Otherwise it
wakes up exactly one process from the condition’s list of waiting processes.
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.
Now suppose that, when the [Link]() operation is invoked by a process P, there exists a suspended
process Q associated with condition x. Clearly, if the suspended process Q is allowed to resume its
execution, the signalling process P must wait. Otherwise, both P and Q would be active
simultaneously within the monitor. Note, however, that conceptually both processes can continue with
their execution.
Two possibilities exist:
1. Signal and wait. P either waits until Q leaves the monitor or waits for another condition.
2. Signal and continue. Q either waits until P leaves the monitor or waits for another condition.

Figure. Monitor with condition variables.

DEADLOCK
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, 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.

Page 12 of 29
 BCA Sem 2 Operating Systems - Module 3

System Model
A system consists of a finite number of resources to be distributed among a number of competing
processes. The resources may be partitioned into several types (or classes), each consisting of some
number of identical instances. CPU cycles, files, and I/O devices (such as printers and DVD drives)
are examples of resource types. If a system has two CPUs, then the resource type CPU has two
instances. Similarly, the resource type printer may have five instances.
If a process requests an instance of a resource type, the allocation of any instance of the type should
satisfy the request. If it does not, then the instances are not identical, and the resource type classes
have not been defined properly.
For example, a system may have two printers. These two printers may be defined to be in the same
resource class if no one cares which printer prints which output. However, if one printer is on the
ninth floor and the other is in the basement, then people on the ninth floor may not see both printers
as equivalent, and separate resource classes may need to be defined for each
printer.
A process must request a resource before using it and must release the resource after using it. A
process may request as many resources as it requires to carry out its designated task. Obviously, the
number of resources requested may not exceed the total number of resources available in the system.
In other words, a process cannot request three printers if the system has only two.
Under the normal mode of operation, a process may utilize a resource in only the following sequence:
1. Request. The process requests the resource. If the request cannot be granted immediately (for
example, if the resource is being used by another process), then the requesting process must wait until
it can acquire the resource.
2. Use. The process can operate on the resource (for example, if the resource is a printer, the process
can print on the printer).
3. Release. The process releases the resource.
A set of processes is in a deadlocked state when every process in the set is waiting for an event that
can be caused only by another process in the set. The events with which we are mainly concerned
here are resource acquisition and release. The resources may be either physical resources (for
example, printers, tape drives, memory space, and CPU cycles) or logical resources (for example,
semaphores, files etc).
To illustrate a deadlocked state, consider a system with three CD RW drives. Suppose each of three
processes holds one of these CD RW drives. If each process now requests another drive, the three
processes will be in a deadlocked state. Each is waiting for the event “CD RW is released,” which
can be caused only by one of the other waiting processes. This example illustrates a deadlock
involving the same resource type.
Deadlocks may also involve different resource types. For example, consider a system with one
printer and one DVDdrive. Suppose that process Pi is holding the DVD and process Pj is holding
the printer. If Pi requests the printer and Pj requests the DVD drive, a deadlock occurs.

Page 13 of 29
 BCA Sem 2 Operating Systems - Module 3

Deadlock Characterization
1. Necessary Conditions
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 preemption. Resources cannot be preempted; that is, a resource can be released only
voluntarily by the process holding it, after that process has completed its task.
4. Circular 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.
[Link]-Allocation Graph
Deadlocks can be described more precisely in terms of a directed graph called a system resource-
allocation graph. This graph consists of a set of vertices V and a set of edges E. The set of vertices
V is partitioned into two different types of nodes: P = {P1, P2, ..., Pn}, the set consisting of all the
active processes in the system, and R = {R1, R2, ..., Rm}, the set consisting of all resource types in the
system.
A directed edge from process Pi to resource type Rj is denoted by Pi → Rj ; it signifies that process
Pi has requested an instance of resource type Rj and is currently waiting for that resource. A directed
edge from resource type Rj to process Pi is denoted by Rj → Pi ; it signifies that an instance of resource
type Rj has been allocated to process Pi . A directed edge Pi → Rj is called a request edge; a directed
edge Rj → Pi is called an assignment edge.
We represent each process Pi as a circle and each resource type Rj as a rectangle. Since resource type
Rj may have more than one instance, we represent each such instance as a dot within the rectangle.
Note that a request edge points to only the rectangle Rj , whereas an assignment edge must also
designate one of the dots in the rectangle.
When process Pi requests an instance of resource type Rj , a request edge is inserted in the resource-
allocation graph. When this request can be fulfilled, the request edge is instantaneously transformed
to an assignment edge. When the process no longer needs access to the resource, it releases the
resource. As a result, the assignment edge is deleted.
The resource-allocation graph depicts the following situation.

Page 14 of 29
 BCA Sem 2 Operating Systems - Module 3

Figure : Resource-allocation graph.

• The sets P, R, and E:

 P = {P1, P2, P3}
 R = {R1, R2, R3, R4}
 E = {P1 → R1, P2 → R3, R1 → P2, R2 → P2, R2 → P1, R3 → P3}
• Resource instances:
◦ One instance of resource type R1
◦ Two instances of resource type R2
◦ One instance of resource type R3
◦ Three instances of resource type R4
• Process states:
◦ Process P1 is holding an instance of resource type R2 and is waiting for an instance of resource
type R1.
◦ Process P2 is holding an instance of R1 and an instance of R2 and is waiting for an instance of R3.
◦ Process P3 is holding an instance of R3.
If the graph contains no cycles, then no process in the system is deadlocked. If the graph does contain
a cycle, then a deadlock may exist.
If each resource type has exactly one instance, then a cycle implies that a deadlock has occurred. If
the cycle involves only a set of resource types, each of which has only a single instance, then a
deadlock has occurred. Each process involved in the cycle is deadlocked. In this case, a cycle in the
graph is both a necessary and a sufficient condition for the existence of deadlock. If each resource
type has several instances, then a cycle does not necessarily
imply that a deadlock has occurred. In this case, a cycle in the graph is a necessary but not a sufficient
condition for the existence of deadlock.
Suppose that process P3 requests an instance of resource type R2. Since no resource instance is
currently available, we add a request edge P3→ R2 to the graph.

Page 15 of 29
 BCA Sem 2 Operating Systems - Module 3

Figure 7.2 Resource-allocation graph with a deadlock.

At this point, two minimal cycles exist in the system:

Processes P1, P2, and P3 are deadlocked. Process P2 is waiting for the resource R3, which is held by
process P3. Process P3 is waiting for either process P1 or process P2 to release resource R2. In
addition, process P1 is waiting for process P2 to release resource R1.
Consider the resource-allocation graph

Figure Resource-allocation graph with a cycle but no deadlock

In this example, we also have a cycle: P1 → R1 → P3 → R2 → P1
There is no deadlock. Observe that process P4 may release its instance of resource type R2. That
resource can then be allocated to P3, breaking the cycle.
If a resource-allocation graph does not have a cycle, then the system is not in a deadlocked state. If
there is a cycle, then the system may or may not be in a deadlocked state.

Page 16 of 29
 BCA Sem 2 Operating Systems - Module 3

Methods for Handling Deadlocks

The deadlock problem can be handled in one of the three ways.
 Use a protocol to prevent or avoid deadlocks, ensuring that the system will never enter a
deadlocked state.
 Allow the system to enter a deadlocked state, detect it, and recover.
 Ignore the problem altogether and pretend that deadlocks never occur in the system.

To ensure that deadlocks never occur, the system can use either a deadlock prevention or a
deadlock-avoidance scheme.
Deadlock prevention provides a set of methods to ensure that at least one of the necessary
conditions cannot hold.
Deadlock avoidance requires that the operating system be given additional information in advance
concerning which resources a process will request and use during its lifetime. With this additional
knowledge, the operating system can decide for each request whether or not the process should wait.
To decide whether the current request can be satisfied or must be delayed, the system must consider
the resources currently available, the resources currently
allocated to each process, and the future requests and releases of each process.

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. We elaborate on
this approach by examining each of the four necessary conditions separately.
[Link] 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.
[Link] 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.
We can implement this provision by requiring that system calls requesting resources for a process
precede all other system calls.
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
Page 17 of 29
 BCA Sem 2 Operating Systems - Module 3

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 two main disadvantages. 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. Otherwise, we
must request all resources at the beginning for both protocols.
Second, starvation is possible. A process that needs several popular resources may have to wait
indefinitely, because at least one of the resources that it needs is always allocated to some other
process.
[Link] Preemption
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
preempted. In other words, these resources are implicitly released. The preempted resources are added
to the list of resources for which the process is waiting. The process will be restarted only when it can
regain its old 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 pre-empt 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. While it is waiting, some of its resources may be preempted,
but only if another process requests them. A process can be restarted only when it is allocated the new
resources it is requesting and recovers any resources that were pre-empted while it was waiting.
This protocol is often applied to resources whose state can be easily saved and restored later, such as
CPU registers and memory space. It cannot generally be applied to such resources as mutex locks
and semaphores.
4. Circular Wait
The fourth and final condition for deadlocks is the circular-wait condition. One way to ensure that
this condition never holds is to impose a total ordering of all resource types and to require that each
process requests resources in an increasing order of enumeration.
To illustrate, we let R = {R1, R2, ..., Rm} be the set of resource types. We assign to each resource type
a unique integer number, which allows us to compare two resources and to determine whether one
precedes another in our ordering. Formally, we define a one-to-one function F: R→N, where N is the

Page 18 of 29
 BCA Sem 2 Operating Systems - Module 3

set of natural numbers. 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. Alternatively, we can require that a process requesting an instance of resource type
Rj must have any resources Ri such that F(Ri ) ≥ F(Rj ). Note also that if several instances of the same
resource type are needed, a single request for all of them must be issued.
If these two protocols are used, then the circular-wait condition cannot hold. We can demonstrate
this fact by assuming that a circular wait exists
Deadlock Avoidance
Deadlock-prevention algorithms, prevent deadlocks by limiting how requests can be made. The limits
ensure that at least one of the necessary conditions for deadlock cannot occur. Possible side effects of
preventing deadlocks by this method, however, are low device utilization and reduced system
throughput.
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. Each
request requires that in making this decision the system consider the resources currently available, the
resources currently allocated to each process, and the future requests and releases of each process.
The various algorithms that use this approach differ in the amount and type of information required.
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. A deadlock-avoidance
algorithm dynamically examines the resource-allocation state to ensure that a circular-wait condition
can never exist. The resource allocation state is defined by the number of available and allocated
resources and the maximum demands of the processes. In the following sections, we explore two
deadlock-avoidance algorithms.
[Link] 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
if, for each Pi , the resource requests that Pi can still make can be satisfied by the currently available
Page 19 of 29
 BCA Sem 2 Operating Systems - Module 3

resources plus the resources held by all Pj, with j < i. In this situation, if the resources that Pi needs
are not immediately available, then Pi can wait
until all Pj have finished. When they have finished, Pi can obtain all of its needed resources, complete
its designated task, return its allocated resources, and terminate. When Pi terminates, Pi+1 can obtain
its needed resources, and so on. If no such sequence exists, then the system state is said to be unsafe.
A safe state is not a deadlocked state. Conversely, a deadlocked state is an unsafe state. Not all unsafe
states are deadlocks, however (Figure 7.6). 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.
To illustrate, we consider a system with twelve magnetic tape drives and three processes: P0, P1, and
P2. Process P0 requires ten tape drives, process P1 may need as many as four tape drives, and process
P2 may need up to nine tape drives. Suppose that, at time t0, process P0 is holding five tape drives,
process P1 is holding two tape drives, and process P2 is holding two tape drives. (Thus, there are
three free tape drives.)

Figure. Safe, unsafe, and deadlocked state spaces.

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

Page 20 of 29
 BCA Sem 2 Operating Systems - Module 3

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 four available
tape drives. Since process P0 is allocated five tape drives but has a maximum of ten, it may request
five more tape drives. If it does so, it will have to wait, because they are unavailable. Similarly, process
P2 may request six additional tape drives and have to wait, resulting in a deadlock. Our mistake was
in granting the request from process P2 for one more tape drive. If we had made P2 wait until either
of the other processes had finished and released its resources, then we could have avoided the
deadlock.
Given the concept of a safe state, we can define avoidance algorithms that ensure that the system will
never deadlock. The idea is simply to ensure that the system will always remain in a safe state.
Initially, the system is in a safe state.
Whenever a process requests a resource that is currently available, the system must decide whether
the resource can be allocated immediately or whether the process must wait. The request is granted
only if the allocation leaves the system in a safe state.
In this scheme, if a process requests a resource that is currently available, it may still have to wait.
Thus, resource utilization may be lower than it would otherwise be.
[Link]-Allocation-Graph Algorithm
If we have a resource-allocation system with only one instance of each resource type, we can use a
variant of the resource-allocation graph for deadlock avoidance. In addition to the request and
assignment edges, we introduce a new type of edge, called a claim edge.
A claim edge Pi → Rj indicates that process Pi may request resource Rj at some time in the future.
This edge resembles a request edge in direction but is represented in the graph by a dashed line. When
process Pi requests resource Rj , the claim edge Pi → Rj is converted to a request edge. Similarly,
when a resource Rj is released by Pi , the assignment edge Rj → Pi is reconverted to a claim edge Pi
→ Rj .
Note that the resources must be claimed a priori in the system. That is, before process Pi starts
executing, all its claim edges must already appear in the resource-allocation graph. We can relax this
condition by allowing a claim edge Pi → Rj to be added to the graph only if all the edges associated
with process Pi are claim edges.
Now suppose that process Pi requests resource Rj. The request can be granted only if converting the
request edge Pi → Rj to an assignment edge Rj → Pi does not result in the formation of a cycle in the
resource-allocation graph. We check for safety by using a cycle-detection algorithm. An algorithm
for detecting a cycle in this graph requires an order of n2 operations, where n is the number of
processes in the system.
If no cycle exists, then the allocation of the resource will leave the system in a safe state. If a cycle
is found, then the allocation will put the system in an unsafe state. In that case, process Pi will have
to wait for its requests to be satisfied.

Page 21 of 29
 BCA Sem 2 Operating Systems - Module 3

Figure Resource-allocation graph for deadlock avoidance.

To illustrate this algorithm, we consider the resource-allocation graph of Figure 7.7.
Suppose that P2 requests R2. Although R2 is currently free, we cannot allocate it to P2, since this
action will create a cycle in the graph (Figure 7.8). A cycle, as mentioned, indicates that the system
is in an unsafe state. If P1 requests R2, and P2 requests R1, then a deadlock will occur.

Figure 7.8 An unsafe state in a resource-allocation graph.

[Link]’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. The name was chosen because the
algorithm could be used in a banking system to ensure that the bank never
allocated its available cash in such a way that it could no longer satisfy the needs of all its customers.
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:

Page 22 of 29
 BCA Sem 2 Operating Systems - Module 3

• Available. A vector of length m indicates the number of available resources of each type. If
Available[j] equals k, then k instances of resource type Rj are available.
• 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. If Allocation[i][j] equals k, then process Pi is currently allocated k instances of resource
type Rj .
• Need. An n × m matrix indicates the remaining resource need of each process. If Need[i][j] equals
k, then process Pi may need k more instances of resource type Rj to complete its task.
 Need[i][j] equals Max[i][j]− Allocation[i][j].
These data structures vary over time in both size and value.
To simplify the presentation of the banker’s algorithm, we next establish some notation. Let X and Y
be vectors of length n. We say that X ≤ Y if and only if X[i] ≤ Y[i] for all i = 1, 2, ..., n. For example,
if X = (1,7,3,2) and Y = (0,3,2,1), then Y ≤ X. In addition, Y < X if Y ≤ X and Y _= X.
We can treat each row in the matrices Allocation and Need as vectors and refer to them as Allocationi
and Needi . The vector Allocationi specifies the resources currently allocated to process Pi ; the vector
Needi specifies the additional resources that process Pi may still request to complete its task.
3.1 Safety Algorithm
We can now present the algorithm for finding out whether or not a system is
in a safe state. This algorithm can be described as follows:
1. Let Work and Finish be vectors of length m and n, respectively. Initialize
Work = Available and Finish[i] = false for i = 0, 1, ..., n − 1.
2. Find an index i such that both
a. Finish[i] == false
b. Needi ≤Work
If no such i exists, go to step 4.
3. Work =Work + Allocationi
Finish[i] = true
Go to step 2.
4. If Finish[i] == true for all i, then the system is in a safe state.
This algorithm may require an order ofm × n2 operations to determine whether
a state is safe.
3.2 Resource-Request Algorithm
Let Requesti be the request vector for process Pi . If Requesti [ j] == k, then process Pi wants k
instances of resource type Rj . When a request for resources is made by process Pi , the following
actions are taken:
1. If Requesti ≤Needi , go to step 2. Otherwise, raise an error condition, since the process has exceeded
its maximum claim.
2. If Requesti ≤ Available, go to step 3. Otherwise, Pi must wait, since the resources are not available.
3. Have the system pretend to have allocated the requested resources to process Pi by modifying the
state as follows:
Page 23 of 29
 BCA Sem 2 Operating Systems - Module 3

Available = Available–Requesti ;
Allocationi = Allocationi + Requesti ;
Needi = Needi –Requesti ;
If the resulting resource-allocation state is safe, the transaction is completed, and process Pi is
allocated its resources. If the new state is unsafe, then Pi must wait for Requesti , and the old
resource-allocation state is restored.
3.3An Illustrative Example
To illustrate the use of the banker’s algorithm, consider a system with five processes P0 through P4
and three resource types A, B, and C. Resource type A has ten instances, resource type B has five
instances, and resource type C has seven instances. Suppose that, at time T0, the following snapshot
of the system has been taken:

We claim that the system is currently in a safe state. Indeed, the sequence <P1, P3, P4, P2, P0>
satisfies the safety criteria. Suppose now that process P1 requests one additional instance of resource
type A and two instances of resource type C, so Request1 = (1,0,2). To decide whether this request
can be immediately granted, we first check that Request1 ≤ Available—that is, that (1,0,2) ≤ (3,3,2),
which is true. We then pretend that this request has been
fulfilled, and we arrive at the following new state:

Page 24 of 29
 BCA Sem 2 Operating Systems - Module 3

We must determine whether this new system state is safe. To do so, we execute our safety algorithm
and find that the sequence <P1, P3, P4, P0, P2> satisfies the safety requirement. Hence, we can
immediately grant the request of process P1.
You should be able to see, however, that when the system is in this state, a request for (3,3,0) by P4
cannot be granted, since the resources are not available.
Furthermore, a request for (0,2,0) by P0 cannot be granted, even though the resources are available,
since the resulting state is unsafe.
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

In the following discussion, we elaborate on these two requirements as they pertain to systems with
only a single instance of each resource type, as well as to systems with several instances of each
resource type. At this point, however, we note that a detection-and-recovery scheme requires overhead
that includes not only the run-time costs of maintaining the necessary information and executing the
detection algorithm but also the potential losses inherent in recovering from a deadlock.
[Link] 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.
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. An edge Pi → Pj exists in a wait-for graph if and only if the corresponding
resource allocation graph contains two edges Pi → Rq and Rq → Pj for some resource Rq .
In Figure , we present a resource-allocation graph and the corresponding wait-for graph.

Page 25 of 29
 BCA Sem 2 Operating Systems - Module 3

As before, a deadlock exists in the system if and only if the wait-for graph contains a cycle. To detect
deadlocks, the system needs to maintain the wait-for-graph and periodically invoke an algorithm that
searches for a cycle in the graph. An algorithm to detect a cycle in a graph requires an order of n2
operations, where n is the number of vertices in the 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. The algorithm employs several time-varying data structures that are similar to those used in
the banker’s algorithm.
• 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 .
To simplify notation, we again treat the rows in the matrices Allocation and Request as
vectors; we refer to them as Allocationi and Requesti . The detection algorithm simply investigates
every possible allocation sequence for the processes that remain to be completed.

Page 26 of 29
 BCA Sem 2 Operating Systems - Module 3

This algorithm requires an order of m × n2 operations to detect whether the system is in a deadlocked
state.
To illustrate this algorithm, we consider a system with five processes P0 through P4 and three resource
types A, B, and C. Resource type A has seven instances, resource type B has two instances, and
resource type C has six instances. Suppose that, at time T0, we have the following resource-allocation
state:

We claim that the system is not in a deadlocked state. Indeed, if we execute our algorithm, we will
find that the sequence <P0, P2, P3, P1, P4> results in Finish[i] == true for all i.
Suppose now that process P2 makes one additional request for an instance of type C. The Request
matrix is modified as follows:

Page 27 of 29
 BCA Sem 2 Operating Systems - Module 3

We claim that the system is now deadlocked. Although we can reclaim the resources held by
process P0, the number of available resources is not sufficient to fulfill the requests of the other
processes. Thus, a deadlock exists, consisting of processes P1, P2, P3, and P4.
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 preempt 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.
Aborting a process may not be easy. If the process was in the midst of updating a file, terminating it
will leave that file in an incorrect state. Similarly, if the process was in the midst of printing data on
a printer, the system must reset the printer to a correct state before printing the next job. If the partial
termination method is used, then we must determine which deadlocked process (or processes) should
be terminated. This determination is a policy decision, similar to CPU-scheduling decisions. The
question is basically an economic one; we should abort those processes whose termination will incur
the minimum cost. Unfortunately, the term minimum cost is not a precise one.
Many factors may affect which process is chosen, including:
1. What the priority of the process is
2. How long the process has computed and how much longer the process will compute before
completing its designated task
3. How many and what types of resources the process has used (for example, whether the resources
are simple to pre-empt)
4. How many more resources the process needs in order to complete
5. How many processes will need to be terminated
6. Whether the process is interactive or batch
2 Resource Preemption
To eliminate deadlocks using resource pre-emption, we successively pre-empt some resources
fromprocesses and give these resources to other processes until the deadlock cycle is broken.
If preemption 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
Page 28 of 29
 BCA Sem 2 Operating Systems - Module 3

such parameters as the number of resources a deadlocked process is holding and the amount of time
the process has thus far consumed.
2. Rollback. If we pre-empt a resource from a process, what should be done with that process? 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. It is difficult to determine what a safe state is,
the simplest solution is a total rollback: abort the process and then restart it. Although it is more
effective to roll back the process only as far as necessary to break the deadlock, this method requires
the system to keep more information about the state of all running processes.
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?
In a system where victim selection is based primarily on cost factors, it may happen that the same
process is always picked as a victim. As a result, this process never completes its designated task, a
starvation situation any practical system must address. We must ensure that a process can be picked
as a victim only a (small) finite number of times. The most common solution is to include the number
of rollbacks in the cost factor.

*************************** ** End of Module 3*****************************

Page 29 of 29