Reader-Writer Problem

Reader-writer problem is one of fundamental problems in concurrent systems. In a single-threaded environment type of access (read or write) is mostly irrelevant - once a thread has a reference to an object, it can do whatever access it wants (and in most cases you can change read to write w/o any problems). However, in a concurrent environment type of access is fundamental, because a plurality of threads can read data w/o any synchronization and conflicts, while write access must be exclusive (that is, at most 1 thread at a time).

Hey, there are reader-writer mutexes available, so what's the problem?

The problem is that traditional reader-writer mutexes do not scale. Period. At all. They degrade ungracefully under high reader load. Below are results from a synthetic benchmark of pthread_mutex_t, pthread_spinlock_t and pthread_rwlock_t (locked only for read access) on a 4 processor x 4 core AMD machine:

Huh? How it is to you? Not that bad? Ok, let's add a line for what we would like to observe, that is a perfect linear speedup of pthread_spinlock_t:

In order to a reader-writer mutex to scale reader's time under mutex must be significant, on the order of, let's say, 10'000 cycles. And the more hardware threads you have the longer the time must be. Otherwise, inter-reader synchronization overheads dominate, and the system does not scale. The root cause is that synchronization protocol that is executed by each reader upon rw mutex lock and unlock is-a write access (regarding mutex' internal data) and can be executed by at most 1 thread at a time.

Moreover, mutual exclusion between a writer and readers can be a problem too. Either writers or readers can starve under load, note that the more hardware threads you have the higher load they produce. That is, it's not a function of only a program, it also depends on underlying hardware, and after upgrade to a "faster" machine, you may see performance degradation (it's really not that infrequent in real life).

The whole idea of advanced reader-writer synchronization primitives is to make logically read-only accesses physically read-only wrt shared data and/or eliminate mutual exclusion between readers and writers.

There are several techniques for that.

Move on to Multi-Version Concurrency Control