Deadlocks in DS

Deadlocks
Deadlock :- state of permanent blocking of a set of processes each of which is waiting for an event that only another process in the set can cause.

;
Deadlocks

 Sequence of events reqd to use a resc:

 Request

 Allocate

 Release
Causes Of Deadlocks

• Mutual Exclusion – Resources being held must be in non-

shareable mode.

• Hold n Wait – A Process is holding one resource and is

waiting for another, which is held by another process.

• No Preemption – Resource cannot be preempted even if it

is being requested.

• Circular Wait – Presence of a cycle of waiting processes.

CSE - 8344
Resource Allocation Graph
Deadlock Modeling

 Directed Graph: a pair (N,E)

N – nonempty set of nodes
 E – set of directed edges

 A directed edge is an ordered pair (a,b)

where a & b are the nodes.

 Path:A path is a sequence of nodes
(a,b,c,…,i,j) such that (a,b) is a directed
edge.
Deadlock Modeling

 Cycle: a path whose first and last nodes

are the same.
 Reachable Set:

the reachable set of node a = set of all

nodes b such that a path exists from a to
b.
Resource Allocation Graph

 Process nodes: represents process

 Shown as a circle, with the name of the
process written inside the circle
 Resource nodes: represents process
 Shown as a rectangle, with the name of the
process written inside the rectangle.
 Each instance of the resource is

represented as a bullet
Resource Allocation Graph

 Assignment Edge: a directed edge from

a resource to a process.
 Signifies that resource is held by the
process
 Request Edge: a directed edge from a
process to a resource.
 Signifies
that process made a request for
the resource and is waiting for the resource.
Illustrating A Deadlock

• Wait-For-Graph (WFG)
 Nodes – Processes in the system
 Directed Edges – Wait-For blocking relation

 Simplified form of RAG

CSE - 8344
Wait-For-Graph (WFG)
RAG Corresponding WFG

A Cycle represents a Deadlock

Deadlocks in Distributed Systems :

 Deadlocks in distributed systems are similar to deadlocks in single

processor systems, only worse, as

 They are harder to avoid, prevent or even detect.

 They are hard to cure when tracked down because all relevant
information is scattered over many machines.
Types of Deadlocks:
 People sometimes might classify deadlock into
the following types:
 Communication deadlocks -- competing

with buffers for send/receive

 Resources deadlocks -- exclusive access

on I/O devices, files, locks, and other
resources.
Types of Deadlocks:
 Resource Deadlocks

 A process needs multiple resources for an activity.

 Deadlock occurs if each process in a set request resources
held by another process in the same set, and it must receive
all the requested resources to move further.

 Communication Deadlocks

 Processes wait to communicate with other processes in a set.

 Each process in the set is waiting on another process’s
message, and no process in the set initiates a message until
it receives a message for which it is waiting.
Strategies to handle deadlocks:

 Ostrich Algo …(ignore the problem, pretend that there is no problem)

 Detection….. (let deadlocks occur, detect them, and try to recover)

 Prevention….. (statically make deadlocks structurally impossible)

 Avoidance….. (avoid deadlocks by allocating resources carefully)

 Deadlock avoidance is never used in distributed system,

 The problem is that the banker’s algorithm need to know (in

advance) how much of each resource every process will eventually
need. This information is rarely, if ever, available.

 Hence, we will just talk about deadlock detection and deadlock

prevention.
Distributed Deadlock Detection
System.
Deadlock Detection:

 Centralized Deadlock Detection System.

 Distributed Deadlock Detection System

 Hierarchical Deadlock Detection System.

.
Centralized Deadlock Detection
System.
Centralized Deadlock Detection

 Central co-ordinator
 It maintains the RAG and WFG for the
entire system.
 It is the union of the individual graphs.
 The sub-graphs are propogated to the
coordinator.
 A message is sent each time an arc is
added or deleted.
Construction of WFG for DS
Updating of central coordinator’s
information:
 Continuous transfer

 Periodic transfer: local coordinator periodically sends a list of arcs

 Transfer on request: central coordinator invokes detection

algorithm and requests info from each site.
Centralized Deadlock Detection
 A local coordinator for each site maintains a local WFG for the
site.
 There is a central coordinator (centralized deadlock detector) that
is responsible for constructing the union of all individual WFGs.
 The central coordinator constructs the global WFG from the
information received the local WFGs of all the sites
 Working:
 If a cycle is found in the local WFG, a local deadlock is detected….to
