Part 6 of 7 · 4 min read
Lessons
What the two problems teach
In plain words: The read-write lock fits a read-mostly workload: data read much more often than it is written, where the read part of the work is long enough to repay the extra cost of the lock. Examples: a routing table, a configuration, a cache lookup. The lock has an internal counter of readers, and its bookkeeping is more costly than a mutex's. When the critical section is tiny, the extra cost can exceed the gain, and a plain mutex wins. In the test above, with one thread, the read-write lock needed 0.034 to 0.051 s, against the mutex's 0.035 to 0.039 s: no advantage without parallel readers. The test with several readers is the one to measure in your own program.
Further choices appear in practice: a read-write lock where writers are rare and the lock policy is known, a mutex when critical sections are short, and a copy-on-write scheme in which readers use a snapshot that a writer replaces (read-copy-update, used inside the Linux kernel for read-mostly data), which removes the reader's cost almost altogether.
The philosophers show the discipline for code that takes several locks:
- A global lock order, written down and followed everywhere. This is the first remedy.
- Hold few locks, for a short time. A thread that never needs two locks cannot deadlock on locks.
- Use
trylockand back off when the order cannot be fixed: if the second lock is busy, release the first, wait a random short time, and start again. It avoids deadlock but can cause a livelock, in which threads keep retrying and no one progresses. - Test with pauses between lock acquisitions, as the philosopher test did, so that rare timings appear in the test and not in production. Tools such as ThreadSanitizer (page 8) can also find lock-order problems.
Read-mostly workload
A read-mostly workload is a pattern of use in which shared data is read far more often than it is changed, so that allowing readers to proceed in parallel is worth the extra cost of a read-write lock.
Example: a table of routes that is consulted for every request and updated once an hour.
Common mistake
Using a read-write lock everywhere "for speed". It is slower than a mutex when critical sections are tiny or writes are common, and the default reader preference can starve writers. Measure first.
Interview angle
Answer in your head first, then open it.
What is the readers-writers problem?
Many readers may share data, but a writer needs exclusive access.
What can go wrong with reader preference?
A steady stream of readers can starve a waiting writer.
What are the dining philosophers?
Five threads, five forks, each needing two: a model of deadlock over several locks.
How do you prevent deadlock with several locks?
Take them in one global order, or limit how many threads compete.
What is livelock?
Threads keep reacting to each other and retrying, and none makes progress.
Check yourself: 1. When does a plain mutex beat a read-write lock? 2. What is livelock, and how does it differ from deadlock? 3. Give one rule for code that takes several locks.
Words you will meet
| Word | Meaning |
|---|---|
| Read-write lock | A lock with shared read mode and exclusive write mode |
| Reader preference | New readers may join while a writer waits |
| Writer preference | Readers wait behind a waiting writer |
| Writer starvation | A writer that never gets the lock |
| Dining philosophers | Five threads sharing five forks |
| Resource ordering | Taking locks in a fixed global order |
| Livelock | Threads keep retrying and make no progress |
| Read-mostly | Data read much more often than written |
Quick notes
- A read-write lock is a lock with two modes, shared and exclusive: any number of threads may hold it in read mode at once, a thread in write mode holds it alone, and read and write modes never overlap.
- 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.
- The dining philosophers problem is a synchronisation problem in which five threads sit round a table with one shared resource, a fork, between each neighbouring pair, each thread needs both.
- Resource ordering is a deadlock-prevention technique in which all resources (locks) are given a fixed global order and every thread acquires the ones it needs strictly in increasing order, so that a circular chain of waits cannot form.
- A read-mostly workload is a pattern of use in which shared data is read far more often than it is changed, so that allowing readers to proceed in parallel is worth the extra cost of a read-write lock.