Table of Contents

Overview

This guide shows how to replace the kernel's scheduling policy. The mechanism side (context switching, the thread registry, the timer entry, the synchronization primitives, the GC bridge) never changes; everything an algorithm decides goes through one interface, IScheduler. How the mechanism works, and how the default Stride policy uses this interface, is covered in the scheduler article; this page assumes it.

Replacing the policy takes three steps:

  1. Implement IScheduler, using the per-thread and per-CPU data slots for the algorithm's bookkeeping. The slots' setter is internal, so today a policy lives inside Cosmos.Kernel.Core, next to Stride/.
  2. Respect the kernel constraints: the hooks run in interrupt context or under disabled interrupts, on live scheduler state.
  3. Install it with SchedulerManager.SetScheduler(new MyScheduler()). The manager calls ShutdownCpu on the outgoing policy and InitializeCpu on the incoming one for every CPU. Install at boot, before threads exist (as LibraryInitializer does): nothing migrates queued threads or their attached bookkeeping into the new policy, so a mid-flight swap strands them.

The interface

Most hooks receive the PerCpuState they operate on, and run either under the manager's interrupt-masked lifecycle entries or in interrupt context itself; the exceptions are noted below. A policy that does not need a hook leaves it a no-op.

Member Called from Contract
Name logging A display name for boot logs
InitializeCpu(state) SetScheduler Allocate the per-CPU bookkeeping into state.SchedulerData
ShutdownCpu(state) SetScheduler Release it (the incoming policy gets a clean slot)
OnThreadCreate(state, thread) CreateThread Allocate the per-thread bookkeeping into thread.SchedulerData; do not queue the thread yet
OnThreadReady(state, thread) ReadyThread (wakes, first start, sleep expiry) Make the thread runnable: place it and insert it into the run structure
OnThreadBlocked(state, thread) BlockThread and MarkSleeping Remove the thread from the run structure; save whatever must survive the park
OnThreadYield(state, thread) ScheduleFromInterrupt (the preempted thread, if it stayed Ready) and YieldThread Re-insert a thread that gave up the CPU
OnThreadExit(state, thread) ExitThread Remove it everywhere and drop its bookkeeping
OnTick(state, current, elapsedNs) the timer interrupt Account the elapsed time; return true to request a reschedule. elapsedNs is the configured tick interval, not a measurement
PickNext(state) ScheduleFromInterrupt Return the next thread to run, or null to run the idle thread
OnPickFailed(state, thread) nothing yet Declared for a pick the mechanism cannot honor; put the thread back. No caller today
SelectCpu(thread, currentCpu, cpuCount) nothing yet Choose a starting CPU for a thread; honor ThreadFlags.Pinned
OnThreadMigrate(thread, fromState, toState) Balance implementations Move the thread's bookkeeping (and any virtual-time base) between CPUs
Balance(state, allCpuStates) nothing yet Rebalance load across CPUs; honor Pinned
SetPriority(state, thread, priority) / GetPriority(thread) nothing in-tree today (a DevKernel diagnostic reads GetPriority) Priority is policy-defined: Stride reads it as tickets, a real-time policy would read it as a priority level. Called under a spinlock, not with interrupts masked
GetRunQueueCount(state) / GetRunQueueThread(state, index) diagnostics Read-only introspection of the run structure

SelectCpu, Balance, OnPickFailed, and SetPriority have no mechanism-side caller today (the kernel runs on one CPU, and nothing sets priorities yet). Implement them for completeness, but do not rely on them being exercised. Note also that Name, SelectCpu, and GetPriority receive no PerCpuState, and that InitializeCpu/ShutdownCpu run from SetScheduler under a plain spinlock, in thread context with interrupts enabled.

Attaching state

Thread and PerCpuState both inherit SchedulerExtensible, which carries exactly one object? slot, SchedulerData, reserved for the active policy. Its setter is internal to Cosmos.Kernel.Core, which is why a policy currently has to live in that assembly. Allocate in the creation hooks, read with the typed accessor, and tolerate null (a thread can exit between a tick and the hook that observes it):

public sealed class MyThreadData { public ulong Deadline; }
public sealed class MyCpuData { public List<Thread> Queue { get; } = new(); }

public void OnThreadCreate(PerCpuState state, Thread thread)
    => thread.SchedulerData = new MyThreadData();

public bool OnTick(PerCpuState state, Thread current, ulong elapsedNs)
{
    MyThreadData? data = current.GetSchedulerData<MyThreadData>();
    if (data == null) { return true; }   // thread already exited; just reschedule
    ...
}

One slot per object is the whole budget. A policy that needs several values defines one class holding them, as StrideThreadData and StrideCpuData do.

Kernel constraints

The hooks run inside the kernel's most sensitive window, so four rules are not optional:

  • You are in interrupt context. OnTick and PickNext run inside the timer interrupt; the lifecycle hooks run under DisableInterruptsScope from whatever thread called the manager. Nothing may block, park, or wait in a hook.
  • Do not allocate on the tick path. Allocation is technically interrupt-safe in this kernel, but an allocation in OnTick or PickNext can trigger a collection inside the tick. Allocate in OnThreadCreate and InitializeCpu, where creation already pays for it, and pre-size collections there.
  • No List<T>.Remove, Contains, or IndexOf on scheduler paths. They route through EqualityComparer<T>.Default, which needs runtime helpers the kernel does not provide. Scan with ReferenceEquals and use RemoveAt, as StrideScheduler.RemoveThreadFromQueue does.
  • Guard structure mutations against the tick. A hook mutating the run structure can itself be interrupted by the timer unless interrupts are masked. The lifecycle hooks and the tick hooks get that masking from the manager, but InitializeCpu/ShutdownCpu and SetPriority do not (spinlocks only), and any additional entry point a policy exposes (a diagnostics read, a tuning setter) must take InternalCpu.DisableInterruptsScope() itself.

