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.

Nested Locking With a Singly Linked List

Example 4-4 and Example 4-5 show how to take three locks at once, but prevent deadlock by taking the locks in a prescribed order.

Example 4-4 Singly Linked List Structure

typedef struct node1 {
    int value;
    struct node1 *link;
    pthread_mutex_t lock;
} node1_t;

node1_t ListHead;

This example uses a singly linked list structure with each node containing a mutex. To remove a node from the list, first search the list starting at ListHead (which itself is never removed) until the desired node is found.

To protect this search from the effects of concurrent deletions, lock each node before any of its contents are accessed. Because all searches start at ListHead, there is never a deadlock because the locks are always taken in list order.

When the desired node is found, lock both the node and its predecessor since the change involves both nodes. Because the predecessor's lock is always taken first, you are again protected from deadlock. Example 4-5 shows the C code to remove an item from a singly linked list.

Example 4-5 Singly Linked List With Nested Locking

node1_t *delete(int value)
{
    node1_t *prev, *current;

    prev = &ListHead;
    pthread_mutex_lock(&prev->lock);
    while ((current = prev->link) != NULL) {
        pthread_mutex_lock(&current->lock);
        if (current->value == value) {
            prev->link = current->link;
            pthread_mutex_unlock(&current->lock);
            pthread_mutex_unlock(&prev->lock);
            current->link = NULL;
            return(current);
        }
        pthread_mutex_unlock(&prev->lock);
        prev = current;
    }
    pthread_mutex_unlock(&prev->lock);
    return(NULL);
}

Nested Locking With a Circular Linked List

Example 4-6 modifies the previous list structure by converting it into a circular list. There is no longer a distinguished head node; now a thread might be associated with a particular node and might perform operations on that node and its neighbor. Note that lock hierarchies do not work easily here because the obvious hierarchy (following the links) is circular.

Example 4-6 Circular Linked List Structure

typedef struct node2 {
    int value;
    struct node2 *link;
    pthread_mutex_t lock;
} node2_t;

Here is the C code that acquires the locks on two nodes and performs an operation involving both of them.

Example 4-7 Circular Linked List With Nested Locking

void Hit Neighbor(node2_t *me) {
    while (1) {
        pthread_mutex_lock(&me->lock);
        if (pthread_mutex_lock(&me->link->lock)!= 0) {
            /* failed to get lock */             
            pthread_mutex_unlock(&me->lock);              
            continue;         
        }         
        break;     
    }     
    me->link->value += me->value;     
    me->value /=2;     
    pthread_mutex_unlock(&me->link->lock);     
    pthread_mutex_unlock(&me->lock);
}

Condition Variable Attributes

Use condition variables to atomically block threads until a particular condition is true. Always use condition variables together with a mutex lock.

With a condition variable, a thread can atomically block until a condition is satisfied. The condition is tested under the protection of a mutual exclusion lock (mutex).

When the condition is false, a thread usually blocks on a condition variable and atomically releases the mutex waiting for the condition to change. When another thread changes the condition, it can signal the associated condition variable to cause one or more waiting threads to wake up, acquire the mutex again, and reevaluate the condition.

Condition variables can be used to synchronize threads among processes when they are allocated in memory that can be written to and is shared by the cooperating processes.

The scheduling policy determines how blocking threads are awakened. For the default SCHED_OTHER, threads are awakened in priority order.

The attributes for condition variables must be set and initialized before the condition variables can be used. The functions that manipulate condition variable attributes are listed in Table 4-4.

Table 4-4 Condition Variable Attributes

The differences between Solaris and POSIX threads, when defining the scope of a condition variable, are shown in Table 4-5.

Table 4-5 Condition Variable Scope Comparison

Initialize a Condition Variable Attribute

pthread_condattr_init(3THR)

Use pthread_condattr_init(3THR) to initialize attributes associated with this object to their default values. Storage for each attribute object is allocated by the threads system during execution. The default value of the pshared attribute when this function is called is PTHREAD_PROCESS_PRIVATE, which means that the initialized condition variable can be used within a process.

Prototype:
int	pthread_condattr_init(pthread_condattr_t *cattr);

#include <pthread.h>
pthread_condattr_t  cattr;
int ret;

/* initialize an attribute to default value */
ret = pthread_condattr_init(&cattr); 

cattr is an opaque data type that contains a system-allocated attribute object. The possible values of cattr's scope are PTHREAD_PROCESS_PRIVATE (the default) and PTHREAD_PROCESS_SHARED.

Before a condition variable attribute can be reused, it must first be reinitialized by pthread_condattr_destroy(3THR). The pthread_condattr_init() call returns a pointer to an opaque object. If the object is not destroyed, a memory leak will result.