Writer Starvation and the No-Starve Solution

Key Insight
The basic solution can starve writers. Adding a turnstile semaphore ensures waiting writers eventually get access.
Writer Starvation Problem
Continuous stream of readers blocks writer foreverR1 readingR2 entersR3 entersR1 leaves, R4 enters... forever ...WriterWAITINGforever...No-Starve SolutionAdd turnstile semaphoreWriter locks turnstileNew readers must wait
The Starvation Scenario
Readers R1, R2 are reading. Writer W arrives, waits on roomEmpty. R3 arrives, enters (R count still > 0). R1 leaves but R4 arrives. The room is never empty because new readers sneak in before the last leaves.
The Turnstile Solution
Add a turnstile semaphore. Writer locks it when waiting. New readers must pass through the turnstile. Once locked, new readers queue behind the writer. When current readers finish, writer enters, writes, unlocks turnstile, and queued readers proceed.
Fairness Trade-off
The turnstile gives writers a way to "cut the line." But it does not prioritize: readers and writers are served roughly in arrival order. This is fair but may not be optimal for all workloads.
Pattern: Add a turnstile semaphore. Readers: turnstile.wait() turnstile.signal() then lightswitch. Writers: turnstile.wait() then roomEmpty.wait(), write, roomEmpty.signal() turnstile.signal().

💡 Key Takeaways

✓Basic solution allows writer starvation: if readers continuously arrive before last reader exits, writer waits on roomEmpty forever while readers keep entering freely

✓Starvation is not deadlock (threads make progress) but violates bounded waiting; manifests as write latency spikes during read-heavy workloads where writes hang for seconds

✓No-starve solution adds turnstile semaphore: writer holds turnstile while waiting on roomEmpty, blocking new readers at turnstile instead of letting them enter room

✓Writer code: turnstile.wait(), roomEmpty.wait(), critical section, turnstile.signal(), roomEmpty.signal(); reader code: turnstile.wait(), turnstile.signal(), then lightswitch pattern

✓Guarantees every waiting writer eventually proceeds after bounded number of threads; exact ordering depends on scheduler (FIFO gives arrival order, random gives probabilistic fairness)

📌 Examples

1Starvation scenario: readers R1, R2 in room, writer W1 arrives and waits; R3 arrives and enters (room has readers), R1 leaves, R4 arrives and enters, R2 leaves; cycle continues with W1 never getting in

2No-starve in action: R1, R2 in room, W1 arrives, takes turnstile, blocks on roomEmpty; R3 arrives, blocks on turnstile (not room); R1 and R2 exit, W1 enters; W1 exits, signals turnstile, R3 proceeds

3Production impact: database write during peak traffic (10K reads/sec) might wait 30+ seconds in basic solution; with turnstile, write completes within 2x average read duration because new reads queue

← Back to Readers-Writers Problem Overview