Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

feat(maitake): add utilities for work-stealing #322

Merged
merged 47 commits into from
Oct 8, 2022
Merged

feat(maitake): add utilities for work-stealing #322

merged 47 commits into from
Oct 8, 2022

Conversation

hawkw
Copy link
Owner

@hawkw hawkw commented Sep 25, 2022

Summary

This branch adds support for implementing work-stealing systems across
multiple schedulers to the maitake::scheduler module. In particular,
it adds the following new APIs:

  • A scheduler::Injector type, representing a shared injector queue
    that can be used to spawn tasks to be executed by any of a set of
    worker Schedulers,
  • A scheduler::Stealer type, which wraps a
    cordyceps::mpsc_queue::Consumer and steals tasks from an Injector
    queue or Scheduler/StaticScheduler's run queue,
  • Scheduler::try_steal and StaticScheduler::try_steal methods, which
    return a Result<Stealer, TryStealError>, for attempting to steal
    tasks from a given scheduler's queue

I've also updated the mycelium::rt module to use these new APIs to
implement a global spawn with work-stealing across multiple cores.

Implementation Notes

In order to implement work-stealing, it was necessary to modify the
Task type to allow the scheduler field stored by the task to be
changed after the task is created. This may occur when a task is stolen
from one scheduler by another, or when a task is spawned on a shared
Injector queue and not yet bound to a scheduler.

This required changing the scheduler field to an UnsafeCell.
Currently, access to the UnsafeCell is controlled by the task's state
bits, and the current state system is sufficient for ensuring a task is
not bound to a new scheduler while it's queued.

Tasks can only be re-bound to the same type of scheduler, since the
size of the stored scheduler field must be the same when rebinding.
Currently, this is checked by a debug assertion in the Task code, and
the work-stealing APIs use PhantomData to prevent tasks from being
stolen from a scheduler of one type and spawned by a scheduler of a
different type.

Future Work

Some things that this branch doesn't do, but I'd like to get to in the
future:

  • Consider adding support in maitake for setting a global Injector
    queue
    to use with an ambiently-available task::spawn function?
  • Consider changing how tasks store the Schedule reference so that
    the UnsafeCell can be replaced with an AtomicPtr. This would
    probably require one of the following:
    • Changing the Schedule trait to have clone_scheduler(*const ())
      and drop_scheduler(*const ()) or similar, to hook into ref counting
      for the Arc scheduler,
    • Type-erasing Schedule instances with another custom vtable. That
      could potentially permit stealing tasks from a scheduler of one
      type onto a scheduler of a different type, if the vtable could also
      be changed (requiring a vtable pointer...)
  • Make the Injector queue work with the task::Builder API.
    Currently, tasks configured with a builder must be spawned on a real
    Scheduler, and cannot be spawned on an Injector. It would be nice
    to fix that.
  • Write more docs, including:
    • Guide level docs on how to implement work-stealing. I didn't write
      this yet because I'm lazy and want to get this PR merged sooner...
    • Add examples in the API docs

@hawkw hawkw force-pushed the eliza/worksteal branch 2 times, most recently from 3471e1e to 90d9851 Compare September 28, 2022 18:10
By using an exhaustive destructuring in manual `fmt::Debug` impls, we
get a compiler error if an additional field is added to a type with a
manual `Debug` impl which is not used in the `Debug` impl. This is nice,
since it helps guard against accidentally adding a field without
formatting it.

I've applied this refactoring to *most* manual `Debug` impls, with the
exception of a few that do something more weird than just manually
printing all the `Debug`-able field values.

This caught at least one case where I had forgotten to add a field to a
`Debug` impl :)
 
Thanks to Twitter User @cratelyn for this idea <3
@hawkw hawkw changed the title wip: feat(maitake): add utilities for work-stealing feat(maitake): add utilities for work-stealing Oct 8, 2022
@hawkw hawkw enabled auto-merge (squash) October 8, 2022 16:50
@hawkw hawkw merged commit 5283cf9 into main Oct 8, 2022
@hawkw hawkw deleted the eliza/worksteal branch October 8, 2022 16:58
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

Successfully merging this pull request may close these issues.

None yet

1 participant