15 ms·

The Linux Scheduler: A Decade of Wasted Cores [pdf]

467 points by tdurden 11y ago

j1vms 11y ago
As indicated in the paper, patches (currently for kernel 4.1) are here: https://github.com/jplozi/wastedcores https://github.com/jplozi/wastedcores
- rando3826 11y ago
  Are they accepted upstream? If not, I'd like to see a link to the lkml thread for these.
  - rincebrain 11y ago
    I can't find any evidence they were submitted upstream at any juncture. Moreover, since (several of) the patches seem to rip out a bunch of logic in favor of very simple logic, they would probably be contentious without broad testing and probably a runtime option to configure the behavior.
    - verroq 11y ago
      And uses spaces instead of tabs. Someone will need to go fix them up.
      - jeffreyrogers 11y ago
        Not sure why you're being downvoted. Tabs instead of spaces is the Linux kernel style.
  - justinmk 11y ago
    I wonder if they are discouraged by the experience of Con Kolivas[1] who proposed an alternative scheduler back in 2007. (Apparently he is still maintaining his "-ck" fork of the linux kernel[2]!) I only mention this as a historical case that has remained in my memory. Maybe Linus is willing to revisit the issue, I don't follow LKML. [1] https://en.wikipedia.org/wiki/Con_Kolivas https://en.wikipedia.org/wiki/Con_Kolivas [2] http://ck-hack.blogspot.com/2015/12/bfs-467-linux-43-ck3.html http://ck-hack.blogspot.com/2015/12/bfs-467-linux-43-ck3.htm...
    - LoSboccacc 11y ago
      I remember the whole debacle back then when the lkml was summarized on that website I can't remember It'd be interesting to see if that branch exhibit the same behavior and issues.
      - tremon 11y ago
        Maybe KernelTrap? I was sad when it shut down, it was a very useful resource for following Linux development from the sidelines.
        LoSboccacc 11y ago
        Yeah that one! The memories.
      - DCoder 11y ago
        You might be thinking of LWN. They covered the scheduler multiple times over the years: https://lwn.net/Kernel/Index/#Scheduler https://lwn.net/Kernel/Index/#Scheduler
    - doe88 11y ago
      I do not follow Kernel Dev enough to have a good representation of what happened, but it seems to me that it was another example of smart people pushed out. Nowadays I think he is just maintaining his patches from one kernel release to the next, it was smart for Con to stop interacting with them and move to other types of devs, it comes a point where you have to keep your sanity.
  - melchebo 11y ago
    The conference where this will be presented starts next week. So I think they'll post it after they catched up some sleep after that.
    - anonymousDan 11y ago
      Which conference, Eurosys?
      - desdiv 11y ago
        Yes, since the filename is eurosys16-final29.pdf.
thinkingkong 11y ago
Some authors appear to work with the old Xen crew (now founders at coho). Impressive work!
wutf 11y ago
This is extremely promising. Makes you wonder if we ought not go further and implement a machine learning-based scheduler that studies and anticipates workloads and schedules accordingly so as to help jobs complete as quickly as possible.
- rifung 11y ago
  Why machine learning? The paper says that the need to handle the complexities of modern hardware made it so that the scheduler failed to do its fundamental job. Machine learning sounds like it would add even more complexity but perhaps I just fail to see why machine learning is a good idea here. I don't see how you can predict workloads based off historical data and if you're going to try to predict workloads based off binaries, the overhead would likely outweigh any benefits you would get. I'll admit I am no expert in machine learning but I have a hard time understanding why you would look at this problem and think machine learning is the solution.
  - wutf 11y ago
    "I don't see how you can predict workloads off of historical data" ... Think about that part, then:)
  - tigershark 11y ago
    The only reason is because machine learning is fashionable at the moment and a lot of people like to suggest it as the panacea. I can't even imagine the terrible overhead that machine learning would impose in probably the most critical part of the OS.
    - wutf 11y ago
      Prediction can be extremely fast.
      - marcosdumay 11y ago
        But learning is always slow. What is the point of machine learning if you disable learning?