be resolved locally by the local coordinator.
 Cycle found in the global WFG, a distributed deadlock is detecetd…
to be resolved by the central coordinator.
Centralized Control
 Simple conceptually:
 Each node reports to the master detection node

 The master detection node builds and analyzes the WFG

 The master detection node manages resolution when a

deadlock is detected
 Some serious problems:
 Single point of failure

 Network congestion issues

 False deadlock detection

Phantom deadlock:
 A deadlock that is ‘detected’ but is not really a deadlock is called
a Phantom (or a False) deadlock

 As this procedure will take some time, there is a chance that one
of the transactions that holds a lock will meanwhile have released
it,
 In which case, the deadlock will no longer be existing.

 For eg.,
 if there is a cycle ABCA, and B aborts after the information concerning
B has been collected, then the cycle has been already broken and there is no
deadlock existing
False Deadlocks
Machine 0 Machine 1 Coordinator Coordinator
A S S C A S C A S C

R T R T R T

B B B

B release R, and ask for T

Mi: delete edge from R to B
Mj: add edge from B to T
But if Mj reaches before Mi, then false deadlock is
detected.
Solution :
 One possible way to prevent false deadlock is to use the
Lamport’s algorithm to provide global timing for the distributed
systems.

 When the coordinator gets a message that leads to a suspect

deadlock:
 It send everybody a message saying “I just received a

message with a timestamp T which leads to deadlock. If

anyone has a message for me with an earlier timestamp,
please send it immediately”
 When every machine has replied, positively or negatively, the

coordinator will see that the deadlock has really occurred or

not.
Edge-chasing algorithm
 Probe based distributed algorithm for Deadlock Detection

 Also called as, Chandy-Misra-Haas’s Algorithm.

 Working:
 When a process that requests for a resource, fails to get it and
times out,
 It generates a special probe message and sends it to the
process (or processes) holding the requested resource.

 The probe contains the following fields:

 The id of the process just blocked
 The id of the process sending this message
 The id of the process to whom this message is being sent
Edge-chasing algorithm
 On receipt of the probe message, the receiver checks to see if it
itself is waiting for any resource.

 If not, this means that the recipient is using the resource requested
by the process that sent the probe message to it.
 In this case, the recipient simply ignores the probe message.

 On the other hand, if the recipient is itself waiting for any resource, it
passes the probe message to the resource holding process (or
processes)
Edge-chasing algorithm
 But, before the probe is forwarded, the recipient does following
modifications
 The first field is left unchanged
 The recipient changes the second field to its own process id.
 The third field is changed to the id of the process that will be
the new recipient of the probe.

 Every new recipient of the probe message repeats this

procedure.

 If the probe message returns back to the original sender,( the

process whose id is the first field of the message), a cycle exists
and, the system is deadlocked!!!
Edge-chasing algorithm

(P1,P1,P3)
P1 P3 P5

(P1,P3,P5)
(P1,P2,P1)
(P1,P3,P2)

P4 P2

(P1,P2,P4)
Edge-chasing algorithm
Machine 0 Machine 1 Machine 2

(0,4,6)
4 6
(0,2,3)
0 1 2 3 8
(0,5,7)
5 7

(0,8,0)
Advantages & Disadvantages
 Easy to implement
 As each message is of fixed length …three componemts
always
 Requires few computation steps

 The overhead of the algorithm Is fairly low…one probe message

per time

 There is no graph constructing or information collecting involved

 False deadlocks are not detected by the algorithm

Recovery

 Recovery through operator intervention

 Recovery through termination
 Recovery through rollback
Recovery through operator
intervention
 Asking for Operator Intervention.
 Old method
 The simplest way is to inform the operator that
a deadlock has occurred and to let the
operator deal with it manually.
 The system may assist the operator in
decision making for recovery by providing him
or her with a list of the processes involved in
the deadlock.
Recovery through termination
 Termination of Processes.
 The simplest way
 Terminate (kill) one or more processes and
reclaim the resources held by them, which can
then be reallocated.
 First, analyze the resource requirements and
interdependencies of the processes involved
in a deadlock cycle and then select a set of
processes, which, if killed, can break the cycle.
Recovery through rollback

 Killing a process is expensive,

 Since it requires restart from the beginning
 So rollback the process to a point where the

resource was not allocated.

 Processes are often checkpointed.

 If required processes are restarted from any

checkpoint.