QP/C++  7.4.0-rc.3
Real-Time Embedded Framework
Loading...
Searching...
No Matches
Preemptive Non-Blocking Kernel

Non-Preemptive KernelPreemptive Dual-Mode Kernel

Concepts & Definitions

The Active Object model of computation can work with a wide range of real-time kernels. Specifically for the kernel discussed in this section, the non-blocking and run-to-completion characteristics of the Active Object model open up a possibility of using a non-blocking, run-to-completion kernel. Such a kernel can be preemptive and fully compatible with the requirements of Rate Monotonic Scheduling/Analysis (RMS/RMA) method [RMS/RMA:91]. Still, a non-blocking kernel is much simpler and significantly more efficient than any traditional blocking RTOS kernel.

QK Preemptive Non-Blocking Kernel

QK is a preemptive, non-blocking, fixed-priority, run-to-completion, single-stack, event-driven kernel integrated with the QP Framework. QK executes all Active Objects in discrete, one-shot, non-blocking RTC steps that can preempt each other. This preemption is similar to how prioritized interrupts can preempt each other and nest on a single stack (e.g., see description of interrupt handling in ARM Cortex-M [Yiu:14]). Interrupts, just like RTC steps in Active Objects, are also one-shot, run-to-completion steps that are not allowed to block.

Remarks
The one-shot, run-to-completion, non-blocking, preemptible schedulable units of work are known in the literature as "jobs" (Stack Resource Policy [SRP:90]) or "basic tasks" (OSEK/AUTOSAR terminology [OSEK:03]). Similar concepts are also called "fibers" (e.g., Q-Kernel), "deferred interrupts" (e.g., SMX kernel), or "software interrupts" (e.g., TI-RTOS).

Preemptions in QK

As a fully preemptive, fixed-priority kernel, QK must ensure that at all times the CPU executes the highest-priority Active Object (AO) as soon as it becomes ready to run. Fortunately, only two scenarios can lead to preemption of a lower-priority AO1 by a higher-priority AO2.

Note
The QK kernel is one of the simplest and most efficient kernels fully compatible with RMS/RMA/DMS. Due to the simplicity, the QK kernel is a recommended choice for safety-critical applications.

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

Figure SRS-QK-SYN: Synchronous Preemption in QK. The stack is shown in the bottom panel grows "down" (as on ARM Cortex-M).

Figure SRS-QK-SYN illustrates a synchronous preemption scenario:

[1] QK idle loop (QK idle task) is preempted by an AO1, which executes its RTC step

[2] AO1 posts an event to a higher-priority AO2, which calls the "QK activator"

[3] "QK activator" activates (calls) the AO2 RTC step

[4] AO2 RTC step completes and returns to the "QK activator"

[5] "QK activator" returns back to AO1, which remained synchronously preempted

[6] AO1 completes its RTC step and returns to "QK activator" (previous instance)

[7] "QK activator" finds no more AOs to run and returns to the QK idle loop.

Remarks
A traditional RTOS kernel does not distinguish between the synchronous and asynchronous preemptions (see next) and makes all preemptions look like the more stack-intensive asynchronous preemptions. In contrast, a run-to-completion kernel like QK can implement synchronous preemption as a simple function call, which is more efficient than a full context-switch.

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

Figure SRS-QK-ASN: Asynchronous Preemption in QK. The stack is shown in the bottom panel grows "down" (as on ARM Cortex-M).

Figure SRS-QK-ASN illustrates an asynchronous preemption scenario:

[1] QK idle loop (QK idle task) is preempted by an AO1, which executes its RTC step

[2] An interrupt fires and asynchronously preempts the AO1 RTC step

[3] The ISR for the interrupt starts running and posts an event to high-priority AO2

[4] The ISR sends the EOI (End-of-Interrupt) command to the interrupt-controller, but does NOT return to the preempted context (so the interrupt stack frame remains on the stack). Instead, the ISR calls "QK activator".

Remarks
The details of this step depend on the CPU and interrupt controller and might be more complex. For example ARM Cortex-M CPU requires additional step of activating the PendSV exception.)

[5] "QK activator" activates (calls) the AO2 RTC step

[6] AO2 RTC step completes and returns to the "QK activator"

