Scheduler

Scheduler is a trait for the scheduler and defined in awkernel_async_lib/src/scheduler.rs as follows.

#![allow(unused)]
fn main() {
pub(crate) trait Scheduler {
    /// Enqueue an executable task.
    /// The enqueued task will be taken by `get_next()`.
    fn wake_task(&self, task: Arc<Task>);

    /// Get the next executable task.
    fn get_next(&self) -> Option<Arc<Task>>;

    /// Get the scheduler name.
    fn scheduler_name(&self) -> SchedulerType;

    #[allow(dead_code)] // TODO: to be removed
    fn priority(&self) -> u8;
}
}

There are several functions regarding the scheduler in awkernel_async_lib/src/scheduler.rs.

SchedulerType is an enum for the scheduler type and defined in awkernel_async_lib/src/scheduler.rs as follows.

#![allow(unused)]
fn main() {
pub enum SchedulerType {
    ClusteredEDF(u64, CpuSet), // relative deadline and CPU affinity set
    GEDF(u64),                 // relative deadline
    PrioritizedFIFO(u8),
    PrioritizedRR(u8),
    Panicked,
}
}

SleepingTasks

SleepingTasks is a struct for managing sleeping tasks and defined in awkernel_async_lib/src/scheduler.rs as follows.

#![allow(unused)]
fn main() {
struct SleepingTasks {
    delta_list: DeltaList<Box<dyn FnOnce() + Send>>,
    base_time: u64,
}
}

SleepingTasks struct has the following functions.

Scheduler Implementation

Some schedulers are implemented under the folder awkernel_async_lib/src/scheduler.

$ ls awkernel_async_lib/src/scheduler
> clustered_edf.rs  gedf.rs  panicked.rs  prioritized_fifo.rs  prioritized_rr.rs

A scheduler can be implemented by implementing Scheduler Trait. Each scheduler must be registered in the following three locations. fn get_next_task(), fn get_scheduler(sched_type: SchedulerType) and pub enum SchedulerType.

ClusteredEDF Scheduler

The Clustered Earliest Deadline First (ClusteredEDF) scheduler is implemented in clustered_edf.rs. This scheduler is an EDF variant that restricts each task to a set of CPU cores (a cluster), specified as a CpuSet bitmask. Pinning a task to a single core (partitioned scheduling) is the special case of a one-bit CpuSet.

The scheduler holds a single affinity-aware priority queue, AffinityBTreeQueue, backed by an augmented B-tree. Each entry carries (priority, affinity, task), where the priority is the pair (absolute_deadline, wake_time); smaller values dequeue first, so tasks are ordered by earliest deadline with wake time as a tie-breaker. Every B-tree node stores the OR of the affinities in its subtree, which lets pop_for_cpu(cpu) find the earliest-deadline task runnable on cpu in logarithmic time while skipping subtrees with no eligible entry.

When a task is enqueued via wake_task(), the scheduler reads the SchedulerType::ClusteredEDF(relative_deadline, cpu_set) attached to the task and calculates the absolute deadline as uptime + relative_deadline. If the task is part of a DAG, calculate_and_update_dag_deadline() (shared with the GEDF scheduler) is used instead to propagate deadlines through the DAG. The task is then pushed into the queue with its cpu_set as the affinity mask. Preemption is handled via invoke_preemption(): if no core in the set is idle and the task is not already running, the core running the lowest-priority task among the set is chosen, and an IPI is sent to it when the newly enqueued task has an earlier deadline than the task currently running (or pending preemption) on that core.

get_next() pops the earliest-deadline task whose cpu_set contains the calling CPU (pop_for_cpu), so a task is only ever dequeued by a core within its set. This guarantees CPU affinity. CPU 0 (the primary core) is always excluded from cpu_set when a task is spawned. The cpu_set is normalized at spawn time by removing CPU 0 and out-of-range bits; if this leaves the set empty (for example an empty set, or one naming only CPU 0 or out-of-range cores), the task is not rejected but falls back to all worker cores (1..num_cpu()) with a warning.