jor-el 11y ago
The quotes in the paper are interesting: "Nobody actually creates perfect code the first time around, except me. But there’s only one of me.” Linus Torvalds, 2007 And another, which highlights why there might be many more unearthed bugs, and would probably go unnoticed. "I suspect that making the scheduler use per-CPU queues together with some inter-CPU load balancing logic is probably trivial . Patches already exist, and I don’t feel that people can screw up the few hundred lines too badly" Looking at the bigger picture in general, this again shows that getting software right is not easy. Now and then you still hear about the bugs popping up in the code which is very core to an OS. One I can recall is a decade old TCP bug which Google fixed last year[1]. [1] http://bitsup.blogspot.sg/2015/09/thanks-google-tcp-team-for-open-source.html http://bitsup.blogspot.sg/2015/09/thanks-google-tcp-team-for...
- akkartik 11y ago
  I don't think the paper contradicts the second quote. It just points out that things got a lot more complex since. "this again shows that getting software right is not easy." Not easy, yes, but in my experience getting software right isn't too difficult. What seems impossibly hard is keeping software right, maintaining correctness in the presence of new requirements, compatibility constraints and just sheer caring about different things than we used to[1]. At some point I suspect you'd get a better design by rewriting things from scratch. But the way we do development makes rewriting stressful and error-prone, leading to the repeated arguments about whether rewriting is good or bad[2]. The question isn't whether rewriting is good or bad. Software is the most malleable medium known to man, and we should do all we can to embrace that essential malleability that is its primary characteristic and boon. The question is how not to mess up rewriting, how to keep our clay from gradually getting more and more brittle under the weight of added constraints. (I work on this problem: https://github.com/akkartik/mu/blob/7f5a95cdbe/Readme.md https://github.com/akkartik/mu/blob/7f5a95cdbe/Readme.md. It's been 31 days since I last got on my soapbox in this forum: https://news.ycombinator.com/item?id=11285529. https://news.ycombinator.com/item?id=11285529.) [1] "The future is a disagreement with the past about what is important." http://carlos.bueno.org/2010/10/predicting-the-future.html http://carlos.bueno.org/2010/10/predicting-the-future.html [2] Against rewrites: http://www.joelonsoftware.com/articles/fog0000000069.html; http://www.joelonsoftware.com/articles/fog0000000069.html; https://steveblank.com/2011/01/25/startup-suicide-%E2%80%93-rewriting-the-code; https://steveblank.com/2011/01/25/startup-suicide-%E2%80%93-... https://basildoncoder.com/blog/pg-wodehouse-method-of-refactoring.html https://basildoncoder.com/blog/pg-wodehouse-method-of-refact.... Pro-rewrite seems the minority position: http://brettweigl.tumblr.com/post/48385335083/what-can-product-managers-do-during-rewrites; http://brettweigl.tumblr.com/post/48385335083/what-can-produ... http://building.wanelo.com/2012/09/14/the-big-switch-how-we-rebuilt-wanelo-from-scratch-and-lived-to-tell-about-it.html; http://building.wanelo.com/2012/09/14/the-big-switch-how-we-... http://alicebob.cryptoland.net/why-i-rewrote-quivi-from-scratch http://alicebob.cryptoland.net/why-i-rewrote-quivi-from-scra... (with many apologies). And yet we've seen several major rewrites: Netscape (for all Joel Spolsky's criticism above, would Firefox had been possible without the rewrite? Echoing Jeff Bezos's dictum, open source projects can afford to be misunderstood for a long time), Python 3 [edit: no, Python 3 was not a rewrite as I was corrected below], Perl 6, Angular 2. A more balanced viewpoint: https://blog.learningbyshipping.com/2013/04/02/surviving-legacy-code https://blog.learningbyshipping.com/2013/04/02/surviving-leg....
blinkingled 11y ago
Interesting work certainly. The patches look more like proof of concept rather than something that's ready for mainline. I think they're better off if they post a RFC patch to LKML as it exists to facilitate discussion and testing.
- melchebo 11y ago
  It should probably mainly be seen as a proof of concept for their scheduler decision visualization tools. Which are not public for the time being. That should make checking and fixing bugs easier in the future.
akkartik 11y ago
Is anyone able to explain Figure 1? I don't understand what the levels are, and whether level 1 is the coarsest or the finest. The caption doesn't seem to make sense either way.. Also, Algorithm 1 is in terms of cpus, but the description mentions 'nodes' and 'cores'. Is a CPU a core or a node? Neither?
- wmf 11y ago
  Unfortunately the authors are using AMD machines which behave differently than most others because pairs of cores are conjoined into "modules" that share resources. In AMD processors, a cpu is a core. In almost all other processors, a cpu is a SMT thread (aka Hyperthread). In figure 1 the levels/shades represent distance from node/socket 1, darker being closer. So node 1 is distance 0 from itself, two other nodes are distance 1, and one node is distance 2.
  - nazmunsuma 11y ago
    I agree.
  - fulafel 11y ago
    ARM doesn't do SMT either.
  - melchebo 11y ago
    From what I understand from this presentation the 'scheduling domain' abstraction is reused through different layers of the hierarchy. So for example the two hyperthreads on one logical core are also modeled as 'scheduling domain'. https://events.linuxfoundation.org/images/stories/slides/lfcs2013_murthy.pdf?update https://events.linuxfoundation.org/images/stories/slides/lfc...
  - tremon 11y ago
    The only thing shared in a bulldozer core is the FPU (and perhaps some cache, not sure). For all other purposes, a bulldozer module contains two full CPU cores. Also, what CPUs besides Intel's and IBM's use SMT?
brendangregg 11y ago
I've worked scheduling bugs in other kernels before (Linux is not an outlier here). The key metric we keep an eye on is run queue latency, to detect when threads are waiting longer than one would expect. And there's many ways to measure it; my most recent is runqlat from bcc/BPF tools, which shows it as a histogram. eg: # ./runqlat Tracing run queue latency... Hit Ctrl-C to end. ^C usecs : count distribution 0 -> 1 : 233 |*********** | 2 -> 3 : 742 |************************************ | 4 -> 7 : 203 |********** | 8 -> 15 : 173 |******** | 16 -> 31 : 24 |* | 32 -> 63 : 0 | | 64 -> 127 : 30 |* | 128 -> 255 : 6 | | 256 -> 511 : 3 | | 512 -> 1023 : 5 | | 1024 -> 2047 : 27 |* | 2048 -> 4095 : 30 |* | 4096 -> 8191 : 20 | | 8192 -> 16383 : 29 |* | 16384 -> 32767 : 809 |****************************************| 32768 -> 65535 : 64 |*** | I'll also use metrics that sum it by thread to estimate speed up (which helps quantify the issue), and do sanity tests. Note that this isolates one issue -- wait time in the scheduler -- whereas NUMA and scheduling also effects memory placement, so the runtime of applications can become slower with longer latency memory I/O from accessing remote memory. I like to measure and isolate that separately (PMCs). So I haven't generally seen such severe scheduling issues on our 1 or 2 node Linux systems. Although they are testing on 8 node, which may exacerbate the issue. Whatever the bugs are, though, I'll be happy to see them fixed, and may help encourage people to upgrade to newer Linux kernels (which come with other benefits, like BPF).
- caf 11y ago
  It looks like the "Group Imbalance" and "Overload on Wakeup" bugs could be noticeable on a 2-node system under the right conditions. So could the "Missing Scheduling Domains" bug, but only if you are offlining / onlining CPUs. None of them should affect a 1-node system, and the "Scheduling Group Construction" bug requires a multi-level node hierarchy.
haberman 11y ago
This is absolutely nuts! If this result is true, our Linux machines have been wasting 13-24% of our silicon and energy for years (that number is for "typical Linux workloads") because the scheduler fails to fulfill its most basic duty. The quotes from Linus in the paper just twist the knife.
- rincebrain 11y ago
  ISTR something from Google about modifications to their Linux systems to eke out maximum resource utilization [1], so I would not be surprised if changes with this level of impact may exist. [1] - http://csl.stanford.edu/~christos/publications/2015.heracles.isca.pdf http://csl.stanford.edu/~christos/publications/2015.heracles...
- andrewchambers 11y ago
  If the CPU is idle it isn't wasting energy.
  - mjg59 11y ago
    The rest of the system is still a (roughly) fixed cost, and a 75% loaded CPU package still consumes more than 75% of the power of a 100% loaded CPU package.
  - dchest 11y ago
    From the linked paper: "Resulting performance degradations are in the range 13-24% for typical Linux workloads, and reach 138× in some corner cases. Energy waste is proportional."
- melchebo 11y ago
  From the looks of it, this mainly applies if you are running a NUMA system. Which you probably are not. Though it may apply in other places where 'scheduling domains' are used to model hardware (e.g. hyperthreading and maybe big.LITTLE).
  - rodgerd 11y ago
mmaunder 11y ago
I'm just a lowly performance obsessed dev who uses things like node, php, python, etc. I run very high traffic applications and spend a lot of time buying and building my own servers to try to eek out every ounce of performance. So can someone who knows about linux kernel internals explain the impact of this research? I read the abstract and some of the paper and it sounds very promising - like we may get significantly more performance out of our cores for multi-threaded or multi-process applications.
- im_down_w_otp 11y ago
  You will probably get significantly more performance out of your cores for multi-threaded or multi-process applications if you stop using node, php, python, etc. and use something that's more performance oriented.
  - _yosefk 11y ago
    Well, one might also get more performance per dollar if they programmed FPGAs, DSPs or GPUs instead of CPUs, and one might also get more performance per dollar if they designed their own hardware. (I do the latter for a living.) However, "performance of Node, PHP and Python" is a sensible goal in its own right, and I disagree with the implication of your comment, and that of sister comments, that it is not a sensible goal. There's a lot of useful code written in Node, PHP and Python, and moreover, this might remain true for a long while because "something more performance oriented" is likely to be less programmer productivity oriented in that a correct, easy to use program or library will take more time to get done. Also, Node and Python specifically can be damn fast (numpy for instance is unbeatable for large linear algebra programs, because it uses optimized libraries under the hood, etc. etc.) And some things simply can't be done in a satisfactory fashion in anything but a dynamic language, any more than you can get Apache to run on a GPU. "Dynamic" is a feature, not just a source of overhead. So "a performance-obsessed scripting language developer" is a perfectly fine way to describe oneself IMO.
    - pjc50 11y ago
      Aren't all three of those languages single-threaded? So the only way to distribute work is to run one copy per core and distribute on a per-request basis?
deleted 11y ago
[deleted]
Someone 11y ago
Page 8: "To fix this bug, we alter the code that is executed when a thread wakes up. We wake up the thread on the local core—i.e., the core where the thread was scheduled last— if it is idle; otherwise, if there are idle cores in the system, we wake up the thread on the core that has been idle for the longest amount of time." I don't quite understand the choice for picking the core that was idle for the longest time. I think they use that as a predictor of future load of the CPU, and scheduling based on future load see,s a good idea, but I think this could lead to cases where it prevents one of more CPUs to go to low power states when the system doesn't have enough work to keep all its cores fully occupied. (Edit: how did I overlook the following paragraph, where they discuss this issue?) Also, in general, I think they too easily call changes that remove the corner cases they find fixes. Chances are that they introduce other corner cases, either on workloads they didn't test or on hardware they didn't test (caveat: I know very little about the variation in hardware that is out there)
- mjg59 11y ago
  Picking the core that was idle for the longest period may end up working as a proxy for picking the coolest core, and as such encouraging more even distribution of heat and reducing the probability of thermal throttling?
  - Spidler 11y ago
    Couldn't it also work to prevent getting cores into deeper sleep states?
- melchebo 11y ago
  The last paragraph of that segment says they pick it because it's the first in the list of idle cores. E.g. if a core is no longer idle it removes itself from the list, and it adds itself at the end, so effectively it's ordered in deminishing idletime time. Though from my understanding of the patch they walk over all CPUs which is not precisely constant time, and it doesn't seem to be just the list of idle CPUs; for_each_online_cpu(_cpu): https://github.com/jplozi/wastedcores/blob/master/patches/overload_on_wakeup_linux_4.1.patch#L23 https://github.com/jplozi/wastedcores/blob/master/patches/ov... That said from what I grasp of the code it also doesn't bail out when power management is enabled, so maybe the public code or the paper are not at the same stage of development.
Animats 11y ago
Scheduling has become a hard problem. There's cache miss cost in moving a task from one CPU to another. CPUs can be put into power-saving states, but take time to come out of them. Sharing the run queue across CPUs has a locking cost. So it's now a cost optimization problem. That's a lot of work to be doing at the sub-millisecond decision level.
- fpoling 11y ago
  One of the point in the article is that despite scheduler's importance and complexity there were no tools that allowed to evaluate the performance. This work contributed such tools and those immediately allowed to identify quite a few bugs. Fixing those improves performance on NUMA systems rather substantially across various loads.
  - sitkack 11y ago
    You can't do science without measurement.
  - kevan 11y ago
    >there were no tools that allowed to evaluate the performance. This reminds me of Brian Cantril's remarks in a talk (sorry, can't remember which one) about Solaris and DTrace. For the first time ever, DTrace gave them the ability to look into the live performance of low-level OS code and they found a lot of pathological worst-case behavior that no one suspected beforehand. No matter how good your team is it's really hard to accurately predict how a system will behave, measurement is key.
