A Concurrency Puzzle

This is a concurrency problem I found interesting while working with multi-threaded C++. I would say it sits at an intermediate level (easy enough to reason about, but subtle enough that a naive solution breaks under scrutiny).

The Setup

You have a shared resource accessed by two kinds of threads: readers and writers. The rules are simple:

• Multiple readers can access the resource simultaneously (they don't interfere with each other).
• A writer needs exclusive access (no readers or other writers can be active while it writes).

A function like this gets called from many threads concurrently:

void funny(bool write) {
    if (write) {
        writeOperation();
    } else {
        readOperation();
    }
}

The goal: ensure that while writeOperation is running, no readOperation runs at the same time (and vice versa).

I know what you might be thinking right now. If you know beforehand whether you are going to write, why not stop the reading threads from the outer scope? Sure, you can do that. But what if you can't know:

void funny() {
    bool write = shouldWrite();
    if (write) {
        writeOperation();
    } else {
        readOperation();
    }
}

Now you can't lock from the outside (the branch hasn't happened yet). The synchronization has to live inside funny, which makes it a more interesting problem.

For simplicity I'll focus on the first variant, where the flag is known upfront. The second is structurally the same, just more tedious to wire up at the call site.

The Semaphore

The solution is a custom semaphore that tracks active readers and whether a write is in progress:

/**
 * Multiple-reader / single-writer synchronization primitive.
 */
struct Semaphore {
    std::mutex              mtx;
    std::condition_variable readFree;
    std::condition_variable writeFree;

    bool             blocked        = false;
    std::atomic<int> currentReaders = 0;

    // Called before entering a write region.
    // Returns the lock so the caller keeps the critical section alive.
    std::unique_lock<std::mutex> write() {
        // Acquire the mutex (no other read() or write() can get past here).
        std::unique_lock<std::mutex> lck(mtx);

        // Wait until all in-flight readers are done.
        // Note: while waiting, the mutex is released, so new readers can still
        // enter (blocked is still false). This means a continuous stream of
        // readers could starve a writer (a known limitation of this design).
        writeFree.wait(lck, [this]() { return currentReaders == 0; });

        // Mutex is reacquired here. Set blocked so that readers arriving
        // after the lock is returned to the caller will wait on readFree
        // instead of entering.
        blocked = true;
        return lck;
    }

    void writeFinished(std::unique_lock<std::mutex>& lck) {
        // Still holding the mutex here (safe to clear the flag).
        blocked = false;
        lck.unlock();
        readFree.notify_all(); // wake any readers that were waiting
    }

    // Called before entering a read region.
    void read() {
        std::unique_lock<std::mutex> lck(mtx);

        // Wait if a write is in progress.
        readFree.wait(lck, [this]() { return !blocked; });

        currentReaders++;
        // Release the mutex so other readers can enter concurrently.
        lck.unlock();
    }

    void readFinished() {
        // std::atomic makes this decrement safe without holding the mutex.
        currentReaders--;
        // Notify any writer that was waiting for readers to drain.
        writeFree.notify_all();
    }
};

How It Works

Write path: acquiring the mutex prevents any new readers or writers from getting in. The writer waits for currentReaders to reach zero, but while waiting it releases the mutex, which means new readers can still enter since blocked is not yet set. Once the predicate is satisfied, the mutex is reacquired and blocked is set to true. The lock is then returned to the caller so the write operation runs inside the critical section. When done, writeFinished clears blocked, drops the lock, and wakes all waiting readers.

Read path: a reader acquires the mutex only long enough to check blocked and increment currentReaders, then releases it immediately. This is the key insight: multiple readers can be inside readOperation simultaneously because they hold the mutex only during entry bookkeeping, not during the actual work.

Why std::atomic for currentReaders? Multiple readers decrement it in readFinished without holding the mutex. The atomic ensures those concurrent decrements don't corrupt the counter.

Writer starvation: if readers arrive continuously, a waiting writer may never see currentReaders == 0. This design doesn't protect against that. For production use, you'd want a fairness mechanism (for example, a writer could set a pendingWrite flag before waiting, and new readers would check that flag and yield).

Usage

Semaphore sem;

void funny(bool write) {
    if (write) {
        auto lck = sem.write();
        writeOperation();
        sem.writeFinished(lck);
    } else {
        sem.read();
        readOperation();
        sem.readFinished();
    }
}

One thing worth noting: if writeOperation or readOperation throws, writeFinished / readFinished won't be called and the semaphore will be left in a broken state. A production version should wrap those calls in a RAII guard. But for understanding the core mechanism, the code above captures it cleanly.