QP/C++
7.3.4
Real-Time Embedded Framework
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 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.
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.
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 11_01 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.
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 11_02 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".
[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.
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.
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 11_01 and Figure 11_02).
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.
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.
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.
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.
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.
| SRS-QP-11_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". |
| SRS-QP-11_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. |
| SRS-QP-11_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-04_55). |
| SRS-QP-11_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-11_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-11_20) is enabling the QV scheduler in the system clock tick. |
| SRS-QP-11_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. |
| SRS-QP-11_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. |