Operating System:15CS43T 2020-21

UNIT- 3
SYNCHRONIZATION AND DEADLOCKS

Background: 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 race condition. To prevent race conditions, concurrent
processes must be synchronized

3.1 Critical section Problem

Consider a system consists of “n” number of processes P0, P1, P2..... Pn-1. Each
process has a segment of code, called a “critical section”. In which the process may be
updating table, changing variable etc. The figure 3.1 illustrates the critical section
problem.

The important feature of the system is that, when one process is executing in its
critical section, no other process is to be 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 to enter its critical section. The section of code
implementing this request is the “entry section”.

Do
{

Entry section

Critical section

Exit section

Remainder section
} while (1);
Fig 3.1 General structure of Critical-section problem
The critical section is followed by an “Exit section”. The remaining is the
remainder section.

A solution to the critical-section problem must satisfy the following 3

requirements.

1. Mutual Exclusive: - If process P1 is executing in its critical section, then no other

processes can be executing in their critical sections.
Computer Science and Engineering 41
Operating System:15CS43T 2020-21

2. Progress: - If no process is executing in its critical section and there exist some
processes that wish to enter their critical section, then the selection of the processes that
will enter the critical section next cannot be postponed indefinitely.

3. Bounded waiting: - A bound must exist 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.

There are two approaches used to handle critical section in operating system

1. Preemptive kernels

2. Non-Preemptive kernels

1. Preemptive Kernels – It allows a process to be preempted while it is running in

kernel mode

2. Non-Preemptive Kernels – It does not allow process to be preempted while it is

running in kernel mode

3.1.1 Semaphores
A semaphore is a synchronization tool used to solve the critical-section problem of mutual
exclusive.

A semaphore can be accessed only through two standard operations. They are

1. Wait ( )
2. Signal ( )
The definition of wait ( ) and signal ( ) are
Definition of wait ( ) Definition of signal ( )
Wait (S) signal (S)
{ {
while S<=0 S++;
S- -; }
}
S- is the semaphore integer variable
When one process modifies the semaphore values, then no other process can
simultaneously modify that same semaphore value. Operating systems often distinguish
between counting and binary semaphore.

Computer Science and Engineering 42

Operating System:15CS43T 2020-21

 The value of a counting semaphore can range over an unrestricted domain.

Counting semaphores can be used to control access to a given resources consisting
of a finite number of instances.

 The value of a binary semaphore can range between 0 and 1. On some systems,
binary semaphores are known as mutex locks, as they are locks that provide
mutual exclusion.

We can use binary semaphores to deal with critical- section problem for multiple
processes. The n processes share a c semaphore, mutex, initialized to 1. Each process Pi is
organized as below

Do

Waiting (mut x);

//critical section

Signal (mut x);

//remainder section

} while (true);

Processes will share common semaphore variable called “mutx” (mutual exclusion).

DEADLOCKS:
Introduction
The waiting process will never change their state because their resource they have
requested on held by other waiting process. This situation is called as “Deadlock”.

OR

A set of blocked processes each holding a resource and waiting to acquire a resource held
by another process in the set.

3.2 System model

A system consists of a finite number of resources to be distributed among a number of
competing processes. There are two types of resources

1. Preemptable resource - A resource, that can be taken away from the running process
that holds the resource that may causing system failure.

Computer Science and Engineering 43

Operating System:15CS43T 2020-21

2. Non-Preemptable resource - A resource, which cannot be taken away from the

running process that holds the resource without causing system failures.

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.
The number of resources requested may not exceed the total number of resources available
in the system.

Under the normal mode of operation, a process may utilize a resource in only the
following sequence.

 Request - If the request cannot be granted immediately then the requesting process
must wait until it can acquire the resource.

 Use - The process can operate on the resource.

 Release - The process release the resource.

3.3 Deadlock characterization

There are two types of deadlock characterization
 Necessary condition
 Resource allocation graph

3.2.1 Necessary condition

A deadlock occurs if the following 4 condition satisfied simultaneously in a system.

1. Mutual Exclusion - Only one process can use the resource at a time. If another process
requests that resources, 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 - Resource cannot be preempted that is a resource can be released only

voluntarily by the process holding or after it has completed its task.

