Pimpri Chinchwad Education Trust’s

Pimpri Chinchwad College of Engineering, Pune

BCE6414: Operating Systems

Unit-4
Deadlocks

Mrs. Bodireddy Mahalakshmi

Ph.D. (Scholar), M. E. (Computer Engineering)
Assistant Professor, Department of Computer Engineering,
Pimpri Chinchwad College of Engineering, Pune
• Every process in a set of processes is waiting for an event that can
be caused only by another process in the set.

• A set of blocked processes each holding a resource and waiting to

acquire a resource held by another process in the set

• When two trains approach each other at a crossing, both shall come
to a full stop and neither shall start up again until the other has gone.
 System Model
● System consists of resources
● 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:
− Must request before use
− Use it
− Must release after using
Four necessary conditions should hold simultaneously

• Mutual exclusion
• Hold and wait
• No pre-emption
• Circular wait

•Resource allocation
graph
Resource-Allocation Graph
• RAG is a DIRECTED graph G= {V, E}
• V has two types: Process and Resource nodes
• 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 Pi → Rj
• Assignment edge Rj → Pi
• Sets of P, R and E
• Resource instances
• Process states
 Resource-Allocation Graph (Cont.)
● Process

● Resource Type with 4 instances

Pi
● Pi requests instance of Rj Rj

Pi
● Pi is holding an instance of Rj Rj
RAG RAG with cycle
and deadlock RAG with cycle but
NO deadlock
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
1. Ignore and pretend that deadlock will never occur
2. Prevent or avoid so that system will never enter deadlock
3. Let system enter deadlock, detect and recover

Deadlock prevention - ensures that at least one of the

necessary conditions cannot hold
Deadlock avoidance gives OS additional information in
advance for the required resources during the lifetime of the
process.
Mutual exclusion
• must hold for non-sharable resources
• not required for sharable resources (e.g., read-only files);

Hold and wait

• Release all resources before requesting new no hold
Process should request all required resources before starting execution
Process is allocated a resource when it has none

•Disadv:
• Low resource utilization
• Starvation
No Preemption

1. Preempt currently held resources, if the requested resource is not

available -> add into resource pool -> process gets resources only when
old as well as requested resource are available
2. A. Check availability of requested resources(Rx) , if yes allocate

B. if not, check if it is allocate to other process, which is waiting for

resources. If yes, pre-empt required Rx allocate to requesting process.

C. If Rx not available not held by waiting process, requesting process

goes in waiting state.
Circular wait

• First three option are impractical

• Practicalsolution invalidate this condition
1. Impose total Ordering on resource types
2. Request in increasing order
• Requires additional information
• P needs R1 and R2; Q needs R2 and then R1.
• Simplest method: each process to declare maximum no. of required
resources.
• Algorithm dynamically check resource-allocate state to ensure that
circular-wait condition never occurs
• Safe State:
System can allocate resources to each process in some order and still
avoid a deadlock.
• A system is in a safe state only if there exists a safe sequence.
• There exists a sequence <P1, P2, …, Pn> of ALL the processes in the system
such that 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.
Example: Consider a system with twelve magnetic tape drives and three processes: P1 , P2 , and P3

Proce Max Allocated Current

ss requireme resources require
nt ment
P1 10 5 5
P2 4 2 2
P3 9 2 7

• Safe sequence = <P2, P1, P3>

 •So , avoidance just requires to ensure that system is in
safe state.

•Two variants of avoidance algorithm

1. System with only one instance of each resource type
RAG
2. Multiple instances of each resource type Banker’s
algorithm
• Request edge Pi → Rj
• Assignment edge Rj → Pi
• Claim edge Pi → Rj
• process Pi may request resource Rj; represented by a dashed line
• Claim edge converts to request edge when a process 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
To avoid deadlock

• Resources must be claimed a priori in the system

