DEADLOCK DETECTION ALGORITHMS

• All sites collectively cooperate to detect a cycle in the state graph.

• Initiated wherever a process is forced to wait.

• Distributed deadlock detection algorithms divided into four classes:

1.Path-pushing algorithm

2.Edge-chasing algorithm

3.Diffusion computation algorithm

4.Global state detection algorithm

A Path-Pushing Algorithm

•Wait for dependencies is propagated in the form of paths.

•Obermarck's algorithm is chosen to illustrate a path pushing deadlock detection algorithm.

•Processes are referred to as transactions which are denoted by T1, T2.... Tn.

•Obermarck's algorithm has two interesting features:

1.Non-local portion of the Global TWF graph at a site is abstracted by a distinguished node.

2.Transactions are totally ordered.

The Algorithm Deadlock detection at a site follows the following iterative process

1. Site waits for deadlock related information from other sites.

2. Site combines the received information with its local TWF graph to build an updated TWF graph.

3. For all cycles 'ExT1T2—Ex' which contain the node Ex, the site translate them in string form ‘Ex, T1, T2, Ex'

An Edge-Chasing Algorithm

• Chandy-Misra-Haas's distributed deadlock detection algorithm for AND request model.

• This algorithm uses message called a probe.

• A probe is triple (i, j, k) denoting that it belongs to a deadlock detection.

• A probe message travels along the edges of the Global TWF graph.

• Process Pj is said to be dependent on another process Pk.

• Process Pj is locally dependent account process Pk.

• The System maintains a Boolean array, dependenti.

The Algorithm

On the receipt of proverb (i, j, k) the sites takes the following actions.

if

(d) Pk is blocked and

(e) dependentk (i) is false, and

(f) Pk has not replied to all requests of Pj

then

begin

dependentk(i)= true;

if k= i

then declare that Pi is deadlocked

else for all Pm & Pn such that

(a’) Pk is locally dependent upon Pm, and

(b') Pm is waiting on Pn, and

(c') Pm & Pn are on different sites,

send probe (i, m, n) to the home site of Pn

end.

Centralised Deadlock Detection Algorithms

The Completely Centralized Algorithms

• A designated site called the control site.

• All sites request and release resources also local resources. Reliability is poor. T1 T2 lock R1 lock R1 unlock Ri unlock R1 lock R2 lock R2 unlock R2 unlock R2

Other Edge-Chasing Algorithms

The Mitchell-Merritt Algorithm

• Each node of TWF graph has two labels:

Private and public

• Private label of each node is unique.

• Algorithm detects a deadlock by propagating the public label of nodes.

• A blocked transaction periodically reads the public level of blocking transaction.

• A deadlock is detected when a transaction receives its own public label.

Sinha-Natrajan Algorithm

• Transactions are assigned a unique priorities and antagonistic conflicts.

• Circulating a probe message through a cycle in the Global TWF graph.

• Deadlock is detected when the probe issued buy the highest priority transaction in the cycle returns to it.

• Detector of deadlock and resolve deadlock by aborting the lowest priority transaction of the cycle.

A Diffusion Computation Based Algorithm

• Deadlock detection computation is diffused through the WFG of the system.

• These algorithms make use of echo algorithms to detect deadlocks.

• This computation is superimposed on the underlying distributed computation.

• Process sends out query messages along all the outgoing edges in the WFG.

• Does not send a reply message until it has received a reply message for every query it sent.

• It immediately sends back a reply message.

• The initiator of deadlock detection detects a deadlock when it receives reply for every query it had sent out.

• The algorithm works as follows:

Initiate a diffusion computation for a blocked process Pi

send query(i, i, j) to all processes Pj in the dependent set DSi of Pi; numi(i):= DSil; waiti(i):= true;

When a blocked process Pk receives a query(i, j, k):

if this is the engaging query for process Pk

then send query(i, k, m) to all Pm in its dependent set DSk;

numk(i): = |DSkl; waitk(i):= true

else if waitk(i) then send a reply (i, k, j) to Pj

When a process Pk receives a reply(i, j, k):

if waitk(i)

then begin

numk(i)= numk(i) – 1;

if numk(i)= 0

then if i=k then declare a deadlock

else send reply (i, k, m) to the process Pm

which sent the engaging query.

A Global State Detection Based Algorithm

• Kshemkalyani-Singhal algorithm has a single phase.

• A sweep is traversal of the WFG.

• Algorithm records snapshot of distributed WFG.

• Recorded distributed WFG is reduced to determine if the initiator is deadlocked.

• Both the outward and the inward sweeps are executed concurrently in the algorithm.

System Model

• The system has n nodes, and every pair of nodes is connected by a logical channel.

• Events are assigned timestamps using Lamport's clocks.

• The computation messages can be either REQUEST, REPLY or CANCEL messages.

• Sending and receiving of REQUEST, REPLY, and CANCEL messages are computation events.

Informal Description of the Algorithm

• Distributed WFG is recorded using FLOOD messages in the outward sweep.

• Local state and sends FLOOD messages along all of its outward dependencies.

• ECHO messages perform reduction of the recorded WFG by simulating the granting of requests in the inward sweep.

• Node init detects the deadlock if it is not reduced when the deadlock detection algorithm terminates

Termination Detection

• Initiator can determine that it will not receive any more ECHO messages.

•The algorithm uses a termination detection technique based on weights in conjunction with SHORT messages.

•A weight of 1.0 at the initiator node, distributed among all FLOOD messages sent out by the initiator.

• FLOODs sent out along outward edges at that node to expand the WFG further.

Hierarchical Deadlock Detection Algorithm

• Logically arranged in hierarchical Fashion, and a site is responsible for detecting deadlocks.

The Menasce-Muntz Algorithm:

• All the controllers are arranged in the tree fashion.

• Controller at the bottom most level called leaf controllers.

• A leaf controller maintains a part of the Global TWF graph.

• A non leaf controller maintains all TWF graphs spanning its children controllers.

• Parent controller makes changes in its TWF graph.