RCU

Overview	The performance of synchronization instructions on shared memory multiprocessors (SMMP) has declined dramatically compared to the performance of simple instructions. As a result, operating system developers for SMMPs have sought out synchronization algorithms that avoid using these instructions, especially in commonly executed paths. One such algorithm that has been applied successfully in state-of-the-art SMMP operating systems is Read-Copy Update (RCU). RCU is a reader-writer synchronization algorithm that uses multi-version and deferred-destruction techniques to allow readers to execute in parallel with writers, while avoiding expensive synchronization instructions. For read-mostly scenarios, which occur frequently in operating systems in the guise of configuration and routing structures that track infrequently changing external state, this approach leads to significant performance and scalability improvements. However, successful use of RCU poses software engineering challenges because it can require reorganization of code and transformation of some existing algorithms. In this project we are defining the conceptual basis of RCU, designing and evaluating efficient implementions of it in SMMP operating system kernels, and exploring the software engineering challenges posed by RCU. We are mining design patterns from various uses of RCU in production systems, including the Linux 2.6 kernel, and are exploring transformational design patterns that can expand the applicability of RCU. A longer term goal of the project is to develop tools that aid in the use of RCU and eventually lead to its automation.
People	Faculty: Jonathan Walpole Students: Josh Tripplet, Jim Cotillier, Ahmed Badran, Suzanne Wood Collaborators: Paul McKenney (Linux Tech. Ctr, IBM), Tom Hart (U. Toronto)
Papers	Paul McKenney, "Exploiting Deferred Destruction: An Analysis of Read-Copy-Update Techniques" Ph.D. Thesis, OGI School of Science and Engineering, OHSU, July 2004.
Software
Sponsors

Back to Jonathan Walpole's home page