[7] "QK activator" performs interrupt-return back to AO1, which remained asynchronously preempted

[8] AO1 completes its RTC step and returns to "QK activator" (previous instance)

[9] "QK activator" finds no more AOs to run and returns to the QK idle loop.

Single-Stack Kernel

By requiring that all AOs run-to-completion and enforcing fixed-priority scheduling, a non-blocking kernel like QK can manage all context information using only a single stack and the CPU's natural stack protocol. Whenever an AO posts an event to a higher-priority AO, QK kernel uses a regular C function call to build the higher-priority AO context on top of the existing stack context (synchronous preemption). Whenever an interrupt preempts an AO and the interrupt posts an event to a higher-priority AO, the QK kernel uses the already established interrupt stack frame on top of which to build the higher-priority AO context, again using a regular C function call (asynchronous preemption).

This simple form of context management is adequate because every AO, just like every ISR, runs to completion. Because the preempting AO must also run to completion, the lower-priority context will never be needed until the preempting AO (and any higher-priority AO that might preempt it) has completed and returned — at which time the preempted AO will, naturally, be at the top of the stack, ready to be resumed.

Idle Processing in QK

The situation when QK kernel finishes processing all RTC steps in all Active Objects is called the idle condition. In that case, the QK kernel executes idle processing. Idle processing in QK can be viewed as the lowest-priority task (of priority 0), but unlike all other one-shot tasks, it has a structure of an endless loop (see "QK idle loop" in Figure SRS-QK-SYN and Figure SRS-QK-ASN).

This QK idle loop invokes a QK-idle-callback defined in the application, to let the application, among others, put the CPU and peripherals in a low-power sleep mode. Existence of such a single point to apply low-power modes is a hallmark of a power-friendly architecture.

Remarks
The QK-idle-callback is invoked with interrupts enabled because transition to a sleep mode in a preemptive QK kernel is safe form the hazards described for the non-preemptive QV kernel.

Selective Scheduler Locking

As all preemptive kernels, QK requires the QP Application to be very careful with any resource sharing among Active Objects. Ideally, the Active Objects should communicate exclusively via events and otherwise should not share any resources. However, at the cost of increased coupling among Active Objects, QP Application might choose to share selected resources. However, such QP Application takes the burden on itself to apply a mutual exclusion mechanism while accessing any shared resources.

QK kernel provides selective scheduler locking as a powerful mutual exclusion mechanism. Specifically, before accessing a shared resource, an Active Objects can lock the QK scheduler up to the specified priority ceiling. This prevents Active Object preemption up to the specified priority ceiling, while not affecting Active Objects (or interrupts) of priority higher than the priority ceiling. After accessing the shared resource the Active Object must unlock the QK scheduler. Selective scheduler locking in QK is related to IPCP/SRP (Immediate Priority Ceiling Protocol/Stack Resource Policy) and is immune to unbound priority inversion [SRP:90].

Selective scheduling locking is a non-blocking mechanism. If an Active Object that needs to protect a shared resource is running, it means that all Active Objects of higher priority have no events to process. Consequently, simply preventing activation of higher-priority AOs that might access the resource is sufficient to guarantee the mutually exclusive access to the resource. Of course, you don't need to worry about any lower-priority AOs that might be preempted because they never resume until the current AO runs to completion.

Selective scheduler lock requests made by the same Active Object can nest. The nested lock requests can only increase the priority ceiling. Also, the nested lock requests must unlock the scheduler by restoring the previous priority ceiling.

Preemption-Threshold Scheduling

While preemption is a desirable property that enables techniques like RMS/RMA by decoupling higher-priority Active Objects from lower-priority ones in the time domain, too much preemption has also negative effects. These include the overhead of preemption and restrictions on sharing resources. For example, sometimes a group of Active Objects forms a cohesive subsystem, where preemption of one group member by another might be unnecessary and undesirable.

To ease some of the inherent problems of preemption, QK provides and advanced feature called preemption threshold scheduling (PTS), [PTS:07]. PTS allows an Active Object to specify a preemption threshold to selectively restrict preemption by other Active Objects. Active Objects that have priorities higher than the preemption threshold are still allowed to preempt, while those less than the threshold are not allowed to preempt.