Bookkeeping the mechanism already does, so a policy does not have to: Thread.State transitions, the thread registry, _needReschedule on wakes, TLAB return on exit, and the idle-thread fallback when PickNext returns null.

Worked sketches

The same questions recur for every algorithm: what to store per thread and per CPU, what shape the run structure takes, what triggers preemption in OnTick, and what must survive a park. The sketches below answer them for the classic algorithms.

Round-Robin

A FIFO queue with fixed-quantum preemption.

Hook Behavior
PerCpuState.SchedulerData A queue of threads
Thread.SchedulerData A remaining-quantum counter
OnThreadReady Enqueue at the tail
OnThreadBlocked Remove from the queue (a running thread is not in it; removal covers a queued thread going to sleep)
OnTick Charge elapsedNs against the quantum; return true at zero
OnThreadYield Re-enqueue at the tail, reset the quantum
PickNext Dequeue the head

FIFO order already bounds latency at quantum * queue depth, so Round-Robin needs no wakeup placement logic at all.

Multi-Level Feedback Queue (MLFQ)

Several priority levels; threads demote when they burn a full quantum and promote when they block early.

Hook Behavior
PerCpuState.SchedulerData An array of queues, one per level
Thread.SchedulerData Current level and quantum-used counter
OnThreadReady Enqueue at the thread's current level
OnThreadBlocked Promote one level (it blocked before its quantum ran out: treat as interactive)
OnTick Charge time; a full quantum at this level demotes on the next yield
PickNext Scan levels top-down, dequeue the first non-empty head
periodic (e.g. every N ticks in OnTick) Reset all threads to the top level, the classic anti-starvation boost

MLFQ tracks no virtual time; its whole bookkeeping is integer levels.

Fixed-priority preemptive (FPP)

The default policy of most RTOSes (FreeRTOS, Zephyr, ThreadX): the highest-priority runnable thread always runs, FIFO within a level.

Hook Behavior
PerCpuState.SchedulerData An array of queues indexed by priority
Thread.SchedulerData A static priority
OnThreadReady Enqueue at the thread's level; the _needReschedule the manager sets makes a higher-priority wake preempt on the next interrupt exit
OnTick Return true if any level above the current thread's is non-empty (pure priority, no quantum)
PickNext Top-down scan, dequeue the first head
SetPriority Move the thread between levels

Rate Monotonic is FPP with one extra rule in OnThreadCreate: assign priority from 1 / period (shorter period, higher priority), and reject the thread if total utilization crosses the schedulability bound.

Earliest-Deadline-First (EDF)

Dynamic priority by absolute deadline; optimal on one CPU (100% utilization against Rate Monotonic's ~69%), harder to reason about under overload.

Hook Behavior
PerCpuState.SchedulerData A min-heap keyed on absolute deadline
Thread.SchedulerData Period, relative deadline, absolute deadline
OnThreadReady absolute = now + relative, insert into the heap
OnTick Return true if the heap root's deadline is earlier than the current thread's
PickNext Pop the root

FIFO (cooperative)

A debugging policy: one queue, OnTick always returns false, threads run until they block or exit. Useful when chasing a race that disappears under preemption. Note the limits of "cooperative" here: with no working voluntary switch, a compute-bound thread that never blocks never leaves the CPU.

Real-time notes

The policy/mechanism split makes the framework a plausible base for a real-time kernel: the context switch is deterministic (no allocation on the switch path), Pinned gives per-thread affinity, Sleep provides the wakeup deadline a periodic task needs, and SetPriority is the handle a priority protocol would use. What a hard-RT build still has to add sits on both sides of the interface:

  1. Bounded hook cost. Everything in OnTick and PickNext is worst-case interrupt latency. Stride's linear sorted insert would not qualify; per-priority FIFOs or a heap keep the hooks O(log n) or better.
  2. Priority inheritance. The kernel Mutex wakes FIFO and hands ownership directly to the head waiter, with no priority boost for the holder. Fair, but it inverts priorities. The inheritance protocol (boost the holder to the highest waiter's priority via SetPriority, restore on release) has its hook available and no implementation.
  3. A deadline-driven tick. The scheduler tick is a fixed 10 ms interval. On ARM64 its driver (the Generic Timer) already re-arms a one-shot every interrupt; on x64 the tick is the hardware-periodic LAPIC timer, which would need switching to one-shot re-arm. On top of either sits the missing piece: the policy feedback that programs the next interrupt to the next deadline instead of a fixed period, a scheduler-to-timer channel that does not exist yet.
  4. Admission control. Nothing stops oversubscription; a Rate Monotonic or EDF policy has to enforce its own utilization bound in OnThreadCreate.

Checklist

  1. Define the per-thread and per-CPU records; allocate them in OnThreadCreate and InitializeCpu, read them with GetSchedulerData<T>(), tolerate null.
  2. Pick the run structure (queue, sorted list, heap, multi-level). The mechanism only ever asks PickNext.
  3. Put the preemption decision, and nothing slow, in OnTick's return value.
  4. Decide what survives a park: whatever OnThreadBlocked saves is what wakeup placement in OnThreadReady has to work with.
  5. Use ReferenceEquals scans, pre-sized collections, and DisableInterruptsScope on any entry the manager does not already guard.
  6. Implement SelectCpu, OnThreadMigrate, and Balance honoring Pinned, and treat them as dormant until SMP lands.
Edit this page