- acqq 11y ago
  To take this work more seriously I miss the discussion of the potential negative effect of their patches. The way it's presented, it gives the false impression that "it will just work." However, their premise of "just wake the idle cores as soon as there are threads to run" can actually be harmful in some real-life scenarios, especially regarding the additional power use and the slowdown introduced by switching from the filled to the empty caches. Intuitively, as they demonstrate the "speedup" on some specific programs using some specific patterns I'd expect that some specific programs and patterns exist that don't necessary benefit from every change they present.
nickysielicki 11y ago
> the scheduler, that once used to be a simple isolated part of the kernel grew into a complex monster whose tentacles reached into many other parts of the system, That's what I call vivid language!
jondubois 11y ago
Many people in the Node.js community have had first-hand experience with with this issue. Node.js has had to turn off OS-based scheduling for its cluster module because you always ended up with a couple of CPUs taking all the load (and accepting new connections) while most of them remained idle. I thought it was either a bug with the TCP polling mechanism or with the Linux OS scheduler itself. It's good that this issue is finally getting some attention.
- melchebo 11y ago
  That might be what they call the 'overload on wakeup' bug. Maybe try the patch? I've read that the patch additionally needs a small fix, the goto label position went missing. Probably just before rcu_read_unlock() in that function: http://lxr.free-electrons.com/source/kernel/sched/fair.c#L5139 http://lxr.free-electrons.com/source/kernel/sched/fair.c#L51...
