Deadlocks and their prevention

A deadlock is a state where two or more tasks are blocked because they are perpetually waiting for resources which have already been allocated to the same set of tasks.

Indiscriminate use of two or more semaphores may lead to such a situation.

task1:                     task2:

P(S1);                      P(S2);
P(S2);                      P(S1);
    .                               .
    .                               .
    .                               .
V(S2);                      V(S1);
V(S1);                      V(S2);
end;                          end;

These two tasks may easily deadlock. Assume that they both are at the same priority level and that round-robin scheduling is applied.

Task 1 obtains S₁. At that moment, and before it is able to acquire S₂, its time slice expires and it is placed at the end of its priority queue. Task 2 is activated. It obtains S₂ and tries to acquire S₁. But S₁ has already been allocated to Task 1. Task 2 blocks waiting for S₁. Task 1, which has remained ready, becomes active and immediately tries to acquire S₂ which has been allocated to Task 2. Thus task 1 also blocks waiting for S₂.

A DEADLOCK

A dependence graph has as nodes the resources (semaphores) of the processes. There is a directed edge from a semaphore Si to semaphore Sj if in any of the processes, there ais a sequence of two subsequent P operations involving these two semaphores.

Example:

task1:                      task2: P(S1);                       P(S2); P(S2);                       P(S1);    .                                .    .                                .    .                                . V(S2);                       V(S1); V(S1);                       V(S2); end;                           end;

If the dependence graph contains a cycle, then deadlocks are possible

The graph depicted in the previous page contains a cycle indicating a possible deadlock situation for the set of tasks Task1 and Task2.

To guarantee freedom from deadlocks, it suffices that cycles in the dependence graph be broken.

If the required resources are ordered, and the tasks request resources according to their order (i.e. a higher order resource cannot be requested until all the required lower order resources have been obtained) then the resulting dependence graph is acyclic, and thus no deadlocks can occur.

Example:

task1:                        task2: P(S1);                        P(S2); P(S2);                        P(S1);    .                                  .    .                                  .    .                                  . V(S2);                        V(S1); V(S1);                        V(S2); end;                            end;

If precautions are not taken, deadlocks may happen.

Detecting a deadlock on-line is rather difficult, it involves a complete search on the state space of the tasking environment.

One may deem that a deadlock has occurred if a task is blocked for a "long" period of time. An arbitrary timeout can be used, which if exceeded, may signify a deadlock.

In such a situation, it is required that the latent task releases all its resources.

In certain situations, it is computationaly more efficient to obtain the required resources in any arbitrary order (e.g. if some preliminary work needs to be done that requires only part of the resources).

Obviously, such an approach is prone to deadlocks. A way to avoid deadlocks (akin to timeout) is to immediately release all obtained resources upon a block. After that, one may try again to acquire the resources, hopefully with better success.

To be able to release the resources, it means that the state of the task must remain consistent after their release (i.e. it either must be restorable to the state before the acquisition of the resources or the state reached is self consistent and does not require the acquisition of the next resource to accomplish that -- e.g. it does not need to update a globally shared variable).

Use of resource ordering and two-way locking in computer communications problems.

One class of multiprocessor architectures comprises a set of processors communicating over dedicated channels.

This architecture is modeled as a graph. Different graphs signify different communication topologies.

Hypercubes are popular interconnects.

The problem now becomes that of how to allocate channels to communicating nodes so as deadlocks are avoided.

Various communication mechanisms may be used.

Store and Forward
	Messages hop from node to node. They are buffered by the node. The resources that need to be managed in store and forward are message queues maintained by the nodes to accommodate the intermediate buffering of the messages as they traverse the network. Early method, suffers from large latencies because of the intermediate storing of the messages. Still in use in large area networks (internet).
Circuit Switching
	A sequence of channels is allocated to a circuit connecting a source to a destination, and all the channels are utilized simultaneously.
Wormhole Routing
	A pipeline of short buffers is formed connecting source to destination. Parts of the message is stored in the pipeline as it is routed and delivered.

Routing Policies

e-cube
	This is a deadlock-free policy. Channels/buffers are ordered to guarantee the absence of deadlocks. Channels at higher dimensions are not requested unless all required lower dimensions have been obtained. Suffers from the fact that between a source and a destination there exists exactly one path.
backtracking
	Two way locking policy. Form the path utilizing any available channel that brings the path closer to the destination. If there is a block, dissolve the path and try again. This policy provides a multitude of alternate paths between any source-destination pair, in effect increasing the capacity of the network.It suffers from thrashing at high loads.

Backtracking is deadlock avoiding in that it forces a timeout of 0 for blocked paths. It can utilize any available source-destination path, and it thus diminishes delays.
It suffers though from thrashing at high offered loads.