Advanced Synchronization - Operating Systems: Principles and Practice - page 284

classRCULock{
private:
//Globalstate
SpinlockglobalSpin;
longglobalCounter;
DEFINE_PER_PROCESSOR(staticlong,quiescentCount); //Oneperprocessor

//Per-lockstate
SpinlockwriterSpin;

//PublicAPIomitted
...

}

Figure6.20:Global and per-lock data structures for a simple quiescence-based
RCU implementation. Credit: This pseudocode is based on an implementa-
tion by Paul McKenney in \Is Parallel Programming Hard, And, If So, What
Can be Done About It?

regardless of the number of concurrent readers. Conversely, we are willing to
allow writes to have a high latency (i.e., we are willing to allow long grace
periods, where it might be tens of milliseconds from when an update is published
until the system can guarantee that no readers can access the old version),
though we would like the overhead of writes to stay modest (i.e., the CPU
consumption of the write operations should be small, allowing a large numbers
of writers to complete their updates quickly, even if old versions may continue
to be used by readers for some time, and allowing other threads to run while a
thread waits for a grace period to expire.)

A common technique for achieving these goals is to change the scheduler,
integrating the RCU implementation with that of the scheduler. In contrast with
the synchronization primitives described in the previous chapter, which make
no assumptions about the scheduler, this integration allows us to rely on strong
assumptions about when reads can occur, which relieves us of the (expensive)
responsibility of tracking exactly how many readers are active at any given time.
In particular, our implementation will require two things from the scheduler: (1)
RCU read critical sections complete without being interrupted and (2) whenever
a thread on a processor is interrupted, the scheduler updates some per-processr
RCU state. Then, once a write completes, RCULock::Synchronize() simply
waits for all processors to be interrupted at least once. At that point, the old
version of the object is known to be quiescent |no thread has access to that old

Denition: quiescent

version (other than the writer that changed it.)

Figure 6.20 and Figure 6.21 show a simple implementation of RCU based

on quiescent states.

The first thing to notice is that ReadLock() and ReadUnlock() are extremely
cheap operations|they update no state and merely ensure that the read will
not be interrupted; in a non-preemptable kernel, these functions need to do