This is not the current version of the class.

Section 4: Scalability and OS design

In this section, we’ll discuss two contrasting approaches to building operating systems for multicore computers.


“The Multikernel: A new OS architecture for scalable multicore systems.” Andrew Baumann, Paul Barham, Pierre-Evariste Dagand, Tim Harris, Rebecca Isaacs, Simon Peter, Timothy Roscoe, Adrian Schüpbach, and Akhilesh Singhania. In Proc. SOSP 2009.

Commodity computer systems contain more and more processor cores and exhibit increasingly diverse architectural tradeoffs, including memory hierarchies, interconnects, instruction sets and variants, and IO configurations. Previous high-performance computing systems have scaled in specific cases, but the dynamic nature of modern client and server workloads, coupled with the impossibility of statically optimizing an OS for all workloads and hardware variants pose serious challenges for operating system structures.

We argue that the challenge of future multicore hardware is best met by embracing the networked nature of the machine, rethinking OS architecture using ideas from distributed systems. We investigate a new OS structure, the multikernel, that treats the machine as a network of independent cores, assumes no inter-core sharing at the lowest level, and moves traditional OS functionality to a distributed system of processes that communicate via message-passing.

We have implemented a multikernel OS to show that the approach is promising, and we describe how traditional scalability problems for operating systems (such as memory management) can be effectively recast using messages and can exploit insights from distributed systems and networking. An evaluation of our prototype on multicore systems shows that, even on present-day machines, the performance of a multikernel is comparable with a conventional OS, and can scale better to support future hardware.

For this paper, focus on Sections 1--5.1, 5.4, and 5.5.

Linux scalability

“An Analysis of Linux Scalability to Many Cores.” Silas Boyd-Wickizer, Austin T. Clements, Yandong Mao, Aleksey Pesterev, M. Frans Kaashoek, Robert Morris, and Nickolai Zeldovich. In Proc. OSDI 2010.

This paper analyzes the scalability of seven system applications (Exim, memcached, Apache, PostgreSQL, gmake, Psearchy, and MapReduce) running on Linux on a 48-core computer. Except for gmake, all applications trigger scalability bottlenecks inside a recent Linux kernel. Using mostly standard parallel programming techniques—this paper introduces one new technique, sloppy counters—these bottlenecks can be removed from the kernel or avoided by changing the applications slightly. Modifying the kernel required in total 3002 lines of code changes. A speculative conclusion from this analysis is that there is no scalability reason to give up on traditional operating system organizations just yet.

Before reading the paper, learn about Amdahl's Law. Then, in the paper, focus on Sections 1, 3, 4.1, 4.3, 4.5, 4.6, 4.7, 5.2, 5.5, and 5.6.


As you read these papers, consider the following question, and post a followup with your response to the Piazza announcement of section by one hour before section.

The Barrelfish paper makes some arguments about the potential scalability of conventional operating system designs that the Linux scalability paper appears to refute. Explain how the arguments in both papers are compatible despite this apparent contradiction.