Module maitake::scheduler

Schedulers for executing tasks.

In order to execute asynchronous tasks, a system must have one or more schedulers. A scheduler (also sometimes referred to as an executor) is a component responsible for tracking which tasks have been woken, and polling them when they are ready to make progress.

This module contains scheduler implementations for use with the maitake task system.

Using Schedulers

This module provides two types which can be used as schedulers. These types differ based on how the core data of the scheduler is shared with tasks spawned on that scheduler:

• Scheduler: a reference-counted single-core scheduler (requires the “alloc” feature). A Scheduler is internally implemented using an Arc, and each task spawned on a Scheduler holds an Arc clone of the scheduler core.
• StaticScheduler: a single-core scheduler stored in a static variable. A StaticScheduler is referenced by tasks spawned on it as an &'static StaticScheduler reference. Therefore, it can be used without requiring alloc, and avoids atomic reference count increments when spawning tasks. However, in order to be used, a StaticScheduler must be stored in a 'static, which can limit its usage in some cases.
• LocalScheduler: a reference-counted scheduler for !Send Futures (requires the “alloc” feature). This type is identical to the Scheduler type, except that it is capable of spawning Futures that do not implement Send, and is itself not Send or Sync (it cannot be shared between CPU cores).
• LocalStaticScheduler: a StaticScheduler variant for !Send Futures. This type is identical to the StaticScheduler type, except that it is capable of spawning Futures that do not implement Send, and is itself not Send or Sync (it cannot be shared between CPU cores).

The Schedule trait in this module is used by the Task type to abstract over both types of scheduler that tasks may be spawned on.

Spawning Tasks

Once a scheduler has been constructed, tasks may be spawned on it using the Scheduler::spawn or StaticScheduler::spawn methods. These methods allocate a new Box to store the spawned task, and therefore require the “alloc” feature.

Alternatively, if custom task storage is in use, the scheduler types also provide Scheduler::spawn_allocated and StaticScheduler::spawn_allocated methods, which allow spawning a task that has already been stored in a type implementing the task::Storage trait. This can be used without the “alloc” feature flag, and is primarily intended for use in systems where tasks are statically allocated, or where an alternative allocator API (rather than liballoc) is in use.

Finally, to configure the properties of a task prior to spawning it, both scheduler types provide Scheduler::build_task and StaticScheduler::build_task methods. These methods return a task::Builder struct, which can be used to set properties of a task and then spawn it on that scheduler.

Executing Tasks

In order to actually execute the tasks spawned on a scheduler, the scheduler must be driven by dequeueing tasks from its run queue and polling them.

Because maitake is a low-level async runtime “construction kit” rather than a complete runtime implementation, the interface for driving a scheduler is tick-based. A tick refers to an iteration of a scheduler’s run loop, in which a set of tasks are dequeued from the scheduler’s run queue and polled. Calling the Scheduler::tick or StaticScheduler::tick method on a scheduler runs that scheduler for a single tick, returning a Tick struct with data describing the events that occurred during that tick.

The scheduler API is tick-based, rather than providing methods that continuously tick the scheduler until all tasks have completed, because ticking a scheduler is often only one step of a system’s run loop. A scheduler is responsible for polling the tasks that have been woken, but it does not wake tasks which are waiting for other runtime services, such as timers and I/O resources.

Typically, an iteration of a system’s run loop consists of the following steps:

• Tick the scheduler, executing any tasks that have been woken,
• Tick a [timer]¹, to advance the system clock and wake any tasks waiting for time-based events,
• Process wakeups from I/O resources, such as hardware interrupts that occurred during the tick. The component responsible for this is often referred to as an I/O reactor.
• Optionally, spawn tasks from external sources, such as work-stealing tasks from other schedulers, or receiving tasks from a remote system.

The implementation of the timer and I/O runtime services in a bare-metal system typically depend on details of the hardware platform in use. Therefore, maitake does not provide a batteries-included runtime that bundles together a scheduler, timer, and I/O reactor. Instead, the lower-level tick-based scheduler interface allows running a maitake scheduler as part of a run loop implementation that also drives other parts of the runtime.

A single call to Scheduler::tick will dequeue and poll up to Scheduler::DEFAULT_TICK_SIZE tasks from the run queue, rather than looping until all tasks in the queue have been dequeued.

Examples

A simple implementation of a system’s run loop might look like this:

use maitake::scheduler::Scheduler;

/// Process any time-based events that have occurred since this function
/// was last called.
fn process_timeouts() {
    // this might tick a `maitake::time::Timer` or run some other form of
    // time driver implementation.
}


/// Process any I/O events that have occurred since this function
/// was last called.
fn process_io_events() {
    // this function would handle dispatching any I/O interrupts that
    // occurred during the tick to tasks that are waiting for those I/O
    // events.
}

/// Put the system into a low-power state until a hardware interrupt
/// occurs.
fn wait_for_interrupts() {
    // the implementation of this function would, of course, depend on the
    // hardware platform in use...
}

/// The system's main run loop.
fn run_loop() {
    let scheduler = Scheduler::new();

    loop {
        // process time-based events
        process_timeouts();

        // process I/O events
        process_io_events();

        // tick the scheduler, running any tasks woken by processing time
        // and I/O events, as well as tasks woken by other tasks during the
        // tick.
        let tick = scheduler.tick();

        if !tick.has_remaining {
            // if the scheduler's run queue is empty, wait for an interrupt
            // to occur before ticking the scheduler again.
            wait_for_interrupts();
        }
    }
}

Scheduling in Multi-Core Systems

WIP ELIZA WRITE THIS

---

1. The maitake::time module provides one Timer implementation, but other timers could be used as well. ↩

Macros

• new_static
  Safely constructs a new StaticScheduler instance in a static initializer.

Structs

• Injector
  An injector queue for spawning tasks on multiple Scheduler instances.
• LocalScheduleralloc
  A reference-counted scheduler for !Send tasks.
• LocalSpawneralloc
  A handle to a LocalScheduler that implements Send.
• LocalStaticScheduler
  A statically-initialized scheduler for !Send tasks.
• LocalStaticSpawner
  A handle to a LocalStaticScheduler that implements Send.
• Scheduleralloc
  An atomically reference-counted single-core scheduler implementation.
• StaticScheduler
  A statically-initialized scheduler implementation.
• Stealer
  A handle for stealing tasks from a Scheduler’s run queue, or an Injector queue.
• TaskStub
  A stub Task.
• Tick
  Metrics recorded during a scheduler tick.

Enums

• TryStealError
  Errors returned by Injector::try_steal, Scheduler::try_steal, and StaticScheduler::try_steal.

Traits

• Schedule
  Trait implemented by schedulers.