EC-20.2 Inside a Real-Time Operating System: Tasks, Priority and Scheduling

What this is and why it exists

A real-time operating system is a much smaller thing than the name suggests.

It is a program whose job is to decide which piece of your code runs next. It switches between pieces fast enough that each appears continuous. There is no file system, no user, and often no memory protection. On a small part the whole kernel is a few thousand lines.

Understanding it well means understanding one data structure and one decision. The structure is the record kept for each task. The decision is made at every timer tick and at the end of every interrupt: is a higher-priority task now ready to run?

The vocabulary

• Task — an independent piece of work with its own stack and its own flow of control.
• Context switch — saving one task's registers and restoring another's.
• Task control block — the record holding a task's state, priority and stack pointer.
• Ready, running, blocked — the three states a task spends its life in.
• Preemption — stopping a running task because a higher-priority one became ready.
• Tick — the periodic timer interrupt that drives the kernel's sense of time.
• Utilisation — the fraction of processor time a set of tasks needs.
• Rate-monotonic — assigning priority by period, shortest period highest.
• Schedulable — a set of tasks that provably always meets its deadlines.

The mental model

Start with the task. Each one has a stack of its own, and a small record saying where it stopped and how important it is. Switching between two tasks means pushing one set of registers onto one stack and popping another set from another stack. That is the whole trick, and once it is clear the kernel stops being mysterious.

Each task is in one of three states. Running means it has the processor, and only one task can be running. Ready means it could run but something more important is running instead. Blocked means it is waiting for something and cannot run even if the processor is free.

The scheduler asks its question at two moments: on the tick, and when an interrupt handler finishes. At those moments it looks for the highest-priority ready task and runs it. Knowing exactly when the question is asked explains almost every surprising ordering a beginner sees.

Priorities are not a matter of taste. For independent periodic tasks there is a proven answer: give the shortest period the highest priority. This is called rate-monotonic assignment, and no other fixed assignment does better. There is also a utilisation figure below which such a set is guaranteed to fit, which settles many arguments outright.

The alternative is to schedule by whichever deadline is nearest. This uses the processor better and can reach full utilisation. It also degrades badly when the system is overloaded, because the tasks nearest to failing get priority and everything misses together. That is why most shipped systems still use fixed priorities.

Two practical cautions. Every task costs a stack, so more tasks is not automatically better. And the kernel itself costs time. Context switch, tick handling and interrupt latency are all measurable on your part with a spare pin. They differ by an order of magnitude between parts. An analysis that ignores them is arithmetic rather than engineering.

What you should now be able to explain or do

• Describe what happens, register by register, during a context switch.
• Name the three task states and say what moves a task between them.
• Say exactly when the scheduler makes its decision.
• Apply rate-monotonic assignment to a set of periodic tasks and check the utilisation bound.
• Explain why earliest-deadline scheduling is better on paper and rarer in practice.
• Measure the context switch time and interrupt latency of a real part.

Check yourself