4. Circular wait - There must exists a set of waiting process {P0, P1, P2, and P3.....Pn}
such that P0 is waiting for a resource that is held by P1. P2 is waiting for a resource that is
held by P2....Pn-1 is waiting for a resource that is held by P0 and Pn is waiting for a resource
that is held by P0.

Computer Science and Engineering 44

Operating System:15CS43T 2020-21

3.2.2 Resource allocation Graph

Deadlocks can be described more precisely in terms of a directed graph called a system
resource-allocation graph .This can be used to describe deadlock. This graph consists of
set of vertices V & set of edges E. The set of vertices V is divided into two different types
of nodes.

Pi= {P1, P2....Pn}

Rj= {R1, R2....Rn}
 request edge – directed edge P1  Rj
 assignment edge – directed edge Rj  Pi

 Process

 Resource Type with 4 instances

 Pi Requests instance of Rj

 Pi is holding an instance of Rj

Fig 3.1 Resource-allocation graph with deadlock

Request edge must 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.
Computer Science and Engineering 45
Operating System:15CS43T 2020-21

The resource allocation graph in above depicts the following situations:

 The set P, R and E

P= {P1, P2, P3}

R= {R1, R2, R3, R4}

E= {P1R1, P2P3, R1P2, R2P1, R3P3}

 Resource instances:

 One instance of the resource R1

 Two instances of the Resource R2

 One instance of resource R3

 Three instances of the resource type R4

 Process state

 Process P1 is holding resource type R2 & waiting for resource types R1.

 Process P2 is holding resource type R1 & R2 & waiting for resource type R3.

 Process P3 is holding resource type R3.

Given definition of a resource-allocation graph, it can be shown that, 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.

Cycles:
P1R1P2R3P3R2P1
P2R3P3R2P2

Fig 3.2 Resource-allocation graph with a deadlock

Cycle P1R1P3R2P1

Computer Science and Engineering 46

Operating System:15CS43T 2020-21

Fig: 3.3 Resource-allocation graph with a cycle but no deadlock

 If graph contains no cycles  no deadlock.

 If graph contains a cycle 

1. if only one instance per resource type, then deadlock.

2. if several instances per resource type, possibility of deadlock.

3.3 Methods for handling Deadlocks

The deadlock problem can be handled in one of 3 ways

1. Deadlock Prevention—never allow system to enter a deadlock state

2. Deadlock Avoidance--- Ignore the problem altogether and pretend that

deadlocks never occur in the system

3. Deadlock Detection-- Allow the system to enter a deadlock state, detect it and

recover.

3.4 Deadlock Prevention

A deadlock can be prevented by ensuring that at least one of the necessary conditions
cannot hold.

1. Mutual Exclusion – The mutual- exclusion condition must hold for non-sharable
resources. The sharable resources cannot have deadlock because there is no mutual
exclusion condition.

2. Hold and Wait – must guarantee that whenever a process requests a resource, it does
not hold any other resources.

 Require process to request and be allocated all its resources before it begins
execution, or allow process to request resources only when the process has none.

Computer Science and Engineering 47

Operating System:15CS43T 2020-21

 Low resource utilization; starvation possible.

3. No Preemption –If a process that is holding some resources requests another resource
that cannot be immediately allocated to it, then all resources currently being held are
released.

 Preempted resources are added to the list of resources for which the process is
waiting.

 Process will be restarted only when it can regain its old resources, as well as the
new ones that it is requesting.

4. Circular wait - One way to ensure that this condition never holds is to impose a total
ordering of all resources types and to require that each process requests resources in an
increasing order of enumeration

4.5 Deadlock Avoidance

An alternative method for avoiding deadlocks is to require additional information about
how resources are to be requested. 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 release of each process.

 The simplest and most useful model requires that each process declare the
maximum number of resources of each type that it may need.
 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 process.

Following are the deadlock avoidance algorithm

1. Safe and unsafe state

2. Resource-allocation-graph algorithm

3. Banker’s algorithm

1 Safe and Unsafe state

A state is “safe” if the system can allocate resources to each process(up to its maximum)
is some order and still avoids a deadlock. A system is in safe state if there exists a safe
sequence. A sequence of processes <P1,P2,..., Pn> is a safe sequence for the current

