Using Locking Hierarchies

You will occasionally want to access two resources at once. Perhaps you are using one of the resources, and then discover that the other resource is needed as well. There could be a problem if two threads attempt to claim both resources but lock the associated mutexes in different orders. For example, if the two threads lock mutexes 1 and 2 respectively, then a deadlock occurs when each attempts to lock the other mutex. Example 4–2 shows possible deadlock scenarios.

Example 4–2 Deadlock

The best way to avoid this problem is to make sure that whenever threads lock multiple mutexes, they do so in the same order. When locks are always taken in a prescribed order, deadlock should not occur. This technique is known as lock hierarchies: order the mutexes by logically assigning numbers to them.

Also, honor the restriction that you cannot take a mutex that is assigned n when you are holding any mutex assigned a number greater than n.

However, this technique cannot always be used—sometimes you must take the mutexes in an order other than prescribed. To prevent deadlock in such a situation, use pthread_mutex_trylock(). One thread must release its mutexes when it discovers that deadlock would otherwise be inevitable.

Example 4–3 Conditional Locking

In Example 4–3, thread 1 locks mutexes in the prescribed order, but thread 2 takes them out of order. To make certain that there is no deadlock, thread 2 has to take mutex 1 very carefully; if it were to block waiting for the mutex to be released, it is likely to have just entered into a deadlock with thread 1.

To ensure this does not happen, thread 2 calls pthread_mutex_trylock(), which takes the mutex if it is available. If it is not, thread 2 returns immediately, reporting failure. At this point, thread 2 must release mutex 2, so that thread 1 can lock it, and then release both mutex 1 and mutex 2.