Multithreaded Programming Guide

Code Examples of Mutex Locking

Example 4–1 shows some code fragments with mutex locking.


Example 4–1 Mutex Lock Example

#include <pthread.h>

pthread_mutex_t count_mutex;
long long count;

void
increment_count()
{
    pthread_mutex_lock(&count_mutex);
    count = count + 1;
    pthread_mutex_unlock(&count_mutex);
}

long long
get_count()
{
    long long c;
    
    pthread_mutex_lock(&count_mutex);
    c = count;
    pthread_mutex_unlock(&count_mutex);
    return (c);
}

The two functions in Example 4–1 use the mutex lock for different purposes. The increment_count() function uses the mutex lock to ensure an atomic update of the shared variable. The get_count() function uses the mutex lock to guarantee that the 64-bit quantity count is read atomically. On a 32-bit architecture, a long long is really two 32-bit quantities.

When you read an integer value, the operation is atomic because an integer is the common word size on most machines.

Examples of Using Lock Hierarchies

Occasionally, you might 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. A problem exists 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, a deadlock occurs when each attempts to lock the other mutex. Example 4–2 shows possible deadlock scenarios.


Example 4–2 Deadlock

Thread 1 

Thread 2 

pthread_mutex_lock(&m1);

/* use resource 1 */


pthread_mutex_lock(&m2);


/* use resources 1 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 when threads lock multiple mutexes, the threads do so in the same order. When locks are always taken in a prescribed order, deadlock should not occur. This technique, known as lock hierarchies, orders the mutexes by logically assigning numbers to the mutexes.

Also, honor the restriction that you cannot take a mutex that is assigned n when you are holding any mutex assigned a number that is 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 the thread discovers that deadlock would otherwise be inevitable.


Example 4–3 Conditional Locking

thread1 

thread2 

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 Example 4–3, thread1 locks mutexes in the prescribed order, but thread2 takes the mutexes out of order. To make certain that no deadlock occurs, thread2 has to take mutex1 very carefully. If thread2 blocks while waiting for the mutex to be released, thread2 is likely to have just entered into a deadlock with thread1.

To ensure that thread2 does not enter into a deadlock, thread2 calls pthread_mutex_trylock(), which takes the mutex if available. If the mutex is not available, thread2 returns immediately, reporting failure. At this point, thread2 must release mutex2. Thread1 can now lock mutex2, and then release both mutex1 and mutex2.

Examples of Using Nested Locking With a Singly-Linked List

Example 4–4 and Example 4–5 show how to take three locks at once. Deadlock is prevented 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 that contains a mutex. To remove a node from the list, first search the list starting at ListHead until the desired node is found. ListHead is never removed.

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, a deadlock cannot occur 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);
}

Example of Nested Locking With a Circularly-Linked List

Example 4–6 modifies the previous list structure by converting the list structure into a circular list. Because a distinguished head node no longer exists, a thread can be associated with a particular node and can perform operations on that node and its neighbor 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 that involves both locks.


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_trylock(&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);
}