UNIT – 2

Deadlocks

❖Deadlocks
● System Model
● Deadlock Characterization
● Methods for Handling Deadlocks
● Deadlock Prevention
● Deadlock Detection, and Avoidance
● Recovery from Deadlock

System Model
● System consists of resources
● Resource types R1, R2, . . ., Rm
They are CPU cycles, memory space, I/O
Devices
● Each resource type Ri has Wi instances
For i = 1, 2, …, n
● Each process utilizes a resource as follows:
❖ Request
❖ Use
❖ Release

❖ 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, …, Pn} 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
● Pn is waiting for a resource that is held by P0

❖Deadlock with Mutex Locks

Mutual Exclusion

● At least one resource must be held in a non�sharable mode

● Only one process at a time can use the resource

Resource-Allocation Graph ( RAG )

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 Pi <- Rj
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

Methods for Handling Deadlocks

1) Ensure that the system will never enter a

deadlock state:
● Deadlock Prevention
● Deadlock Avoidance
2) Allow the system to enter a deadlock state and
then Recover

Deadlock Prevention Method

Mutual Exclusion
Not required for sharable resources (e.g., read-only
files);

Must hold for non-sharable resources

Hold and Wait
Must guarantee that whenever a process
requests a resource, it does not hold any other
Resources

Process to request and be allocated all its

resources before it begins execution

Allow process to request resources only when the

process has none allocated to it

Low resource utilization; starvation possible

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

Circular Wait

Impose a total ordering of all resource types

Require that each process requests resources in

an increasing order of enumeration
Deadlock Avoidance Methods

➔ Requires that the system has some additional priori

information

● Requires that each process declare the maximum number of

resources of each type that it may need
● The deadlock-avoidance algorithm dynamically examines the
resource-allocation state to ensure that there can never be a
circular-wait condition
● Resource-allocation state is defined by the number
of available and allocated resources, and the
maximum demands of the processes

Safe State

● When a process requests an available resource,

system must decide if immediate allocation leaves the
system in a safe state

● System is in safe state if there exists a sequence

<P1, P2, …, Pn> of ALL the processes in the systems.

● For each Pi, the resources that Pi can still request can
be satisfied by

currently available resources + resources held by all the Pj, with j < i
 ● If Pi resource needs are not immediately
available, then Pi can wait until all Pj have
finished

● When Pj is finished, Pi can obtain needed

resources, execute, return allocated resources,
and terminate

● When Pi terminates, Pi + 1 can obtain its needed

resources, and so on

Basic Facts
● If a system is in safe state no deadlocks

● If a system is in unsafe state possibility of deadlock

➔ Avoidance => ensure that a system will never enter an

unsafe state.

Safe, Unsafe, and Deadlock States

Deadlock Avoidance Algorithms

● Single instance of a resource type
➔ Use a Resource-Allocation Graph

● Multiple instances of a resource type

➔ Use the Banker’s Algorithm
Resource-Allocation Graph (Arrorw marks )

● Claim edge Pi Rj indicated that process Pi may

request resource Rj; represented by a dashed line

● Claim edge converts to request edge when a process

confirm to requests a resource

● Request edge converted to an assignment edge when

the resource is allocated to the process

● When a resource is released by a process, assignment

edge reconverts to a claim edge

● Resources must be claimed a priori in the system

Resource-Allocation Graph
Unsafe State In Resource-Allocation Graph

Resource-Allocation Graph Algorithm

Suppose that process Pi requests a resource Rj

The request can be granted only if converting the

request edge to an assignment edge does not
result in the formation of a cycle in the resource
allocation graph

Banker’s Algorithm

● Multiple instances of Resource

● Each process must a priori claim maximum use

● When a process requests a resource it may have to

wait

When a process gets all its resources; it must return them in a finite
amount of time
Data Structures for the Banker’s Algorithm
Let n = number of processes
m = number of resources types
For i,j = 1,2,...,n
Available: Vector of length m. If Available[j] = k, there are k
instances of resource type Rj available

Max: n x m matrix. If Max[i, j] = k, then process Pi may

request at most k instances of resource type Rj

