Introduction

• Deadlocks are 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 communicates processes P₁, P2, ..., ·, Pi, ..., Pn that 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 n and communicate solely by passing messages ocommunication 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.

•Following assumptions are made :

1. The systems have only reusable resources.

2. Processes are allowed to make only exclusive access to resources.

3. There is only one copy of each resource.

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

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

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

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 P₁ to node P₂ if P₁ is blocked and is waiting for P₂ to release some resource.

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

Deadlock Handling Strategies

• There are three strategies for handling deadlocks, viz.,

(i) deadlock prevention,

(ii) deadlock avoidance, and

(iii) 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 before it begins executing or by preempting a proc holds the needed resource. simultaneously

• This approach is highly inefficient and impract 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).