atemerev 11y ago
The year is 2016. Software engineers are still obsessed with squeezing every last drop of performance from a single core, adding multicore or distributed load support as an afterthought. Sorry, it doesn't work this way anymore. There will be no more single core performance increases — laws of physics forbid it. Instead, we will see more and more cores in common CPUs (64, then 256, then 1024 — then it will be merged with GPGPUs and FPGAs with their stream processing approach). Learn distributed programming or perish.
- jeffhuys 11y ago
  I don't think this is a good way to look at it. In my opinion, having a "perfect" single core is much more valuable than an octo-core CPU. Take a look at the iPhone 6s. Two cores, and it runs faster than some octo-core Androids. I may be a bit of a noob in this area, but something tells me that is significant.
  - wodenokoto 11y ago
    I'm also a noob, but according to parent, the reason why the iPhone runs faster is that all optimisation is done for 1 core, which would then leave the 8 cores doing nothing, despite having much, much more raw power available than the single iPhone core. Or put in another way: If we want more raw processing power, we need more cores, but we don't want more cores because software is optimised for a single core.
    - tigershark 11y ago
      Not true, even in multithreaded scenarios the A9 is more performant than the multicore android phones or it has a comparable performance in the worst case if I remember correctly. In single threaded scenarios it simply destroys all the other mobile chips and it is comparable with some low power Intel chips.
      - wodenokoto 11y ago
        That is the point. If software can't use multithreads, then strong single threads will win.
edwintorok 11y ago
Nice work: paper, (upcoming tools), and actual patches. Wish they'd look at disk I/O next, there are some problems there that are hard to describe other than anecdotically: e.g. my system runs on a SSD and periodically copies data to a HDD with rsnapshot. When rsnapshot runs rm on the HDD things freeze for a moment, (even switching windows in X) although the only thing using the HDD is that rm ...
- EdiX 11y ago
  Could it be https://lkml.org/lkml/2016/3/30/424 https://lkml.org/lkml/2016/3/30/424 ?
  - edwintorok 11y ago
    thanks, I'll have to try that although in my case the writes and reads are done on entirely different devices (although maybe there is a shared queue somewhere?)
- melchebo 11y ago
  It seems like everything with buffer/process queues needs a good polish to optimize for fairness. E.g. this is just being readied: http://blog.cerowrt.org/post/fq_codel_on_ath10k/ http://blog.cerowrt.org/post/fq_codel_on_ath10k/ (also note higher throughput as result)
unoti 11y ago
It'd be interesting to run the same tests on the Windows scheduler to see how it compares. Anyone know?
thrownaway2424 11y ago
I wonder what the impact is on networking loads. Often the most important thing is for a thread to wake on the core with ready access to the packet that woke it. Other scheduling concerns are counterproductive.
hinkley 11y ago
The bit about creating a cgroup per tty was news to me, and now I'm wondering if the way I usually manage Linux servers scales up to heavy traffic (usually if I'm involved it's small potatoes). Presumably things started as sysv scripts or even docker containers don't have this problem?
kazinator 11y ago
"Cores may stay idle for seconds while ready threads are waiting in runqueues." I do not believe it, sorry. Troll paper. Check out the massive indentation change in this patch which obscures the changes being made: https://github.com/jplozi/wastedcores/blob/master/patches/scheduling_group_construction_linux_4.1.patch https://github.com/jplozi/wastedcores/blob/master/patches/sc... Good grief.
- studentrob 11y ago
  Hm, github.com's diff doesn't let you ignore changes in whitespace? Bummer. Anyway that's not basis enough to invalidate their claims. They're published in EuroSys [1]. Is that not a reputable journal/conference? Plus this dude has a sweet CV layout [2]. I'm inclined to believe him on that basis alone. [1] http://www.i3s.unice.fr/~jplozi/wastedcores/ http://www.i3s.unice.fr/~jplozi/wastedcores/ [2] http://www.i3s.unice.fr/~jplozi/ http://www.i3s.unice.fr/~jplozi/
  - kazinator 11y ago
    Fact is, the "dude" doesn't know how to get his text editor to use the same tabbing as the kernel code he's editing, and doesn't know how to run a patch through the kernel's "checkpatch.pl" script, without which it will be rejected from upstreaming. The idea that the kernel runs idle tasks on cores while actual tasks are runnable (and that this situation persists for seconds) is ridiculous. It's such a gaping problem, that everyone doing anything with Linux anywhere would be running into it on a regular basis. Think about all the people out there who carefully profile the performance of their multi-threaded apps. Like all of them wouldn't notice missing seconds of execution?
    - studentrob 11y ago
      I've not studied this branch of CS since college a decade+ ago. As far as I know, certain elements of the kernel aren't modified very often. Also the researcher claims to introduce new tools that didn't exist before. Again I think if the journal, EuroSys, is reputable, then that journal would vet the findings properly. Replicating people's work is standard procedure. Maybe people need time to attempt that. Right on if you are proven right!
melchebo 11y ago
Presentation PDF: http://www.i3s.unice.fr/%7Ejplozi/wastedcores/files/extended_talk.pdf http://www.i3s.unice.fr/%7Ejplozi/wastedcores/files/extended...

