Practical Concerns for Scalable Synchronization
Paul E. McKenney, Thomas E. Hart, Jonathan Walpole · 2005
With the advent of multi-core chips and simultaneous multithreading technologies, high degrees of parallelism will soon become the norm for both small- and large-scale systems. Operating systems for such highly parallel environments require efficient synchronization. Unfortunately, the everincreasing overhead of synchronization instructions on modern CPUs has made such efficiency difficult to achieve. This paper evaluates the performance of synchronization strategies on modern CPU architectures. We show that synchronization instructions can be a thousand times more expensive than normal instructions and that formerly scalable synchronization strategies now perform very poorly. We then evaluate several state-of-the-art solutions that combine copy-based update and deferred reclamation to allow lock-free concurrent reading. These solutions exhibit different update management and reclamation strategies, each of which performs well, but offers a unique trade-off between performance, memory consumption, and complexity. We present an experimental evaluation of these strategies, focusing primarily on the read-mostly scenarios common in operatingsystem kernels, and discuss the impact of potential future changes in CPU architecture.