RK0: The Real-Time Kernel '0'

If no more details are to be provided, the kernel has a top and a bottom layer. On top of that, the executive manages the resources needed by the application. On the bottom, the Low-level Scheduler works as a software extension of the CPU. Together, they implement the Task abstraction — the Concurrency Unit that enables a multitasking environment.

In systems design jargon, the Executive enforces policy (what should happen). The Low-level Scheduler provides the mechanism (how it gets done). The services are the primitives that gradually translate policy decisions into concrete actions executed by the Scheduler. K0’s goal is determinism on low-end devices. Its multitasking engine operates without mimics of userland: tasks run in privileged mode on a different stack pointer from the system stack.

Given the architecture, RK0 targets applications with the following characteristics:

As the ready queue table is indexed by priority - the index 0 points to the queue of ready tasks with priority 0, and so forth, and there are 32 possible priorities - a 32-bit integer can represent the state of the ready queue table. It is a BITMAP:

In the RK0 source code, the following routines implement the bitmap update:

Having the Ready Queue Table bitmap, we find the highest priority non-empty task list as follows:

(1) Isolate the rightmost '1':

In this case:

The rationale here is that, for a number N, its 2’s complement -N, flips all bits - except the rightmost '1' (by adding '1') . Then, N & -N results in a word with all 0-bits except for the less significant '1'.

(2) Extract the rightmost '1' position:

This instruction would return #30, and #31 - #30 = #01 in the example above.

For the example above, mult = 0x2 * 0x077CB531 = 0x0EF96A62. The 5 leftmost bits (the index) are 00001 → table[1] = 1.

During a context switch, the procedures to find the highest priority non-empty ready queue table index are as follows:

There are two System Tasks: the Idle Task and the Timer Handler Task.

The Idle Task runs whenever there is no other ready task to be dispatched. The CPU enters on low-power. The kernel assigns the Idle Task priority during initialisation, taking into account all priorities the user has defined. Unless user tasks occupy all 32 priorities, the Idle Task is treated as an ordinary lowest priority and has a position in the ready queue table. Otherwise, it is selected if Ready Queue Bitmap is 0x00000000.

The Timer Handler Task is dispatched whenever an Application Timer expires to run a Callout function. Nominally its priority is 0, but on practice it could be considered as having priority -1, because it always takes precedence over other tasks with priority 0.

An essential characteristic of the scheduler is that it is a preemptive run-to-completion scheduler. This term, 'run-to-completion' has slightly different meanings depending on the context. It is often related to strictly cooperative schedulers, in the sense tasks must yield the processor. Otherwise, they monopolise the CPU.

In RK0, tasks with the same priority will run on a First-In-First-Out discipline. This is different from schedulers that employ a time-slice or a quantum for tasks, so they are forced to yield after a period and are put at the tail of the Ready Queue.

The term run-to-completion here is to be interpreted as follows:

These are timers associated with kernel calls that are blocking. Thus, establishing an upper-bound waiting time might benefit them. When the time for unblocking is up, the kernel call returns, indicating a timeout. When blocking is associated with a kernel object (other than the Task Control Block), the timeout node will store the object waiting for queue’s address, so it can be removed if time expires.

These are Application Timers that will issue a callback when expiring. In addition to a callout function, an Application Timer receives an initial phase delay and a period and can choose to run once (one-shot) or auto-reload itself.

The callback runs within a System Task with priority 0 and is non-preemptible, which makes the scheduler prioritise it over other tasks. Callouts must be short and unblocking, as they can cause high CPU contention.

For clarity, Timer Callouts are on a separate list in the kernel, although they share the same TIMEOUT node.

When a routine calls alloc(), the address to be returned is the one a "free list" is pointing to, say addr1. Before returning addr1 to the caller, we update the free list to point to the value stored within addr1 - say addr8 at that moment.

When a routine calls free(addr1), we overwrite whatever has been written in addr1 with the value-free list point to (if no more alloc() were issued, it would still be addr8), and addr1 becomes the free list head again.

Allocating and deallocating fixed-size blocks using this structure and storing meta-data this way is as deterministic (O(1)) and economical as we can get for dynamic memory allocation.

A drawback is if a routine writes to non-allocated memory within a pool it will spoil the meta-data and the Allocator will fail.

One possible usage pattern is a task’s cycle begins checking for any events (it is able/supposed to handle). If using it on a supervisor task — it can create a neat event-driven pattern for a soft/firm real-time system:

