Struct FairClassRq 

pub struct FairClassRq {
    entities: BTreeMap<(u64, u64), (Arc<Task>, u64)>,
    by_id: BTreeMap<u64, (u64, u64)>,
    min_vruntime: u64,
    total_weight: u64,
    runnable_count: usize,
}

Per-CPU run queue for the Completely Fair Scheduler.

Uses two BTreeMaps for O(log n) operations without allocation on the fast paths (pick_next, remove):

• entities: primary map keyed by (vruntime, task_id) : the minimum entry is always the next task to schedule.
• by_id: reverse index mapping task_id → primary key : enables O(log n) removal by task ID in remove() without scanning entities.

This replaces the previous BinaryHeap-based design which used lazy deletion (O(n) remove() scan, phantom entries, generation counters). The BTreeMap approach gives:

Operation	Complexity	Allocates?
enqueue	O(log n)	yes : 2 BTreeMap nodes (wakeup path)
pick_next	O(log n)	no : removes 2 nodes
remove	O(log n)	no : removes 2 nodes

No phantom entries means no generation counter, no prune_stale_head(), and no per-entry liveness checks. The BTreeMap pair is the authoritative record of which tasks are currently on the run queue.

Fields

entities: BTreeMap<(u64, u64), (Arc<Task>, u64)>

Primary index: (vruntime, task_id) → (Arc<Task>, weight). Ordered so pop_first() yields the task with the smallest vruntime. task_id is part of the key to ensure uniqueness when two tasks share the same vruntime.

by_id: BTreeMap<u64, (u64, u64)>

Reverse index: task_id → primary key. Allows remove(task_id) to locate and delete the entities entry in O(log n) without scanning the primary map.

min_vruntime: u64

total_weight: u64

runnable_count: usize

Implementations

impl FairClassRq

pub fn new() -> Self

Creates a new instance.

fn period(&self) -> u64

Total scheduling period in ticks.

BASE_SLICE_TICKS * (nr_runnable + 1) : each runnable task gets at least one full BASE_SLICE_TICKS per round. +1 accounts for the currently-running task that is not counted in runnable_count.

fn vtime_slice(&self) -> u64

Virtual-time slice: the vruntime budget for the current task.

fn time_slice(&self, cur_weight: u64) -> u64

Wall-clock time slice scaled by cur_weight relative to total weight.

Trait Implementations

impl SchedClassRq for FairClassRq

fn enqueue(&mut self, task: Arc<Task>)

Enqueues a task onto the run queue.

Clamps vruntime to min_vruntime so waking tasks do not receive an unfair head start over tasks that have been waiting. O(log n); allocates two BTreeMap nodes.

fn len(&self) -> usize

Returns the number of tasks currently on the run queue.

fn pick_next(&mut self) -> Option<Arc<Task>>

Picks the next task to run: the one with the smallest vruntime.

O(log n), allocation-free.

fn update_current( &mut self, rt: &CurrentRuntime, task: &Task, is_yield: bool, ) -> bool

Updates the vruntime of the currently-running task and decides whether it should be preempted.

Returns true if the task has exhausted its time slice or its vruntime has overtaken the leftmost task’s vruntime by more than vtime_slice.

fn remove(&mut self, task_id: TaskId) -> bool

Removes the task identified by task_id from the run queue.

Uses the by_id reverse index for O(log n) lookup, then removes both entries. Allocation-free. Returns true if the task was present.

fn is_empty(&self) -> bool

Returns whether empty.