Computer Science and Engineering 48

Operating System:15CS43T 2020-21

allocation state if, for each Pi, the resource requests that Pi can still make can be satisfied
by the currently available resources plus the resources held by all Pj with j<i

A deadlocked state is on “unsafe state”. In an unsafe state, the operating system cannot
prevent processes form requesting resource such that a deadlock occurs.

So we can define deadlock avoidance algorithm: If the system is in safe state, the
system can be deadlocked and if the system is in unsafe state, then system can in deadlock.

Avoidance: Ensure that a system will never enter an unsafe state.

Fig 3.4 Safe, unsafe and deadlock state spaces

2 A resource allocation graph algorithm
This can be used for deadlock avoidance for resource allocation system with only one
instance of each resource type. In addition to the request and assignment edges it has
introduced 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.

Fig 3.5 Resource-allocation graph for deadlock avoidance

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. If no cycles exists, then the
allocation of the resource will leave the system in a safe state. If a cycle if found, then the
allocation will put the system in an unsafe state. Therefore, process Pi will have to wait for
its request to be satisfied.

Computer Science and Engineering 49

Operating System:15CS43T 2020-21

Fig 3.6 An unsafe state in a resource-allocation graph

3 Banker’s Algorithm
The banker’s algorithm uses an “avoidance policy”. This algorithm is applicable to
resource allocation systems with multiple instances of each resource type.

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 safe state. If it
will, the resources are allocated; otherwise, the process must wait until some other process
releases enough resources.

Implementation:
Let ‘n’ indicates the number of processes in the system & ‘m’ indicates the number of
resource types, then following data structures are needed for the banker’s algorithm.

 Available: - An array or vector of length ‘m’ indicates the number of available

resources of each type.

If available[j] equals k there are k instances of resource type Rj 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 instance 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 Rj.

 Need: - An “n*m” matrix indicates the remaining resource need of each process. If
Need[i][j] equals k, then process Pi need K more instances of resource type Rj to
complete its task. Need[i][j] = Max[i][j]-Allocation[i][j]

Computer Science and Engineering 50

Operating System:15CS43T 2020-21

Banker’s algorithm is implemented using following two algorithms

o Safety algorithm
o Resource-Request algorithm
. Safety Algorithm
This algorithm is used to find whether the system is in safe state or not. 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 i such that both
a. Finish[i] == false
b. Needi ≤ Work
3. Work = Work+Allocation
Finish[i] = true
Go to step2
4. If Finish[i] == true for all i, then the system is in a safe state.

This algorithm may require an order of m*n2 operations to determine whether a state is
safe

Resource-Request Algorithm:
This algorithm is used to determine if requests can be safely granted.
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 step3. 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:
Available = Available-Requesti;
Allocationi = Allocationi + Requesti;
Needi = Needi – Requesti;
If the resulting resource-allocation state is safe, the transaction state is safe, the transaction
is completed, and process Pi is allocated its resources. However, if the new state is unsafe,
then Pi must wait for requesti, and the old resource-allocation state is unsafe.

Computer Science and Engineering 51

Operating System:15CS43T 2020-21

Example:
5 Processes P0 through P4;
3 resource types : A (10 instances), B (5 Instances) and C (7 instances)

Snapshot at time T0
Process Allocation Max Available
ABC AB ABC
P0 010 7C
53 332
P1 200 322
P2 302 902
P3 211 222
P4 002 433

Calculate the safe sequence?

Solution:
Process Need = Max - Allocation
ABC
P0 010
P1 200
P2 302
P3 211
P4 002

Process Allocation Max Need Available

ABC ABC ABC ABC
P1 200 322 122 332
P3 211 222 0 1 1 5 3 2 (Available = Allocation(P1)+Available)
P4 002 433 431 743
P2 302 902 600 745
P0 010 753 7 4 3 10 4 7
Available= (10, 4, 7) + (0, 1,0) = 10 5 7

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

3.6. Deadlock Detection

In deadlock detection, the system must provide the following two operations

1. The algorithms are used to test the state of the system to determine whether a
deadlock has occurred or not.
2. An algorithm to recover from the deadlock.
There are two types of methods are used to detect the deadlock
1. Single instance of each resource type
2. Several instance of resource type

