Course No.

CSSE - 601

Distributed System
 Course No. CSSE - 601

Distributed Deadlock
Detection
Objective
•Introduction •Deadlock Avoidance
•Resource vs. Communication •Deadlock Detection and
Deadlocks Recovery
•A Graph-Theoretic Model •Control Organizations
•Resource Allocation Graph •Centralized
•Wait-For Graph Deadlock-Detection
•Deadlock handling strategies in •Distributed Deadlock
DS Detection Algorithms
•Deadlock Prevention •Algorithms Unleashed
Perspectives
Introduction
•In distributed systems, a process can request and release
resources (local or remote) in any order, which may not be
known a priority and a process can request some resources
while holding others
• If the sequence of the allocation of resources to processes is
not controlled in such environments, deadlocks can occur.
•The problem of deadlocks has been generally studied in
distributed systems under the following model:
• The systems have only reusable resources.
• Processes are allowed only exclusive access to resources.
• There is only one copy of each resource.
 Introduction
• A process can be in two states:
• running or blocked
• In the running state (also called the active state), a process has all the
needed resources and is either executing or is ready for execution.
• In the blocked state, a process is waiting to acquire some resources.
• Deadlock is a situation in which a set of processes is blocked waiting for
other process in the set to release the resource
• Following conditions should hold simultaneously for deadlock to occur:
1. Mutual Exclusion 2. No preemption
3. Hold and wait 4. Circular Wait
 DDD: Resource vs. Communication
Deadlocks
• Two types of deadlocks have been discussed:
• Resource deadlock
• Processes can simultaneously wait for several resources and cannot proceed until
they have acquired all those resources
• A set of processes is resource-deadlock if each process in the set requests resources
held by another process in the set and it must receive all of the requested resources
before it can become unblocked
• Communication deadlock
• Processes wait to communicate with other processes among a set of processes
• A waiting process can unblock on receiving a communication from any one of these
processes
• A set of processes is communication deadlocked if each process in the set is waiting
to communicate with another process in the set and no process in the set ever
initiates any further communication until it receives the communication for which it is
waiting
 DDD: A Graph-Theoretic Model
• The state of process-resource interaction in distributed systems can be
modeled by a bi-partite directed graph called a resource allocation graph.
• The nodes of this graph are processes and resources of a system, and the
edges of the graph depict assignments or pending requests.
• A pending request is represented by a request edge directed from the node
of a requesting process to the node of the requested resource.
• A resource assignment is represented by an assignment edge directed from
the node of an assigned resource to the node of the assigned process.
• A system is deadlocked if its resource allocation graph contains a directed
cycle or a knot.
DDD: Resource Allocation Graph

P1
R1 R4

P4 P2 Assignment Edge

Request Edge
R2 P3 R3
DDD: Wait-For Graph
•Wait-For Graphs:
• In distributed systems, the system state can be
modeled or represented by a directed graph, called a
wait-for graph (WFG)
•In a WFG, nodes are processes and there is a directed
edge from node P1 to node P2 if P1 is blocked and is
waiting for P2 to release some resource
•A system is deadlocked if and only if there is a directed
cycle or not (depending upon the underlying model) in
the WFG
DDD: Wait-For Graph

P1 P2

P4 P3
DDD: Deadlock handling strategies in DS
•There are three strategies to handle deadlock
•Deadlock Prevention
•Deadlock Avoidance
•Deadlock Detection and Recovery
•Deadlock handling is complicated to implement in
DS because no one site has accurate knowledge of
the current state of the system and because every
inter-site communication involves a finite and
unpredictable delay
 DDD: Deadlock Prevention
• Deadlock can be prevented in a DS through following approaches:
• Deadlock can be prevented in a DS through linear ordering of the resources, simple to implement with
less overhead.
• Can be achieved either by having a process acquired all the needed resources simultaneously before it
begins execution or by preempting a process that holds the needed resources.
• Can use time-stamping and priority with resource preemption.
• To control the preemption each process is assigned a unique priority.
• These values are used to decide whether a process will wait for Pj if Pi has a priority higher than Pj,
otherwise Pi is rolled back.
• It prevents deadlock because for any edge Pi-> Pj, in the wait-for-graph, Pi has a higher priority then Pj,
then a cycle can’t exist
• Low priority process will always be rolled back
• It can be avoided by the use of timestamps, two schemes can be used as following:
• The Wait-Die Scheme.
• The Wound-Wait Scheme.
 DDD: Deadlock Avoidance
•A resource is granted to a process if the resulting global state is safe
( a global state includes all the processes and resources of the DS)
•Deadlock is practically impossible to implement because
• Every site has to maintain information on the global state of the system,
which translates into huge storage requirements an extensive
communication costs
• The process of checking for a safe global state must be mutually
exclusive, because if several sites concurrently perform checks for a safe
state they may all find the state safe but the net global state may not be
safe
• Due to the large number of processes and resources it will be
computationally expensive to check for a safe state
DDD: Deadlock Detection and Recovery
•Requires an examination of the status of
process-resource interaction for the presence of
cyclical wait
•Two conditions exist in the DS:
•Once a cycle is formed in the WFG, it persists until its
is detected and broken, and
•Cycle detection can proceed concurrently with the
normal activities of a system
•We’ll study the techniques to detect deadlock in a DS
instead of trying to prevent or avoid it
 DDD: Deadlock Detection and Recovery
