Fairness

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 Bathroom Problem The Bathroom Problem is a classic coordination puzzle that illustrates fairness, starvation prevention, and group coordination in concurrent systems. First proposed by Jon Kleinberg, it demonstrates how to manage resource access with group-based constraints. The Scenario A unisex bathroom has: Capacity for N people Only people of one gender at a time Random arrivals from multiple genders The rules: Multiple people of the same gender can enter simultaneously (up to capacity) People of different genders cannot be in the bathroom at the same time When empty, either gender can enter Must prevent starvation - no gender should wait forever The Challenge: Fairness vs Throughput The trap is starvation. Consider: ...