Cooperative Run-to-Completion KernelPreemptive Dual-Mode Kernel

Theory of Operation

The preemptive, non-blocking QK kernel is specifically designed to execute non-blocking active objects (see also [PSiCC2, Chapter 10]). QK runs active objects in the same way as prioritized interrupt controller (such as NVIC in ARM Cortex-M) runs interrupts using single stack. Active objects process their events in run-to-completion (RTC) fashion and remove themselves from the call stack, the same way as nested interrupts remove themselves from the stack upon completion. At the same time high-priority active objects can preempt lower-priority active objects, just like interrupts can preempt each other under a prioritized interrupt controller. QK meets all the requirement of the Rate Monotonic Scheduling (a.k.a. Rate Monotonic Analysis RMA) and can be used in hard real-time systems.

Note: The non-blocking, run-to-completion, preemptive threads are known in the literature as "basic threads" (OSEK/AUTOSAR terminology), sometimes also called "fibers" (e.g., Q-Kernel) or "software interrupts" (e.g., TI-RTOS).

The preemptive, run-to-completion (RTC) QK kernel breaks entirely with the endless-loop structure of the thread routines and instead uses threads structured as one-shot, discrete, run-to-completion functions, very much like ISRs [PSiCC2, Chapter 10]. In fact, the QK kernel views interrupts very much like threads of a “super-high” priority, except that interrupts are prioritized in hardware by the interrupt controller, whereas threads are prioritized in software by the RTC kernel.

As a fully preemptive multithreading kernel, QK must ensure that at all times the CPU executes the highest-priority thread (active object) that is ready to run. Fortunately, only two scenarios can lead to readying a higher-priority thread:

[1] When a lower-priority thread posts an event to a higher-priority thread, the kernel must immediately suspend the execution of the lower-priority thread and start the higher-priority thread. This type of preemption is called synchronous preemption because it happens synchronously with posting an event to the thread's event queue.

Note: The stack usage shown in the bottom panel displays stack growing down (towards lower addresses), as it is the case in ARM Cortex-M.

Figure 08_01: Synchronous Preemption in QK

[2] When an interrupt posts an event to a higher-priority thread than the interrupted thread, upon completion of the ISR the kernel must start execution of the higher-priority thread instead of resuming the lower-priority thread. This type of preemption is called asynchronous preemption because it can happen asynchronously, any time interrupts are not explicitly disabled.

Note: The stack usage during asynchronous preemption on ARM Cortex-M is slightly simplified in the diagram below. A more detailed stack usage diagram is discussed later in the section explaining the Detailed stack allocation in QK for ARM Cortex-M.

Figure 08_02: Asynchronous Preemption in QK

Note: A traditional RTOS kernel does not distinguish between the synchronous and asynchronous preemptions and makes all preemptions look like the more stack-intensive asynchronous preemptions. In contrast, a RTC kernel can implement synchronous preemption as a simple function call (to QK_activate_()), which is much more efficient than a full context-switch.

QK Features

Scheduler Locking

Requirements

REQ-QP-08_00

REQ-QP-08_00
QP Application must not use any signals reserved by QP Framework
Description Application-level signals must start at the limit provided by QP Framework and can never go below that limit.

REQ-QP-08_10

REQ-QP-08_10
Application-level Signals shall map unambiguously to the Event subclasses defined in the QP Application
Description The QP Application must be able to unambiguously identify the Event subclass based just on the Signal of the received event.

Cooperative Run-to-Completion KernelPreemptive Dual-Mode Kernel