My Ssec Capstone Project A SURVEY OF DEADLOCK HANDLING STRATEGIES Anupa Ann Jacob Dept

A SURVEY OF DEADLOCK HANDLING STRATEGIES Anupa Ann Jacob Dept

A SURVEY OF DEADLOCK HANDLING
STRATEGIES
Anupa Ann Jacob Dept. of CSISBITS Pilani
Pilani, India
[email protected] Nisha Merin Jacob
Dept. of CSISBITS Pilani
Pilani, India
[email protected] Prof. Amit Dua
Dept. of CSIS BITS Pilani
Pilani, India
[email protected]
Abstract —Deadlock refers to a specic condition when two or
more processes are each waiting for another to release a resource,
or more than two processes are waiting for resources in a circular
chain. Various algorithms and strategies have been proposed
for deadlock prevention, avoidance and detection/resolution in
ordinary centralized operating systems. In distributed systems,
deadlock prevention/avoidance is impractical due to the associ-
ated costs and deadlock detection is difcult due to the absence
of shared memory and the inherent delay in communication. We
attempt to study numerous deadlock detection and avoidance
strategies provided by different authors and compare these. Index Terms —deadlock detection, deadlock detection schedul-
ing, deadlock resolution, distributed systems, livelock
I. IN T RO D U C T I O N
In their paper 1 Protocols for deadlock detection in
distributed database systems, Ho and Ramamoorthy presents
three deadlock detection protocols – one phase, two phase and
hierarchical approaches. It is difcult to obtain a consistent
view of the system due to inherent communication delay and
therefore the two phase approach is prone to false deadlocks.
In hierarchical approach, the compute sites are divided into
clusters and pre – processing of status reports is done by
control site of each cluster which reduces the communication
overhead. Local distributed deadlock detection by cycle detection
and clustering 2 proposes a distributed deadlock detection
algorithm for store and forward communication networks. It
is an enhancement of knot detection algorithm (for static
network) in a dynamic environment. It is capable of detecting
all nodes involved in a deadlock. This is initiated only in case
of a potential deadlock. On deadlock detection in distributed systems 3 is an
attempt to prove that Menasce-Muntz distributed algorithm is
incorrect and suggest possible remedies. A counter example
is provided to prove the incorrectness of the algorithm. The
practicality of the improved algorithm is also discussed. The
paper also discusses various other decentralised protocols like
Goldman and online protocols as well as centralized and
hierarchical protocols like Menasce-Muntz. Two phase deadlock detection algorithm 4 presents an ap-
proach where phase 1 of the algorithm analyses the conditions
of the system of interacting transactions and phase 2 performs
actual cycle detection. Phase 2 is invoked only if phase 1 detects necessary conditions for deadlock in the system. The
cycles in TWF graph is considered as the sufcient condition
for deadlock.
Sufcient condition for a communication deadlock and dis-
tributed deadlock detection 5 is an attempt to provide the suf-
cient condition for deadlock in case of the two most common
system models – resource (AND) model and communication
(OR) model. It also explores in details the various deadlock
handling approaches – continuous, centralized periodical and
hierarchical. The paper suggests a protocol that is insensitive
to phantom deadlocks and process failures.
Performance analysis of distributed deadlock detection al-
gorithms 6 suggests a tree based hierarchical algorithm to
perform a probabilistic study of the performance of deadlock
detection and resolution. Duration of deadlocks, number of
algorithm invocations, mean waiting time of a blocked process
etc. are considered.
On optimal deadlock detection scheduling 7 endeavours
to dene an optimum frequency for deadlock detection taking
into account the overall message overhead, so as to yield the
minimum long run average cost.
Stability and deadlock avoidance in distributed systems for
trafc control 8 describes a distributed trafc control method.
This is an application of deadlock detection in a real-life
situation of rail trafc-ow control, where early detection of
critical conditions is necessary to devise appropriate decisions
and drive routing mechanisms.
Spin detection hardware for improved management of multi-
threaded systems 9 demonstrates the design of a hardware
mechanism to detect spinning and its enhancement to identify
livelocks in a system.
II. ALGORITHMS FOR ANALYSIS
This section contains a brief description of the deadlock
detection algorithms that we have considered for our analysis.
Ho-Ramamoorthy proposes 3 approaches – one phase, two
phase and hierarchical. In the two phase approach, each site
maintains a process status table corresponding to all the
processes initiated at that site. A cycle in the wait-for graph
constructed using the information in these table indicates the
presence of a possible deadlock, and hence, a second round

