Deadlock Detection
FREDRICK
.N.MURANGIRI
Department
of Computer Science
Kenyatta
University
Abstract
Deadlocks occur
in processes when more than one process wait for a resource which is being held by another process. Deadlocks also occur as a result of
incorrect ordering of lock acquisitions
,and also when sequence of allocation of resources to processes is not
controlled .In this paper I will concentrate on two types of deadlocks; distributed and dynamic
deadlocks and their detection methods
which include use of various algorithms, use of Pulse which is a system daemon
which dynamically detects deadlocks in applications and use of Dreadlocks which is an efficient new shared memory spin lock that
actively detects deadlocks. Distributed deadlock is detected by the distributed
control manager , I propose a
distributed Deadlock Detection Algorithm based on the Finite Automata and draw
the wait for graph(WFG) for the
distributed transaction with the help of
finite automata. I will only review resources deadlocks and briefly
mention other strategies of handling deadlocks and their environments.
Keywords:
deadlock detection, algorithms, distributed systems, transactional memory
Introduction
According to Shivendra et al.(2015) a deadlock situation occurs when a process
enters into a waiting state because a resource requested is being held by
another waiting process,which is also
waiting for another resource. Deadlocks commonly occurs in processes of
operating systems either distributed or centralized and in database
transactions. It is common in systems which carry out multiprocessing whereby
hardware and software resources are used to perform a task.The are two major models
in which deadlocks occur:
AND model- in
this model a process is allowed to make several resource requests and is locked
until all the requests are granted .Processes in this model can be involved in
several deadlock cycles at once.
OR model- a
process can make several requests and is locked until any of them is granted, it
is also known as Communication model.
Deadlock Conditions
For a deadlock
to occur these several conditions must
be met.
a.Mutual
exclusion-there must be a resource which only one process can
access it at a time.
b.Hold
and wait-a situation whereby one process is holding a
resource and waiting for a resource being held by another resource.eg
Ti-h (RI and Ti-w Rj) Where
Ti: Transaction i
Ri, Rj: Resources respectively ith and jth
h: resource in hold.
w: resource in wait.
c.No preemption –A resource can only be
released when the process has completed
the task
d.Circular wait-This is a situation whereby a
process is waiting for a resource which is being held by another process which
is also waiting for the resource to be
released by the first process i.e Ti?Tj?Tk?Ti
Transaction Ti is waiting for a resource held by Tj which is
also waiting for a resource held by Tk which is waiting for a resource
held by the first transaction Ti ,so it forms a circle.
Deadlock Detection
According to Shivendra et al.(2015) When doing a deadlock detection the manager lets the deadlock occur first, then applies an algorithm to determine
if it has occurred or not, this is relatively easy because the resources that each process has locked
and/or currently requested are known to the resource scheduler of the operating
system.
According to Elmagarmid(1985) primarily the main task done by
a detection algorithm is to find cycles among transactions waiting for the
resource held by the other process .Fundamentally deadlock
detection involves finding cycles in a directed graph .In the graph,
transactions and resources are represented by vertices and the requests and
allocations by edges. Algorithms used in deadlock detection can be classified as distributed, centralized or hierarchical.
For distributed schemes ,there is no single site that has all the information relating to all transactions
and resources involved in the graph. Therefore for deadlock detection to happen
information must be passed between sites .There is a variant of this scheme in Edge Chasing
deadlock detection algorithm, it involves sending information according to the
structure of the graph. In hierarchical algorithms detection is based on sites
so that the detection can done by the site which is closest to the deadlock as much as possible. Centralized
detection algorithms require that the information represented by the graph be
kept at central acting controller which is responsible for running the
detection and the resolution algorithms. Detection schemes have one main
disadvantage in that there is an overhead incurred due to detection of cycles
in the graph and the abortion and restart of the transactions when a deadlock is
detected. In
distributed detection strategies there may be additional overhead due transfer
between sites of the
message. Equally selection of the transaction to be aborted
increases the
complexity of the scheme.
The accuracy of a
deadlock detection algorithm is determined by two
conditions, whether it is detected in a finite time and if
detected does it really exist
There is need for
more research to be done in providing
more techniques for
proving the correctness of deadlock detection algorithms.
The Proposed Algorithm
In the proposed
algorithm as an optimization parameter for deadlock detection several message comparisons have been
taken,to find out distributed systems deadlocks
we have used state transitions and avoided sending triple probing
message,With the use of finite automata its not necessary to send probe message in the outgoing link as it
is clearly argued by Shivendra
et al.(2015) . By
using the Chandy Misra Haas model the concept of sending the number of probe
message has been used to find out deadlock and so the number of probe message
and their comparison is high in the AND model.
There is no overhead for sending and waiting for the probe massage for
the initiator and the number of
transition it takes to detect the deadlock in the system is less because of the
use of finite automata , this decreases not only the comparisons of messages
but also removes the concept of probe message overhead.
According to Shivendra et al.(2015) finite automata is
used to detect a deadlock, this is
achieved by taking the process id as an input(sigma) and the process as a
state. Using a transition function a transition table is drawn and this helps
in detecting a deadlock in a distributed
system should it be there. In the course of transition the unvisited or
unexpended vertex/transition is selected to be visited and we fully expand the selected node/transition. Equally one of the unvisited nodes from the transition
table is selected. If any node/transition has been visited once, its not
explored further. The process of expansions of vertices/transition is repeated
until either a deadlock is got in the transition table or all the nodes have been
expanded. A flag value has been given to the starting node of the transition so
whenever we have fully expanded a node ,we compare the flag value and decide whether there is a
deadlock in the system or not. If a deadlock is not got for the first time, then a second node is
taken and the process repeated . This is done for all the available nodes in the distributed
system.
This is illustrated as follows: Suppose we have 10 resources
(A,B,C,D,E,F,G,H,I,J) and
4 Processes (P0, P1, P2, P3)
Here h denotes resource in hold and w denote wait for the
resource.
With reference to figure 1 below:
P0—h?A, P0—w?C;
P1—w?A, P1—h?B, P1—w?D;
P2—h?C, P2—w?H, P2—h?J;
P3—w?B, P3—w?F, P3—h?H, P3-h?G;
P4—w?E, P4—f?F;
P5—h?D, P5—h?E, P5—w?I;
P6—h?I, P6—w?G, P6—w?J;
In this proposed algorithm the wait for graph is based on
transition
input and current state.
Here we have taken the transition input from the resource
allocated
process, for which the current process is in waiting state,see
Fig1 below.
Figure1:
Wait for graph(WFG) for distributed systems
This proposed algorithm(using finite automata) can also be
used to detect a distributed deadlock whereby the wait for graph(WFG) is
distributed over various sites. Any site can initiate the deadlock detection
process through constructing a global wait-for graph from local wait-for
graphs at a deadlock detector or by a distributed algorithm
like Edge Chasing.It is the decision of the control manager to go for deadlock
detection and this might be based on some threshold value like CPU utilization
,throughput or when the system is responsive. In summary the proposed algorithm
is for deadlock detection in a distributed environment, is wholly based on
finite automata and hence the execution is based on transition function of
detection algorithm. By use of this
algorithm phantom deadlocks are avoided hence making it more efficient by
having reduced overheads.
Pulse
Tong et. al(2005) describe Pulse as a
novel
operating system mechanism which runs as a daemon that dynamically
detects various types of deadlock in application programs. It periodically
scans the system for processes which have been blocked for a long time and if
it finds some it speculatively executes them ahead so as to determine if they are deadlocked or
not.By executing them it discovers their dependencies which are used to construct
a general resource graph and checks if
the graph contains cycles which would indicate presence of a deadlock. This
capability to look into the future allows Pulse to detect deadlocks involving
consumable resources, such as synchronization semaphores and pipes, which are hardly identified by other tools.For
the purpose of this paper Pulse focuses on detecting deadloacks caused by bugs in applications programs.It has been
implemented in Linux Kernel 2.6.8.1 and results indicate that it can pick
deadlocks when incorrect solutions are applied to dining-philosophers and smokers-problems and
also a deadlock scenario in the Apache server version 2.0.49.Pulse has three
modes i.e nap, monitor and detection .When idle it enters into a nap mode but
periodically it awakens and enters into monitor mode.In monitor mode it scans
the system to see if any process has been in sleep mode for a long time.If it
finds none it goes back to nap mode but should it find some it enters into
detection mode and identifies the events which the sleeping processes are
waiting for .For it to identify the dependency among the sleeping processes it
forks each of them to create a speculative process.By changing the status of
the lock on which its parent is blocked
to free ,a speculative processes ensures it wouldn’t block again and then
executes ahead in its parent program
.Pulse use copy-on-write mechanism in Unix fork and also disallows speculative
process from doing an input/output write so to avoid changing the state of the
normal processes.Pulse records all events during execution and uses these
records to match with the events waited for by the sleeping processes .A match between process A and
B indicates that once process A
completes it will produce an event which unlocks process B. Pulse works by
creating a general resource graph
,whereby nodes denote the sleeping processes and the events they are waiting
for while edges denote the dependencies
discovered by Pulse. Presence of a deadlock is denoted by existence of a cycle
on the graph and Pulse prints the entire graph to help the programmers decipher
the cause of the deadlock.
Dreadlocks
Dreadlocks
is a simple deadlock detecting spin which is frequently applied in
multiprocessor systems. Oftenly concurrent programs rely on locks to avoid race
condition as threads attempt to access shared data structures .Occassionally
programs with locks may experience a deadlock when one program
attempts to acquire a lock held
by another.In utilization of dreadlocks each thread maintains a digest for wait
for graphs(WFG) and changes for WFGs are propagated as the threads acquire and
release locks. A deadlock is detected by a thread when its own identifier
appears in the digest. According to Eric et.al. (2008) by using this
approach explicit wait for graphs and elaborate probing mechanism commonly used in distributed
deadlock detection algorithms are avoided and this improves over the other
previous deadlock detection strategies.
Related Work
The
topic on deadlock detection has been very attractive to researchers and
consequently various methodologies have come up ,many have come up with algorithms like Obermarck’s
Path Pushing Algorithm, Chandy-Misra-Haas Edge-Chasing
Algorithm, Bracha Algorithm, Sinha Scheme ,Ho’s Scheme and Kawazu’s algorithm. Notably there is a
lot of literature on deadlocks detection in both the distributed systems and
the database systems ,most advocate for probe messages which find cycles in wait for graph of threads and resources while others are of
the idea of maintain an explicit form of the waits-for graph, and seek more
efficient algorithms. Giant players in the industry have also come up with
various approaches to the deadlock problem whereby Microsoft suggests modelling multithreaded Win32 applications as
Petri Nets and using their DLDETECT tool to statically analyze programs for
potential deadlock .Equally Sun Solaris provides the Crash Analysis Tool (CAT)
which helps users to statically analyze system crash dumps so as
to identify simple lock-induced deadlocks.Similarly, Linux supports the
Non-Maskable Interrupt (NMI) watchdog, this periodically prints out system
information that can help statically identify deadlock.
Conclusion
Over the years
deadlocking has been a problem
in most multiprocessing systems and database systems,in this paper I have presented a proposed algorithm using
finite automata alongside Pulse and Dreadlocks as methods of detecting
deadlocks, all these approaches alongside other methods existing out there have
their various strengths and weaknesses hence more research
needs to be done to come up with more robust
methods of dealing with deadlocks.
References
1.Shivendra
Kumar P, Hari Krishna T, Kapoor RK (2015) Distributed Deadlock Detection
Technique with the Finite Automata. J Inform Tech Softw Eng 5: 148. doi:10.4172/2165-7866.1000148
2.Farajzadeha N,
Hashemzadeha M, Mousakhania M, Haghighata AT (2005)
An Efficient
Generalized Deadlock Detection and Resolution Algorithm in
Distributed
Systems. The Fifth International Conference on Computer and
Information
Technology. Shanghai.
3. Yeung CF,
Hung SH , Lam KY, Law CK (1994) A New Distributed Deadlock
Detection
Algorithm ForDistributed Database Systems. Browse Conference
Publications 1:
506-510.
4. Brzezirislti
J, Helary JM, Raynal M (1995) Deadlocks in Distributed Systems:
Request Models
andDefinitions. IEEE 186-193 Cheju Island.
5. Chendy M,
Misra J, Haas LM (1983) Distributed Deadlock Detection.
ACMTmns. Comput
Syst 1: 143-156
6. Holliday JL,
Abbadi EA (2000) Distributed Deadlock Detection. University of
California at
Santa Barbara.
7. Lee S, Lee Y
A (1999) Distributed Algorithm for Deadlock Detection under ORrequest
Model.
Conference: Reliable Distributed Systems, IEEE.
8. Obermarck, R
(1982) Distributed Deadlock Detection Algorithm ACM Trans.on
Database Systems
9.Moss J.E.,
“Nested Transactions: An Approach to Reliable Distributed Computing”,
Ph.D. Thesis. MIT/LCS/TR-260. April 1981.
10.
Tsai W.-C., “Distributed Deadlock Detection in Distributed Database Systems.
Ph.D. Thesis,Department of Computer Science, University of Illinois
at
Urbana-Champaign, Jan 1982.
11.
Tsai W.-C. and Belford G,,”Detecting Deadlock in DistributedSystems”,
INFOCOM 1982. 89-95
12.
Elmagarmid A.K.,”Deadlock ,Detection and
Resolution in Distributed Processing Systems,” Ph.D. Thesis. The Ohio
State University 1985.
13:
Tong Li, Carla S. Ellis, Alvin R. Lebeck, and Daniel
J. Sorin,(2005) Pulse: A Dynamic Deadlock Detection Mechanism Using Speculative
Execution,
USENIX
Annual Technical Conference ,Anaheim, California, April 10–15
14.Eric
K.,Maurice H.(2008),:Dreadlocks:Efficient Deadlock Detection, Retrieved from www.erickoskinen.com
15: Li, T., Ellis, C. S., Lebeck, A. R.,
and Sorin, D. J. Pulse: a dynamic deadlock detection mechanism using
speculative execution. In ATEC’05: Proceedings of the USENIX Annual Technical
Conference 2005 on USENIX Annual Technical Conference (Berkeley, CA,USA, 2005),
USENIX Association, pp. 3–3.
