Linux Kernel Scalability: Using the Right Tool for the Job

The tutorial covers effective use of 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 design principles and 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'' and use of CPU affinity as explained in Robert Love's illuminating Linux Journal article to more edgy techniques such as reliably reference-counting data without use of locking and 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.

Given that Moore's Law has dramatically changed performance tradeoffs over the past few decades, it makes sense to look ahead to see what changes might be in the offing. The tutorial therefore 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. Ottawa, Ontario, and Canada law permitting, we will take a pool on the outcome.