Real-time scheduling

A real-time system is correct only if its work finishes on time. The work is usually described as tasks that each release a job every period, with a worst-case execution time and a deadline, often the end of the period. In hard real time a missed deadline is a failure, as in a motor controller; in soft real time a miss degrades the result, as in audio that crackles. The question a real-time scheduler answers in advance is schedulability: given the tasks, will every deadline be met?

Two classic policies answer it on one CPU. Rate Monotonic gives each task a fixed priority from its period, the shorter the period the higher the priority, and is the best fixed-priority assignment for such tasks. A set of n tasks is guaranteed schedulable when its total utilization, the sum of each task's execution time over its period, stays under n(2^(1/n) - 1), a bound that falls toward about 69% as n grows. Earliest Deadline First (EDF) always runs the ready job whose deadline is nearest, a priority that changes with every release, and meets every deadline up to 100% utilization. They also fail differently: under overload, Rate Monotonic misses the deadlines of its lowest-priority tasks first, while an overloaded EDF can miss deadlines in a cascade across all of them. Admission control keeps a system under its bound by refusing a task that would push the utilization over it, when the task is created, instead of letting it cause misses later.

The trap is everything the analysis assumes to be bounded. The guarantees hold only if every cost is known: the scheduler's own decision time, the interrupt latency, the time a lower-priority thread holds a lock a task needs, and the granularity of the timer that releases jobs. A pick that is linear in the number of threads, a lock without priority inheritance, or a tick coarser than the shortest deadline breaks the guarantee while every task stays within its own budget.

In Cosmos nothing is real-time by default: the Stride policy divides time by share, not by deadline. A policy can implement Rate Monotonic or EDF over IScheduler, and has to bring its own admission control through an entry point of its own, since no hook can refuse a thread and nothing in the kernel limits utilization. The kernel side lacks pieces too. The tick runs at a fixed period, 10 ms from boot, so a deadline is met at best to the nearest tick, and no channel lets a policy program the next timer interrupt for its nearest deadline. OnTick and PickNext add to the interrupt latency, so their cost has to be bounded, and the Mutex has no priority inheritance. See Real-time notes.