• Request for a resource 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
- No cycle : safe state
- Cycle : unsafe state => let process wait
BANKER’S ALGORITHM
• For multiple instances of resource types
• Less efficient than RAG
• Bank should never allocate its available cash in way that needs of all
customers are not satisfied.
1. A new process enters system with list of required resources
2. Number should not increase the maximum number of resources
3. System determines whether allocation leads to safe state
4. If yes, allocate resources
5. If not, let process wait for resources to be freed
Required data structures: (n - processes; m resource types)
• 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]
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 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
• Let Requesti be the 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; else error.
2. If Requesti ≤ Available, go to step 3; else Pi must wait
3. Pretend to allocate requested resources to Pi by modifying the state as follows:
Available = Available Request;
Allocationi = Allocationi + Requesti;
Needi = Needi Requesti;
If resultant allocation state is
● safe ⇒ the resources are allocated to Pi
● unsafe ⇒ Pi must wait, and the old resource-allocation state is restored
• Five process P0 to P4; Three resource types A= 10 , B =5 and C = 7
instances

• Current state
Process Allocation Max Available
A B C A B C A B C
P0 0 1 0 7 5 3 3 3 2
P1 2 0 0 3 2 2
P2 3 0 2 9 0 2
P3 2 1
PRAVIN S.
1 2 2 2
P4 0GAME 0 2 4 3 3

• Let’s find Need matrix; Need = Max - Allocation

Process Need
• Is this system in safe state?
A B C
P0 7 4 3 • Assume P1, submits additional Request1(1,0,2)
P1 1 2 2 • Step 1 - If Requesti ≤ Needi go to step 2 : (1,0,2) ≤ (1,2,2)
P2 6 0 0 ?
P3 0 1 1
• Step 2 - if Requesti ≤ Available, go to step 3 : (1,0,2) ≤
P4 4 3 1
(3,2,2) ?

• Step 3 Pretend allocation

 Allocatio NeedAvailabl
n e
ABC ABC ABC
P0 0 1 0 743 230
P1 3 0 2 020
P2 3 0 2 600
P3 2 1 1 011
P4 0 0 2 431
• Now check whether system is in safe state?
 DEADLOCK DETECTION

Allow the system to enter into a

deadlock, detect and recover
• RAG converted to wait-for graph
• Remove the resource nodes and collapse the appropriate edges

• Check for cycle

• If exists,
deadlock
 Exercises
Construct wait for graph and detect whether the system is in deadlock?

RAG -1 RAG -2
• Available : A vector of length m

• Allocation: An n x m matrix
• Request: An n x m matrix indicates the current request of
each process. If Request [i][j] = k, then process Pi is requesting k
more instances of resource type.Rj.
1. Let Work and Finish be vectors of length m and n, respectively
Initialize:
(a) Work = Available
(b) For i = 1,2, …, n, if Allocationi ≠ 0, then
Finish[i] = false; otherwise, Finish[i] = true

2. Find an index i such that both:

(a) Finish[i] == false
(b) Requesti ≤ 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] == false, for some i, 1 ≤ i ≤ n, then the

system is in deadlock state. Moreover, if Finish[i] ==
false, then Pi is deadlocked

Algorithm requires an order of O(m x n2) operations to detect

whether the system is in deadlocked state
•Abort all deadlocked processes
•Abort one process at a time until the deadlock cycle is eliminated
•Order of abort….
• Priority of the process
• How long process has computed, and how much longer to completion
• Resources the process has used
• Resources process needs to complete
• How many processes will need to be terminated
• Is process interactive or batch?
•Selecting a victim: minimize cost

•Rollback: return to some safe state, restart process for

that state

•Starvation : same process may picked always as victim,

include number of rollback in cost factor
• Silberschatz, Galvin, Gagne, "Operating System Principles", 10th
Edition

• Stallings W., "Operating Systems- internals and design principles", 9th

Edition.

• Deitel, Deitel, Choffnes, “Operating System”, 3rd edition, Pearson

• Andrew S. Tanenbaum; Modern Operating Systems; Prentice Hall
of India Publication; 4th Edition