Deadlock and how to avoid it

Deadlock is a situation where two processes are each waiting for the other to release a resource it held, or more than two processes are waiting for resources in a circular chain, so that no one can have the resource required and all stop running.

Deadlock can happen between processes, thread or task (in vxWorks). And it can happen on any kinds of shared resources. I use process here for discussion.

There are three conditions in order for a deadlock to happen:
1. Each of the processes involved access multiple shared resources.
2. Each of the processes involved hold some shared resources while requiring other shared resources.
3. A circular waiting chain potentially possible.

To handle a deadlock, basically we have to break one or more of the conditions above. There are four ways to avoid it as far as I know.
1. All the processes apply the same coding pattern. And the pattern is, all the processes require (semWait for example) the shared resources in the same order, so that circular chain will be formed.
This method is suitable for smaller scale application, where all the shared resources can be listed and ordered.

2. Back-off algorithm. Each of the processes either have all the shared resources it need before proceed or none of them. In reality, the first semTake() can use WAITFOREVER, and the subquential semTake() use NOWAIT. And if one of the subsequential semTake() fail, it will back off and release all the resources it already holds.
This method increase the coding complexity. And it's not suitable for realtime system as the back off takes unpredictable time.

3. Avoid processes access multiple resources. This can be done by redesign the software's structure, algorithm or data structure. For example, a client-server model can be used so that only the server manage the shared resources, while client access the resources through the server.

4. Use some sort of watchdog to monitor the processes and if a deadlock is detected, reset the system or the processes.
Since a deadlock situation rarely happens, and if built-in mechanism is too expensive, then a third party monitor maybe suitable. For example, Linux kernel totally ignore deadlock and pretend it will never happen! (Supprising, isn't it? But that's real. When a deadlock indeed happens, the system just reboot.)