What is deadlock avoidance and what are some examples?

Question

What is deadlock avoidance? What is the goal, what is it supposed to achieve? Can you give some examples of different types of deadlock avoidance algorithms and why are there different ones? Why is there not one type of deadlock avoidance algorithm?

Answer 1

Deadlocks occur when there is a cycle of processes (or other things) such that each element of the cycle is waiting for the next element of the cycle. Because the cycle wraps round, no element in the cycle can proceed. See e.g. https://en.wikipedia.org/wiki/Wait-for_graph.

Deadlock avoidance amounts to ensuring that such cycles can never exist. Ideas include having only one object that anybody ever waits for, enforcing a rule that processes never wait for anything while holding anything that anybody else ever waits for, or (most common) imposing an order on the things that processes wait for and only requesting them in this order.

There is a writeup of this in the context of processes at https://cs.nyu.edu/courses/spring02/V22.0202-002/lecture-08.html (section 3.6) and in the context of packet routing at http://pages.cs.wisc.edu/~tvrdik/8/html/Section8.html.

For similar reasons I claim that when two people are trying to walk through a doorway in opposite directions the one exiting the smaller space should have priority - but I notice that people don't obey this convention in real life.