• Deadlock detection and resolution entails addressing two basic issues:
• First, detection of existing deadlocks and
• Second resolution of detected deadlocks.
• The detection of deadlocks involves two Issues:
• Maintenance of the WFG and
• Search of the WFG for the presence of cycles (or knots)
• In distributed systems, a cycle may involve several sites, so the search for
cycles greatly depends upon how the WFG of the system is represented
across the system
• Depending upon the manner in which WFG information is maintained and
the search for cycles is carried out, there are centralized, distributed, and
hierarchical algorithms for deadlock detection in distributed systems.
 DDD: Deadlock Detection and Recovery
•Deadlock resolution involves breaking existing wait-for
dependencies in the system WFG to resolve the deadlock
•It involves rolling back one or more processes that are deadlocked
and assigning their resources to blocked processes in the
deadlock so that they can resume execution
 DDD: Control Organizations
• Centralized Control
• Provided with a control site responsible of constructing WFG
• However, a single point of failure, congested links, continuous message generation for deadlock
detection, are the demerits.
• Distributed Control
• Detection of a global deadlock is shared equally
• Deadlock detection is initiated only when a waiting process is suspected to be a part of deadlock
cycle.
• However, such systems are difficult to design, several sites may initiate detection for the same
deadlock, proof of correctness is difficult, deadlock resolution is cumbersome.
• Hierarchical Control
• Site detects deadlocks involving only its descendent sites
• Exploits access patterns local to a cluster of sites to efficiently detect deadlocks.
• However, the control is defeated if most deadlocks span several clusters.
 Centralized Deadlock-Detection
•The Completely Centralized Algorithm:
•A designated site called the Control Site is provided which maintains
the WFG of the entire system
• It checks the WFG for the existence of deadlock cycles whenever a
request edge is added to the WFG.
•Sites request or release through Request and Release message for
all resources, whether local or remote.
•However, it is highly inefficient due to concentration of all messages.
• It imposes larger delays, large communication overhead, and the
congestion of communication links.
• Moreover, the reliability is poor due to single point of failure.
 Centralized Deadlock-Detection
• The Ho-Ramamoorthy Algorithms:
• Two proposals to resolve the problems in Centralized algorithm
• The Two-Phase Algorithm
• Every site maintains a status table containing status of all the processes initiated at that site.
• A designated site requests the status table from all sites, periodically.
• Two received reports are matched and a WFG is generated based on the differences.
• The drawback is it may report a false deadlock.
• The One-Phase Algorithm
• It request one status report from each site, however, each site maintains two status table, i.e. resource &
process.
• Resource table keeps track of transactions, whereas the process table keeps track of resources locked.
• Periodically, a designated site requests both the tables from every site, constructs a WFG using the
information provided by both tables.
• If no cycle is found, then the system is not deadlocked.
 Distributed Deadlock Detection Algorithms
• All sites collectively cooperate to detect a cycle in the state graph that is
likely to be distributed over several sites of the system.
• The algorithm can be initiated whenever a process is forced to wait.
• The algorithm can be initiated either by the local site of the process or
by the site where the process waits.
• These algorithm can be divided into four classes,
• Path-pushing algorithm
• Edge-chasing algorithm
• Diffusion computation algorithm
• Global state detection algorithm
 Distributed Deadlock Detection Algorithms
Edge-Chasing Algorithm
• If Pi is locally dependent on itself then • then
declare deadlock
• begin
• Else for all Pj and Pk such that Pi is locally
• dependentk(i)=true;
dependent upon Pj, and Pj is waiting on Pk,
and Pj and Pk are on different sites, • if k=I then declare that Pi is deadlocked
• Send probe(i,j,k) to the home site of Pk • else for all Pm and Pn such that Pk is locally
dependent upon Pm, and Pm is waiting on
• On receipt of probe(i,j,k), the site takes the
Pn and Pm and Pn are on different sites,
following actions:
• send probe(i,m,n) to the home sites of Pn
• If Pk is blocked, and dependentk(i) is false,
and Pk has not replied to all requests of Pj • end
 Distributed Deadlock Detection Algorithms
• Example:
P
2

P
P
3
1

Site-1 P
P
4
9
P P
8 6 P
P 5

10
P

Site-3 7
Site-2
 Distributed Deadlock Detection Algorithms
• Example:
P
2

P
P
3
1

Site-1 P
P
4
9
P P
8 6 P
P 5

10
P

Site-3 7
Site-2
 Distributed Deadlock Detection Algorithms
