Operating System

11/29/2012

CECS 526

Distributed Deadlock Handling

Deadlock Handling in Distributed System

• Deadlock prevention is achieved by denying the existence of one or more of the necessary conditions for deadlock. Commonly adopted strategies include:

– (1) having a process acquire all needed resources simultaneously before it begins execution, or – (2) using a liner ordering scheme for resource acquisition to prevent circular waits. Unless information about resource availability and process requests are maintained centrally on one site, such an approach is impractical for a distributed system.

• In deadlock avoidance, a resource is granted to a process if the resulting state is safe. For a distributed system, the safe state checking must examine the global state that involves all processes and resources in all sites. This approach is impractical for distributed systems because:

– (1) The need to maintain information on the global state for every site leads to huge storage requirements and extensive communication costs – (2) the safe state checking will be computationally expensive due to the potentially large number of processes and resources involved, and – (3) the safe state checking for the global state must be mutually exclusive. If we allow multiple sites to perform safe state checking concurrently, each site for a different request, they may find the state safe but the net global state may not be.

1

11/29/2012

System Model

• In light of the difficulty in deadlock detection for the general resource system, the study of deadlock problems in distributed systems usually adopts a simpler system model assuming:

– Reusable resources only – Only exclusive accesses to resources – Each resource has only one instance

• With the simpler system model as defined above, deadlock detection can be achieved by finding a cycle in the Wait For Graph (WFG) of the resource system.

Phantom Deadlock

One major difficulty in deadlock detection in distributed...