§29.1Concurrent Counters

Before we leave locks behind, a practical detour: how do you actually use them to make everyday data structures safe for many threads at once? Adding locks so a structure can be shared is what makes it thread safe thread safe A data structure with locks added so multiple threads may use it concurrently and still get correct results. Exactly where the locks go decides both correctness and performance. defined in ch. 29 — open in glossary — but where you put them decides both whether it is correct and whether it is fast.

This is a decades-deep research area (thousands of papers; Moir and Shavit’s survey is the classic map). We take a guided tour of four everyday structures — counter, list, queue, hash table — each starting from the dumbest correct design and refining only when measurement forces us to.

29.1 Concurrent Counters

A counter is about the simplest structure there is. Without locks it is trivial — and completely unsafe under threads:

typedef struct __counter_t {
    int value;
} counter_t;

void init(counter_t *c) {
    c->value = 0;
}
void increment(counter_t *c) {
    c->value++;
}
void decrement(counter_t *c) {
    c->value--;
}
int get(counter_t *c) {
    return c->value;
}

typedef struct __counter_t {
    int value;
    pthread_mutex_t lock;
} counter_t;

void init(counter_t *c) {
    c->value = 0;
    Pthread_mutex_init(&c->lock, NULL);
}
void increment(counter_t *c) {
    Pthread_mutex_lock(&c->lock);
    c->value++;
    Pthread_mutex_unlock(&c->lock);
}
// decrement/get: same lock/unlock bracket

The safe version follows the simplest possible pattern: one lock, acquired on entry to every routine and released on return — exactly what a monitor does automatically around object methods. You now have a working concurrent counter. If it is fast enough, you are done — never add complexity a simple design already handles.

Simple, but not scalable

The trouble is performance. Benchmark it: each thread increments a single shared counter one million times, on a four-CPU iMac, varying the thread count. Ideally, more CPUs finish the same-per-thread work in the same wall-clock time — that ideal is called perfect scaling perfect scaling Threads finish work on many CPUs just as fast as one thread does its share on one CPU — more total work, done in parallel, so wall-clock time does not grow. defined in ch. 29 — open in glossary : the work is done in parallel, so more of it does not take longer.

The single-lock counter does the opposite (the “Precise” line):

One thread does its million updates in about 0.03 seconds; two threads take over five seconds — a catastrophe, and it only worsens with more threads. All the work serializes through a single lock.

Scalable counting: the approximate counter

The fix, studied for years and genuinely load-bearing for real OS performance, is the approximate counter approximate counter A scalable counter (a.k.a. sloppy counter) representing one logical count as per-CPU local counters (each with a local lock) plus a single global counter/lock. Threads bump their local contention-free; a local is flushed to the global and reset once it reaches threshold S — trading accuracy (the global lags by up to CPUs×S) for scalability. defined in ch. 29 — open in glossary (a.k.a. sloppy counter). Represent one logical counter as many physical counters: one local counter per CPU core (each with its own lock), plus a single global counter (with its own lock).

A thread increments its local counter, synchronized only by that local’s lock — so threads on different CPUs never contend. Periodically, to keep the global fresh, a local’s value is transferred to the global (acquire global lock, add, reset local to 0). How often? Governed by a threshold S. Walk the book’s exact trace:

The same trace as a table — the flush rows carry the punchline:

Here is the whole implementation (Figure 29.4). Note update() only reaches for the global lock on the rare threshold crossing, and get() returns the global — approximate, on purpose:

typedef struct __counter_t {
    int             global;            // global count
    pthread_mutex_t glock;             // global lock
    int             local[NUMCPUS];    // per-CPU count
    pthread_mutex_t llock[NUMCPUS];    // ... and locks
    int             threshold;         // update frequency
} counter_t;

void update(counter_t *c, int threadID, int amt) {
    int cpu = threadID % NUMCPUS;
    pthread_mutex_lock(&c->llock[cpu]);
    c->local[cpu] += amt;
    if (c->local[cpu] >= c->threshold) {   // transfer to global
        pthread_mutex_lock(&c->glock);
        c->global += c->local[cpu];
        pthread_mutex_unlock(&c->glock);
        c->local[cpu] = 0;
    }
    pthread_mutex_unlock(&c->llock[cpu]);
}

int get(counter_t *c) {
    pthread_mutex_lock(&c->glock);
    int val = c->global;
    pthread_mutex_unlock(&c->glock);
    return val;                            // only approximate!
}

The threshold S is the whole knob

S trades accuracy against performance. Small S ≈ the non-scalable counter (accurate global, constant flushing); large S ≈ excellent scalability, but the global can lag the truth by up to CPUs × S:

With S = 1024 the approximate counter’s four-million-updates-on-four-CPUs time is hardly higher than one thread’s million updates on one CPU — near-perfect scaling, from a structure that only occasionally synchronizes.