Read-Write Locks

Shared access for readers, exclusive access for writers: the three fairness policies and who starves, a tested Python lock, why upgrading deadlocks, and Java's ReentrantReadWriteLock and StampedLock.

Overview

A read-write lock has two modes. Any number of threads can hold the read lock at the same time, because reading does not change the data. The write lock is exclusive: while a thread holds it, nobody else reads or writes. For data that is read far more often than it is written, such as a configuration map or an in-memory directory, readers stop waiting for each other.

It is not a free upgrade from a mutex. It is more complex, so each acquire costs more; it needs a policy for who goes next when readers and writers both wait; and it has a deadlock trap that a plain lock does not (upgrading). Interviewers use it to see whether you know those costs.

Shared and exclusive

The whole mechanism is one compatibility table: can a new request be granted given what is held right now?

Nothing — Granted — Granted
Read, by one or more threads — Granted (subject to the policy below) — Waits until every reader leaves
Write, by one thread — Waits — Waits

The policy: who goes next

The hard question is the middle row. A reader holds the lock, a writer is waiting, and a new reader arrives. Letting the new reader in keeps readers fast but can make the writer wait forever; making it wait protects the writer. This is the classic readers-writers problem, and it has three standard answers.

Reader preference — Granted — Writers, if readers keep overlapping — Writes that can be late
Writer preference — Waits — Readers, if writers keep coming — Updates that must land promptly, such as config changes
Fair (arrival order) — Waits if the writer came first — Nobody — Mixed load where neither side may starve

Java's ReadWriteLock docs list exactly these as the choices an implementation must make, and note that writer preference is common because writes are expected to be short and rare. ReentrantReadWriteLock in fair mode grants the lock in roughly arrival order: a fair reader blocks if the write lock is held or any writer is waiting.

A read-write lock from a condition variable

Python's standard library has no read-write lock, so interviewers often ask you to build one. One lock and one condition variable are enough: the state is the reader count, whether a writer holds the lock, and how many writers are waiting. Counting the waiting writers is what makes this version writer-preferring.

The three tests check the three properties: two readers really are inside at once (the barrier would break otherwise), a queued writer blocks a new reader and then gets the lock, and a thread that holds the read lock can never get the write lock. Every wait uses wait_for, which re-checks the predicate after each wakeup, and notify_all, because readers and writers wait on the same condition for different things.

Why upgrading deadlocks

A thread holding the read lock asks for the write lock. The write lock waits until the reader count is zero, and that thread is one of the readers, so it waits for itself. If two readers try to upgrade at once, each waits for the other. The third test above shows the first case.

Downgrade: write, then read — Yes — Take the read lock while holding the write lock, then release the write lock
Upgrade: read, then write — No; lock() blocks forever, tryLock() returns false — Release the read lock, take the write lock, then check the data again
Upgrade with StampedLock — Conditionally — tryConvertToWriteLock(stamp) succeeds only if no other reader holds it; otherwise returns 0

The recheck after re-locking is not optional: between releasing the read lock and getting the write lock, another writer may already have made the change.

Optimistic reads

Java's StampedLock adds a third mode. tryOptimisticRead() takes no lock at all; it returns a stamp. The reader copies the fields into local variables and then calls validate(stamp), which is true only if no writer took the lock since. If it fails, the reader falls back to a real read lock.

The docs are blunt about the risks: fields read optimistically may be wildly inconsistent, so read only into locals and use them only after validating; and StampedLock is not reentrant and has no conditions.

What you will be able to do

State the compatibility rules and when a read-write lock beats a mutex.
Compare reader preference, writer preference and fair policies, and say who starves under each.
Build a writer-preferring read-write lock from one lock and one condition variable, and test it.
Explain why upgrading a read lock deadlocks and how to do it safely.
Use ReentrantReadWriteLock and StampedLock and know their limits.

Interview questions

What is a read-write lock, and when is it better than a mutex?
What is the readers-writers problem, and how do the three policies differ?
Implement a read-through cache with a read-write lock. What is the classic bug?
What does StampedLock add, and when would you use it?
When should you not use a read-write lock?