Deadlock prevention in a complicated system

Question

Suppose I have a system with 7 processes and 3 resources A, B, C. Suppose every process needs to read & write a different non-empty subset of {A, B, C}, how do I efficiently prevent deadlocks? i.e. cant put a mutex on the 3 resources together as a whole.

Answer 1

If the mutex support non-blocking acquisition (often referred as trylock), a deadlock-avoiding solution can be implemented without lock ordering/hierarchy. The algorithm is as follows:

1. Acquire the lock for the first resource; here waiting is allowed.
2. Once the first lock is acquired, try acquiring another one with try-lock.
3. If try-lock fails (indicating that a resource is busy), release all previously acquired locks and go to the step 1.
4. If try-lock succeeds, repeat from step 2 for all remaining resources.

Deadlock avoidance is achieved through non-blocking acquisition (never wait for a lock if you already hold one) and cooperation (be a good neighbor and release whatever you already acquired if you cannot continue without blocking).

Such a strategy is used in e.g. Boost for acquiring multiple locks at once. Actually, in Boost it's even more advanced: after releasing locks at step 3, they start waiting from the lock that was busy at the previous attempt.

Also, look at these SO topics: Acquire a lock on two mutexes and avoid deadlock, Multiple mutex locking strategies and why libraries don't use address comparison

Answer 2

These kind of problems are usually solved when we organize resources into some kind of hierarchy. You have three resources, {A, B, C}, and we can decide that A is on the top of hierarchy, and C is at the bottom. Now there are two approaches:

Pessimistic: if I need resource X then I must also acquire all resources that are above X, even if I don't need them at this time. The reason is that I might need them at some other time, while still holding the resource X.

Optimistic: if I need resource X then acquire it. If later I need resource X-below, then acquire it as well, no problem there. But, if after X I need resource X-above then tough luck, I can't have it while holding resource X, but I could release resource X, and then first acquire X-above, and after that X again.

If all processes respect the hierarchy of resources then deadlock cannot occur.

Answer 3

You need to decide on an order the resources will be acquired and then always acquire them in the same order.

Using your example, the resources should always be acquired in the order A, B, C. So, for example:

P1 => A
P2 => A C
P3 => C
P4 => B C
P5 => B
P6 => A B
P7 => A B C

This way there will never be a scenario where all the processes are holding one resource and waiting on a resource that another process has.

In a more simple scenario:

P1 => A B
P2 => B C

Here both process will get their first resource, but process P1 will block because P2 has B, However, P2 will be able to acquire C and will make progress. At some point it will release C which will allow P1 to proceed.

If you don't acquire them in a fixed order then you can get something like the following:

P1 => A B
P2 => B A

Now each process has locked on one resource and is waiting for the other process to release the resource it needs, causing a deadlock.