Scheduler work stealing.

[bblum]

Currently: Tasks are scheduled on sched_loops in round-robin fashion, and are tied to their sched_loop for their entire lifetime. This can lead to surprising performance with irregular task setups.

It does not seem too hard to implement a 'steal' mechanism by which idle sched_loops can reach over to overloaded ones to balance some of the load. My impression is that the classic presentation involves idle processors busy-looping around the steal mechanism until they pick up something to do; I've even seen a talk on a purportedly very clever mechanism that was totally lockless. But... we just can't eat up all CPUs when not fully loaded.

One thing I haven't quite grasped is how to do this without thrashing some global synchronisation whenever we decide to steal. If I'm not mistaken, the whole point of work stealing is that each processor's runqueue not be in a cacheline that multiple processors want... but I think that if we want to suspend idle CPUs, we need to have a global semaphore-alike setup that gets poked every time a task (a) spawns, (b) blocks, (c) wakes, (d) exits. And, well, this is basically when scheduler runqueues get accessed anyway.

Currently we take a global (per-scheduler) lock on (a) and (d) already, but not (b) or (c). Is there an option for work stealing that puts idle CPUs to sleep without hitting global state during the extra lifecycle events?

[brson]

I don't have any answers right now, but I'm going to drop this link here: http://supertech.csail.mit.edu/papers.html. These are all the cilk papers, many about work stealing.

[nikomatsakis]

One thing: not having to solve these kinds of annoying---but solved---implementation decisions is the reason why I thought it make sense to consider basing our implementation on a well-tested scheduler, like TBB. I still basically think we ought to try prototyping that.

That said, there are existing implementations that do solve these kinds of problems, and to the extent allowed by law we can also peek at what they do. I remember I did a few things when I was implementing my own work-stealing scheduler a while back, but I don't remember what worked well—I think I was never fully satisfied with this particular aspect of my design, as there was a potential race in which a thread might go to sleep just as new work was being posted and hence be idle. Of course that thread would wake if there were yet more work posted, or if a certain timeout elapsed, so in practice this wasn't a big deal. But I imagine there are more elegant solutions out there.

[graydon]

Hmm. So on irc I said I'd like you to clarify the bug in terms of sched vs thread, and I'll repeat that request here in more detail.

Here is my (possibly wrong) understanding of the current system:

By default there is one sched. It's multi threaded and the threads all share a pool of tasks. So that may involve too much locking but it already means that most tasks auto balance across idle cores.

If a user makes multiple scheds, it's generally because they want to pin a task to a thread. Or a smaller set of threads. That's the whole reason the api for multiple scheds exists. So in these cases, stealing tasks between scheds is incorrect, by definition.

If I'm right about those assumptions, then I don't really see what this bug means, except maybe taking fewer locks in the multi threaded sched case. Am I misinformed of how the current system works?

[nikomatsakis]

I had assumed that this referred to stealing within the main scheduler? It seems like we ought to have each scheduler map to a pool of threads (which possibly has size 1). Tasks may move around within this pool however we like but do not cross pools.

Also—there is lots of interesting work on scheduling for better locality. In particular for Servo, Leo Meyerovich's work at Berkeley on parallelizing layout uses a variation on work-stealing in which they first do classic work stealing, but they record which processor ended up processing which nodes in the tree. In latter phases they just replay this. Or something like that. He claimed it was essential for good performance, as classical work stealing proved too much overhead. So I'm sure we'll be tweaking this as we go to give user's more control!

[bblum]

@brson ooh, useful. I didn't look yet at the cilk papers, but the "worst page-replacement policy" paper (well, the abstract) is amazing.

@nikomatsakis I am still not sure what the nature of the problem is. if the answer is "Well yeah, you just suck it up and bounce on a global lock for every lifecycle operation", well, that wouldn't take much effort at all to implement with what we've got. if, on the other hand, there are clever heuristics that achieve good balancing and avoiding the global lock, that wheel would be a lot worse to reinvent.

@graydon No, threads within a sched do not share a pool of tasks; each thread has their own pool. The benefit which we'd lose from changing to what you described is the task block/wakeup paths only need a per-cpu lock (sched_loop->lock), rather than the global lock needed for spawn and exit (scheduler->lock).

Basically what you described is what we want; the question is how can we implement it right.

@nikomatsakis hmm. nodes in trees is getting a lot closer to data-aware scheduling, which is beyond the scope of the runtime scheduler. It might be easy to make the runtime expose a "cpu affinity" option, and have a data-aware library that makes use of that.

[nikomatsakis]

@bblum I don't know what the best solutions are either. Clearly busy-looping trying to steal isn't it. I think what I had before was pretty straight-forward: basically a shared boolean flag indicated whether there were any idle threads combined with a linked list of idle threads. After they failed to steal, threads would acquire a lock, atomically add themselves to the list, and set the flag. When producing work, you would check the flag and, if it is true, wake up an idle task and deliver the work item directly to them rather than pushing it onto your queue. However, I don't claim this was particularly smart, as I said I was never fully satisfied with it. I don't know what sort of protocols are used in other systems, it feels like you can do better though!

[bblum]

@nikomatsakis "when you had before" - what system was that for?

it sounds like that's analogous to the "global lock" approach i was mentioning - producing work is task-wakeup (always), and becoming idle is task-block-if-it-was-your-last-task. it sounds like becoming idle was the complicated path in your system, which is in keeping with the point of work-stealing that busy cpus not be burdened with it.

i think there is probably not a way to avoid global locking in the wakeup case. i suspect tasks blocking can bypass the global lock if it wasn't the last task on that cpu.

i will also note that the cpu affinity i mentioned above is a good reason to keep one-runqueue-per-cpu instead of a global pool of tasks.

[nikomatsakis]

@bblum this was a scheduler I did as part of my PhD work. Ultimately the system relied on a global lock, the flag was used to avoid touching the lock in the common case where lots of tasks are being produced and the system is generally operating at a good level of throughput (in which case, tasks are not idle).

[nikomatsakis]

oh, @bblum, regarding the data-specific stuff, I am envisioning that there will be custom schedulers tailored to specific strategies, perhaps even schedulers implemented just for one application.

[bblum]

I won't have time to do this justice before my internship is over.

[brson]

That's ok! The work you did on tasks was awesome.

[bblum]

One important implementation detail note: in rust_sched_loop - currently, current task stays on the RQ. If it gets taken off, i.e. to steal it, that may introduce a problem where it won't get killed by kill_all if the runtime is failing.

This has to do with the fix for #2671 - sched_loops now have a field called killed, which is set when the runtime fails. If this races with stealing (i.e., so the stolen task misses the kill signal), the sched_loop would need to check its killed flag before starting to run the stolen task.