Expand description
Key-affine fair scheduling as a pure data structure.
There is no async, no clock, no IO and no allocation policy here beyond the
queues this module owns. Time is an explicit monotonic Duration supplied
by the caller, and work items are opaque payloads. The exceptions are
[ring] and [waker_slot], which are here for unsafe containment rather
than because they are part of the scheduling model; see below.
§Fairness model
Each key has at most one in-flight item, so a key with a million queued items occupies exactly one dispatch slot, the same as a key with one. Given that, fairness reduces to which ready key is dispatched next?
A completed key is never greedily re-dispatched. Both new arrivals and
completions place a key at the BACK of a round-robin ready ring, and
dispatch always pops from the FRONT. A key sitting at position k is
therefore dispatched within k dispatches: a strict bound, hence
starvation-free. One key cannot monopolize a shard.
There is one ring per work class, each with its own in-flight budget, so a flood of one class cannot starve another. A key routes to a ring based on the class of its CURRENT queue head, so a key with mixed classes moves between rings in FIFO order as it drains.
§Trusting the caller
Everything this module knows about a payload: its affine key, its work class and its optional deadline: is stamped once by the caller at admission and never recomputed. A caller-supplied trait implementation that answered inconsistently on a second call would otherwise desynchronize the ready rings from the per-key queues, so the opportunity is removed rather than documented away.
§Unsafe code
This crate is where the workspace keeps its unsafe, so that there is one
place to audit rather than a policy with exceptions. Every other crate is
#![deny(unsafe_code)], and here it is confined to modules that opt back in
one at a time:
- the queue slab, which indexes without bounds checks;
- [
waker_slot], which guards anOption<Waker>with a two-bit lock; - [
ring], which guards a slot’s value with a publication stamp; - the cell shim the last two share, which is one constructor and one
accessor and exists so that both present loom’s checked
UnsafeCellshape rather than each rolling its own.
Each states the invariant it relies on at the top of its file,
debug_assert!s it at every use, and is checked by a model test under Miri.
The two synchronization primitives are additionally model-checked by loom,
which verifies the exclusion arguments mechanically: a slot read that
escaped its stamp fails the model as a causality violation rather than
passing as undefined behaviour that happens not to bite.
Modules§
- timer
- A predictable, shard-local hierarchical timer wheel.
Structs§
- Admit
- A work item being admitted, with its scheduling metadata already stamped.
- Completion
- The result of a dispatched item, returned to the scheduler.
- Config
- Per-shard scheduling limits.
- Dispatch
- A work item that the scheduler has granted exclusive ownership of its key.
- Scheduler
- A key-affine, class-fair scheduler over opaque payloads
Pand per-key stateS. - Snapshot
- Instantaneous scheduler gauges.
Enums§
- Disposition
- What became of a key’s state once its work finished.
Type Aliases§
- ClassId
- Index of a work class, in
0..CLASSES.