of status information is collected to create yet another wait-
for graph containing only those transactions involved in the
previously detected cycle. This approach has a tendency to
detect phantom deadlocks. The one phase algorithm requires
the sites to maintain process status table as well as resource
status table. These details are collected at a control site and a
demand graph is constructed using those transactions that have
matching entries in both process and resource status tables.
The hierarchical approach was proposed as an alternative to
the above mentioned centralized approaches as it is costly to
transfer all status information to one site in a large distributed
system. In this approach, the nodes/sites in the system are
divided into clusters and a site is periodically chosen as the
central controller which in turn chooses a control site for
each cluster. Each control site constructs demand graphs for
the cluster sites and detects intra-cluster deadlocks. The inter-
cluster wait-for information is then passed to the central con-
trol site for detection of inter-cluster deadlocks. This concept
can be extended to many levels, to form a hierarchy, which
can greatly reduce the communication overhead. Knot detection algorithm suggested by Cidon, Jaffe and Sidi
2 has two components – one for static environment and its
enhancement for dynamic environments. This algorithm looks
for cycles of clusters and merges them into bigger clusters. A
knot is reported if a cluster with no link directed outside is
found. At the end of the execution of the algorithm, each node
is either FREE (not part of the knot) or DEADLOCKED. In a
dynamic environment, many iterations of the above mentioned
algorithm for static environment is run. A new iteration is ini-
tiated when there is a transition from NOT-FULL to FULL. To
identify different iterations, a non-decreasing iteration number
is attached to every node, where lower iteration numbers are
considered older. Any message with a higher iteration number
will not be processed until the node processes all the messages
of the lower iterations. In Menasce-Muntz algorithm, all the controllers are orga-
nized in a tree fashion. The leaf controllers manage resources
and others are responsible for deadlock detection. Any change
in a controller’s TWF graph due to resource allocation, wait
or release is propagated to its parent controller, who makes
changes in its own TWF graph, searches for cycles and
propagates any changes upward.
Gligor and Shattuck 3 has demonstrated the incorrect-
ness of Menasce-Muntz deadlock detection algorithm and
recommends remedies for the same. To distinguish between
a false deadlock and a real one may require O(n 2
) messages
to be exchanged among n sites. The modied algorithm is
unfeasible due to the implementation complexity arising out
of the condensation of the TWF graph. The protocol proposed by Goldman requires the construc-
tion of an ordered blocked-process list (OBPL) for each invo-
cation of deadlock detection algorithm. This is less vulnerable
to false deadlocks. But, it is restrictive as it prevents a process
from issuing multiple resource requests. The on-line protocol proposed by Isloor and Marsland aims
for timely detection of deadlocks at the site which causes the deadlock. This differs from Menasce-Muntz algorithm in that
it maintains complete transaction (process) – resource graphs
and not just condensed TWF graphs – at every site of the
distributed system. This protocol is incorrect because deadlock
detection is not initiated when a site receives a request to add
an arc to the graph from a different site.
The two phase deadlock detection algorithm proposed by
Elmagarmid and Datta 4 permits multiple outstanding re-
quests and sharing of a resource among multiple transactions
i.e., the relationship between transactions and resources is
many to many. This algorithm runs in two phases, where
the rst phase analyses the set of interacting transactions and
invokes the second phase only if there is a possibility of
deadlock.
Barbara and Zbigniew 5 put forward the sufcient condi-
tion for deadlocks in resource and communication models and
presented a protocol for deadlock detection using query mes-
sages. A cycle is detected when a query message propagates
back to the initiator.
III. CLASSIFICATION OF DEADLOCK DETECTION ALGORITHMS Fig. 1. Classication of deadlock detection algorithms in distributed systems
The algorithms described in the previous section are classi-
ed as follows. Centralized Distributed Hierarchical

We Will Write a Custom Essay Specifically
For You For Only $13.90/page!


order now

Ho-
Ramamoorthy
two-phase
Ho-
Ramamoorthy
one-phase
Goldman
Online protocol
by Marsland-
Isloor
Two phase
algorithm by
Elmagarmid-
Datta
Barbara-
Zbigniew
Ho-
Ramamoorthy
hierarchical
Menasce-Muntz
Knot detection by
Cidon-Jaffe-Sidi