Allocation: n x m matrix. If Allocation[i, j] = k then Pi is

currently allocated k instances of Rj

Need: n x m matrix. If Need[i, j] = k, then Pi may need k

more instances of Rj to complete its task
Need[i, j] = Max[i, j] – Allocation[i, j]

Safety Algorithm
1. Let Work and Finish be vectors of length m and n,
respectively. Initialize:
Work = Available
Finish [i] = false for i = 0, 1, …, n - 1

2. Find an i such that

(a) Finish [i] == false && 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
Resource-Request Algorithm for Process Pi

Requesti = request vector for process Pi

.
If Requesti [j] = k then process Pi wants k instances of
resource type Rj

1. If Requesti <= Needi go to step 2. Otherwise, raise error

condition, since process has exceeded its maximum claim

2. If Requesti <= Available, go to step 3. Otherwise Pi must

wait, since resources are not available

3. Allocate requested resources to Pi by modifying the state as

follows:

Available = Available – Requesti;

Allocationi = Allocationi + Requesti;

Needi = Needi – Requesti;

If safe the resources are allocated to Pi

If unsafe P must wait, and the old resource-allocation

state is restored
Example of Banker’s Algorithm

5 processes P1 – P5;

3 resource types: A (10 instances),

B (5 instances), and C (7 instances)
Snapshot at time T0
:
Allocation Max Available
ABC ABC ABC
P1 0 1 0 753 332
P2 2 0 0 322
P3 3 0 2 902
P4 2 1 1 222
P5 0 0 2 433
Determine the System is Safe State or NOT.

Context of the Need Matrix

Step 0: Determine the matrix Need

Need = Max – Allocation

Need
ABC
P1 7 4 3
P2 1 2 2
P3 6 0 0
P4 0 1 1
P5 4 3 1
Banker’s Algorithm
Available Resources of A, B and C are 3, 3, and 2.
Check if each type of resource request is available for each process.

Step 1: For Process P1:

Need <= Available
7, 4, 3 <= 3, 3, 2 condition is false.
Examine another process, P2.

Step 2: For Process P2:

Need <= Available
1, 2, 2 <= 3, 3, 2 condition true
P2 Works now completed, it released all Resources
Available = Available + Allocation
(3, 3, 2) + (2, 0, 0) => 5, 3, 2 ( cur. Avail + cur. Alloc )
Examine another process P3.

Step 3: For Process P3:

Need <= Available
6, 0, 0 < = 5, 3, 2 condition is false.
Examine another process, P4.

Step 4: For Process P4:

Need <= Available
0, 1, 1 <= 5, 3, 2 condition is true
P4 Works now completed, it released all Resources
Available = Available + Allocation
5, 3, 2 + 2, 1, 1 => 7, 4, 3 ( cur. Avail + cur. Alloc )
Similarly, we examine another process P5.

Step 5: For Process P5:

Need <= Available
4, 3, 1 <= 7, 4, 3 condition is true
P5 Works now completed, it released all Resources
Available = Available + Allocation
7, 4, 3 + 0, 0, 2 => 7, 4, 5 ( cur. Avail + cur. Alloc )
 Examine resource request for processes P1 and P3.

Step 6: For Process P1:

Need <= Available
7, 4, 3 <= 7, 4, 5 condition is true
P1 Works now completed, it released all Resources
Available = Available + Allocation
7, 4, 5 + 0, 1, 0 => 7, 5, 5 ( cur. Avail + cur. Alloc )
Examine another process P3

Step 7: For Process P3:

Need <= Available
6, 0, 0 <= 7, 5, 5 condition is true
P3 Works now completed, it released all Resources
Available = Available + Allocation
7, 5, 5 + 3, 0, 2 => 10, 5, 7 ( cur. Avail + cur. Alloc )

The system is in a safe state since the sequence

< P2, P4, P5, P1, P3> satisfies safety criteria

What will happen if the resource request (1, 0, 0) for process P1

can the system accept this request immediately?

For granting the Request (1, 0, 2),

Check that Request <= Available,
(1, 0, 2) <= (3, 3, 2), condition is true

So the process P1 gets the request immediately.