For example, all Active Objects in a group might specify the same preemption threshold (alongside their unique priorities). Such preemption threshold will prevent preemption within the group, while still allowing preemption by other Active Objects with higher priorities than the preemption threshold.

Task-Level Response

The maximum time an event for the highest-priority Active Object can be delayed is called the task-level response. The preemptive QK kernel always executes the highest-priority Active Object immediately as it becomes ready to run (see Preemptions in QK). Therefore, the task-level response in the QK kernel is determined only by the context switch time, which is independent on the lower-priority Active Objects. That is what is meant that a preemptive kernel decouples tasks in the time domain.

Remarks
Selective scheduler locking and preemption-threshold scheduling re-introduce some time-domain coupling among Active Objects and can also negatively impact the task level response of the QK kernel.

As a preemptive kernel with fixed-priority scheduling, QK fulfills all requirements of the Rate Monotonic Scheduling/Analysis (RMS/RMA) [RMS/RMA:91] and the related Deadline-Monotonic Scheduling (DMS) [RMS/RMA:91][DMS:91]. Additionally, the no-blocking nature of QK makes the applications easier to analyze and thus actually even more suitable for RMS/RMA than a traditional blocking RTOS.

Requirements

SRS_QP_QK_00

SRS_QP_QK_00 : QP Framework shall provide preemptive non-blocking QK kernel as one of the built-in kernels.

Description

QP Framework shall provide QK kernel implementation and ports to the supported CPU/compiler combinations as one of the optional software components. QP Application can then choose the QK kernel to execute Active Objects. Such a selection is exclusive, meaning that when QP Application selects the QK kernel, other kernels are excluded and cannot be used.

Description

QP Framework can implement the QK kernel component by re-using already existing mechanisms, such as event queues for Active Objects, event delivery mechanisms, event memory management, etc. That way, the QK kernel implementation can be quite small and consist only of the missing pieces, such as the QK scheduler and "activator".

Forward Traceability

SRS_QP_QK_10

SRS_QP_QK_10 : QK kernel shall provide an idle-callback defined in QP Application.

Description

When QK kernel finishes processing all RTC steps in all Active Objects it shall execute the QK idle loop. This QK idle loop shall invoke an idle-callback (a function) defined in QP Application. The idle-callback can perform any processing, including putting the CPU and peripherals in a low-power sleep mode.

Use Case

The idle-callback shall be invoked with interrupts enabled and can perform Software Tracing data transfer to the host, or other processing.

Forward Traceability

SRS_QP_QK_20

SRS_QP_QK_20 : QK kernel shall provide API to selectively lock scheduling Active Objects below the specified scheduler-lock ceiling priority.

Description

The selective scheduler locking API shall prevent scheduling any Active Objects whose unique priority is below the specified scheduler-lock ceiling priority.

Use Case

The main use case for selective scheduler locking is during multicasting events to prevent unexpected and confusing event sequences (see SRS_QP_EDM_55).

Forward Traceability

SRS_QP_QK_21

SRS_QP_QK_21 : QK kernel shall provide API to unlock scheduling Active Objects.

Description

The scheduler unlocking API shall complement the scheduler locking API (see SRS_QP_QK_20). The scheduler unlocking API shall restore the scheduler-lock ceiling established in the most recent call to the scheduler locking API.

Use Case

The main use case for selective scheduler locking (matching the use case in SRS_QP_QK_20) is enabling the QV scheduler in the system clock tick.

Forward Traceability

SRS_QP_QK_30

SRS_QP_QK_30 : QK kernel shall support preemption-threshold scheduling (PTS).

Description

Support for preemption-threshold scheduling (PTS) means that each Active Object can be assigned a preemption-threshold (alongside its unique QP priority). The Active Object with a given preemption-threshold cannot be preempted by Active Objects with the unique QP priorities below the preemption threshold.

Forward Traceability

SRS_QP_QK_31

SRS_QP_QK_31 : The preemption-threshold assigned to an Active Object must be consistent with its unique QP priority.

Description

The preemption-threshold assigned to an Active Object can be only higher than the unique QP priority. Additionally, the preemption-threshold cannot exceed preemption thresholds assigned to any higher-priority Active Objects.

Forward Traceability

Non-Preemptive KernelPreemptive Dual-Mode Kernel