§31.5–31.8Reader-Writer Locks … Summary

We close the semaphore tour with a flexible lock, the most famous concurrency puzzle of all, and a look under the hood.

31.5 Reader-Writer Locks

Sometimes one lock is too blunt: many operations only read a structure and could safely run together; only writes need exclusivity. A reader-writer lock reader-writer lock A lock that permits many readers to access a data structure concurrently but grants a writer exclusive access. Built from semaphores: the FIRST reader acquires the write lock (blocking writers) and the LAST reader releases it. Simple, but can starve writers and often costs more than a plain lock. defined in ch. 31 — open in glossary captures that — many readers OR one writer:

typedef struct _rwlock_t {
    sem_t lock;      // binary semaphore, guards `readers`
    sem_t writelock; // held while ANY reader or the writer is active
    int   readers;   // # readers currently inside
} rwlock_t;

void rwlock_acquire_readlock(rwlock_t *rw) {
    sem_wait(&rw->lock);
    rw->readers++;
    if (rw->readers == 1)          // FIRST reader...
        sem_wait(&rw->writelock);  // ...grabs the writelock
    sem_post(&rw->lock);
}
void rwlock_release_readlock(rwlock_t *rw) {
    sem_wait(&rw->lock);
    rw->readers--;
    if (rw->readers == 0)          // LAST reader...
        sem_post(&rw->writelock);  // ...releases it
    sem_post(&rw->lock);
}
void rwlock_acquire_writelock(rwlock_t *rw) { sem_wait(&rw->writelock); }
void rwlock_release_writelock(rwlock_t *rw) { sem_post(&rw->writelock); }

The clever bit is the first/last reader dance with writelock:

It works, but note the fairness flaw the trace ends on: as long as readers keep arriving, readers never hits 0, so a waiting writer can starve. (A better version blocks new readers once a writer is waiting.) And reader-writer locks often aren’t worth it — the extra overhead can outweigh the concurrency gained.

31.6 The Dining Philosophers

Dijkstra’s famous puzzle — the dining philosophers dining philosophers Dijkstra's classic concurrency problem: five philosophers around a table with one fork between each pair; each needs both neighboring forks to eat. The naive 'grab left then right' solution deadlocks (all hold their left fork, all wait forever for their right). Breaking the symmetry — one philosopher grabs right-then-left — removes the cycle. defined in ch. 31 — open in glossary — impractical, but a rite of passage (and a favorite interview question). Five philosophers, five forks; each alternates thinking and eating, and needs both neighboring forks to eat. The loop:

while (1) {
    think();
    get_forks(p);
    eat();
    put_forks(p);
}
int left(int p)  { return p; }
int right(int p) { return (p + 1) % 5; }

The naive get_forks — grab left, then right — deadlocks. Walk it:

void get_forks(int p) {
    sem_wait(&forks[left(p)]);
    sem_wait(&forks[right(p)]);
}

void get_forks(int p) {
    if (p == 4) { // highest grabs right first
        sem_wait(&forks[right(p)]);
        sem_wait(&forks[left(p)]);
    } else {
        sem_wait(&forks[left(p)]);
        sem_wait(&forks[right(p)]);
    }
}

Changing the acquisition order for just one philosopher breaks the circular dependency — no cycle can form, so no deadlock. (put_forks stays the same.) We’ll see this “break the cycle” idea generalized in the next chapter on deadlock.

31.7 Thread Throttling

A humbler use: throttling thread throttling Admission control via a semaphore: initialize it to N and bracket a region of code with sem_wait()/sem_post() to cap how many threads run that region at once — e.g. keeping a memory-intensive section from over-committing memory and thrashing. defined in ch. 31 — open in glossary (admission control). To keep “too many” threads out of a dangerous region — say a memory-hungry section that would exhaust RAM and trigger thrashing if all threads entered at once — initialize a semaphore to the maximum you’ll allow, and bracket the region with sem_wait()/sem_post(). The semaphore naturally caps concurrency at that number.

31.8 How To Implement Semaphores

Finally, we can build a semaphore from the primitives it generalizes — one lock, one condition variable, and a value (the authors dub it a “Zemaphore”):

typedef struct __Zem_t {
    int value;
    pthread_cond_t cond;
    pthread_mutex_t lock;
} Zem_t;

void Zem_wait(Zem_t *s) {
    Mutex_lock(&s->lock);
    while (s->value <= 0)
        Cond_wait(&s->cond, &s->lock);
    s->value--;
    Mutex_unlock(&s->lock);
}
void Zem_post(Zem_t *s) {
    Mutex_lock(&s->lock);
    s->value++;
    Cond_signal(&s->cond);
    Mutex_unlock(&s->lock);
}

One deliberate difference from Dijkstra’s semaphore: the Zemaphore’s value never goes below 0, so it doesn’t track the waiter count — this is simpler and matches Linux. Curiously, the reverse — building a condition variable out of semaphores — is famously hard; even expert concurrent programmers got it wrong.

31.9 Summary

Semaphores are a powerful, flexible primitive — some programmers use them for everything, shunning locks and CVs. We’ve seen just a few classics (fork/join, bounded buffer, reader-writer, dining philosophers, throttling); Downey’s free Little Book of Semaphores has many more.