• Example:
, 2 ) P
1,1
e(
2

rob
P
P
P
3
1

Site-1 P
P
4
9
P P
8 6 P
P 5

10
P

Site-3 7
Site-2
 Distributed Deadlock Detection Algorithms
• Example: Pr
ob
,2)
P
e(
1,1 1,2
e(
2
,3)
rob
P
P
P
3
1

Site-1 P
P
4
9
P P
8 6 P
P 5

10
P

Site-3 7
Site-2
 Distributed Deadlock Detection Algorithms
• Example: Pr
ob
,2)
P
e(
1,1 1,2
e(
2
,3)
rob
P
P
P
Prob
1
3
e (1
,3,4)

Site-1 P
P
4
9
P P
8 6 P
P 5

10
P

Site-3 7
Site-2
 Distributed Deadlock Detection Algorithms
• Example: Pr
ob
,2)
P
e(
1,1 1,2
e(
2
,3)
rob
P
P
P
Prob
1
3
e (1
,3,4)

Site-1 P Pr
ob
P e(
4
1,4
9
P
,5)
P
8 6 P
P 5

10
P

Site-3 7
Site-2
 Distributed Deadlock Detection Algorithms
• Example: Pr
ob
,2)
P
e(
1,1 1,2
e(
2
,3)
rob
P
P
P
Prob
1
3
e (1
,3,4)

Site-1 P Pr
ob
P e(
4
1,4
9
P
,5)
P
6 P
8 Probe (1,5,6)
P 5

10
1 ,5,7)
P b e (
Pro
Site-3 7
Site-2
 Distributed Deadlock Detection Algorithms
• Example: Pr
ob
,2)
P
e(
1,1 1,2
e(
2
,3)
rob
P
P
P
Prob
1
3
e (1
,3,4)

Site-1 P Pr
ob
P e(
4
1,4
9
P
,5)
P
8 Probe (1,6,8) 6
Probe (1,5,6) P
P 5

10
1 ,5,7)
P b e (
Probe (1,7,10) Pro
Site-3 7
Site-2
 Distributed Deadlock Detection Algorithms
• Example: Pr
ob
,2)
P
e(
1,1 1,2
e(
2
,3)
rob
P
P
P
Prob
1
3
e (1
,3,4)

Site-1 P Pr
ob
P e(
4
1,4
9
P
,5)
Prob P
e (1,
8,9) 8 Probe (1,6,8) 6
Probe (1,5,6) P
P 5

10
1 ,5,7)
P b e (
Probe (1,7,10) Pro
Site-3 7
Site-2
 Distributed Deadlock Detection Algorithms
• Example: Pr
ob
,2)
P
e(
1,1 1,2
e(
2
,3)
rob
P
P
P
Prob
1 , 9 ,1) 1
3
e (1
,3,4)
be (
Pro
Site-1 P Pr
ob
P e(
4
1,4
9
P
,5)
Prob P
e (1,
8,9) 8 Probe (1,6,8) 6
Probe (1,5,6) P
P 5

10
1 ,5,7)
P b e (
Probe (1,7,10) Pro
Site-3 7
Site-2
 Hierarchical Deadlock Detection Algorithm
• In hierarchical deadlock detection algorithms, sites are arranged in a
hierarchical fashion, and a site detects deadlocks involving only its
descendant sites
• Hierarchical algorithms exploit access patterns local to a cluster of sites to
efficiently detect deadlocks
• However, hierarchical deadlock detection algorithms require special care
while arranging the sites in a hierarchy
• For efficiency, most deadlocks should be localized to as few clusters as
possible - the objective of hierarchical control is defeated if most deadlocks
span several clusters
• These algorithms can be divided into two classes,
• The Menasce-Muntz Algorithm
• The Ho-Ramamoorthy Algorithm
 Hierarchical Deadlock Detection Algorithm
• The Ho-Ramamoorth Algorithm:
• Sites are grouped into several disjoint clusters.
• Periodically, a site is chosen as a central control site, which dynamically
chooses a control site for each cluster.
• The central control site requests from every control site their intercluster
transaction status information and wait-for relation.
• A control site collects status tables from all the site in its cluster and applies
the one-phase deadlock detection algorithm.
• It then sends status information and wait-for relation to the central control
site.
• Finally, the central site constructs a system WFG and searches it for cycles.
Hierarchical Deadlock Detection Algorithm
Control Site

Central Site

Control Site Control Site

 Algorithms Unleashed Perspectives
• Theory of Correctness
• A formal proof of the correctness is nontrivial
• TWF graph and deadlock cycles can form in innumerable ways and it is difficult to imagine
• Deadlock is very sensitive to the timing of requests
• Message delays are unpredictable
• Performance
• The number of messages exchanges may not be the true indicator as it varies in algorithms
• The persistence of deadlocks results in wasteful utilization of resources, therefore, the average
time a deadlock persist can be an important measure
• Other measures include, storage overhead, processing overhead, resource holding time, etc.
• Deadlock Resolution
• A deadlock is resolved by aborting at least one process and granting the released resources to
other processes.
 Thanks
Email: [email protected]