Multithreaded Programming Guide

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;
    while ((current = prev->link) != NULL) {
        if (current->value == value) {
            prev->link = current->link;
            current->link = NULL;
        prev = current;