A reader-writer lock lets many readers in at once, or exactly one writer. The tempting implementation, "readers may enter whenever no writer is active", has a nasty property: if readers keep arriving, the writer never gets in.
time -> 0 1 2 3 4 5 6 7
R1 [==========]
R2 [==========]
R3 [==========]
R4 [==========]
W ....waiting.............. (never enters)
At every instant there is at least one reader inside, so "no active writer and..." keeps letting new readers in, and the writer waits as long as the traffic lasts. That is writer starvation.
Fixes and what they cost:
- Writer preference: once a writer is waiting, new readers queue behind it. Writers get through; now a stream of writers can starve readers.
- Fair (FIFO) queue: everyone is served in arrival order, readers batched together while adjacent. Starvation is gone; throughput drops slightly, because readers cannot always overtake.
- Avoid the lock: for read-mostly data, replace the structure atomically and let readers use the old copy until they finish.
There is no free lunch, there is only a choice of who you let wait.