Deadlock

Deadlock is a situation or condition of a lock where set of processes (or threads) have requests for resources that can never be satisfied. Eventually, a process cannot proceed because it needs to obtain a resource held by another process but it itself is holding a resource that the other process needs.

 

Deadlock in distributed systems

In distributed system the same conditions for deadlock in uni processors applicable. Unfortunately, as in many other aspects of distributed systems, they are harder to detect, avoid, and prevent. Four strategies can be used to handle deadlock:

1. ignorance: ignore the problem; assume that a deadlock will never occur. This is a surprisingly common approach.


2. detection: let a deadlock occur, detect it, and then deal with it by aborting and later restarting a process that causes deadlock.


3. prevention: make a deadlock impossible by granting requests so that one of the necessary conditions for deadlock does not hold.


4. avoidance: choose resource allocation carefully so that deadlock will not occur. Resource requests can be honored as long as the system remains in a safe (non-deadlock) state after resources are allocated.

The last of these, deadlock avoidance through resource allocation is difficult and requires the ability to predict precisely the resources that will be needed and the times that they will be needed. This is difficult and not practical in real systems. The first of these is trivially simple but, of course, ineffective for actually doing anything about deadlock conditions. We will focus on the middle two approaches.

In a conventional system, the operating system is the component that is responsible for resource allocation and is the ideal entity to detect deadlock. Deadlock can be resolved by killing a process. This, of course, is not a good thing for the process. However, if processes are transnational in nature, then aborting the transaction is an anticipated operation. Transactions are designed to withstand being aborted and, as such, it is perfectly reasonable to abort one or more transactions to break a deadlock. The transaction can be restarted later at a time when, we hope, it will not create another deadlock.