The Linux scheduler
Top Cited Papers
- 18 April 2016
- conference paper
- conference paper
- Published by Association for Computing Machinery (ACM)
Abstract
As a central part of resource management, the OS thread scheduler must maintain the following, simple, invariant: make sure that ready threads are scheduled on available cores. As simple as it may seem, we found that this invariant is often broken in Linux. Cores may stay idle for seconds while ready threads are waiting in runqueues. In our experiments, these performance bugs caused many-fold performance degradation for synchronization-heavy scientific applications, 13% higher latency for kernel make, and a 14-23% decrease in TPC-H throughput for a widely used commercial database. The main contribution of this work is the discovery and analysis of these bugs and providing the fixes. Conventional testing techniques and debugging tools are ineffective at confirming or understanding this kind of bugs, because their symptoms are often evasive. To drive our investigation, we built new tools that check for violation of the invariant online and visualize scheduling activity. They are simple, easily portable across kernel versions, and run with a negligible overhead. We believe that making these tools part of the kernel developers' tool belt can help keep this type of bug at bay.Keywords
This publication has 24 references indexed in Scilit:
- Traffic managementPublished by Association for Computing Machinery (ACM) ,2013
- Our troubles with Linux and why you should carePublished by Association for Computing Machinery (ACM) ,2011
- FACTPublished by Association for Computing Machinery (ACM) ,2011
- Contention-Aware Scheduling on Multicore SystemsACM Transactions on Computer Systems, 2010
- Efficient operating system scheduling for performance-asymmetric multi-core architecturesPublished by Association for Computing Machinery (ACM) ,2007
- Thread clusteringPublished by Association for Computing Machinery (ACM) ,2007
- Using model checking to find serious file system errorsACM Transactions on Computer Systems, 2006
- Exploring Thread and Memory Placement on NUMA Architectures: Solaris and Linux, UltraSPARC/FirePlane and Opteron/HyperTransportLecture Notes in Computer Science, 2006
- CMCACM SIGOPS Operating Systems Review, 2002
- EraserACM Transactions on Computer Systems, 1997