Chapter 14: Classic Interview Problem: Readers-Writers

Why this matters

Chapter 6 introduced the reader-writer pattern with a working implementation; this chapter treats it as the interview problem it commonly is — specifically probing whether you can identify and articulate the starvation trade-off between different valid solutions, which is the real depth this problem tests beyond "can you write a lock."

The problem, precisely stated

"Design synchronization for a shared resource where multiple readers can access it concurrently, but a writer needs exclusive access. Implement acquire_read/release_read and acquire_write/release_write."

The "readers-preference" solution

[BEGINNER] Chapter 6's implementation is a readers-preference solution: as long as at least one reader is active, new readers can keep joining freely, and a writer must wait until all readers finish:

class ReadersPreferenceLock:
    def __init__(self):
        self._readers = 0
        self._read_lock = threading.Lock()
        self._write_lock = threading.Lock()

    def acquire_read(self):
        with self._read_lock:
            self._readers += 1
            if self._readers == 1:
                self._write_lock.acquire()

    def release_read(self):
        with self._read_lock:
            self._readers -= 1
            if self._readers == 0:
                self._write_lock.release()

    def acquire_write(self):
        self._write_lock.acquire()

    def release_write(self):
        self._write_lock.release()

The problem a strong candidate identifies proactively: "This solution can starve writers — if readers arrive frequently enough that the reader count never drops to zero, a waiting writer could wait indefinitely, even though no individual reader holds the resource for very long. This is exactly the starvation hazard from Chapter 3, and it's a real risk in genuinely read-heavy production workloads, not just a theoretical concern."

The "writers-preference" solution

[SENIOR INSIGHT] A different valid solution inverts the priority: once a writer is waiting, no new readers are allowed to start (though already-in-progress reads are allowed to finish), ensuring the writer doesn't wait indefinitely behind a continuous stream of new readers:

class WritersPreferenceLock:
    def __init__(self):
        self._readers = 0
        self._writers_waiting = 0
        self._read_lock = threading.Lock()
        self._write_lock = threading.Lock()
        self._writers_waiting_lock = threading.Lock()

    def acquire_read(self):
        with self._writers_waiting_lock:
            pass  # if a writer is waiting/active, THIS blocks new readers from proceeding here
        with self._read_lock:
            self._readers += 1
            if self._readers == 1:
                self._write_lock.acquire()

    def release_read(self):
        with self._read_lock:
            self._readers -= 1
            if self._readers == 0:
                self._write_lock.release()

    def acquire_write(self):
        with self._writers_waiting_lock:
            self._writers_waiting += 1
            if self._writers_waiting == 1:
                pass  # (illustrative -- a complete implementation blocks new readers here)
        self._write_lock.acquire()

    def release_write(self):
        self._write_lock.release()
        with self._writers_waiting_lock:
            self._writers_waiting -= 1

The trade-off this introduces, which a strong candidate names explicitly: writers-preference solves writer starvation, but can now starve readers instead — if writers arrive frequently enough, new readers might wait indefinitely behind a continuous stream of writers, even though reads are typically fast and could otherwise proceed concurrently with each other.

The fair (FIFO) solution: the actual resolution

