Deadlock  Detection

FREDRICK
.N.MURANGIRI

Department
of Computer Science

Kenyatta
University

[email protected]

 

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 dead­locks 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 dead­lock .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.Simi­larly, Linux supports the
Non-Maskable Interrupt (NMI) watchdog, this periodically prints out system
infor­mation 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.