Using Read-Copy-Update Techniques for System V IPC in the Linux 2.5 Kernel

Read-copy update (RCU) allows lock-free read-only access to data structures that are concurrently modified on SMP systems. Despite the concurrent modifications, read-only access requires neither locks nor atomic instructions, and can often be written as if the data were unchanging, in a ``CS 101'' style. RCU is typically applied to read-mostly linked structures that the read-side code traverses unidirectionally.

Previous work has shown no clear best RCU implementation for all measures of performance. This paper combines ideas from several RCU implementations in an attempt to create an overall best algorithm, and presents a RCU-based implementation of the System V IPC primitives, improving performance by more than an order of magnitude, while increasing code size by less than 5% (151 lines). This implementation has been accepted into the Linux 2.5 kernel.