Amity School of Engineering & Technology

System Model
• Resource types R1, R2, . . ., Rm
CPU cycles, memory space, I/O devices

• Each resource type Ri has Wi

instances.
• Each process utilizes a resource as
follows:
– request
– use
– release
 Amity School of Engineering & Technology

DEADLOCK
• In a computer system deadlocks arise
when members of a group of processes
which hold resources are blocked
indefinitely from access to resources held
by other processes within the group
 Amity School of Engineering & Technology

Deadlock Characterization
Deadlock can arise if four conditions hold simultaneously.
• Mutual exclusion: only one process at a time can use a
resource

• Hold and wait: a process holding at least one resource is

waiting to acquire additional resources held by other
processes

• No preemption: a resource can be released only voluntarily

by the process holding it, after that process has completed
its task

• Circular wait: there exists a set {P0, P1, …, P0} of waiting

processes such that P0 is waiting for a resource that is held
by P1, P1 is waiting for a resource that is held by
P2, …, Pn–1 is waiting for a resource that is held by
Pn, and P0 is waiting for a resource that is held by P0.
 Amity School of Engineering & Technology

Resource-Allocation Graph
A set of vertices V and a set of edges E.

• V is partitioned into two types:

– P = {P1, P2, …, Pn}, the set consisting of all the
processes in the system

– R = {R1, R2, …, Rm}, the set consisting of all

resource types in the system

• Request edge – directed edge Pi → Rj

• Assignment edge – directed edge Rj → Pi

 Amity School of Engineering & Technology

Resource-Allocation Graph
• Process

• Resource Type with 4 instances

• Pi requests instance of Rj
Pi
Rj
• Pi is holding an instance of Rj

Pi
Rj
 Amity School of Engineering & Technology

Example of a Resource Allocation

Graph
 Amity School of Engineering & Technology

Resource Allocation Graph With A Deadlock

 Amity School of Engineering & Technology

Graph With A Cycle But No Deadlock

 Amity School of Engineering & Technology

Basic Facts
• If graph contains no cycles  no
deadlock

• If graph contains a cycle 

– if only one instance per resource type,
then deadlock
– if several instances per resource type,
possibility of deadlock
 Amity School of Engineering & Technology

Deadlock Handling
we can deal with the deadlock problem in
one of three ways:
• We can use a protocol to prevent or avoid
deadlocks, ensuring that the system will
never enter a deadlocked state.
• We can allow the system to enter a
deadlocked state, detect it, and recover.
• We can ignore the problem altogether and
pretend that deadlocks never occur in the
system.
 Amity School of Engineering & Technology

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.
 Amity School of Engineering & Technology

[Link] Exclusion:- The mutual-exclusion

condition must hold for nonsharable
resources. For example, a printer cannot be
simultaneously shared by several
processes. Sharable resources, in contrast,
do not require mutually exclusive access
and thus cannot be involved in a deadlock.
we cannot prevent deadlocks by denying the
mutual-exclusion condition, because some
resources are intrinsically nonsharable.
 Amity School of Engineering & Technology

[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 can be used
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, however, it must release all the
resources that it is currently allocated.
 Amity School of Engineering & Technology

• Both these protocols have two main

disadvantages. First, resource utilization
may be low, since resources may be
allocated but unused for a long period.
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.
 Amity School of Engineering & Technology

[Link] Preemption:- The third necessary

condition for deadlocks is that there be no
preemption 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.
 Amity School of Engineering & Technology

[Link] 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.
 Amity School of Engineering & Technology

Deadlock Avoidance
 Amity School of Engineering & Technology

Banker’s Algorithm in Operating

System
The banker’s algorithm is a resource
allocation and deadlock avoidance
algorithm that tests for safety by simulating
the allocation for predetermined maximum
possible amounts of all resources, then
makes an “s-state” check to test for possible
activities, before deciding whether allocation
should be allowed to continue.
 Amity School of Engineering & Technology

Following Data structures are used to

implement the Banker’s Algorithm:
• Let ‘n’ be the number of processes in the
system and ‘m’ be the number of resources
types.
• Available :
• It is a 1-d array of size ‘m’ indicating the
number of available resources of each type.
• Available[ j ] = k means there
are ‘k’ instances of resource type Rj
 Amity School of Engineering & Technology

Max :
• It is a 2-d array of size ‘n*m’ that defines the
maximum demand of each process in a
system.
• Max[ i, j ] = k means process Pi may request
at most ‘k’ instances of resource type Rj.
Allocation :
• It is a 2-d array of size ‘n*m’ that defines the
number of resources of each type currently
allocated to each process.
• Allocation[ i, j ] = k means process Pi is
currently allocated ‘k’ instances of resource
type Rj
 Amity School of Engineering & Technology

Need :
• It is a 2-d array of size ‘n*m’ that
indicates the remaining resource need of
each process.
• Need [ i, j ] = k means
process Pi currently need ‘k’ instances of
resource type Rj
• for its execution.
• Need [ i, j ] = Max [ i, j ] – Allocation [
i, j ]
 Amity School of Engineering & Technology
Banker’s algorithm consists of Safety
algorithm and Resource request algorithm
Safety Algorithm
The algorithm for finding out whether or not a system is in a
safe state can be described as follows:
• 1) Let Work and Finish be vectors of length ‘m’ and ‘n’
respectively.
Initialize: Work = Available
Finish[i] = false; for i=1, 2, 3, 4….n
• 2) Find an i such that both
a) Finish[i] == false
b) Needi <= Work
if no such i exists goto step (4)
• 3) Work = Work + Allocation[i]
Finish[i] = true
goto step (2)
• 4) if Finish [i] == true for all i
then the system is in a safe state
 Amity School of Engineering & Technology

