Information Technology Reference
In-Depth Information
In particular, RCU optimizes the read path to have extremely low synchroniza-
tion costs, even if there are many concurrent readers. However, writes can be
delayed for a long time|tens of milliseconds in some implementations.
Why RCU? We might hope that
readers-writers locks
would be an adequate
solution for read-dominated workloads. Recall that readers-writers locks allow
multiple concurrent active readers, but there is an active writer no other writer
or reader can be active.
The problem with the readers-writers locks approach is its cache behavior for
concurrent reads with short critical sections. Recall that before reading, a reader
acquires a readers-writers lock in read mode. To do this, it must read and then
update some state in the readers-writers synchronization object. Unfortunately,
this access pattern causes a large number of cache misses when there are a large
number of concurrent readers.
In particular, on a multiprocessor, when one processor updates a hardware
cache line, it invalidates that cache line in all other caches. Then, when another
processor wants to read and update the data, it first suffers a cache miss and
must fetch the data from the rst processor's cache or from main memory; then
it must invalidate the cache line in other caches; finally, it can update the data
in its cache. On a modern processor, fetching and invalidating a cache line can
take hundreds of cycles. If there are a large number of processors trying to read
a data structure protected by a readers-writers lock, the average processor may
wait thousands of cycles to acquire the lock in read mode, even if there are no
writers.
So, for critical sections less than a few thousand cycles and for programs
where there may be many threads simultaneously trying to read an object, the
standard readers-writers lock can impose significant overheads.
The RCU approach. How can we let concurrent reads access a data struc-
ture that can also be written without having to suffer the cache effects of up-
dating the state of a synchronization variable on each read?
To meet this challenge, RCU weakens its semantics in two ways compared
to readers-writers locks.
1. Relax R/W semantics. RCU allows up to one read/write critical sec-
tion to be concurrent with any number of read-only critical sections. A
read-only critical section that overlaps a read/write critical section may
see the old or new version of the data structure.
Note that an object that uses RCU for synchronization must maintain
multiple versions of its state, and it must guarantee that an old version is
not freed until all readers have finished accessing it. The time from when
an update occurs until the old version has been freed is called the grace
