Deadlock Avoidance


We focus a great deal of attention on the four necessary conditions for deadlock, because these form the basis for deadlock prevention. If we can ensure that any of the four necessary conditions will never be met, we have created a system where deadlock (involving those resources) is impossible. There are, however, common situations in which:

For many such cases, deadlock avoidance may be an easy and effective solution. Consider the following deadlock situation: The problem, in this case, is not a particular resource dependency graph, but merely that we exhausted a critical resource. There are many similar situations where: In situations like these, it is common to keep track of free resources, and refuse to grant requests that would put the system into a dangerously resource-depleted state. Making such case-by-case decisions to avoid deadlocks is called deadlock avoidance.


Declining to grant requests that would put the system into an unsafely resource-depleted state is enough to prevent deadlock. But the failure of a random allocation request (in mid-operation) might be difficult to gracefully handle. For this reason, it is common to ask processes to reserve their resources before they actually need them.

Consider the sbrk(2) system call. It does not actually allocate any more memory to the process. It requests the Operating System to change the size of the data segment in the process' virtual address space. The actual memory assignments will not happen until the process begins referencing those newly authorized pages. If we can determine that the requested reservation would over-tax memory, we can return an error from the sbrk system call, which the process can then decide how to handle. If, however, we waited until a page was referenced before we decided we did not have sufficient memory, we might have no alternative but to kill the process.

This approach is not limited to memory. For example ...

Unlike malloc(3), these other operations do not tell us how much new resource the process wants to consume. But in each of these cases there is a request (to which we can return an error) before we reach actual resource exhaustion. And it is this failable request that gives us the opporutunity to consider, and avoid a resouce-exhaustion deadlock.


In most situations, it is unlikely that all clients will simultaneously request their maximum resource reservations. For this reason, it is often considered relatively safe to grant somewhat more reservations than we actually have the resources to fulfill. The reward for over-booking is that we can get more work done with the same resources. The danger is that there might a demand that we cannot gracefully handle.

Dealing with Rejection

What should a process do when some resource allocation request (e.g. a call to malloc(3)) fails?

There are many possible responses, and different responses make sense in different situations. But the key here is that, since the allocation request failed with a clean error, the process has the opportunity to try to manage the situation in the most graceful possible way.