Linux Kernel Scalability: Using the Right Tool for the Job
This tutorial reviews performance trends in CPU architecture, showing how Moore's Law has changed the relationship between instruction, pipeline-flush, memory-latency, and contention overheads. This relationship has in turn influenced the optimal design of SMP software design.
The tutorial then covers various Linux kernel primitives, including spinlocks (such as spinlock_t), sleep locks (such as sema_t), reference counting, CPU-private data (such as DEFINE_PER_CPU), RCU, atomic primitives (such as atomic_t), and memory barriers. Although this tutorial will quickly review correct use of these primitives, the main focus will be on techniques that provide the best performance with the least complexity.
These techniques will be illustrated primarily with examples from the Linux kernel, and range from tried-and-true principles such as ``lock data not code'' from Rusty Russell's most excellent ``Unreliable Guide to Locking'' to more edgy techniques such as ways of reliably reference-counting data without use of locking and ways of atomically moving an element from one linked list to another while permitting lock-free readers and avoiding use of exotic atomic primitives. Both the performance and complexity of each example will be discussed.
The tutorial closes by outlining four likely system-architecture scenarios with varying degrees of parallelism, and describing which of these principles and techniques are likely to apply best to each of them. The relative probabilities of each scenario will also be briefly discussed. Canberra and Australia law permitting, we will take a pool on the outcome.
Paul E. McKenney is a distinguished engineer at IBM and has worked on SMP, NUMA, and RCU algorithms for longer than he cares to admit. Prior to that, he worked on packet-radio and Internet protocols (but long before the Internet became popular), system administration, realtime systems, and even business applications. His hobbies include running and the usual house-wife-and-kids habit.