Computer Science and Engineering 52

Operating System:15CS43T 2020-21

3.6.1 Single instance of each resource type

If all resources have only a single instance, then we can define deadlock detection
algorithm that uses a variant of the resource-allocation graph called “wait-for-graph”.

An edge from Pi to Pj in a “wait-for-graph” implies that process Pi is waiting process Pj

to release a resource that needs for Pi.

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.
A deadlock exits in the system if and only if the wait-for graph contains a cycle. To detect
deadlock, the system needs to maintain the wait-for graph and periodically invoke an
algorithm that searches for cycle in the graph.

The below figure 3.2 illustrate the example to represent a resource-allocation graph and
the corresponding wait-for graph.

P5

P5
R1 R3 R4

P1 P1 P2 P3
P2 P3

R2 R5

P4 P4

a. Resource allocation graph b. Corresponding wait-for graph

3.6.2 Several instances of Resource type

The “wait-for-graph” schema is not applicable to a resource-allocation system with
several instance of each resource type.

The deadlock detection algorithm of a system with multiple instance of resource type uses
the following data structure.

Computer Science and Engineering 53

Operating System:15CS43T 2020-21

 Available: - An array or 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 instance of resource type Rj.

Algorithm
1 Let Work and Finish be vectors of length m and n respectively. Initialize
Work = Available for i= 0, 1,....., n-1, If Allocationi ≠ 0 , then Finish[i] = false for

i =0, 1,....., n-1 otherwise Finish[i] = true

2 Find an index i such that both

Finish[i] == false
Requesti ≤ Work
If no such i exists, go to step 4.
3. Work = Work+Allocation
Finish[i] = true
Go to step2
4. If Finish[i] == false, for some i, 0≤i≤ n, then the system is in a deadlocked state.
Moreover, if for all i, then the system is in a safe state. If Finish[i] == false, then
process Pi is deadlocked.

This algorithm may require an order of m*n2 operations to determine whether the system
is in a deadlocked state.

Example:

Consider a system with five processes P0 through P4 and three resources types A, B,C.
Resource 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.

Process Allocation Request Available
ABC ABC ABC
P0 010 000 000
P1 200 202
P2 303 000

Computer Science and Engineering 54

Operating System:15CS43T 2020-21

P3 211 100
P4 002 002

If we execute the algorithm in the sequence <P0, P2, P3, P1, P4> then the system is not in
deadlock.

Process Allocation Request Available

ABC ABC ABC
P0 010 000 000
P2 303 000 010
P3 211 100 313
P1 200 202 524
P4 002 002 724

If P2 makes request for one instance of C then the system is in deadlock.

3.7 Recovery from Deadlock

There are two options for breaking a deadlock
1. Process termination
2. Resource Preemption
4.7.1 Process termination
There are two methods are available in process termination

a. Abort all deadlock process

b. Abort one process at a time until the deadlock cycle is eliminated

a. Abort all deadlock process

This method will break the deadlock cycle but it is expensive since the aborted
process may have computed for a long time and must be recomputed later.

b. Abort one process at a time until the deadlock cycle is eliminated

This method involves overhead since after each process is aborted, a deadlock
detection algorithm must be invoked to determine whether any process are still
deadlocked.

4.7.2 Resource Preemption

In this method, resources are preempted from process and are given to other process
successively until the deadlock cycle is broken.

In this case there are 3 issues needed

Computer Science and Engineering 55
Operating System:15CS43T 2020-21

 Selecting a victim: - selecting process or resources to Preempted on basis of

“minimize cost” to come out of deadlock.

 Rollback: - Rollback is abort the process at deadlock and then restart if it is in

“safe state”.

 Starvation: - pick the victim in such a way not starvation situation occurs.

References:

[1] Operating System Principles – Abraham Silberschatz, Peter Baer Galvin, Greg
Gagne, 8th edition, Wiley-India.
[2 ] Operating Systems, I. Chandra Mohan, PHI, 2013
[3 ] http://www.tutorialspoint.com/operating_system/
[4] http://courses.cs.vt.edu/~csonline/OS/Lessons/index.html
[5] http://www.nptel.ac.in

Computer Science and Engineering 56