§29.2–29.3Concurrent Linked Lists … Concurrent Queues

The counter taught the pattern: start with one big lock, refine only if you must. Now the same story for the structures threads actually pass around — lists, queues, hash tables — where where you lock starts to really matter.

29.2 Concurrent Linked Lists

Focus on insert and lookup. The obvious version takes the lock on entry and drops it on exit — but watch the error path:

int List_Insert(list_t *L, int key) {
    pthread_mutex_lock(&L->lock);
    node_t *new = malloc(sizeof(node_t));
    if (new == NULL) {
        perror("malloc");
        pthread_mutex_unlock(&L->lock); // must
        return -1;                      // unlock
    }                                   // on the
    new->key  = key;                    // error
    new->next = L->head;                // path too!
    L->head   = new;
    pthread_mutex_unlock(&L->lock);
    return 0;
}

void List_Insert(list_t *L, int key) {
    // synchronization not needed
    node_t *new = malloc(sizeof(node_t));
    if (new == NULL) {
        perror("malloc");
        return;              // no unlock needed!
    }
    new->key = key;

    // just lock the critical section
    pthread_mutex_lock(&L->lock);
    new->next = L->head;
    L->head   = new;
    pthread_mutex_unlock(&L->lock);
}

The rewrite works because malloc() is itself thread-safe — only the shared-list update truly needs the lock. Pulling allocation outside the lock means the malloc-failure path no longer has a lock to release, so the easy-to-forget unlock-before-return simply vanishes. That matters: a study of Linux kernel patches found nearly 40% of bugs live on such rarely-taken error paths. lookup gets the same treatment — one lock/unlock around a single common exit instead of an unlock at every return.

Scaling linked lists: hand-over-hand locking

One big lock serializes the whole list. Researchers tried hand-over-hand locking hand-over-hand locking Lock coupling: one lock per list node instead of one lock for the whole list. A traversal grabs the next node's lock before releasing the current node's, enabling overlapping traversals — though per-node acquire/release overhead usually loses to a single big lock in practice. defined in ch. 29 — open in glossary (a.k.a. lock coupling): a lock per node, grabbing the next node’s lock before releasing the current one. Step through the motion:

Conceptually it enables lots of concurrency. In practice it is hard to beat a single lock: acquiring and releasing a lock at every node of a traversal is so expensive that even large lists and many threads rarely come out ahead. Perhaps a hybrid — a new lock every few nodes — would pay off. (Measure before believing.)

29.3 Concurrent Queues

For a queue you could just add one big lock (you know how by now). Michael and Scott did better: two locks — one for the head, one for the tail — so enqueues and dequeues can run at the same time. The enabling trick is a dummy node, allocated at init, that separates the head and tail operations:

typedef struct __queue_t {
    node_t          *head;
    node_t          *tail;
    pthread_mutex_t head_lock, tail_lock;
} queue_t;

void Queue_Init(queue_t *q) {
    node_t *tmp = malloc(sizeof(node_t));  // the dummy
    tmp->next = NULL;
    q->head = q->tail = tmp;               // both point at it
    pthread_mutex_init(&q->head_lock, NULL);
    pthread_mutex_init(&q->tail_lock, NULL);
}

void Queue_Enqueue(queue_t *q, int value) {
    node_t *tmp = malloc(sizeof(node_t));
    tmp->value = value;
    tmp->next  = NULL;
    pthread_mutex_lock(&q->tail_lock);     // tail end only
    q->tail->next = tmp;
    q->tail = tmp;
    pthread_mutex_unlock(&q->tail_lock);
}

int Queue_Dequeue(queue_t *q, int *value) {
    pthread_mutex_lock(&q->head_lock);     // head end only
    node_t *tmp = q->head;
    node_t *new_head = tmp->next;
    if (new_head == NULL) {
        pthread_mutex_unlock(&q->head_lock);
        return -1;                         // queue was empty
    }
    *value = new_head->value;
    q->head = new_head;
    pthread_mutex_unlock(&q->head_lock);
    free(tmp);
    return 0;
}

Watch enqueue touch only tail_lock and dequeue only head_lock — and, crucially, run at the same time:

This locks-only queue is common, but it still can’t make a thread wait when the queue is empty or full — a bounded, blocking queue is exactly the job of condition variables in the next chapter. Watch for it.

Choosing a strategy