Task Signals are the the only ITC primitive that cannot be disabled, thus, they are regarded as a Core Mechanism.

Events (Sleep Queues) do not latch events, Direct Signals do not accumulate; Counting Semaphores are event counters. They can count up to RK_SEMA_MAX_VALUE (default is 255).

The typical use case for Counting Semaphores is as a "credit tracker" — one uses it to verify (wait/pend) and indicate (signal/post) the availability of a countable resource — say, number of slots within a queue.

A Binary Semaphore is a specialisation: it counts up to 1 and down to 0 — they do not accumulate. We often say its either FULL or EMPTY. The typical use case is for task-to-task (unilateral or bi-lateral), or ISR-to-task (unilateral) synchronisation.

In this sense, they overlap the Direct Signals mechanism, that can be seen as a pack of private binary semaphores (only the task itself can pend but any task can post). They can also be used as Locks for mutual-exclusion, but it has drawbacks as will be explained later.

Semaphores can also broadcast a signal, on the same way as described for EVENTS, either by wake(n) or flush().

Finally, a query() operation on a semaphore will return the number of waiting tasks if any, or the counter value. To differentiate, the number of waiting tasks is returned as a negative value. A nonnegative value is the semaphore’s counter value.

Notes:

The snippet below shows two tasks lock-stepping by posting and pending on (binary) semaphores. Task2 depends on Task1 finishing 'work1' to perform 'work2'. And vice-versa.

Some code regions are critical in that they cannot be accessed by more than one task at once. Acquiring (lock()) a mutex before entering a region and releasing it when leaving makes that region mutually exclusive.

A Mutex is another semaphore specialisation — it can be seen as a binary semaphore with a notion of ownership - when a task susccesfully acquires a mutex is now the owner, and only this task can release it.

If a task tries to acquire an already locked mutex, it switches to BLOCKED state until the mutex is unlocked by its owner. Then, the highest priority task waiting to acquire the resource is dequeued, as on semaphores.

However, unlike semaphores, the complementary operation, unlock(), when issued by a non-owner, has undefined behaviour. In K0, it will be a hard fault.

Mutexes are solely for mutual exclusion; they cannot be used for signalling. It is common to use Counting Semaphores initialised as 1, or Binary Semaphores for mutual exclusion.

However, particularly for a Counting Semaphore, if the count increases twice in a row, the mutual exclusion is gone. For both, Priority Inversion can become a problem, as will be explained.

PS: Mutexes in RK0 are not recursive. One cannot make reentrant calls on critical regions.

The snippet below shows a consumer-producer pattern for a buffer with K slots (bounded buffer pattern). Two semaphores track the number of slots for the producer and items for the consumer. The mutex prevents any write or read from being disrupted.

Let TH, TM, and TL be three tasks with priority high (H), medium (M) and low (L), respectively. Say TH is dispatched and blocks on a mutex that 'TL' has acquired (i.e.: "TL is blocking TH").

If 'TM' does not need the resource, it will run and preempt 'TL'. And, by transition, 'TH'.

From now on, 'TH' has an unbounded waiting time because any task with priority higher than 'L' that does not need the resource indirectly prevents it from being unblocked — awful.

The Priority Inheritance (PI) Protocol avoids this unbounded waiting. It is characterised by an invariant, simply put:

If employed on the situation described above, task TM cannot preempt TL, whose effective priority would have been raised to 'H'.

It is straightforward to reason about this when you consider the scenario of a single mutex.

But when locks nest — that is, more than one critical region — the protocol also needs to be:

Below, a demonstration:

Result and comments:

Importantly, the worst-case time is bounded by the time the lowest priority task holds a lock (60 ms in the example: 14720ms → 14780ms).

As for each priority update we check each waiting queue for each mutex a task owns, the time-complexity is is linear owner*mutex. But, typically no task ever holds more than a few mutexes. Yet, one should not be encouraged to nest locks if not needed.

A given number of tasks must reach a point in the program before all can proceed, so every task calls a barrWait(&barrier, numberOfTasks) to catch up with the set of tasks it must synchronise.

The last task entering the barrier will broadcast a signal to all tasks waiting for the wake condition.

Note that the mutex enforces a single active task within the barrier. They enter and leave on a 'turnstile'.

Several readers and writers share a piece of memory. Readers can concurrently access the memory to read; a single writer is allowed (otherwise, data would be corrupted).

