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

Reader API RCU::ReadLock()
RCU::ReadUnlock()
Writer API RCU::WriteLock()
RCU::Publish()
RCU::WriteUnlock()
RCU::Synchronize()

Figure6.15: API for read-copy-update (RCU) synchronization.

read_lock read 1 read_unlock read_lock read 2 read_unlock read_lock read 3 read_unlock

read_lock read 4 read_unlock read_lock read 5 read_unlock

read_lock read 6 read_unlock read_lock read 7 read_unlock

write_lock publish v1 write_unlock synchronize OK to free v0

write_lock publish v2 write_unlock synchronize OK to free v1

write_lock publish v3 write_unlock synchronize OK to free v2

Figure6.16: RCU allows one write at a time, and it allows reads to overlap each other and writes.
The initial version is v0, and overlapping writes update the version to v1, v2, and then v3.

clude other writers, RCU::Publish() to issue the write that atomically updates
the data structure so that reads can see the updates, RCU::WriteUnlock() to
allow other writers to proceed, and RCU::Synchronize() to wait for the grace
period to expire so that the old version of the object can be freed. Notice that
as Figure 6.16 illustrates, writes are serialized|only one write can proceed at
a time. But also notice that writes can be concurrent with reads and that one
write's update can be concurrent with another write's grace period: there may
be any number of versions of the object until multiple overlapping grace periods
expire.

Example: Overlapping operations.
Question: For each read in Figure 6.16, which version(s) of the shared state
can the read observe?

Answer: If a read overlaps a publish, it can return the published value or
the previous value.