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);
}