TABLE I
C O M PA R I S O N O F T H E D E A D L O C K D E T E C T I O N A L G O R I T H M S Algorithm Delay No. of
messages No. of
phases Ho-Ramamoorthy two-phase 2nd 4n 2
Ho-Ramamoorthy one-phase nd 2n 1
Goldman nd ;
m.n –
Online protocol by Marsland-Isloor r(n-1) 0 –
Two phase algorithm by Elmagarmid-Datta O(nd) O(n) 2
Barbara-Zbigniew O(nd) O(n) 1
Ho-Ramamoorthy hierarchical (log n)d n(log n) –
Menasce-Muntz nd m(n-1) –
Knot detection by Cidon-Jaffe-Sidi (Static) O(nd) O(n'
2
+m' 2
) 1
Knot detection by Cidon-Jaffe-Sidi (Dynamic) O((nd)
c
) O(n'm') variable
n – total no of nodes
m – no of deadlocked nodes
d – intersite communication delay
r – TWF graph update rate
n' – no. of FULL nodes among n nodes
m' – no. of nodes attached to these n' nodes IV. A PROBABLISTIC APPROACH TO
PERFORMANCE ANALYSIS
A. Algorithm For the analysis, an algorithm is proposed where a tree
structure is considered and the initiator is made the root. Root
sends out probes (ASK) to all its successors. A node receiving
the probe for the rst time becomes the child of the sender
node. The probes are further propagated until it is received by
a node which has already received it or by a node which is
not blocked. The algorithm reports a deadlock when it detects
a back edge. Path strings are used to identify back edges and
SEARCH probes may be used to resolve deadlocks.
B. Performance Analysis Mean deadlock duration is given by,
ET
dur = N
B
X
k = N
d E
T
dur jt
k N
B
N
d+ 1 (1)
Number of algorithm initiations is estimated as,
I = P
B (
e
T
0
+ L
b
X
i =1
n
k
P i
newsucc (1
P
newsucc )L
b
iN
s:i
X
j =0 j P
i;j)
(2)
where,
N d – Average number of deadlocked processes whenever
deadlock occurs in the system
N B – Average number of blocked processes during a deadlock
in the system i.e. includes simply blocked processes as well
as deadlocked processes
ET durjk – Mean deadlock duration for a deadlock formed at
time tk
P B – Probability that a process requesting resources becomes
blocked
T 0 – Time duration for which a blocked process will wait
before initiating the algorithm L
b – Average number of resources a process is waiting for
P newsucc – Probability that a process has one or more new
successors for a blocked request
N s – Average number of new successor for a process per
blocked request
P i.j – Probability that a process with Ns.i successors initiates
the algorithm j times
V. OPTIMAL DEADLOCK DETECTION SCHEDULING
Deadlock detection efciency is not just dependent on
the cost of detection alone, but also on how frequently the
algorithm needs to be invoked. This frequency represents a
trade-off between the costs of detection versus resolution.
Each deadlock acts as a trap which draws more processes into
it, which means that size of the deadlock and consequently
the resolution cost depends on the persistence time of the
deadlock.
The mean average cost of handling a deadlock is,
C(T ) = C
D T
+R
T
0 C
R(
t) dt T
(3)
where is the rate of deadlock formation which follows
a Poisson distribution and 1/T is the frequency of deadlock
detection scheduling. C Ddenotes per deadlock detection cost
and C R(t) is the deadlock resolution cost as a function of
persistence time t.
When the message complexity of deadlock detection is
O(n
) and that of deadlock resolution is O(n
) and 0C(T))
For a distributed deadlock detection whose message com-
plexity is 2n 2
and a distributed deadlock resolution whose mes-
sage complexity is O(n.n D2
(t)), optimal frequency of deadlock
detection scheduling is O(( n)/3). Here, n
D(t) is the deadlock
size at time t.
VI. STABILITY AND DEADLOCK AVOIDANCE
Stability refers to the ability of maintaining equilibrium
conditions when disturbed by changes in the operating condi-
tions. A modication of Banker’s algorithm presents a stable
deadlock avoidance strategy. This requires that all the needed
resources are declared in advance. The main application of
the proposed algorithm is in railway trafc control where
the schedule is known in advance. This is applicable to all
situations where the structure of the system can be mapped
to a network representation and the control problem can be
modelled as a resource allocation problem.
This algorithm makes use of priority based local decision
making to resolve conicts. Internal conicts are said to
occur when a manager receives multiple requests for the
same resource and external conict refer to a situation where
multiple managers compete for the same shared resource.
Internal conicts are resolved by ordering requesting users