467 points by tdurden 11y ago

j1vms 11y ago

As indicated in the paper, patches (currently for kernel 4.1) are here: https://github.com/jplozi/wastedcores https://github.com/jplozi/wastedcores

rando3826 11y ago
Are they accepted upstream? If not, I'd like to see a link to the lkml thread for these.
- rincebrain 11y ago
  I can't find any evidence they were submitted upstream at any juncture. Moreover, since (several of) the patches seem to rip out a bunch of logic in favor of very simple logic, they would probably be contentious without broad testing and probably a runtime option to configure the behavior.
  - verroq 11y ago
    And uses spaces instead of tabs. Someone will need to go fix them up.
    - jeffreyrogers 11y ago
      Not sure why you're being downvoted. Tabs instead of spaces is the Linux kernel style.
- justinmk 11y ago
  I wonder if they are discouraged by the experience of Con Kolivas[1] who proposed an alternative scheduler back in 2007. (Apparently he is still maintaining his "-ck" fork of the linux kernel[2]!) I only mention this as a historical case that has remained in my memory. Maybe Linus is willing to revisit the issue, I don't follow LKML. [1] https://en.wikipedia.org/wiki/Con_Kolivas https://en.wikipedia.org/wiki/Con_Kolivas [2] http://ck-hack.blogspot.com/2015/12/bfs-467-linux-43-ck3.html http://ck-hack.blogspot.com/2015/12/bfs-467-linux-43-ck3.htm...
  - LoSboccacc 11y ago
    I remember the whole debacle back then when the lkml was summarized on that website I can't remember It'd be interesting to see if that branch exhibit the same behavior and issues.
    - tremon 11y ago
      Maybe KernelTrap? I was sad when it shut down, it was a very useful resource for following Linux development from the sidelines.
      - LoSboccacc 11y ago
        Yeah that one! The memories.
    - DCoder 11y ago
      You might be thinking of LWN. They covered the scheduler multiple times over the years: https://lwn.net/Kernel/Index/#Scheduler https://lwn.net/Kernel/Index/#Scheduler
  - doe88 11y ago
    I do not follow Kernel Dev enough to have a good representation of what happened, but it seems to me that it was another example of smart people pushed out. Nowadays I think he is just maintaining his patches from one kernel release to the next, it was smart for Con to stop interacting with them and move to other types of devs, it comes a point where you have to keep your sanity.
- melchebo 11y ago
  The conference where this will be presented starts next week. So I think they'll post it after they catched up some sleep after that.
  - anonymousDan 11y ago
    Which conference, Eurosys?
    - desdiv 11y ago
      Yes, since the filename is eurosys16-final29.pdf.

thinkingkong 11y ago

Some authors appear to work with the old Xen crew (now founders at coho). Impressive work!

wutf 11y ago

This is extremely promising. Makes you wonder if we ought not go further and implement a machine learning-based scheduler that studies and anticipates workloads and schedules accordingly so as to help jobs complete as quickly as possible.

rifung 11y ago
Why machine learning? The paper says that the need to handle the complexities of modern hardware made it so that the scheduler failed to do its fundamental job. Machine learning sounds like it would add even more complexity but perhaps I just fail to see why machine learning is a good idea here. I don't see how you can predict workloads based off historical data and if you're going to try to predict workloads based off binaries, the overhead would likely outweigh any benefits you would get. I'll admit I am no expert in machine learning but I have a hard time understanding why you would look at this problem and think machine learning is the solution.
- wutf 11y ago
  "I don't see how you can predict workloads off of historical data" ... Think about that part, then:)
- tigershark 11y ago
  The only reason is because machine learning is fashionable at the moment and a lot of people like to suggest it as the panacea. I can't even imagine the terrible overhead that machine learning would impose in probably the most critical part of the OS.
  - wutf 11y ago
    Prediction can be extremely fast.
    - marcosdumay 11y ago
      But learning is always slow. What is the point of machine learning if you disable learning?

jor-el 11y ago

The quotes in the paper are interesting: "Nobody actually creates perfect code the first time around, except me. But there’s only one of me.” Linus Torvalds, 2007 And another, which highlights why there might be many more unearthed bugs, and would probably go unnoticed. "I suspect that making the scheduler use per-CPU queues together with some inter-CPU load balancing logic is probably trivial . Patches already exist, and I don’t feel that people can screw up the few hundred lines too badly" Looking at the bigger picture in general, this again shows that getting software right is not easy. Now and then you still hear about the bugs popping up in the code which is very core to an OS. One I can recall is a decade old TCP bug which Google fixed last year[1]. [1] http://bitsup.blogspot.sg/2015/09/thanks-google-tcp-team-for-open-source.html http://bitsup.blogspot.sg/2015/09/thanks-google-tcp-team-for...

