Implement a read-write lock, then keep waiting writers from starving

Implement a read-write lock by hand. Any number of threads may hold it for reading at the same time, but a thread that holds it for writing needs exclusive access: no readers and no other writer. Build it from lower-level primitives, such as a mutex and condition variables, rather than a library read-write lock. This was the multithreading coding exercise of a technical screen, followed by a starvation follow-up. ### Clarifying Questions - Which primitives may I use: a mutex and condition variables, semaphores, or only atomic operations? - Must the lock be reentrant, so that a thread that already holds it for reading can acquire it again? - May a reader upgrade to a writer without releasing first? - Are timed or non-blocking acquisitions (a `try_acquire` with a timeout) required? - Should misuse, such as releasing a lock the thread does not hold, be detected? ### Part 1 — A correct read-write lock Implement `acquire_read()`, `release_read()`, `acquire_write()` and `release_write()` so that readers share the lock and a writer gets exclusive access. ```hint Name the state Decide which few variables describe the lock completely, and the exact condition each kind of waiting thread needs before it may proceed. ``` #### What This Part Should Cover - The invariants the lock maintains and the shared state that encodes them - Blocking without busy-waiting, with correct behavior under spurious wakeups - Which waiting threads are woken on each release, and why ### Part 2 — Keep writers from starving With a straightforward Part 1 lock, a steady stream of readers whose read sections overlap can keep a waiting writer out forever. Change the lock so that a writer that is waiting is guaranteed to get the lock eventually. ```hint Look at the arriving reader Starvation happens because new readers keep joining while earlier ones are still inside. Ask what an arriving reader would need to know in order to behave differently. ``` #### What This Part Should Cover - The mechanism that guarantees a waiting writer progress, and where its state is updated - Whether readers can now starve, and what fairness the lock provides overall - How the change interacts with reentrant reads and with timed-out waiters ### What a Strong Answer Covers - Correct exclusion between writers, and between writers and readers, with all shared state guarded by one mutex - Condition-variable waits in loops that recheck their predicate - A writer-starvation fix that works, explained with a concrete interleaving - An honest account of the remaining fairness trade-off and of deadlock risks (reentrancy, upgrades) - A way to test it: invariant checks under stress, and a test that a writer gets in while readers keep arriving ### Follow-up Questions - Under your Part 2 lock, can readers starve? How would you make the lock fair to both sides? - A thread holding a read lock calls `acquire_read()` again while a writer is waiting. What happens, and how would you fix it? - Two readers both try to upgrade to a write lock. What goes wrong, and how do libraries avoid it? - The workload is almost all reads on many cores. Why might the lock still scale poorly, and what would you change?