based on priorities. A list of requested resources is also
prepared according to this ordering. Then an attempt is made
to satisfy the user requests in an approach similar to Banker’s
algorithm. In case of conicts between competing decision
centers, dynamic priorities are used to decide the winner. The distributed nature along with dynamic priorities among
decision centers allows the algorithm to scale up irrespective
of the network’s extent and can facilitate early detection to
allow real-time control.
VII. LIVELOCK DETECTION USING SPIN DETECTION HARDWARE
Livelocks are similar to deadlocks, except that the live-
locked processes execute continuously without making any
progress. The spin detection hardware can be used to detect
livelocks where the multiple threads spin concurrently waiting
on each other resulting in no effective progress. A thread is said to have been spinning between any two
time instants t aand t
bif and only if,
observable state (registers and memory locations accessed
which also includes the program counter) at instants t a
and t bremains same
any change made by the thread between t
aand t
bis not
observed by any thread outside its processor
Spin detection hardware consists of a 16-entry SDT (Spin
Detection Table) and 64-entry RUB (Register Update Buffer).
RUB is used to track the registers whose values are changed
by the thread in each iteration of a potential spin loop. For
each committed backward control transfer, SDT (at the end of
processor pipeline) is searched for a matching PC (Program
Counter) entry. A match implies a control ow cycle. If not
found, an entry for the PC is made at the top of SDT. A
matching SDT entry for a PC without corresponding RUB
entry indicates spinning. Simultaneous spinning of all threads of a program implies a
livelock. To detect livelocks, the SDT entries may be extended
with time elds so that it can identify simultaneous spinning
of threads. The spinning interval can be calculated from these
time elds and a controller occasionally checks if the intervals
intersect, which point to simultaneous spinning.
VIII. CONCLUSION
Several deadlock detection and avoidance strategies and
algorithms presented by different authors have been studied
in detail and the performance of each has been analysed.
A comparison is provided based on the inferences of this
analysis. We have also considered a probabilistic approach
to performance analysis and made an effort to ponder over
the optimal frequency of deadlock detection scheduling. In
addition, a stable deadlock detection algorithm in a trafc
control scenario and the detection of livelocks using spin
detection hardware were surveyed.
RE F E R E N C E S
1G. S. Ho and C. V. Ramamoorthy, “Protocols for Deadlock Detection in Distributed Database Systems,” IEEE Transactions on Software
Engineering, vol. SE-8, no. 6, November 1982. 2I. Cidon, J. M. Jaffe and M. Sidi, “Local Distributed Deadlock Detection
by Cycle Detection and Clustering,” IEEE Transactions on Software
Eng., vol. SE-13, no. 1, January 1987.
3V. D. Gligor and S. H. Shattuck, “On Deadlock Detection in Distributed Systems,” IEEE Transactions on Software Engineering, vol. SE-6, no.
5, September 1980.
4A. K. Elmagarmid and A. K. Datta “Two-Phase Deadlock Detection Algorithm,”IEEE Transactions on Software Engineering, vol. 15, no.
12, December 1989.
5B. E. Wojcik and Z. M. Wojcik “Sufcient Condition for a Communica- tion Deadlock and Distributed Deadlock Detection,” IEEE Transactions
on Computers, vol. 37, no. 11, November 1988.
6S. Lee and J. L. Kim “Performance Analysis of Distributed Deadlock Detection Algorithms,” IEEE Transactions on Knowledge and Data
Engineering, vol. 13, no. 4, July/August 2001.
7Y. Ling, S. Chen and C. J. Chiang “On Optimal Deadlock Detection
Scheduling,” IEEE Transactions on Computers, vol. 55, no. 9, September
2006.
8G. Parodi, G. Vernazza and R. Zunino “Stability and Deadlock Avoid-
ance in Distributed Systems for Trafc Control,” IEEE Transactions on
Vehicular Technology, vol. 45, no. 4, November 1996.
9T. Li, A. R. Lebeck and D. J. Sorin “Spin Detection Hardware for
Improved Management of Multithreaded Systems,” IEEE Transactions
on Parallel Distributed Systems, vol. 17, no. 6, June 2006.

x

Hi!
I'm Ava

Would you like to get a custom essay? How about receiving a customized one?

Check it out