Deadlock-Issues in deadlock detection & Resolutions



Ø  Deadlock is a fundamental problem in distributed systems.

Ø  A process may request resources in any order, which may not be known a priori and a process can request resource while holding others.

Ø  If the sequence of the allocations of resources to the processes is not controlled, deadlocks can occur.

Ø  A deadlock is a state where a set of processes request resources that are held by other processes in the set.

System model:
Ø  A distributed program is composed of a set of n asynchronous processes p1, p2, . . . , p, . . . , pthat communicates by message passing over the communication network.

Ø  Without loss of generality we assume that each process is running on a different processor.

Ø  The processors do not share a common global memory and communicate solely by passing messages over the communication network.

Ø  There is no physical global clock in the system to which processes have instantaneous access.

Ø  The communication medium may deliver messages out of order, messages may be lost garbled or duplicated due to timeout and retransmission, processors may fail and communication links may go down.

Ø  We make the following assumptions:
·         The systems have only reusable resources.
·          Processes are allowed to make only exclusive access to resources.
·         There is only one copy of each resource.

Ø  A process can be in two states: running or blocked.

Ø  In the running state (also called active state), a process has all the needed resources and is either executing or is ready for execution.

Ø  In the blocked state, a process is waiting to acquire some resource.

Wait-For-Graph (WFG)
Wait for graph (WFG)

Ø  The state of the system can be modeled by directed graph, called a wait for graph (WFG).

Ø  In a WFG , nodes are processes and there is a directed edge from node P1 to mode P2 if P1 is blocked and is waiting for P2 to release some resource.

Ø  A system is deadlocked if and only if there exists a directed cycle or knot in the WFG.

Ø  Figure 1 shows a WFG, where process P11 of site 1 has an edge to process P21 of site 1 and P32 of site 2 is waiting for a resource which is currently held by process P21.

Ø  At the same time process P32 is waiting on process P33 to release a resource.

Ø  If P21 is waiting on process P11, then processes P11, P32m and P21 form a cycle and all the four processes are involved in a deadlock depending upon the request model.

An example of a WFG

Deadlock Handling Strategies:

Ø  There are three strategies for handling deadlocks, viz., deadlock prevention, deadlock avoidance, and deadlock detection.

Ø  Handling of deadlock becomes highly complicated in distributed systems because no site has accurate knowledge of the current state of the system and because every inter-site communication involves a finite and unpredictable delay.

Ø  Deadlock prevention is commonly achieved either by having a process acquire all the needed resources simultaneously before it begins executing or by preempting a process which holds the needed resource.

Ø  This approach is highly inefficient and impractical in distributed systems.

Ø  In deadlock avoidance approach to distributed systems, a resource is granted to a process if the resulting global system state is safe (note that a global state includes all the processes and resources of the distributed system).

Ø  However, due to several problems, deadlock avoidance is impractical in distributed systems.

Ø  Deadlock detection requires examination of the status of process-resource interactions for presence of cyclic wait.

Ø  Deadlock detection in distributed systems seems to be the best approach to handle deadlocks in distributed systems.

Issues in deadlock detection:

·         Deadlock handling using the approach of deadlock detection entails addressing two basic issues: First, detection of existing deadlocks and second resolution of detected deadlocks.

·         Detection of deadlocks involves addressing two issues: Maintenance of the WFG and searching of the WFG for the presence of cycles (or knots).

Correctness Criteria:

A deadlock detection algorithm must satisfy the following two conditions:

(i) Progress (No undetected deadlocks):

·         The algorithm must detect all existing deadlocks in finite time.

·         In other words, after all wait-for dependencies for a deadlock have formed, the algorithm should not wait for any more events to occur to detect the deadlock.

(ii) Safety (No false deadlocks):

·         The algorithm should not report deadlocks which do not exist (called phantom or false deadlocks).

Resolution of detected deadlock:

Ø  Deadlock resolution involves breaking existing wait-for dependencies between the processes to resolve the deadlock.

Ø  It involves rolling back one or more deadlocked processes and assigning their resources to blocked processes so that they can resume execution.

DISTRIBUTED SYSTEM covered following topics in these notes.

Post a Comment

Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.