OS scheduler bugs affecting high-concurrency contention

There is a paper that any one interested in performance at high
concurrency, especially in Linux, should read[1]. While doing
other work, a group of researchers saw behavior that they suspected
was due to scheduler bugs in Linux. There were no tools that made
proving that practical, so they developed such a tool set and used
it to find four bugs in the Linux kernel which were introduced in
these releases, have not yet been fixed, and have this following
maximum impact when running NAS benchmarks, based on running with
and without the researchers' fixes for the bugs:

2.6.32: 22%
2,6.38: 13x
3.9: 27x
3.19: 138x

That's right -- one of these OS scheduler bugs in production
versions of Linux can make one of NASA's benchmarks run for 138
times as long as it does without the bug. I don't feel that I can
interpret the results of any high-concurrency benchmarks in a
meaningful way without knowing which of these bugs were present in
the OS used for the benchmark. Just as an example, it is helpful
to know that the benchmarks Andres presented were run on 3.16, so
it would have three of these OS bugs affecting results, but not the
most severe one. I encourage you to read the paper an draw your
own conclusions.

Anyway, please don't confuse this thread with the one on the
"snapshot too old" patch -- I am still working on that and will
post results there when they are ready.

--
Kevin Grittner
EDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company

[1] Jean-Pierre Lozi, Baptiste Lepers, Justin Funston, Fabien Gaud,
Vivien Quéma, Alexandra Fedorova. The Linux Scheduler: a Decade
of Wasted Cores. In Proceedings of the 11th European
Conference on Computer Systems, EuroSys’16. April, 2016,
London, UK.
http://www.ece.ubc.ca/~sasha/papers/eurosys16-final29.pdf

[2] NAS Parallel Benchmarks.
http://www.nas.nasa.gov/publications/npb.html