Bookkeeping for sleeping workers uses two pieces of state. A single global counter (NUM_CLUSTERED_TASKS_IN_QUEUE) tracks how many tasks are queued across all clustered schedulers; it is maintained by the ClusteredTask RAII wrapper (incremented on enqueue, decremented exactly once on dequeue or drop) and lets get_next_task() skip the clustered schedulers entirely when it is zero. The per-CPU information — which CPUs actually have an eligible task queued — is not duplicated in counters: it is read directly from the run queue, whose B-tree root already maintains the OR of all queued affinities (affinity_mask(), O(1)). wake_workers() obtains this set via Scheduler::queued_cpu_mask() (unioned over all clustered schedulers by clustered_queued_cpu_mask()) and wakes exactly the cores that have an eligible clustered task.

A new clustered scheduler must (1) wrap its queue entries in ClusteredTask, (2) implement Scheduler::queued_cpu_mask(), and (3) be placed in the clustered prefix of PRIORITY_LIST and matched by SchedulerType::is_clustered(); the prefix requirement is enforced at compile time.

GEDF Scheduler

The Global Earliest Deadline First (GEDF) scheduler is implemented in gedf.rs. This scheduler implements a real-time scheduling algorithm that prioritizes tasks based on their absolute deadlines.

The scheduler maintains a BinaryHeap<GEDFTask> as its run queue, where tasks are ordered by their absolute deadlines. When a task is enqueued via wake_task(), the scheduler calculates the absolute deadline by adding the relative deadline (specified in SchedulerType::GEDF(relative_deadline)) to the current uptime. The task's priority is updated using MAX_TASK_PRIORITY - absolute_deadline to ensure proper inter-scheduler priority comparison.

The GEDFTask struct implements custom ordering where tasks are compared first by absolute deadline (earlier deadlines have higher priority), and then by wake time for tie-breaking. The scheduler supports preemption through the invoke_preemption() method, which sends IPIs to target CPUs when a task with an earlier deadline arrives and can preempt currently running tasks.

PrioritizedFIFO Scheduler

The PrioritizedFIFO scheduler is implemented in prioritized_fifo.rs. This scheduler provides fixed-priority scheduling where tasks are executed in First-In-First-Out order within each priority level.

The scheduler uses a PriorityQueue<PrioritizedFIFOTask> as its run queue. When a task is enqueued through wake_task(), the priority is extracted from SchedulerType::PrioritizedFIFO(priority) and used to insert the task into the priority queue. The get_next() method retrieves the task at the head of the highest-priority non-empty queue.

The scheduler implements preemption via invoke_preemption(), which evaluates all currently running tasks and determines if the newly awakened task should preempt any of them. If preemption is triggered, the scheduler sends an IPI to the target CPU and updates the preemption pending queue.

PrioritizedRR Scheduler

The PrioritizedRR (Prioritized Round Robin) scheduler is implemented in prioritized_rr.rs. This scheduler combines fixed-priority scheduling with time quantum enforcement to provide fair CPU time distribution.

The scheduler maintains a PriorityQueue<PrioritizedRRTask> similar to PrioritizedFIFO, but adds time quantum management with a default interval of 4ms (4,000 microseconds). The scheduler provides two preemption mechanisms: invoke_preemption_wake() for priority-based preemption when tasks are awakened, and invoke_preemption_tick() for time quantum-based preemption.

The invoke_preemption_tick() method is called periodically on primary CPU to check if the currently running task has exceeded its time quantum. It compares the elapsed execution time against the configured interval and triggers preemption by sending an IPI if the quantum is exceeded.

Panicked Scheduler

The Panicked scheduler is implemented in panicked.rs. This scheduler handles tasks that have entered a panicked state and provides them with the lowest scheduling priority in the system. The scheduler uses a simple VecDeque<Arc<Task>> as its run queue, implementing basic FIFO ordering without any priority considerations.