Information Technology Reference
In-Depth Information
Update
is
Published
Grace
Period
Ends
read
(old)
read
(new)
read
(old)
read
(new)
read
(old or new)
read
(new)
read
(old or new)
write
(new)
delete
(old)
Grace Period
Figure6.14: Timeline for an update concurrent with several reads for a data
structure accessed with read-copy-update (RCU) synchronization.
period , and RCU must provide a way to determine when a grace period
Definition: grace period
ends.
2. Restrict update rules. To make a data structure update appear atomic
to readers, an RCU update must be published to the data structure with
a single, atomic memory write (e.g., by updating a single pointer.)
Figure 6.14 shows the timeline for a write critical section that is concurrent
with several read critical sections under RCU. If a function that reads the data
structure completes before a write is published, it will (of course) see the old
version of the data structure, and if a read critical section begins after a write
is published it will see the new version. But, if a read critical section begins
before and ends after a write is published, it may see the old version or the new
one; if it reads the updated pointer more than once, it may even first see the old
one and then see the new one. Which version it sees depends on which version
of the single atomically-updated memory location it observes. Furthermore, the
system guarantees that the old version is not deleted until the grace period
expires, which means that deletion of the old versions must be delayed until all
reads that might be observing the old version have completed.
API and use.
RCU is a synchronization abstraction that allows concurrent
Denition: RCU
access to a data structure by multiple readers and a single writer at a time.
Figure 6.15 shows a typical API.
A reader calls
RCU::ReadLock()
and
RCU::ReadUnlock()
before and after
accessing the shared data structure. A writer calls
RCU::WriteLock()
to ex-
