Coding Interview: Implement a Thread-Safe Read-Write Lock

Prompt and use cases

Implement a thread-safe read-write lock: multiple readers may hold it concurrently, while a writer must hold it exclusively. Explain the waiting policy, wake-up rules, reentrancy, and how you prevent indefinite writer starvation. You may use a mutex and condition variables, but not a built-in read-write lock.

This question fits backend, infrastructure, and concurrency roles. It tests synchronization invariants and trade-offs rather than a particular programming language.

What the interviewer evaluates

• Whether you define invariants first: at most one active writer, and no active readers while a writer holds the lock.
• Whether “fairness” becomes an executable admission rule.
• Whether you handle spurious wakeups, exceptional paths, recursive acquisition, and upgrade deadlocks.
• Whether you provide complexity, tests, and a boundary for reusing a production standard library.

Clarifications before answering

Confirm whether acquisition must be interruptible or timed, whether a thread may re-enter, whether read-to-write upgrade is required, and whether fairness means strict FIFO or eventual writer progress. If unspecified, propose a minimal non-reentrant, non-upgradable, writer-preference design and state that boundary explicitly.

A 30-second answer

Name the state: activeReaders, activeWriter, and waitingWriters. A reader enters only when there is no writer and no queued writer; a writer enters only when both active counts are empty. Protect every state change with one mutex, and wake either one writer or a reader group on release. Re-check predicates in a while loop after every condition-variable wakeup. Ban read-to-write upgrade unless the API defines an explicit protocol.

Step-by-step solution

State and invariants

activeWriter is a boolean, activeReaders is a non-negative count, and waitingWriters counts queued writers. The key invariant is activeWriter == true implies activeReaders == 0; a writer may enter only when both are empty. The waiting count controls policy and does not mean a lock is held.

Acquisition and release

A reader waits for !activeWriter && waitingWriters == 0; a writer waits for !activeWriter && activeReaders == 0. Re-check after every condition-variable return to handle spurious wakeups. On writer release, signal one writer if any are queued; otherwise broadcast to readers. When the last reader leaves, signal a writer.

~~~text readLock(): mutex.lock() while activeWriter or waitingWriters > 0: readersCondition.wait(mutex) activeReaders += 1 mutex.unlock()

writeLock(): mutex.lock() waitingWriters += 1 while activeWriter or activeReaders > 0: writersCondition.wait(mutex) waitingWriters -= 1 activeWriter = true mutex.unlock()

writeUnlock(): mutex.lock() activeWriter = false if waitingWriters > 0: writersCondition.signal() else: readersCondition.broadcast() mutex.unlock() ~~~

Fairness and throughput

Oracle documents that non-fair mode may indefinitely postpone a reader or writer, while fair mode uses an approximately arrival-order policy and usually gives up throughput. Distinguish “no starvation” from strict FIFO in the interview.

Model answer

I would start with a non-reentrant, writer-preference implementation. One mutex protects all counters. Readers increment only when there is no active or waiting writer; writers wait until both active counts are empty. Every condition-variable return rechecks its predicate in a while loop. On release, signal a writer when one is queued, otherwise broadcast readers. This preserves the exclusion invariant and prevents an endless stream of new readers from cutting ahead of a writer.

I would explicitly reject read-to-write upgrade: a reader waiting for a write lock can prevent other readers from releasing and deadlock. The caller should release the read lock and compete again, or use a separate queued upgrade protocol. For interruption, timeouts, reentrancy, diagnostics, or strict fairness, I would use a documented platform primitive and test its semantics instead of copying an incomplete lock into business code.

Common mistakes

• Replacing while with if, allowing a spurious wakeup to bypass the predicate.
• Ignoring queued writers and admitting readers forever.
• Waking only one reader after a writer release, or broadcasting unconditionally and creating a thundering herd.
• Allowing upgrades without an upgrade queue, so two readers wait on each other.
• Treating tryLock as a fairness guarantee. Oracle explicitly notes that non-blocking tryLock can barge.

Follow-up questions and responses

How do you test the invariants?

Keep an atomic test snapshot: assert zero readers on writer entry and no writer on reader entry. Run randomized reader and writer threads, and record the event sequence whenever an assertion fails.

How do you test writer starvation?

Continuously generate readers while one writer waits. Record the writer’s queue-to-admission time and maximum wait count. The goal is eventual progress, not an arbitrary fixed millisecond promise.

Why not use one ordinary mutex?

An ordinary mutex is simpler and often has steadier latency. A read-write lock can help only when reads dominate and read critical sections are long enough to overlap. Choose with a benchmark, not intuition.

Can it be reentrant?

Track the writer thread and hold count, plus per-thread read counts. That expands upgrade and release rules substantially. If reentrancy is not required, banning it keeps the state space smaller.

What does POSIX add to the discussion?

POSIX exposes separate read-lock and write-lock operations with defined error returns. The implementation must still respect platform rules for priority and recursive behavior; a custom policy should not be presented as a POSIX guarantee.

When should you stop hand-writing it?

When interruption, timeouts, diagnostics, reentrancy, or portability matter, prefer a verified primitive such as Java ReentrantReadWriteLock or POSIX pthreadrwlock*, and record the fairness choice in the review.