Trait LocalRunQueue

pub trait LocalRunQueue<T = Task> {
    // Required methods
    fn current(&self) -> Option<&Arc<T>>;
    fn update_current(&mut self, flags: UpdateFlags) -> bool;
    fn try_pick_next(&mut self) -> Option<&Arc<T>>;
    fn dequeue_current(&mut self) -> Option<Arc<T>>;

    // Provided method
    fn pick_next(&mut self) -> &Arc<T> { ... }
}

A per-CPU, local runqueue.

This abstraction allows OSTD to inspect and manipulate local runqueues.

Conceptually, a local runqueue maintains:

1. A priority queue of runnable tasks. The definition of “priority” is left to the concrete implementation.
2. The current running task.

Interactions with OSTD

Overview

It is crucial for implementers of LocalRunQueue to understand how OSTD interacts with local runqueues.

A local runqueue is consulted by OSTD in response to one of four scheduling events:

• Yielding, triggered by Task::yield_now, where the current task voluntarily gives up CPU time.
• Sleeping, triggered by crate::sync::Waiter::wait or any synchronization primitive built upon it (e.g., crate::sync::WaitQueue, crate::sync::Mutex), which blocks the current task until a wake-up event occurs.
• Ticking, triggered periodically by the system timer (see crate::arch::timer::TIMER_FREQ), which provides an opportunity to do time accounting and consider preemption.
• Exiting, triggered when the execution logic of a task has come to an end, which informs the scheduler that the task is exiting and will never be enqueued again.

The general workflow for OSTD to handle a scheduling event is as follows:

1. Acquire exclusive access to the local runqueue using Scheduler::mut_local_rq_with.
2. Call LocalRunQueue::update_current to update the current task’s state, returning a boolean value that indicates whether the current task should and can be replaced with another runnable task.
3. If the task is about to sleep or exit, call LocalRunQueue::dequeue_current to remove it from the runqueue.
4. If the return value of update_current in Step 2 is true, then select the next task to run with LocalRunQueue::pick_next.

When to Pick the Next Task?

As shown above, OSTD guarantees that pick_next is only called when the current task should and can be replaced. This avoids unnecessary invocations and improves efficiency.

But under what conditions should the current task be replaced? Two criteria must be met:

1. There exists at least one other runnable task in the runqueue.
2. That task should preempt the current one, if present.

Some implications of these rules:

• If the runqueue is empty, update_current must return false—there’s nothing to run.
• If the runqueue is non-empty but the current task is absent, update_current should return true—anything is better than nothing.
• If the runqueue is non-empty and the flag is UpdateFlags::WAIT, update_current should also return true, because the current task is about to block.
• In other cases, the return value depends on the scheduler’s prioritization policy. For instance, a real-time task may only be preempted by a higher-priority task or if it explicitly yields. A normal task under Linux’s CFS may be preempted by a task with smaller vruntime, but never by the idle task.

When OSTD is unsure about whether the current task should or can be replaced, it will invoke LocalRunQueue::try_pick_next, the fallible version of pick_next.

Internal Working

To guide scheduler implementers, we provide a simplified view of how OSTD interacts with local runqueues internally in order to handle the four scheduling events.

Yielding

/// Yields the current task.
fn yield(scheduler: &'static dyn Scheduler) {
    let next_task_opt: Option<Arc<Task>> = scheduler.mut_local_rq_with(|local_rq| {
        let should_pick_next = local_rq.update_current(UpdateFlags::Yield);
        should_pick_next.then(|| local_rq.pick_next().clone())
    });
    let Some(next_task) = next_task_opt {
        switch_to(next_task);
    }
}

Sleeping

/// Puts the current task to sleep.
///
/// The function takes a closure to check if the task is woken.
/// This function is used internally to guard against race conditions,
/// where the task is woken just before it goes to sleep.
fn sleep<F: Fn() -> bool>(scheduler: &'static dyn Scheduler, is_woken: F) {
    let mut next_task_opt: Option<Arc<Task>> = None;
    let mut is_first_try = true;
    while scheduler.mut_local_rq_with(|local_rq| {
        if is_first_try {
            if is_woken() {
                return false; // exit loop
            }
            is_first_try = false;

            let should_pick_next = local_rq.update_current(UpdateFlags::Wait);
            let _current = local_rq.dequeue_current();
            if !should_pick_next {
                return true; // continue loop
            }
            next_task_opt = Some(local_rq.pick_next().clone());
            false // exit loop
        } else {
            next_task_opt = local_rq.try_pick_next().cloned();
            next_task_opt.is_none()
        }
    }) {}
    let Some(next_task) = next_task_opt {
        switch_to(next_task);
    }
}

Ticking

/// A callback to be invoked periodically by the timer interrupt.
fn on_tick(scheduler: &'static dyn Scheduler) {
    scheduler.mut_local_rq_with(|local_rq| {
        let should_pick_next = local_rq.update_current(UpdateFlags::Tick);
        if should_pick_next {
            cpu_local::set_need_preempt();
        }
    });
}

/// A preemption point, called at an earliest convenient timing
/// when OSTD can safely preempt the current running task.
fn might_preempt(scheduler: &'static dyn Scheduler) {
    if !cpu_local::should_preempt() {
        return;
    }
    let next_task_opt: Option<Arc<Task>> = scheduler
        .mut_local_rq_with(|local_rq| local_rq.try_pick_next().cloned())
    let Some(next_task) = next_task_opt {
        switch_to(next_task);
    }
}

Exiting

/// Exits the current task.
fn exit(scheduler: &'static dyn Scheduler) {
    let mut next_task_opt: Option<Arc<Task>> = None;
    let mut is_first_try = true;
    while scheduler.mut_local_rq_with(|local_rq| {
        if is_first_try {
            is_first_try = false;
            let should_pick_next = local_rq.update_current(UpdateFlags::Exit);
            let _current = local_rq.dequeue_current();
            if !should_pick_next {
                return true; // continue loop
            }
            next_task_opt = Some(local_rq.pick_next().clone());
            false // exit loop
        } else {
            next_task_opt = local_rq.try_pick_next().cloned();
            next_task_opt.is_none()
        }
    }) {}
    let next_task = next_task_opt.unwrap();
    switch_to(next_task);
}

Required Methods

fn current(&self) -> Option<&Arc<T>>

Gets the current runnable task.

fn update_current(&mut self, flags: UpdateFlags) -> bool

Updates the current runnable task’s scheduling statistics and potentially its position in the runqueue.

The return value of this method indicates whether an invocation of pick_next should be followed to find another task to replace the current one.

fn try_pick_next(&mut self) -> Option<&Arc<T>>

Tries to pick the next runnable task.

This method instructs the local runqueue to pick the next runnable task on a best-effort basis. If such a task can be picked, then this task supersedes the current task and the new the method returns a reference to the new “current” task. If the “old” current task presents, then it is still runnable and thus remains in the runqueue.

fn dequeue_current(&mut self) -> Option<Arc<T>>

Removes the current runnable task from runqueue.

This method returns the current runnable task. If there is no current runnable task, this method returns None.

Provided Methods

fn pick_next(&mut self) -> &Arc<T>

Picks the next runnable task.

This method instructs the local runqueue to pick the next runnable task and replace the current one. A reference to the new “current” task will be returned by this method. If the “old” current task presents, then it is still runnable and thus remains in the runqueue.

Panics

As explained in the type-level Rust doc, this method will only be invoked by OSTD after a call to update_current returns true. In case that this contract is broken by the caller, the implementer is free to exhibit any undesirable or incorrect behaviors, include panicking.

Implementors