test

Multithreaded Programming Guide

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. As shown in Failed Cross Reference Format, there could be a problem if two threads attempt to claim both resources but lock the associated mutexes in different orders. In this 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 Deadlock

Thread 1 

Thread 2 

pthread_mutex_lock(&m1); 

 

/* use resource 1 */ 

 

pthread_mutex_lock(&m2); 

 

/* use resources1 and 2 */ 

 

pthread_mutex_unlock(&m2); 

pthread_mutex_unlock(&m1); 

pthread_mutex_lock(&m2); 

 

/* use resource 2 */ 

 

pthread_mutex_lock(&m1); 

 

/* use resources 1 and 2 */ 

 

pthread_mutex_unlock(&m1); 

pthread_mutex_unlock(&m2); 

The best way to avoid this problem is to make sure that whenever threads lock multiple mutexes, they do so in the same order. 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.

Note -

The lock_lint tool can detect the sort of deadlock problem shown in this example. The best way to avoid such deadlock problems is to use lock hierarchies. When locks are always taken in a prescribed order, deadlock should not occur.

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.

Failed Cross Reference Format shows how this is done.

Example 4-3 Conditional Locking

Thread 1 

Thread 2 

pthread_mutex_lock(&m1); pthread_mutex_lock(&m2); 

 

 

 

 

/* no processing */ 

 

pthread_mutex_unlock(&m2); 

pthread_mutex_unlock(&m1);  

for (; ;) 

{ pthread_mutex_lock(&m2); 

 

 

if(pthread_mutex_trylock(&m1)==0) 

/* got it! */  

break;  

/* didn't get it */ 

pthread_mutex_unlock(&m2); 

} 

/* get locks; no processing */ 

pthread_mutex_unlock(&m1); 

pthread_mutex_unlock(&m2); 

In this example, 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.