Kernel-v2 Description

Overview

As described in Kernel Description (kernel-v1), the kernel-v1 is strictly time-driven. That is, any event and scheduling condition will only be detected by a scanner that runs at a fixed interval. The looping scanner/scheduler is the only instance that manages the run-queue. The kernel-v2 is planned to provide a hybrid of time and event driven scheduling. This document describes the changes and the current status.

Note: at least for now, kernel-v2 is not planned to be a replacement for kernel-v1. The latter has its advantages, not least by being very simple, both conceptually and regarding implementation complexity.

Changes from Kernel-v1

Kernel-v1 Recap

The kernel-v1 uses a single looping coroutine that

periodically checks the SysTick counter flag to initiate the evaluation of the threads’ trigger conditions,
detects the trigger conditions to schedule and run the threads
- time period
- time delay
- change of hardware flags
puts the ready threads in a single run-queue,
runs all threads on the run-queue, before a new evaluation of the trigger condition is done.

Since the scheduler coroutine manages the run-queue, interrupts are not permitted to enable/trigger a thread.

Kernel-v2

The kernel-v2 splits the scheduler into two parts:

a SysTick interrupt handler for the evaluation of the threads’ ready conditions, putting the ready threads into the run-queue (procedure looph), and
an executive coroutine that runs the threads on the run-queue (procedure loopc), just as with kernel-v1.

The executive coroutine will always pick the thread at the head of the run-queue to run next, which is the ready thread with the highest priority. The scheduling is still cooperative, ie. a thread will run until it yields back control to the executive. But the SysTick handler may have put another thread into the run-queue “in the background” in the meantime. Other interrupt handlers may also have put a thread into the run-queue.

When a thread yields control using Kernel.Next, it will be put directly into the run-queue again in case it has no trigger conditions. Hence, it may even be that highest prio thread to be run again immediately.

Kernel API

The kernel-v2 API is unchanged compared to kernel-v1.

Status

The kernel-v2 is a first prototype. It’s a derivative of kernel-v1 with as few as possible changes.

Kernel Data Consistency

Overview

Obviously, mutating the run-queue needs to be exclusive at any time. The run-queue is altered when

a thread is put into the queue, according to its priority (Kernel.slotIn),
the thread at the head of the queue, ie. the one with the highest priority, gets removed from the queue to be run (Kernel.slotOut).

Ready Queue Management: Kernel Traps

Both operations above are done via exceptions, which are triggered from the kernel software. The SVC system exception would be the obvious candidate, but Astrobe uses it for run-time error trapping. While this could be resolved, it’s useful to have run-time error detection also in interrupt handlers, at least at this stage of development, and SVC exceptions cannot be used within the SVC exception handler. However, of the 32 interrupts of the RP2040 and its NVIC, only 26 are actually wired ({0..25}), so six ({26..31}) can be used for this purpose.

Using the following exception priority scheme:

prio 0: SVC (highest prio) for run-time errors
prio 1: mutate run-queue (“kernel traps”)
prio 2: SysTick (and other interrupt handlers mutating kernel data)

the NVIC will take care of granting mutual access to the relevant kernel data, without the need of disabling/enabling interrupts or lock-out mechanisms.

Non-kernel interrupts must be prio 2 or 3 for this to work (the RP2040 had four interrupt prio levels).

Adding a thread to the ready queue:

Kernel.slotIn: triggers Kernel.slotInHandler
uses interrupt number 31
used by Kernel.looph (ie. the SysTick handler), Kernel.Enable, and Kernel.Next

Removing the thread at the head of the ready queue:

Kernel.slotOut: triggers Kernel.slotOutHandler
uses interrupt number 30
used by Kernel.loopc, ie. the executive coroutine

Other Kernel Data

The SysTick handler looph uses and mutates thread data for the purpose of evaluating its trigger conditions, such as the period and delay timers. Since the currently running thread can, say, initiate a delay at any time, hence mutating its own data, the current thread is skipped by the SysTick handler.

This ensures that there’s no conflict (race condition) between the current thread and the SysTick handler, giving the current thread full autonomy over its own data.

However, the kernel API provides procedures such as Kernel.SetPeriod, which are currently not safe to use after the kernel has been started using Kernel.Run, since one thread would be mutating another thread’s data. Kernel.ChangePeriod is save, though, as are all in-process API procedures. In order to keep keep both APIs as compatible as possible, the kernel-v1 API might be adjusted, which is straight-forward, but would require changes to application code, such as the example programs.

Kernel Modules

Kernel-v2: apart from the new module Kernel in the new kernel-v2 directory, module SysTick is adapted for the scheduler interrupt handler.

Kernel-v1: the other modules of kernel-v1 are unchanged and can be used with the current version of kernel-v2. With the further evolution of the kernel-v2, these modules will probably get adapted, resulting in new variants in the kernel-v2 directory.

Astrobe Search Path Set-up

Using the kernel-v2 requires the Astrobe search path to be adjusted.

Example Programs

The example programs work with the current version of kernel-v2.