CSE Roadmap

Core tier · about 5 hours · 7 parts

Part 2 of 7 · 2 min read

Readers-writers

Think of it this way. A library reference book can be read by many people at the same time. Nobody reads while the librarian is crossing out a line and writing a new one, however. Several readers at once are harmless. A writer must have the book to itself. The analogy stops in one place: readers in a library see the book as it is, while a thread that reads in the middle of a write sees half-changed data.

In plain words: The readers-writers problem is the problem of letting any number of threads read shared data at the same time, while a thread that changes it has exclusive access, and no thread reads while another writes. A mutex would be correct: it lets one thread in at a time, readers included. It would also be wasteful, as two readers do not harm each other.

A read-write lock has two modes. In read mode, any number of threads can hold the lock together. In write mode, exactly one thread holds it, with no reader. POSIX provides it as pthread_rwlock_t:

Call Job
pthread_rwlock_rdlock(&rw) Take the lock for reading; waits only if a writer holds it
pthread_rwlock_wrlock(&rw) Take it for writing; waits until there are no readers or writers
pthread_rwlock_unlock(&rw) Release it, in whichever mode it was held
pthread_rwlock_timedwrlock(&rw, &t) Take it for writing, but give up at an absolute time

A test shows the gain. Each reader thread reads shared data 20,000 times, with a short computation under the lock, protected by a mutex in one run and by a read-write lock in another:

mutex , 1 reader thread(s): 0.035 s
mutex , 2 reader thread(s): 0.394 s
rwlock, 1 reader thread(s): 0.034 s
rwlock, 2 reader thread(s): 0.035 s

With one thread, the two locks are equal. With two reader threads, the read-write lock took the same time as one thread, since both readers ran together on the two processors. The mutex took more than ten times as long (0.394 s): the threads took turns, and the lock was passed back and forth, with sleeping and waking (page 3). Two readers cost almost nothing with the read-write lock.

Read-write lock

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.

Example: two threads hold rdlock together and run in parallel, while a third thread calling wrlock waits until both have unlocked.

Check yourself: 1. Why do two readers not need to exclude each other? 2. How long did two readers take with the read-write lock, and with the mutex? 3. Which calls take the lock for writing?