Mumbai University > Information Technology > Sem6 > Distributed System

Marks: 10M

Year: May 2015

Deadlock Detection

• It uses an algorithm that examines the state of system to determine whether a deadlock has occurred.
• when a deadlock is detected, the system takes some action to recover from deadlock.

Distributed approach for Deadlock detection

1) WFG based approach 2) probe based approach

WFG (Wait for Graph)

WFG based distributed algorithm, in this each site maintains its own local WFG to model waiting situations and an extra node Pex is added to local WFG of its site and it is connected in following manner.

condition 1: An edge (Pi, Pex) is added if process Pi is waiting for resource in another site being held by any process.

Condition 2: An edge (Pex,Pi) is added if Pj is a process of another site that is waiting for a resource currently being held by process of this site.

1) Edge P1 to Pex because P1 is waiting for resource in site S2, i.e. is held by Pex to P3 . because P3 is a process of a S2 waiting to resource held by P1 of site S1. 2) In WFG of S2 , edge P3 to Pex is added because P3 is waiting for resource in S1 held by P2 and edge (Pex, P1) is added because P1 of site S1 is waiting to the external resource held by P3 os site S2.

• to confirm a distributed deadlock algorithm is invoked by a site where WFG contains the cycle involving mode Pex.
• In our example if S1 detects its cycle itself it sends message Pex,P3, P2,P1,Pex to S2.
• On receiving the message S2 updates its local WFG by adding those edges of the cycle node Pex to its WFG.