Handling Deadlock in Distributed Systems.

• In distributed systems there can be two types of deadlocks. First is a resource deadlock which occurs when two or more processes wait permanently for resource held by each other and second is communication deadlocks which occur among a set of processes when they are blocked waiting for other messages in order to start execution having no transit between messages.
  • Handling deadlocks in distributed systems is complex because the resources, the processes and other information are scattered on different nodes of a system.
  • The commonly used strategies to handle deadlock are:

1.Avoidance

• Deadlock avoidance methods use some advance knowledge of the resource usage of process to predict the future state of the system for avoiding allocations that can eventually lead to a deadlock.
• Deadlock avoidance algorithms are usually in the following steps:

i.When a process requests for a resource, if the resource is available for allocation it is not immediately allocated to the process rather the system assumes that the request is granted.

ii.Using advance knowledge of resource usage of processes and assumptions of step 1 the system analysis whether granting the process request is safe or unsafe.

iii.The resource is allocated to the process only if the analysis of step 2 shows that it is safe to do so otherwise the request is deferred.

• It is important to look at the notion of safety in resource allocation because all the algorithms for deadlock avoidance are based on the concept of safe and unsafe states.
• A system is said to be in safe state if it is not in a deadlock state and there exists some ordering of the process in which the requests are granted to run all of them to completion.
• Any ordering of the process that can guarantee the completion of all the processes is called safe sequence.
• The formation of safe sequence should satisfy the condition that for any process Pi in a safe sequence, the resource that Pi can still request and can be satisfied by currently available resources plus the resources held by all processes lying before Pi in the safe sequence.
• A system is said to be unsafe if no safe sequence exists for that state.
• Deadlock avoidance algorithm basically perform resource allocation is such a manner that ensures the system will always remain in safe state.

2.Prevention

• This approach is based on the idea of designing the system in such a way that deadlocks become impossible. It differs from the avoidance and detection where no runtime testing of potential allocations need to be performed.
• Mutual exclusion, hold-and-wait, no pre-emption and circular-wait are the four necessary conditions for a deadlock to occur. If one of these conditions can never be satisfied then deadlock can be prevented. For this there are three prevention methods namely:

i.Collective requests

These methods deny the hold and wait condition by ensuring that whenever a process requests a resource it does not hold any other resource. Various resource allocation policies can be used.

ii.Ordered Requests

In this method circular-wait is denied such that each resource type is assigned a unique global number to impose total ordering of all resource types.

iii.Preemption

A preemptable resource is one whose state can be easily saved and restored later. Deadlocks can be prevented using resource allocation policies to deny no-preemption condition.

3.Deadlock Detection

• In this approach for deadlock detection, the system does not make any attempt to prevent deadlock but allows processes to request resources and wait for each other in uncontrolled manner.
• Deadlock detection algorithms are same in centralized and distributed systems. Deadlock detection algorithms get simplified by maintaining Wait-for-graph (WFG) and searching for cycles.

i.Centralized Approach for Deadlock Detection

• In this approach a local coordinator at each site maintains a WFG for its local resources and a central coordinator for constructing the union of all the individual WFGs.
• The central coordinator constructs the global WFG from the information received from the local coordinators of all sites.

ii.Hierarchical Approach for Deadlock Detection

• The hierarchical approach overcomes drawbacks of the centralized approach.
• This approach uses a logical hierarchy of deadlock detectors called as controllers.
• Each controller detects only those deadlocks that have the sites falling within the range of the hierarchy. Global WFG is distributed over a number of different controllers in this approach.

iii.Fully Distributed Approaches for Deadlock Detection

In this approach each site shares equal responsibility for deadlock detection. The first algorithm is based on construction of WFG and second one is a probe-based algorithm.

4.Recovery from Deadlock

When a system chooses to use the detection and recovery strategy for handling deadlocks it is not enough to only detect deadlocks. The system must also be able to recover from a detected deadlock. One of the following can be used:

i.Ask for operator intervention

This is the simplest way which is to inform the operator of a deadlock occurrence and let the operator handle it manually. .

The system may assist the operator in decision making for recovery by providing a list of process involved in deadlock.

ii.Termination of Process

Automatic recovery from deadlock can be done by terminating one or more processes to reclaim the resources held by them.

iii.Rollback of processes

In this method processes are check pointed periodically so when a deadlock occurs the process is rolled back to a point where the resource was not allocated to the process causing deadlock.