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

Overview

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. 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.