When a writer finishes, it checks for any readers waiting. If there is, the writer flushes the readers waiting queue. If not, it wakes a single writer, if any. When the last reader finishes, it signals a writer.

Every read or write operation begins with an acquire and finishes with a release.

Some communications are unreliable or important enough so we need guarantees that not only the message could be sent, but also that it could be read.

On a zero-buffer channel, we do not allow messages to be waiting, so they are picked. The sender blocks, waiting for a confirmation that the receiver retrieved the message:

The snippet below presents two clients and one server on a lock-step communication.

It shows how data scope is kept and how it can be lost. In this case, client and server blocking for a response/ACK keeps the data scope.

Had the server not blocked waiting for an ACK, the former response would have been overwritten before a client could have read it, given how priorities are set. To accommodate two clients while still passing by reference, the server would need to keep the response on different buffers.

If a copy were passed as a response, the server would not need to block for an ACK, provided the response was sent before receiving another request.

Mail Queues (or just Queues) are Mailboxes that can hold several messages in a FIFO queue. Indeed, a Mail Queue with a size of 1 will behave as a Mailbox.

The programmer must provide a buffer to hold N message addresses for a Queue. The main primitives are post(), pend(), peek(), and jam().

Peek reads the Queue front message without extracting it, and Jam places a message on the queue front so that this message will be Last-In-First-Out.

Mails will be enqueued in a FIFO order (except when using jam()).

For both Queues and Mailboxes, if your message is a 4-byte message — such as an UINT value — they can (and probably should) be passed by copy: just cast to (VOID*) when transmitting, and cast back to UINT when receiving. Yet, this should be an option only if you are unwilling to use Streams.

Streams resemble classic (named) Pipes. The difference is that messages have a fixed size. On the other hand, pipes transmit and receive any number of bytes for each operation.

For each Stream, the user provides a buffer address with enough capacity (number of messages x message size). Then, the kernel will handle it as a ring buffer.

The message size associated with a Message Stream instance is defined at its initialisation. On transmission, a message is _ deep copied _ from the sender’s storage to the queue; on reception, it moves from the queue to the receiver’s storage.

The important primitives for Message Streams are send(), recv(), jam() and peek().

Sending to a full queue (optionally) blocks the sender. Likewise, receiving from an empty queue.

While both are Message Queues, they are distinct designs that lead to ideal use cases. Note that Mail Queues are particularly difficult to generalise.

While sharing some similarities, there are subtle differences between blocking on a shared resource (by blocking on a locked mutex) and blocking on a message-passing object.

Assuming cases we do not want messages to be overwritten, a sender, when accessing a queue, is acquiring an empty buffer. A receiver is acquiring a full buffer. They are competing for the same object but in different states. Thus, they depend on each other to change the object state.

When a sender blocks on a full shared message object, it does not mean another writer is using the resource; By design it is also unlikely there is a reader blocked on the waiting queue of the object, since every time a write operation completes, any reader blocked on the queue is readied. Whether it is dispatched or not is a scheduler concern. If its priority is higher than the task just finished, it will be immediately dispatched. If not, it is enqueued in the ready queue until it is eventually picked up.

So, if the sender’s priority is higher, it could be propagated to the reader. But, which reader? (This is why semaphores cannot implement priority inheritance protocol — the waiter task cannot know a potential signaller).

With that in mind, there is the option to set ownership: set owner (mesgpass, task handle). From now on, only the owner task can receive from that service object—a blocking send() knows the target task and can raise its priority.

(As 1:N communication normally non-blocking on real-time systems, there is no mechanism to establish 'sender ownership'.)

If another task that is not the owner tries to receive from a kernel message-passing object that has an owner, it fails.

These kernel objects now will resemble an aspect of Ports, a common way of representing tasks on message-passing kernels. (Strictly, they are not Ports, as RK0 is not a message-passing kernel—although I do like the approach.)

An MRM works as a 1-to-many asynchronous Mailbox - with a lock-free specialisation that enables several readers to get the most recent deposited message with no integrity issues. Whenever a reader reads an MRM buffer, it will find the most recent data transmitted. It can also be seen as an extension of the Double Buffer pattern for a 1:N communication.

The core idea of the MRM protocol is that readers can only access the buffer that is classified as the 'most recent buffer'. After a writer publish() a message, that will be the only message readers can get() — any former message being processed by a reader was grabbed before a new publish() - and, from now on, can only be unget(), eventually returning to the pool.

