read-copy-update (RCU) and the grace period
/ AR-SEE-YOO /
Suppose almost everyone reading a shared list just wants to look, and writes are rare. It would be a shame to make every reader pay for a lock or even an atomic publish, since they so vastly outnumber writers. Read-copy-update is a reclamation and synchronization technique, used heavily inside the Linux kernel, built precisely for this read-mostly case. Its remarkable promise is that readers are nearly free — often no locks, no atomic writes, no waiting at all.
The pattern is in the name. To update an item, a writer does not modify it in place where readers might see a half-changed value. Instead it makes a private copy, modifies the copy, and then atomically swaps a single pointer so new readers see the new version, while readers who already grabbed a pointer to the old version continue using it unharmed. The old version is then RETIRED but not freed yet. The writer waits for a grace period: a span of time long enough that every reader who could possibly have been holding a pointer to the old version has finished and let go. Only after the grace period does the writer free the old copy. A reader marks its read-side critical section with rcu_read_lock and rcu_read_unlock (in classic kernel RCU these are essentially free — they just disable preemption); the grace period is detected by waiting until every CPU has passed through a point where it holds no RCU references, called a quiescent state.
Why readers are nearly free is the heart of it: a reader never writes to shared memory and never blocks a writer, so concurrent reads scale almost perfectly across cores. The costs land on the writer side — updates are heavier (copy, swap, wait for a grace period), and the grace period adds latency before memory is actually reclaimed, so retired memory lingers. RCU is therefore a superb fit for data read far more often than written (routing tables, configuration, the kernel's directory-entry cache) and a poor fit for write-heavy structures.
/* Reader: nearly free critical section, no atomic writes. */ rcu_read_lock(); p = rcu_dereference(shared); /* read the current published pointer */ use(p->field); rcu_read_unlock(); /* Writer: copy, modify, publish, wait a grace period, then free the old. */ q = copy_of(p); modify(q); rcu_assign_pointer(shared, q); /* new readers see q */ synchronize_rcu(); /* wait until all old readers are gone */ free(p); /* now safe */
Readers run lock-free; the writer publishes a new version and waits a grace period before freeing the old one nobody can still reach.
RCU's readers are cheap precisely because the cost moves to the writer and to deferred reclamation; the grace period means freed memory lingers, so RCU suits read-mostly data, not write-heavy structures.