A lock-free multiprocessor OS kernel

Henry Massalin, Calton Pu

Abstract

Typical shared-memory multiprocessor OS kernels use interlocking, implemented as spin-locks or waiting semaphores. We have implemented a complete multiprocessor OS kernel (including threads and virtual memory, and I/O including a window system and a file system) using only lock-free synchronization methods based on Compare-and-Swap. Lock-free synchronization avoids many serious problems casued by locks: considerable overhead, concurrency bottlenecks, deadlocks, and priority inversion in real-time scheduling. Measured numbers show the low overhead of our implementation, competitive with user-level thread management systems.