RK0: The Real-Time Kernel '0'

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 RK0 source code, the following routines implement the bitmap update:

The Idle Task priority is assigned by the kernel, during initialisation, taking into account all priorities the system programmer has defined. Unless user tasks are occupying all 32 priorities, the Idle Task is treated as an ordinary lowest priority and has a position in the ready queue table. If not, the idle task on practice will have no queue position and will be selected when the BITMAP is 0. In the above bitmap, the idle task is in readyQueue[6].

Having 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:

In the example above, this instruction would return #30, and #31 - #30 = #01.

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:

To avoid the most common pitfalls when scheduling tasks the system programmer should be aware that:

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 error. When blocking is associated to a kernel object (other than the Task Control Block), the timeout node will store the object waiting 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 run-to-completion - what makes the scheduler prioritise it over other tasks. Callouts must be made 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 economic as we can get for dynamic memory allocation.

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

The memory allocator (if well employed) will never fail; it might take the same amount of time to allocate and free a block. In the test below, three tasks with the same priority are allocating, increasing a counter, and freeing a block of 128 bytes. If the allocator exhibits deterministic behaviour, these counters might differ by at most 1 whenever we pause the device.

Below are the results after ~2.5 million ticks of 0.5 ms.

A Counter Semaphore counts up to N, limited by the maximum number an integer can represent (hardly you’d want that though).

A Binary Semaphore - counts up to 1 and down to 0 — we often say its either FULL or EMPTY.

Counter semaphores are often seen as "credit tracker" as a typical usage is to verify (wait/pend) and indicate (signal/post) the availability of a countable resource — say, number of slots within a queue.

Binary semaphores are typically used for task-to-task synchronisation/notification - unilateral or bilateral. (Although not ideal, it is common to see binary or counter semaphores initialised as '1' for mutual exclusion.)

Semaphores can also broadcast a signal, on the same way as described for EVENTS, either by wake(n) or flush(). The query() on a semaphore will return a non-negative number if there are no tasks blocked on the semaphore. A negative number is to be interpreted as the number of blocked tasks.

PS: often on the snippets it is written kSignal(taskHandle)/kPend(timeout) — this is an application-defined alias for when a task is using a single bit of its signal flags, as if having a single binary private semaphore.

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. As mentioned, it is common to use Counter Semaphores initialised as 1, or Binary Semaphores for mutual exclusion.

However, particularly for a counter 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.

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 message was retrieved by the receiver:

Mailboxes are well-suited for 1:1 communication - fully synchronous (lockstep) command-response or when a task waits for a notification plus a payload (say, the last data read by an Interrupt routine).

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

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

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

If a copy was passed as a reponse, 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). Ther kernel will handle it as a ring buffer.

The message size associated with a Message Stream instance is defined on its initialisation. On transmission, a deep copy of a message from the sender’s storage to the queue takes place; 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 distinct ideal use cases. Note that Mail Queues are particularly difficult to generalise.

While sharing some similarities, there are subtle differences on 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 on 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 there is another writer 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 that has just finished, it will be immediately dispatched. If not, it is enqueued on the ready queue until it is eventually picked.

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

With that in mind, there is the option to set ownership: setowner(mesgpass, taskhandle). From now own, only the owner task can receive from that service object — a blocking send() knows the 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 other task that 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-passsing 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.

The core idea on he MRM protocol is that readers can only access the buffer that is classified as the '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:

Thus as a message is returned only when there there are no readers and and there is new message, and the writer only allocates a new buffer if when reserving the most recent buffer still has reader, after a first publish there will always be a message.

So, the worst-case for a writer is: when reserve(), a reader is active on another buffer. For readers, after the first publish() there will always be a buffer. So, the total number of buffers in the pool is the number of tasks and an extra buffer the writer worst-case.

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

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, Whipers, 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 are sleeping for absolute periods. The producer has a random interval of publishing new data, so it can either interrupt before one has the chance to finish or be inactive while they run more than once.

Thus, different situations can happen:

All these cases are on the image:

Assemble a declared task.

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

The current task yields the processor. Essential when round-robin between tasks with the same priority if there no other blocking calls.

A task pends on its own event flags.

RK_SUCCESS, RK_ERR_FLAGS_NOT_MET, or specific error.

Posts a combination of flags to a task.

RK_SUCCESS or specific error.

Retrieves a task’s signal flags.

RK_SUCCESS or specific error.

Clears the caller task flags.

RK_SUCCESS or specific error.

Initialises an event object.

RK_SUCCESS or specific error.

Suspends a task waiting for a wake signal.

RK_SUCCESS or specific error.

Broadcast signal for an event.

RK_SUCCESS or specific error.

Wakes all tasks.

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

RK_SUCCESS or specific error.

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.

RK_SUCCESS or specific error.

Retrieves the state of a mutex.

Initialises an indirect single mailbox.

Assigns a task owner for the mailbox.

Sends to a mailbox.

Receives from a mailbox.

Posts to a mailbox overwriting current mail, if any.

Reads the mail without extracting it.

Retrieves the state of a mailbox.

Initialises a mail queue.

Assigns a task owner for the queue.

RK_SUCCESS or specific error.

Sends to a mail queue.

Receives from a mail queue.

Reads the head mail without extracting.

Retrieves number of mails within queue.

Sends a message to the queue front.

Initialises a Stream Message Queue.

Assigns a task owner for the stream queue.

Retrieves number of messages in a stream queue.

Sends message to queue front.

Receives a message from the queue.

Sends a message to a message queue.

Receives front message without changing state.

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.

RK_SUCCESS or specific error.

Gets current system tick count.

Total ticks since system start-up.

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.

© 2025 Antonio Giacomelli | All Rights Reserved | www.kernel0.org