read-copy-update
/ RCU -> ar-see-YOO /
Read-copy-update, almost always abbreviated RCU, is a synchronization technique for data that is read constantly but written rarely. The everyday picture is a printed bus timetable posted on a wall. Hundreds of riders read it freely, all at once, with zero coordination and zero waiting — reading costs nothing. When the schedule changes, the transit authority does not erase the posted copy while people are reading it. Instead it prints a fresh updated copy, then quietly swaps the new one in for the old. Anyone mid-read of the old copy finishes reading it harmlessly; new readers see the new copy. The old copy is thrown away only once it is certain nobody is still looking at it.
Mechanically, RCU makes readers extremely cheap — typically a reader takes no lock at all, just marks a lightweight read-side critical section, so concurrent reads never block each other or the writer. A writer that wants to change a node does not modify it in place (which a reader might catch half-done). Instead it makes a private copy, modifies the copy, and then atomically swaps a pointer so it points at the new version. Existing readers happily keep traversing the old version; future readers follow the pointer to the new one. The subtle part is reclamation: the writer must wait for a grace period — long enough that every reader that could have been holding a reference to the old version has finished — before it is safe to free that old version. RCU tracks this with the idea of quiescent states (moments when a CPU is known to hold no RCU-protected reference).
RCU shines in read-mostly workloads and is heavily used inside the Linux kernel for exactly such cases (routing tables, the directory-entry cache, lists of loaded modules), where it gives near-zero read overhead and excellent multicore scalability. The honest trade-offs: writers are more expensive and more complex (copy, swap, then wait out a grace period), updates are deferred rather than instant, and during the swap window readers may see either the old or the new version — so RCU fits data where a brief read of slightly-stale-but-consistent data is acceptable. It is not a drop-in replacement for a lock when writes are frequent or when readers must always see the very latest value.
To update a list node under RCU: copy = clone(node); modify(copy); atomic_swap(pointer, copy); then synchronize_rcu() waits out the grace period; finally free(oldNode). Readers throughout just dereference the pointer with no lock.
Writers copy-then-swap and defer freeing until a grace period proves no reader still holds the old version.
RCU is for read-mostly data and assumes readers tolerate briefly seeing a slightly old (but internally consistent) version. With frequent writes its grace-period and copy overhead can make it slower than a plain lock.