The problem of deadlock in general

Consider three grannies seeking to knit jumpers. There are only three needles available. If all three grannies sought to obtain two needles at the same time, they may all get only one needle each and none of them would be able to proceed with their knitting. This situation is termed deadlock.

System model

The problem of deadlocks in distributed has been generally studied using a model with the following assumptions:

• The system has only reusable resources.
• Processes are allowed only exclusive access to resources.
• There is only one copy of each resource.
• A process is in two possible states: running (it has all needed resources and is either executing or ready to start running) or blocked (it waits to acquire some resources).

Graph-theoretical model

The state of process-resource interaction in distributed systems can be modelled by a bi-partite directed graph called a resource allocation graph. The nodes of the graph are the processes and resources of the system. The edges depict assignements or pending requests . A system is deadlocked if its resource allocation graph contains a directed cycle or a knot.

Special conditions of deadlock detection in didtributed systems

In distributed systems deadlock handling is more complicated because

• No one site has accurate knowledge of the current state of the system.
• Every intersive communication involves a finite and unpredictable delay.
• No individual site can determine if a deadlock exists.

Deadlock handling strategies

Deadlock Prevention: It is achieved by having a process acquire all needed resources simultaneously before it begins execution or preempting a process that helds the needed resource.

Drawbacks

• It decreases the system concurrency.
• A set of processes can be deadlocked in the resource acquiring phase.
• Future resource requirements are unpredictable (not known a priori).

Deadlock Avoidance: A resource is granted to a process if the resulting global system state is safe.

Drawbacks

• The global state needs extensive communication costs, and huge storage requirements in order to be updated.
• The process of checking for a safe global state must be mutually exclusive, so it limits the concurrency.
• Due to large number of nodes it is computationaly expensive to check for a safe state.

Deadlock Detection: It requires an examination of the status of process-resource interactions for the presence of a cyclical wait.

Favorable conditions

• Once a cycle is formed in a Wait-For Graph (WFG), it persists until detected and broken.
• Cycle detection proceeds concurrently with the normal activities of a system. So, it has no negative effect on system throughput.

Issues in deadlock detection

A correct deadlock detection algorithm must satisfy the following two conditions:

• Progress: No deadlock should be undetectable. It should detect all existing deadlocks in finite time.
• It should not detect false deadlocks (phantom deadlocks).

Distributed Control

In this scheme of control the responsibility for detecting a global deadlock is shared equally among all sites. The global state graph is spread over many sites and several sites participate in the detection of a global cycle.

Advantages:

• Distributed control is not vulnerable to a single point of failure.
• No site is swamped with deadlock detection activity.

Disadvantages:

• Difficulty in design due to the lack of shared memory.
• Several sites may initiate deadlock detection for the same deadlock.
• Deadlock resolution is often cumbersome as several sites detect the same deadlock without being aware that other processes involved in the deadlock.

The Edge-Chasing algorithm

Basic Idea: In edge-chasing algorithms, special messages called probes are circulated along the edgs of the WFG to detect a cycle. When a blocked process receives a probe, it propagates the probe along its outgoing channels on the WFG. A process declares a deadlock when it receives a probe initiated by it.

Algorithm (Chandy-Misra-Haas):

Example:

Consider the system shown in the figure below. If process P1 initiates deadlock detection, it sends probe (1, 3, 4) to Site 2. Since P6 is waiting for P8 and P7 is waiting for P10, Site 2 sends probes (1, 6, 8) and (1, 7, 10) to Site 3 which in turn sends probe (1, 9, 1) to Site 1. On receiving probe (1, 9, 1), Site 1 declares that P1 is deadlocked.

Bibliography

• Advanced Concepts in Operating Systems, Mukesh Singhal, Niranjan G. Shivaratri, McGraw-Hill 1994.
• Operating Systems course ( Cs5204 ) Web page: http://ei.cs.vt.edu/~cs5204.