Back to index

The Synergy Between Non-Blocking Synchronization and Operating System Structure

Michael Greenwald and David Cheriton, Stanford

One-line summary: Use CAS-2 (double compare and swap, ideally in hardware) instead of blocking synchronization to safely and efficiently update concurrent data structures. One CAS is the update itself, the other CAS is a version number that protects the entire data structure, to detect inconsistency.

Overview/Main Points

Abstractions of interest: Using DCAS and version numbers for shared data structures and signal delivery: Comparison to other synchronization (Proteus simulations): Implementation:


A potentially high-performance and robust (can't die while holding a lock!) way to increase concurrency of critical OS data structures, and possibly enable efficient implementation of OS services such as signal delivery, based on a neat hack.

Extension: for more constrained cases, can use a single bit (or 2-bit) version number by exploiting the fact (with proper compiler support) that addresses are usually word-aligned.


Back to index