Resource-Request Algorithm
• Let Requesti be the request array for
process Pi. Requesti [j] = k means process
Pi wants k instances of resource type Rj.
When a request for resources is made by
process Pi, the following actions are taken:
 Amity School of Engineering & Technology

• 1) If Requesti <= Needi

Goto step (2) ; otherwise, raise an error
condition, since the process has exceeded its
maximum claim.
• 2) If Requesti <= Available
Goto 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:
Available = Available – Requesti
Allocationi = Allocationi + Requesti
Needi = Needi– Requesti
 Amity School of Engineering & Technology

If the resulting resource-allocation state is

safe, the transaction is completed, and
process P; is allocated its resources.
However, if the new state is unsafe, then P;
must wait for Request;, and the old
resource-allocation state is restored.
 Amity School of Engineering & Technology

• Considering a system with five

processes P0 through P4 and three
resources of type A, B, C. Resource
type A has 10 instances, B has 5
instances and type C has 7 instances.
Suppose at time t0 following snapshot
of the system has been taken:
Amity School of Engineering & Technology
 Amity School of Engineering & Technology

Question1. What will be the content of

the Need matrix?
Amity School of Engineering & Technology
 Amity School of Engineering & Technology

Question2. Is the system in a safe

state? If Yes, then what is the safe
sequence?
 Amity School of Engineering & Technology

The safe sequence is:-

P1,P3,P4,P0,P2
 Amity School of Engineering & Technology

Question3. What will happen if

process P1 requests one additional
instance of resource type A and two
instances of resource type C?
 Amity School of Engineering & Technology

The safe sequence is:-

P1,P3,P4,P0,P2

Hence the new system state is safe, so we

can immediately grant the request for
process P1
 Amity School of Engineering & Technology

Q. In the following state, determine if it

is currently deadlocked
 Amity School of Engineering & Technology

• Problem-01:

A single processor system has three resource types X, Y and

Z, which are shared by three processes. There are 5 units of
each resource type. Consider the following scenario, where
the column alloc denotes the number of units of each
resource type allocated to each process, and the column
request denotes the number of units of each resource type
requested by a process in order to complete execution. Which
of these processes will finish LAST?
(1)P0
(2)P1
(3) P2
(4)None of the above since the system is in a deadlock
Amity School of Engineering & Technology
 Amity School of Engineering & Technology

• According to question-
Total = [ X Y Z ] = [ 5 5 5 ]
Total _Alloc = [ X Y Z ] = [5 4 3]

Now,
• Available = Total – Total_Alloc
= [ 5 5 5 ] – [5 4 3]
=[012]
Amity School of Engineering & Technology
Amity School of Engineering & Technology
Amity School of Engineering & Technology
 Amity School of Engineering & Technology

• Problem-02:
An operating system uses the banker’s algorithm
for deadlock avoidance when managing the
allocation of three resource types X, Y and Z to
three processes P0, P1 and P2. The table given
below presents the current system state. Here, the
Allocation matrix shows the current number of
resources of each type allocated to each process
and the Max matrix shows the maximum number
of resources of each type required by each
process during its execution.
Amity School of Engineering & Technology
Amity School of Engineering & Technology
 Amity School of Engineering & Technology

Answer
• X=2
 Amity School of Engineering & Technology

Deadlock Detection and

Recovery
In this approach, The OS doesn't apply any
mechanism to avoid or prevent the deadlocks.
Therefore the system considers that the
deadlock will definitely occur. In order to get
rid of deadlocks, The OS periodically checks the
system for any deadlock. In case, it finds any of
the deadlock then the OS will recover the
system using some recovery techniques.
 Amity School of Engineering & Technology

The main task of the OS is detecting the

deadlocks. The OS can detect the deadlocks with
the help of Resource allocation graph.
 Amity School of Engineering & Technology

In single instanced resource types, if a cycle is being

formed in the system then there will definitely be a
deadlock. On the other hand, in multiple instanced
resource type graph, detecting a cycle is not just
enough. We have to apply the safety algorithm on
the system by converting the resource allocation
graph into the allocation matrix and request matrix.
 Amity School of Engineering & Technology

To recover the system from deadlocks, either OS

considers resources or processes.
 Amity School of Engineering & Technology

For Resource
Preempt the resource
We can snatch one of the resources from the owner of
the resource (process) and give it to the other process
with the expectation that it will complete the execution
and will release this resource sooner.
Rollback to a safe state
• System passes through various states to get into the
deadlock state. The operating system can rollback the
system to the previous safe state. For this purpose, OS
needs to implement check pointing at every state.
• The moment, we get into deadlock, we will rollback all
the allocations to get into the previous safe state.
 Amity School of Engineering & Technology

For Process
Kill a process
Killing a process can solve our problem but the bigger
concern is to decide which process to kill. Generally,
Operating system kills a process which has done least
amount of work until now.
Kill all process
This is not a suggestible approach but can be implemented
if the problem becomes very serious. Killing all process will
lead to inefficiency in the system because all the processes
will execute again from starting.