Readers-Writers

The Fairness Problem We’ve seen two extremes: Readers preference: Writers can starve Writers preference: Readers can starve The fair solution ensures no starvation - everyone gets served in the order they arrive. The Solution: FIFO Ordering Key idea: Use a queue to serve requests in arrival order. This prevents both reader and writer starvation. Arrival Order: R1, R2, W1, R3, R4, W2 Execution: R1+R2 → W1 → R3+R4 → W2 (batch) (excl) (batch) (excl) Consecutive readers can still batch together, but writers don’t get skipped! ...

The Readers-Writers Problem The Readers-Writers problem is fundamental in concurrent systems where data is shared between multiple threads: Readers: Can access data simultaneously (read-only, no conflicts) Writers: Need exclusive access (modifications can’t overlap) The challenge: Maximize concurrency while maintaining data integrity. Real-World Applications This pattern is everywhere: Databases: SELECT queries (readers) vs UPDATE/INSERT (writers) Caching: Cache reads vs cache updates Configuration: Reading config vs reloading config File systems: Multiple readers, exclusive writes Web servers: Read sessions vs update sessions Readers Preference Solution In this variant, readers get priority: ...

The Writer Starvation Problem In the readers preference solution, we saw how continuous readers can starve writers. The writers preference solution fixes this by giving writers priority. Key idea: When a writer is waiting, no new readers are allowed to start, even if other readers are currently reading. Real-World Need for Writer Priority Some systems need writer priority: Databases with critical updates (billing, inventory) Real-time systems (sensor updates must not be delayed) Logging systems (log writes can’t be delayed) Configuration systems (updates must propagate quickly) Leader election (state changes need priority) The Solution Go’s sync.RWMutex uses readers preference, so we need to implement writer preference manually using additional synchronization: ...