Lock-based Concurrent Data Structures

Protecting Shared State with a Single Lock

A straightforward method to convert a sequential data structure into a concurrent one is wrapping every public operation with acquisition and release of one mutex. This ensures that only one thread at a time can observe or modify the internal state, preserving invariants. The resulting structure is correct but may serialize execution excessively.

Why Coarse-Grained Locking Scales Poorly

On a multiprocessor, threads running on different cores still contend for the same lock cache line, causing frequent cache invalidations and stalls. Consequently, adding more threads often increases total runtime instead of decreasing it, far from the ideal of perfect scaling where extra cores finish extra work in the same wall-clock time.

Reducing Contention via Local Updates

Approximate counters keep a private tally per processor. Most increments touch only the local variable under a per-core lock, which is uncontended if threads stay on their cores. When the local tally hits a threshold it is flushed to a global counter. The global value is therefore slightly stale, yet the design permits much higher throughput because the global lock is acquired infrequently.

Pitfalls

• Omitting the lock on some read paths can introduce data races.
• A coarse-grained lock, while guaranteeing correctness, may become a severe bottleneck.
• Performing potentially long-blocking operations while holding a lock increases the chance of deadlock.

Minimum C11 · complete program · Download .c

#include <stdio.h>
#include <pthread.h>

#define NTHREADS 4
#define NINCS 1000

typedef struct {
    int val;
    pthread_mutex_t mtx;
} ctr_t;

void ctr_init(ctr_t *c) {
    c->val = 0;
    pthread_mutex_init(&c->mtx, NULL);
}

void ctr_inc(ctr_t *c) {
    pthread_mutex_lock(&c->mtx);
    c->val++;
    pthread_mutex_unlock(&c->mtx);
}

int ctr_get(ctr_t *c) {
    pthread_mutex_lock(&c->mtx);
    int v = c->val;
    pthread_mutex_unlock(&c->mtx);
    return v;
}

void *worker(void *arg) { (void)arg;
    ctr_t *c = arg;
    for (int i = 0; i < NINCS; i++)
        ctr_inc(c);
    return NULL;
}

int main(void) {
    ctr_t c;
    ctr_init(&c);
    pthread_t th[NTHREADS];
    for (int i = 0; i < NTHREADS; i++)
        pthread_create(&th[i], NULL, worker, &c);
    for (int i = 0; i < NTHREADS; i++)
        pthread_join(th[i], NULL);
    printf("Final counter: %d\n", ctr_get(&c));
    pthread_mutex_destroy(&c.mtx);
    return 0;
}

Compile locally

gcc -std=c11 -Wall -Wextra -Wpedantic -Werror -pthread ostep-29-locked-data-structures.c -o example && ./example

Expected result

Final counter: 4000

CHECK YOUR UNDERSTANDING

Close the answer. Explain it.

Why cannot a counter protected by a single global lock scale linearly with the number of processors?

Check the sources

• OSTEP chapter PDF

Drafts and official chapters change. The version mark is only the example’s minimum.