danos/docs/os-development/scheduling.md

Scheduling

The scheduler turns danos from a linear "boot then halt" kernel into a running multitasking system. It's fixed-priority preemptive: the highest-priority ready task always runs, and tasks at the same priority take turns. That model is chosen for real-time — it's predictable (you can reason about which task runs when) and its decisions are O(1), unlike a fair-share scheduler.

The scheduler proper (system/kernel/scheduler.zig) is generic; the context switch and new-task stack setup are architecture-specific (system/kernel/architecture/x86_64/, see architecture).

Tasks

A task is a kernel thread: ring-0 code with its own 16 KiB stack (allocated from the heap). A task struct holds its saved stack pointer, priority, state, and a ready-queue link. The currently-running kernel context (kmain) registers itself as task 0, so there's always something to switch from.

The context switch

Switching tasks means swapping stacks. switch_context(old, new) (in isr.s) saves the callee-saved registers on the current stack, stores the stack pointer into the old task, loads the new task's stack pointer, restores its callee-saved registers, and rets — landing wherever the new task was last suspended. Only callee-saved registers are handled explicitly: to the compiler this looks like a normal function call, so it already preserves the caller-saved ones itself (this is the SysV convention doing the work).

A freshly spawned task has never run, so there's nothing to restore. Its stack is faked to look as if it had just called switch_context: init_task_stack lays down a return address pointing at task_trampoline and zeroed callee-saved slots (smuggling the entry function in via the r15 slot). When first switched to, the ret lands in the trampoline, which enables interrupts and calls the entry.

Two ways to switch, one flag discipline

schedule() — pick the best task and switch — runs from two places:

• yield() — a task voluntarily gives up the CPU.
• tick() — the 1000 Hz timer preempts the running task. This is what lets a task that never yields still share the CPU.

The subtlety in mixing them is the interrupt flag (IF). The rule: switch_context is always entered with interrupts disabled — naturally so inside the timer ISR, and explicitly (cli) in yield. Then every task ends up with interrupts enabled again through whichever path resumes it:

• a task suspended in yield re-enables them (sti) right after schedule returns;
• a task suspended mid-ISR resumes through the interrupt return (iretq), which restores the RFLAGS it had when it was preempted (IF set);
• a brand-new task enables them in the trampoline.

One related detail: the timer interrupt is acknowledged (EOI) before its handler runs, so a handler that switches tasks and doesn't return promptly can't stall the LAPIC from delivering the next tick.

Priority selection, in O(1)

Ready tasks live in a FIFO queue per priority level (8 levels), plus a bitmap with one bit per non-empty level. Picking the next task is: find the highest set bit (one instruction), take the front of that level's queue. No list walking, no scanning — the decision cost is constant regardless of how many tasks exist, which is what a real-time scheduler needs.

• Highest priority wins. A ready high-priority task always runs before a lower-priority one.
• Round-robin within a level. When a task is descheduled it goes to the back of its level's queue, so equal-priority tasks share the CPU fairly.

Affinity: pinning a task to a core

By default a task runs on any core — the ready queue above is global, and any idle core pulls the highest-priority task from it (work-conserving; see smp.md). A task can instead be pinned to one core with spawnOn(entry, priority, cpu), giving it an affinity: it will only ever run there, never migrating.

Mechanically, each core has its own pinned queue (same 8-level FIFO + bitmap) alongside the global one. A pinned task is enqueued only into its core's pinned queue; selection compares the top of the global queue and the running core's pinned queue and takes the higher priority (still O(1) — two bit-scans and a compare), with a pinned task winning an equal-priority tie so it can't be starved by global work. Because every queue is mutated under the big kernel lock, one core enqueuing into another core's pinned queue is safe.

This is the explicit-affinity model (no surprise migration mid-deadline), which is the more real-time-predictable direction. spawnOn refuses to pin to an offline or out-of-range core — it creates the task unpinned instead, so it still runs somewhere rather than stranding in a queue no core services, and returns whether the pin took.

Sleeping and the idle task

A task can block — give up the CPU until an event, rather than busy-wait (busy-waiting is the enemy of a real-time system: it wastes cycles a higher-priority task should get). The first form is time-based: sleep(ms) marks the task blocked with a wake deadline and switches away. On every tick the timer wakes any task whose deadline has passed (a bounded scan, so it stays deterministic), which makes it ready again; the scheduler then runs it when its priority comes up. sleep measures its deadline on the calibrated clock, so it's real time.

When every task is blocked, something still has to run — so there's an idle task at the lowest priority that just hlts until the next interrupt (see halting.md). Because it's always runnable, the scheduler always has a task to pick, and the "nothing to run" case never arises.

Event-based blocking

The other form of blocking is waiting for an event rather than a duration. A wait queue is a set of tasks parked until something happens: wait(wq) blocks the caller on it, wake(wq) moves the highest-priority waiter back to ready (preempting if it now outranks the running task). A task links into a wait queue through the same field the ready queues use — it's in exactly one queue at a time. These are the primitives locks, semaphores and IPC are built on.

Blocking safely needs composable critical sections. A blanket cli/sti pair doesn't nest: an IPC channel that clis and then calls wait would have wait's sti re-enable interrupts too early, mid-operation. So the blocking primitives use saveInterrupts / restoreInterrupts — capture the interrupt flag, disable, and later restore only if it was set — which nests correctly. The invariant that makes it all work: schedule() is always entered with interrupts disabled, so a task always resumes from a switch with interrupts disabled and can restore its caller's state.

Verifying it

Three tests (see testing.md) prove the guarantees:

• sched spawns three tasks that busy-loop without ever yielding. They all make progress — which can only happen if the timer is preempting between them and the context switch is correct (nothing yields voluntarily).
• priority (with preemption off, for determinism) spawns tasks at three priorities; they run and exit highest-priority first — [6, 4, 2].
• sleep blocks a task for 50 ms and checks the elapsed time on the clock — a real block (the idle task runs meanwhile), not a busy-wait.
• event blocks a task on a wait queue; waking it (from another task) resumes it, and since it's higher priority it preempts immediately.

What's next (partly done since)

• Priority inheritance — still open. Tasks now do block on shared resources (IPC rendezvous, the big kernel lock), and nothing yet bounds priority inversion — a real-time requirement.
• Task exit / a reaper — done. A dying task goes on its core's reap list in a .reaping state; the timer tick drains the list, frees the stack back to the heap, and recycles the task-table slot.
• Per-address-space tasks — done. User processes each own an address space, and the context switch reloads CR3 when the target's tables differ (see paging.md).