akkartik 11y ago
I don't think the paper contradicts the second quote. It just points out that things got a lot more complex since. "this again shows that getting software right is not easy." Not easy, yes, but in my experience getting software right isn't too difficult. What seems impossibly hard is keeping software right, maintaining correctness in the presence of new requirements, compatibility constraints and just sheer caring about different things than we used to[1]. At some point I suspect you'd get a better design by rewriting things from scratch. But the way we do development makes rewriting stressful and error-prone, leading to the repeated arguments about whether rewriting is good or bad[2]. The question isn't whether rewriting is good or bad. Software is the most malleable medium known to man, and we should do all we can to embrace that essential malleability that is its primary characteristic and boon. The question is how not to mess up rewriting, how to keep our clay from gradually getting more and more brittle under the weight of added constraints. (I work on this problem: https://github.com/akkartik/mu/blob/7f5a95cdbe/Readme.md https://github.com/akkartik/mu/blob/7f5a95cdbe/Readme.md. It's been 31 days since I last got on my soapbox in this forum: https://news.ycombinator.com/item?id=11285529. https://news.ycombinator.com/item?id=11285529.) [1] "The future is a disagreement with the past about what is important." http://carlos.bueno.org/2010/10/predicting-the-future.html http://carlos.bueno.org/2010/10/predicting-the-future.html [2] Against rewrites: http://www.joelonsoftware.com/articles/fog0000000069.html; http://www.joelonsoftware.com/articles/fog0000000069.html; https://steveblank.com/2011/01/25/startup-suicide-%E2%80%93-rewriting-the-code; https://steveblank.com/2011/01/25/startup-suicide-%E2%80%93-... https://basildoncoder.com/blog/pg-wodehouse-method-of-refactoring.html https://basildoncoder.com/blog/pg-wodehouse-method-of-refact.... Pro-rewrite seems the minority position: http://brettweigl.tumblr.com/post/48385335083/what-can-product-managers-do-during-rewrites; http://brettweigl.tumblr.com/post/48385335083/what-can-produ... http://building.wanelo.com/2012/09/14/the-big-switch-how-we-rebuilt-wanelo-from-scratch-and-lived-to-tell-about-it.html; http://building.wanelo.com/2012/09/14/the-big-switch-how-we-... http://alicebob.cryptoland.net/why-i-rewrote-quivi-from-scratch http://alicebob.cryptoland.net/why-i-rewrote-quivi-from-scra... (with many apologies). And yet we've seen several major rewrites: Netscape (for all Joel Spolsky's criticism above, would Firefox had been possible without the rewrite? Echoing Jeff Bezos's dictum, open source projects can afford to be misunderstood for a long time), Python 3 [edit: no, Python 3 was not a rewrite as I was corrected below], Perl 6, Angular 2. A more balanced viewpoint: https://blog.learningbyshipping.com/2013/04/02/surviving-legacy-code https://blog.learningbyshipping.com/2013/04/02/surviving-leg....

blinkingled 11y ago

Interesting work certainly. The patches look more like proof of concept rather than something that's ready for mainline. I think they're better off if they post a RFC patch to LKML as it exists to facilitate discussion and testing.

melchebo 11y ago
It should probably mainly be seen as a proof of concept for their scheduler decision visualization tools. Which are not public for the time being. That should make checking and fixing bugs easier in the future.

akkartik 11y ago

Is anyone able to explain Figure 1? I don't understand what the levels are, and whether level 1 is the coarsest or the finest. The caption doesn't seem to make sense either way.. Also, Algorithm 1 is in terms of cpus, but the description mentions 'nodes' and 'cores'. Is a CPU a core or a node? Neither?

wmf 11y ago
Unfortunately the authors are using AMD machines which behave differently than most others because pairs of cores are conjoined into "modules" that share resources. In AMD processors, a cpu is a core. In almost all other processors, a cpu is a SMT thread (aka Hyperthread). In figure 1 the levels/shades represent distance from node/socket 1, darker being closer. So node 1 is distance 0 from itself, two other nodes are distance 1, and one node is distance 2.
- nazmunsuma 11y ago
  I agree.
- fulafel 11y ago
  ARM doesn't do SMT either.
- melchebo 11y ago
  From what I understand from this presentation the 'scheduling domain' abstraction is reused through different layers of the hierarchy. So for example the two hyperthreads on one logical core are also modeled as 'scheduling domain'. https://events.linuxfoundation.org/images/stories/slides/lfcs2013_murthy.pdf?update https://events.linuxfoundation.org/images/stories/slides/lfc...
- tremon 11y ago
  The only thing shared in a bulldozer core is the FPU (and perhaps some cache, not sure). For all other purposes, a bulldozer module contains two full CPU cores. Also, what CPUs besides Intel's and IBM's use SMT?

brendangregg 11y ago

I've worked scheduling bugs in other kernels before (Linux is not an outlier here). The key metric we keep an eye on is run queue latency, to detect when threads are waiting longer than one would expect. And there's many ways to measure it; my most recent is runqlat from bcc/BPF tools, which shows it as a histogram. eg: # ./runqlat Tracing run queue latency... Hit Ctrl-C to end. ^C usecs : count distribution 0 -> 1 : 233 |*********** | 2 -> 3 : 742 |************************************ | 4 -> 7 : 203 |********** | 8 -> 15 : 173 |******** | 16 -> 31 : 24 |* | 32 -> 63 : 0 | | 64 -> 127 : 30 |* | 128 -> 255 : 6 | | 256 -> 511 : 3 | | 512 -> 1023 : 5 | | 1024 -> 2047 : 27 |* | 2048 -> 4095 : 30 |* | 4096 -> 8191 : 20 | | 8192 -> 16383 : 29 |* | 16384 -> 32767 : 809 |****************************************| 32768 -> 65535 : 64 |*** | I'll also use metrics that sum it by thread to estimate speed up (which helps quantify the issue), and do sanity tests. Note that this isolates one issue -- wait time in the scheduler -- whereas NUMA and scheduling also effects memory placement, so the runtime of applications can become slower with longer latency memory I/O from accessing remote memory. I like to measure and isolate that separately (PMCs). So I haven't generally seen such severe scheduling issues on our 1 or 2 node Linux systems. Although they are testing on 8 node, which may exacerbate the issue. Whatever the bugs are, though, I'll be happy to see them fixed, and may help encourage people to upgrade to newer Linux kernels (which come with other benefits, like BPF).

caf 11y ago
It looks like the "Group Imbalance" and "Overload on Wakeup" bugs could be noticeable on a 2-node system under the right conditions. So could the "Missing Scheduling Domains" bug, but only if you are offlining / onlining CPUs. None of them should affect a 1-node system, and the "Scheduling Group Construction" bug requires a multi-level node hierarchy.

haberman 11y ago

This is absolutely nuts! If this result is true, our Linux machines have been wasting 13-24% of our silicon and energy for years (that number is for "typical Linux workloads") because the scheduler fails to fulfill its most basic duty. The quotes from Linus in the paper just twist the knife.

rincebrain 11y ago
ISTR something from Google about modifications to their Linux systems to eke out maximum resource utilization [1], so I would not be surprised if changes with this level of impact may exist. [1] - http://csl.stanford.edu/~christos/publications/2015.heracles.isca.pdf http://csl.stanford.edu/~christos/publications/2015.heracles...
andrewchambers 11y ago
If the CPU is idle it isn't wasting energy.
- mjg59 11y ago
  The rest of the system is still a (roughly) fixed cost, and a 75% loaded CPU package still consumes more than 75% of the power of a 100% loaded CPU package.
- dchest 11y ago
  From the linked paper: "Resulting performance degradations are in the range 13-24% for typical Linux workloads, and reach 138× in some corner cases. Energy waste is proportional."
melchebo 11y ago
From the looks of it, this mainly applies if you are running a NUMA system. Which you probably are not. Though it may apply in other places where 'scheduling domains' are used to model hardware (e.g. hyperthreading and maybe big.LITTLE).
- rodgerd 11y ago

mmaunder 11y ago

I'm just a lowly performance obsessed dev who uses things like node, php, python, etc. I run very high traffic applications and spend a lot of time buying and building my own servers to try to eek out every ounce of performance. So can someone who knows about linux kernel internals explain the impact of this research? I read the abstract and some of the paper and it sounds very promising - like we may get significantly more performance out of our cores for multi-threaded or multi-process applications.

im_down_w_otp 11y ago
You will probably get significantly more performance out of your cores for multi-threaded or multi-process applications if you stop using node, php, python, etc. and use something that's more performance oriented.
- _yosefk 11y ago
  Well, one might also get more performance per dollar if they programmed FPGAs, DSPs or GPUs instead of CPUs, and one might also get more performance per dollar if they designed their own hardware. (I do the latter for a living.) However, "performance of Node, PHP and Python" is a sensible goal in its own right, and I disagree with the implication of your comment, and that of sister comments, that it is not a sensible goal. There's a lot of useful code written in Node, PHP and Python, and moreover, this might remain true for a long while because "something more performance oriented" is likely to be less programmer productivity oriented in that a correct, easy to use program or library will take more time to get done. Also, Node and Python specifically can be damn fast (numpy for instance is unbeatable for large linear algebra programs, because it uses optimized libraries under the hood, etc. etc.) And some things simply can't be done in a satisfactory fashion in anything but a dynamic language, any more than you can get Apache to run on a GPU. "Dynamic" is a feature, not just a source of overhead. So "a performance-obsessed scripting language developer" is a perfectly fine way to describe oneself IMO.
  - pjc50 11y ago
    Aren't all three of those languages single-threaded? So the only way to distribute work is to run one copy per core and distribute on a per-request basis?

deleted 11y ago

[deleted]

Someone 11y ago

Page 8: "To fix this bug, we alter the code that is executed when a thread wakes up. We wake up the thread on the local core—i.e., the core where the thread was scheduled last— if it is idle; otherwise, if there are idle cores in the system, we wake up the thread on the core that has been idle for the longest amount of time." I don't quite understand the choice for picking the core that was idle for the longest time. I think they use that as a predictor of future load of the CPU, and scheduling based on future load see,s a good idea, but I think this could lead to cases where it prevents one of more CPUs to go to low power states when the system doesn't have enough work to keep all its cores fully occupied. (Edit: how did I overlook the following paragraph, where they discuss this issue?) Also, in general, I think they too easily call changes that remove the corner cases they find fixes. Chances are that they introduce other corner cases, either on workloads they didn't test or on hardware they didn't test (caveat: I know very little about the variation in hardware that is out there)

mjg59 11y ago
Picking the core that was idle for the longest period may end up working as a proxy for picking the coolest core, and as such encouraging more even distribution of heat and reducing the probability of thermal throttling?
- Spidler 11y ago
  Couldn't it also work to prevent getting cores into deeper sleep states?
melchebo 11y ago
The last paragraph of that segment says they pick it because it's the first in the list of idle cores. E.g. if a core is no longer idle it removes itself from the list, and it adds itself at the end, so effectively it's ordered in deminishing idletime time. Though from my understanding of the patch they walk over all CPUs which is not precisely constant time, and it doesn't seem to be just the list of idle CPUs; for_each_online_cpu(_cpu): https://github.com/jplozi/wastedcores/blob/master/patches/overload_on_wakeup_linux_4.1.patch#L23 https://github.com/jplozi/wastedcores/blob/master/patches/ov... That said from what I grasp of the code it also doesn't bail out when power management is enabled, so maybe the public code or the paper are not at the same stage of development.

Animats 11y ago

Scheduling has become a hard problem. There's cache miss cost in moving a task from one CPU to another. CPUs can be put into power-saving states, but take time to come out of them. Sharing the run queue across CPUs has a locking cost. So it's now a cost optimization problem. That's a lot of work to be doing at the sub-millisecond decision level.

fpoling 11y ago
One of the point in the article is that despite scheduler's importance and complexity there were no tools that allowed to evaluate the performance. This work contributed such tools and those immediately allowed to identify quite a few bugs. Fixing those improves performance on NUMA systems rather substantially across various loads.
- sitkack 11y ago
  You can't do science without measurement.
- kevan 11y ago
  >there were no tools that allowed to evaluate the performance. This reminds me of Brian Cantril's remarks in a talk (sorry, can't remember which one) about Solaris and DTrace. For the first time ever, DTrace gave them the ability to look into the live performance of low-level OS code and they found a lot of pathological worst-case behavior that no one suspected beforehand. No matter how good your team is it's really hard to accurately predict how a system will behave, measurement is key.
