Explain the various techniques for Deadlock Prevention

Deadlocks are like a nightmare for the programmers who design and write the programs for the multitasking or multiprocessing systems. For them it is very important to know about how to design programs in such a way as to prevent the deadlocks. 

Deadlocks are a more common problem in the distributed systems which involve a use of the concurrency control and distributed transactions. The deadlocks that occur in these systems are termed as the distributed deadlocks. 

It is possible to detect them using either of the following means:

1. Building a global wait for graph from a local one through a deadlock detector.

2. Using distributed algorithms such as the edge chasing.

- An atomic commitment protocol similar to a two phase commit is used for automatically resolving the distributed deadlocks. 

- Therefore, there is no need for any other resolution mechanism or a global wait for graph. 

- But this is possible only in the commitment ordering based distributed environments. 

- For the environments that have 2 – phase locking, a similar automatic global deadlock resolution takes place.

- There is another class of deadlocks called the phantom deadlocks. 

- These are the ones detected in the system because of some internal delays but they actually do not exist during the detection time.

- Today, their exist a number of ways using which the parallelism can be increased where otherwise severe deadlocks might have been caused by the recursive locks. 

- But like for everything else, this also has a price.

- You either have to accept one of these or both i.e., the data corruption or the performance/ overhead. 

- Preemption and lock–reference counting, WFG or wait – for graph are some of the examples of this. 

- These can be followed either by allowing for the data corruption during the preemption or by using version.

- Apart from these heuristic algorithms and the algorithms that can track all the cycles causing the deadlocks can be used for preventing the deadlocks.

- These algorithms even though they don’t offer 100 percent parallelism, they prevent deadlocks by providing an acceptable degree of the performance overhead versus parallelism. 

This example will make it clearer: 

- Consider at a crossing junction there are 2 trains approaching each other. 

- Their collision can be prevented by some just-in-time prevention means. 

- This mean can be person at the crossing having a switch pressing which will allow only one of them to cross on to the succeeding track super passing the other trains that are also waiting. 

- There are following two types of deadlocks:

1. Recursive locks: In such locks, only one thread can pass through it. Any other threads or processes entering the lock need to wait for the initial one to pass through after its task is finished.
2. Non – recursive locks: Here only once a thread can enter the lock. If the same thread again tries to enter the lock without unlocking it, a deadlock can occur.

- There are issues with both of these. 

- The first one does not provides distributed deadlock prevention and the latter one has no concerns for the deadlock prevention. 

- In the first one, if the number of threads trying to enter the lock equals the number of locked threads, then one of the threads has to be assigned as the super one and then only one can execute it till completion. 

- After the execution of the super thread is complete, the condition reverts back from the recursive lock and the super thread removes its status of being super thread and sends a notification to the locker that the condition has to be re-checked.