Real-time scheduling

Definition

A real-time operating system is a system that

• schedules execution of tasks in a timely deterministic manner, and
• is scalable.

The scheduler follows a set of algorithms that determine which task executes at each moment. Preemptive priority-based scheduling is a mandatory property of the operating system we evaluate for use in our application.

A task or ‘thread’ in this context is a sequential execution stream in a multi-tasking OS (cfr. Simple Platform Abstraction).

Key characteristics for a real-time system are

• reliability (stability),
• predictability (it must be deterministic),
• performance (the faster the better),
• compactness to code size (space is money) and
• scalability (one starts with 2 tasks and eventually one ends up with a seven-headed dragon).

The RTOS we are looking at follow the ‘scheduler paradigm’ (cfr. Operating systems for embedded systems). There are two main levels or categories of execution that can code-execute logic:

• The interrupt level and
• The task level.

About interrupts and tasks

An interrupt is an asynchronous exception of which the source is an internal or external hardware device (note: if the OS supports system calls then software interrupts are possible as well). Implementation dependent Programmable Interrupt Controllers (PICs) prioritize multiple interrupt sources so that at any time the highest priority interrupt is presented to the core CPU for processing. Nesting interrupts refers to the ability of a higher priority interrupt source to preempt the processing of a lower priority interrupt. That means the higher priority interrupt will interrupt the lower priority interrupt, the higher priority interrupt will run to completion (unless interrupted by a higher priority interrupt), and then the lower priority interrupt will resume. The above explanation refers to so-called maskable interrupts: lower priority interrupts are masked (prevented from running) by higher priority interrupts. Non-maskable interrupts are also possible; these have the highest priority (sometimes even higher than the RTOS itself) and cannot be prevented from happening. Click on the figure to enlarge it.

When interrupts are not running, the core has time for running scheduled tasks (Threads at task level). Of course, these tasks can (and should) also be prioritized.

The figure shows an example of  what a cpu or micro-controller is doing in a running system (find the timer tick!).

The performance of an embedded (real-time) system is proportional to:

• the latencies involved with the interrupt and
• the task handling scheme.

Interrupt latency is the time from when the interrupt request is triggered until the ISR ( = the code of the interrupt service routine)  is running. Context information handling (of a task or interrupt) is additional overhead and increases the latency but should also be deterministic and known. Task switching latency is the time when a task should be made to ‘run’, involving the time it takes to store the context information of the running task and restoring the context information of the to-be-run task.

Interrupt priorities are assigned within the PIC; the system designer usually has full or at least some control on them (this is PIC platform specific). But how to determine the priorities of the various tasks? Generally, the more important the task, the higher the priority it should get assigned. This is true for interrupts and tasks, but more criteria are important and should be considered.

Scheduling schemes

Rate Monotonic Scheduling (RMS) is a scheme where priorities are assigned based on the execution rate (how many times per second it should run). Tasks (both ISRs and Threads, thus all schedulable entities in this context) must be periodical and must be independent (e.g. no shared resources). The higher the required execution rate (frequency), the higher the priority.

Earliest Deadline First (EDF) schedules tasks according to frequency (e.g. number of times per seconds the task should run), deadline (to task completion) and task execution duration. A good maximum task execution duration estimation is very important.

Caveats for real-time system implementations

• Deadlocks: true for general software as well.
• Priority inversion: the higher priority task may be blocked waiting for a lower priority task to execute, and tasks with priorities in between have a higher priority in running, thus both lower priority as higher priority task do not run. This can be solved by either giving the lower priority task a priority boost (it usually gets the priority of the blocked high priority task or higher), or by designing the system so that no priority inversion can occur by using e.g. lock-less queues, etc…

Usage advice with reference to the simple platform abstraction

• Only strict and minimal essential tasks are done in interrupt: a small interrupt service routine (ISR) responds to the generated interrupt.
• The ISR possibly queues essential data for later processing and signals the related task (no longer running in interrupt context): sometimes this is called the Interrupt Service Task, Thread (IST) or Bottom Half (e.g. Linux).
• The IST awakes – whenever the scheduler determines it should run given the assigned priorities – as a response to the signal, and starts or resumes processing.
• The IST runs to completion (unless interrupted by a higher priority task or any interrupt), and will again block on a signal or on timeout expiration.
• An IST has a timeout, and it will be ready to run when this timeouts expires anyway.
• An IST is usually signaled from an ISR, but it can also be signaled by another IST.

References

Real-time concepts for Embedded Systems – Qing Li, Caroline Yao.

Embedded Systems Architecture – Tammy Noergaard.