[BEGINNER] Neither preference-based solution eliminates starvation — each simply moves it to the other side. The complete, genuinely fair fix (matching Chapter 3's standard starvation remedy) processes requests in strict arrival order, regardless of whether they're reads or writes: a group of consecutive readers that arrived before a writer are all allowed to proceed together (since reads don't conflict with each other), but once a writer's request has arrived, subsequent readers must wait behind it, and vice versa.

import threading

class FairReadWriteLock:
    """Fair: requests are granted access in strict arrival order, using a single
    lock to serialize request ORDERING even though the actual work (reads)
    may proceed concurrently once granted."""
    def __init__(self):
        self._order_lock = threading.Lock()  # protects the ticket-taking process itself
        self._resource_lock = threading.Lock()  # the actual read/write exclusion
        self._readers = 0
        self._readers_lock = threading.Lock()

    def acquire_read(self):
        with self._order_lock:  # take a "ticket" -- ensures FIFO ordering with writers
            with self._readers_lock:
                self._readers += 1
                if self._readers == 1:
                    self._resource_lock.acquire()

    def release_read(self):
        with self._readers_lock:
            self._readers -= 1
            if self._readers == 0:
                self._resource_lock.release()

    def acquire_write(self):
        with self._order_lock:  # take a "ticket" -- ensures FIFO ordering with readers
            self._resource_lock.acquire()

    def release_write(self):
        self._resource_lock.release()

[IN PRACTICE] This simplified sketch conveys the core idea (a single ordering gate that both readers and writers must pass through in arrival order) — production-grade fair reader-writer locks (available in most languages' standard/concurrent libraries) implement this more efficiently and completely, and the practical lesson for real code is the same as Chapter 5's "prefer standard library implementations" advice: use a well-tested fair reader-writer lock from your language's standard library rather than hand-rolling one, reserving the from-scratch version specifically for interview/learning contexts like this chapter.

Common mistakes

1. Presenting only the readers-preference solution without proactively identifying its writer-starvation risk — this is the single most important insight the problem is testing for, and failing to mention it unprompted is a significant missed signal.
2. "Fixing" writer starvation by simply switching to writers-preference, without recognizing this introduces a symmetric reader-starvation risk — presenting this as a complete, unconditional fix rather than a different trade-off is a common, incomplete answer.
3. Not connecting this problem back to Chapter 3's general starvation hazard and its standard fix (fairness/FIFO ordering) — recognizing the specific instance as an example of the general pattern is a stronger signal than solving it as an isolated puzzle.
4. Implementing a real production system with a hand-rolled reader-writer lock instead of a standard library implementation — appropriate for demonstrating understanding in an interview, but not the right default for actual production code (Chapter 5's broader lesson).

Discussion / interview questions

1. "Implement a basic reader-writer lock, and then identify a fairness problem with your implementation." Strong answer: Implements readers-preference (or writers-preference) correctly, then proactively identifies that it can starve the disfavored side (writers, in the readers-preference case) — showing awareness that the initial "correct" solution isn't the complete picture.

2. "What's the trade-off between readers-preference and writers-preference reader-writer locks?" Strong answer: Readers-preference maximizes read concurrency but risks starving writers under continuous read load; writers-preference prevents writer starvation but risks starving readers under continuous write load — neither eliminates starvation, each just relocates it to the other side.

3. "How would you design a reader-writer lock that avoids starving either side?" Strong answer: Process requests in strict arrival (FIFO) order regardless of type — consecutive compatible requests (multiple reads) can be granted together, but a writer's arrival blocks subsequent readers until it's served, and vice versa — directly Chapter 3's fairness-based starvation fix, applied to this specific problem.

4. "Would you use a hand-rolled reader-writer lock like the ones discussed here in a real production system? Why or why not?" Strong answer: No — real production code should use a well-tested, standard library reader-writer lock implementation; a hand-rolled version is valuable for demonstrating understanding in an interview or learning context, but carries unnecessary risk of subtle bugs compared to a mature, widely-used implementation.

Chapter summary / cheat sheet

• Readers-preference: maximizes read concurrency, risks writer starvation under continuous read load.
• Writers-preference: prevents writer starvation, risks reader starvation under continuous write load — a different trade-off, not a strictly better fix.
• Fair (FIFO): processes requests in strict arrival order regardless of type — the genuine resolution, directly applying Chapter 3's fairness-based starvation fix to this specific problem.
• The real interview signal: proactively identifying the starvation trade-off in your first solution, not just producing correct-looking code — this problem tests judgment about trade-offs, not just synchronization mechanics.
• Use a standard library reader-writer lock in real production code; reserve hand-rolled implementations for interview/learning contexts.

---