Part 3 of 7 · 2 min read
Starvation
Think of it this way. A road with a pedestrian crossing: cars keep coming, and each driver sees only the car ahead. If cars never leave a gap, a person waiting to cross never gets across. A writer is in that position when readers keep arriving. The analogy stops in one place: a person can see the gap, while a lock only knows who has the lock now.
In plain words: When a writer waits for readers to finish, new readers keep arriving. The lock must decide whether those new readers go in before the writer or wait behind it. Two policies:
- Reader preference. A new reader can always join if the lock is held in read mode, even when a writer waits. Reads are fast, and a writer can wait for ever if the read stream never pauses.
- Writer preference. Once a writer waits, new readers wait behind it. The writer gets in as soon as the current readers leave. A steady stream of writers can then starve the readers.
A test with the GNU library's two settings. Three reader threads keep the lock in read mode almost all the time (each reads for 5 ms and starts again at once, with the three offset so that they overlap). A writer arrives after 100 ms and waits up to 3 seconds:
prefer reader: writer gave up after 3.000 s
prefer writer: writer got the lock after 0.004 s
With reader preference, the writer never got the lock in 3 seconds. There was always at least one reader. With writer preference, it got in after 4 ms, as soon as the readers present had finished. The default of the GNU library is reader preference (PTHREAD_RWLOCK_PREFER_READER_NP), so a program with a steady stream of readers and an occasional writer can starve the writer without any bug in the code. The setting is changed with pthread_rwlockattr_setkind_np.
There is no policy that is right for all programs. A third kind is a fair lock that serves requests in order of arrival, which prevents both kinds of starvation, at the price of less parallelism (a reader that arrives after a writer waits, even if the lock is in read mode).
Writer starvation
Writer starvation is the condition in which a thread waiting to write is delayed indefinitely because new readers keep acquiring a read-write lock that gives readers preference.
Example: with reader preference and three overlapping readers, a writer waited the whole 3-second test without getting the lock.
Check yourself: 1. What is the difference between reader preference and writer preference? 2. What did the test show for each? 3. What is the cost of a fair lock?