3 ms·
First of all, great article! Lots of interesting details and great explaination. A few questions: Did you consider work sharing or work requesting instead of
by gpderetta 7y ago
First of all, great article! Lots of interesting details and great explaination.
A few questions:
Did you consider work sharing or work requesting instead of work stealing (the global queue is a form of work sharing of course)? With work requesting you can avoid the required store/load on the pop path. Of course work requesting is not appropriate if the scheduler need to protect against the occasional long running job that doesn't yield to the scheduler in time to service a work request with appropriate frequency, but assuming this is rare enough, an expensive last resort work stealing path could be done via asymmetric synchronization (i.e. sys_membarrier or similar), keeping the pop fast path, well, fast.
Is there any way to make (groups of) tasks be constrained to a specific scheduler? This is particularly useful if they all need to access specific resources as there is no need of mutual exclusion; this works well in applications were executors are eterogeneous and have distinct responsibilities.
Because of the global queue and the work-stealing behaviour, absolutely no ordering is guaranteed for any task, is that correct?
I find surprising that you need to reference count a task explicitly. Having implemented a similar scheduler (albeit in C++), I haven't found the need of refcounting: normally the task is owned by either a scheduler queue or a single wait queue (but obviously never both). In case the task is waiting for any of multiple events, on first wake-up it will unregister itself from all remaining events (tricky but doable); only in the case were is waiting for N events you need an (atomic) count of the events delivered so far (and only if you want to avoid having to wake up to immediately go to sleep waiting for the next event). Also this increment comes for free if you need an expensive synchronization in the wake-up path.
That's all so far, I'm sure I'll come up with more questions later. Again great job and congratulations on the performance improvements.
- Matthias247 7y agoTo answer one question: > I find surprising that you need to reference count a task explicitly. This is likely due to how the task and waker system is defined in Rust. A Waker is kind of a handle to the task, whose lifetime is indefinite. Some code can have a handle/Waker to a task which already has finished long ago. One way to make sure the handle is still valid is to reference count it. Since in the Tokio system the Waker/handle and the tasks internal state are actually the same object, this means the combined state gets a reference count.
- carllerche 7y ago> Did you consider work sharing or work requesting instead of work stealing Not really. It did cross my mind for a moment, but my gut (which is often wrong) is the latency needed to request would be much higher than what is needed to steal. I probably should test it though at some point :) > assuming this is rare enough, an expensive last resort work stealing It's not _that_ rare. Stealing is key when a large batch of tasks arrive (usually after a call to `epoll_wait`). Again, I have no numbers to back any of this :)
- gpderetta 7y agoThe idea is to steal only if request fails to return work in a reasonable time frame i.e. if a job is keeping the scheduler busy for more than a minimum amount of time. I also have no number to back it up (we deal wit a relatively small numbers of fds at $JOB and we care of latency more than throughput), but I do not buy epoll_wait generating late batches of work: it seems to me that you should only be using epoll for fds that are unlikely to be ready for io (i.e those for which a speculative read or write has returned EWOULDBLOCK), which means you should not have large batches of ready fds. Even if you do, the only case you would need to steal after that is if another processor run out of work after this processor returned from epoll wait (if it did before, it should have blocked on the same epoll FD and got a chunk of the work directly or could have signaled a request for work), which might be less likely. Anyway at the end of the day a singe mostly uncontested CAS is relatively cheap on x86 especially if the average job length is large enough, so maybe it is just not worth optimizing it further, especially if it requires more complexity.