acqq 11y ago
To take this work more seriously I miss the discussion of the potential negative effect of their patches. The way it's presented, it gives the false impression that "it will just work." However, their premise of "just wake the idle cores as soon as there are threads to run" can actually be harmful in some real-life scenarios, especially regarding the additional power use and the slowdown introduced by switching from the filled to the empty caches. Intuitively, as they demonstrate the "speedup" on some specific programs using some specific patterns I'd expect that some specific programs and patterns exist that don't necessary benefit from every change they present.

nickysielicki 11y ago

> the scheduler, that once used to be a simple isolated part of the kernel grew into a complex monster whose tentacles reached into many other parts of the system, That's what I call vivid language!

jondubois 11y ago

Many people in the Node.js community have had first-hand experience with with this issue. Node.js has had to turn off OS-based scheduling for its cluster module because you always ended up with a couple of CPUs taking all the load (and accepting new connections) while most of them remained idle. I thought it was either a bug with the TCP polling mechanism or with the Linux OS scheduler itself. It's good that this issue is finally getting some attention.

melchebo 11y ago
That might be what they call the 'overload on wakeup' bug. Maybe try the patch? I've read that the patch additionally needs a small fix, the goto label position went missing. Probably just before rcu_read_unlock() in that function: http://lxr.free-electrons.com/source/kernel/sched/fair.c#L5139 http://lxr.free-electrons.com/source/kernel/sched/fair.c#L51...