To clarify further, the communication steps are listed:

Before ending its cycle, the task releases (unget()) the buffer; on releasing, the kernel checks if the caller task is the last reader and if the buffer being released is not the current MRM Buffer.

If the above conditions are met, the unget() operation will return the MRM buffer to the pool. If there are more readers, OR if it is the current buffer, it remains available.

When the reserve operation detects that the most recent buffer still has readers, a new buffer is allocated to be written and published. If it has no readers, it is reused.

This way, the worst case is a sequence of publish() with no unget() at all — this would lead to the writer finding no buffer to reserve. This is prevented by making: N Buffers = N tasks + 1.

What might lead to some confusion when initialising an MRM Control Block is the need for two different pools:

Both pools must have the same number of elements: the number of tasks communicating + 1.

Consider a modern car - speed variations are of interest in many modules. With a somehow "naive" approach, let us consider three modules and how they should react when speed varies:

As the variations are unpredictable, we need a mechanism to deliver the last speed in order of importance for all these modules. From highest to lowest priority, Cruise, Wipers, and Radio are the three modules that range from safety to comfort.

To emulate this scenario, we can write an application with a higher priority task that sleeps and wakes up at pseudo-random times to produce random values that represent the (unpredictable) speed changes.

The snippet below has 4 periodic tasks. Tasks sleep for absolute periods. The producer publishes new data at a random interval, so it can either interrupt before one has the chance to finish or be inactive while it runs more than once.

Thus, different situations can happen:

All these cases are on the image:

Assembles a declared task.

Declare the objects needed to assemble a task.

Initialises the kernel. This will be called in main() after hardware initialisation.

The current task yields the processor, which is essential when round-robining between tasks with the same priority if there are no other blocking calls.

Disables preemption for the current task until kSchUnlock() is issued.

Restore preemption status. To be called at the end of the operation guarded by kSchLock().

A task pends on its own event flags.

Posts a combination of flags to a task.

Retrieves a task’s signal flags.

Clears the caller task flags.

Initialises an event object.

Suspends a task waiting for a wake signal.

Broadcast signal for an event.

Wakes all tasks.

Wakes a single task sleeping for a specific event (by priority).

Retrieves the number of tasks sleeping on an event.

Initialises a semaphore.

Waits on a semaphore.

Signals a semaphore.

Broadcast signal to a semaphore.

Wakes ALL tasks

Retrieves the count value of a semaphore. A negative value is the number of blocked tasks. A non-negative value is the semaphore’s counter number.

Initialises a mutex.

Locks a mutex.

Unlocks a mutex.

Retrieves the state of a mutex.

Unlocks the associated mutex and sleep for a wake signal.

Same as kEventSignal().

Same as kEventFlush().

Initialises an indirect single mailbox.

Assigns a task owner for the mailbox.

Sends to a mailbox.

Receives from a mailbox.

Reads the mail without extracting it.

Retrieves the state of a mailbox.

Posts to a mailbox overwriting current mail, if any.

Initialises a mail queue.

Assigns a task owner for the queue.

Sends to a mail queue.

Receives from a mail queue.

Reads the head mail without extracting.

Sends a message to the queue front.

Retrieves number of mails within queue.

Initialises a Stream Message Queue.

Assigns a task owner for the stream queue.

Sends a message to a message queue.

Receives a message from the queue.

Receives front message without changing state.

Sends message to queue front.

Retrieves number of messages in a stream queue.

Initialises an MRM Control Block.

Reserves an MRM Buffer to be written.

Copies a message into MRM and makes it most recent.

Receives most recent message within MRM Block.

Pointer to MRM Buffer (to be used later with kMRMUnget). NULL if error.

Releases an MRM Buffer after message consumption.

Gets current system tick count.

Total ticks since system start-up.

Gets amount of time elapsed system start-up in milliseconds.

Total ticks since system start-up in milliseconds.

Initialises an application timer.

Cancels an active timer.

Puts current task to sleep for a number of ticks.

Sleep, compensating any time drifts in-between activations.

Active wait (busy wait) for a number of ticks.

Initialises a memory pool control block.

Allocates memory block from pool.

Pointer to allocated block, or NULL on failure.

Frees a memory block back to pool.

Tasks 1, 2, 3, and 4 are in descending order of priority. If the scheduler is well-behaved, we shall see counters differing by "1."

This is the output after some time running:

Here, the tick is running @ 0.5us