Fair Read-Write Locks: The Turnstile Solution

Solution
Add a turnstile that writers can lock. When a writer is waiting, new readers queue behind the turnstile instead of entering.
The Turnstile Idea
All threads (readers and writers) must pass through a turnstile before entering. Normally the turnstile is open - threads pass right through. But a waiting writer locks the turnstile. New readers queue up behind it instead of barging in.
How It Guarantees Fairness
Writer arrives, locks turnstile, waits for current readers to finish. New readers see locked turnstile and queue. When last reader exits, writer enters. Writer finishes, unlocks turnstile. Queued readers proceed. At least one writer gets through before more readers can enter.
Turnstile Blocks New Readers
Critical SectionR1R2finishing upTurnstileLOCKEDWwaitingR3R4R5queued
The Implementation
Reader: Pass through turnstile (may block if writer waiting). Increment reader count. If first reader, lock room from writers. Do work. Decrement count. If last reader, unlock room.
Writer: Lock turnstile (blocks new readers). Wait for room to be empty. Do work. Unlock room. Unlock turnstile (let queued readers through).
Trade-off: Fairness vs Throughput
Fair locks have lower throughput. Readers that could have proceeded now wait for writers. Choose based on your requirements: reader-preference for maximum read throughput, fair for bounded writer latency.
Key Insight: The turnstile creates a checkpoint. Existing readers finish, writer goes, then queued readers proceed. This guarantees writers are not starved.

💡 Key Takeaways

✓Add a turnstile semaphore. Writers lock it while waiting. New readers queue behind locked turnstile.

✓Existing readers finish (they already passed turnstile). No new readers can enter until writer is done.

✓When last reader exits, writer enters. When writer exits, turnstile unlocks. Queued readers proceed.

✓Fair locks guarantee bounded writer wait time. At least one writer proceeds before more readers.

✓Trade-off: fair locks have lower read throughput. Readers wait even though room has space.

📌 Examples

1Database schema migration: Fair lock ensures migration eventually runs, even under query load.

2Config hot-reload: Fair lock guarantees config updates apply within bounded time, not "when traffic stops."

3Cache rebuild: Fair lock ensures cache can be rebuilt without waiting for all reads to cease.

← Back to Read-Write Locks Overview