atemerev 11y ago

The year is 2016. Software engineers are still obsessed with squeezing every last drop of performance from a single core, adding multicore or distributed load support as an afterthought. Sorry, it doesn't work this way anymore. There will be no more single core performance increases — laws of physics forbid it. Instead, we will see more and more cores in common CPUs (64, then 256, then 1024 — then it will be merged with GPGPUs and FPGAs with their stream processing approach). Learn distributed programming or perish.

jeffhuys 11y ago
I don't think this is a good way to look at it. In my opinion, having a "perfect" single core is much more valuable than an octo-core CPU. Take a look at the iPhone 6s. Two cores, and it runs faster than some octo-core Androids. I may be a bit of a noob in this area, but something tells me that is significant.
- wodenokoto 11y ago
  I'm also a noob, but according to parent, the reason why the iPhone runs faster is that all optimisation is done for 1 core, which would then leave the 8 cores doing nothing, despite having much, much more raw power available than the single iPhone core. Or put in another way: If we want more raw processing power, we need more cores, but we don't want more cores because software is optimised for a single core.
  - tigershark 11y ago
    Not true, even in multithreaded scenarios the A9 is more performant than the multicore android phones or it has a comparable performance in the worst case if I remember correctly. In single threaded scenarios it simply destroys all the other mobile chips and it is comparable with some low power Intel chips.
    - wodenokoto 11y ago
      That is the point. If software can't use multithreads, then strong single threads will win.

edwintorok 11y ago

Nice work: paper, (upcoming tools), and actual patches. Wish they'd look at disk I/O next, there are some problems there that are hard to describe other than anecdotically: e.g. my system runs on a SSD and periodically copies data to a HDD with rsnapshot. When rsnapshot runs rm on the HDD things freeze for a moment, (even switching windows in X) although the only thing using the HDD is that rm ...

EdiX 11y ago
Could it be https://lkml.org/lkml/2016/3/30/424 https://lkml.org/lkml/2016/3/30/424 ?
- edwintorok 11y ago
  thanks, I'll have to try that although in my case the writes and reads are done on entirely different devices (although maybe there is a shared queue somewhere?)
melchebo 11y ago
It seems like everything with buffer/process queues needs a good polish to optimize for fairness. E.g. this is just being readied: http://blog.cerowrt.org/post/fq_codel_on_ath10k/ http://blog.cerowrt.org/post/fq_codel_on_ath10k/ (also note higher throughput as result)

unoti 11y ago

It'd be interesting to run the same tests on the Windows scheduler to see how it compares. Anyone know?

thrownaway2424 11y ago

I wonder what the impact is on networking loads. Often the most important thing is for a thread to wake on the core with ready access to the packet that woke it. Other scheduling concerns are counterproductive.

hinkley 11y ago

The bit about creating a cgroup per tty was news to me, and now I'm wondering if the way I usually manage Linux servers scales up to heavy traffic (usually if I'm involved it's small potatoes). Presumably things started as sysv scripts or even docker containers don't have this problem?

kazinator 11y ago

"Cores may stay idle for seconds while ready threads are waiting in runqueues." I do not believe it, sorry. Troll paper. Check out the massive indentation change in this patch which obscures the changes being made: https://github.com/jplozi/wastedcores/blob/master/patches/scheduling_group_construction_linux_4.1.patch https://github.com/jplozi/wastedcores/blob/master/patches/sc... Good grief.

studentrob 11y ago
Hm, github.com's diff doesn't let you ignore changes in whitespace? Bummer. Anyway that's not basis enough to invalidate their claims. They're published in EuroSys [1]. Is that not a reputable journal/conference? Plus this dude has a sweet CV layout [2]. I'm inclined to believe him on that basis alone. [1] http://www.i3s.unice.fr/~jplozi/wastedcores/ http://www.i3s.unice.fr/~jplozi/wastedcores/ [2] http://www.i3s.unice.fr/~jplozi/ http://www.i3s.unice.fr/~jplozi/
- kazinator 11y ago
  Fact is, the "dude" doesn't know how to get his text editor to use the same tabbing as the kernel code he's editing, and doesn't know how to run a patch through the kernel's "checkpatch.pl" script, without which it will be rejected from upstreaming. The idea that the kernel runs idle tasks on cores while actual tasks are runnable (and that this situation persists for seconds) is ridiculous. It's such a gaping problem, that everyone doing anything with Linux anywhere would be running into it on a regular basis. Think about all the people out there who carefully profile the performance of their multi-threaded apps. Like all of them wouldn't notice missing seconds of execution?
  - studentrob 11y ago
    I've not studied this branch of CS since college a decade+ ago. As far as I know, certain elements of the kernel aren't modified very often. Also the researcher claims to introduce new tools that didn't exist before. Again I think if the journal, EuroSys, is reputable, then that journal would vet the findings properly. Replicating people's work is standard procedure. Maybe people need time to attempt that. Right on if you are proven right!

melchebo 11y ago

Presentation PDF: http://www.i3s.unice.fr/%7Ejplozi/wastedcores/files/extended_talk.pdf http://www.i3s.unice.fr/%7Ejplozi/wastedcores/files/extended...