RK0 – Embedded Real-Time Kernel '0’

If this is your first contact with RK0, its design premise can be stated simply:

Overgeneralisation hides information from the kernel and leaves the application to handle the worst cases.

Semaphores, queues and mutexes are useful mechanisms, and RK0 provides them. But a real-time kernel should not stop at a collection of mechanisms from which the application must reconstruct every meaningful interaction. What repeatedly appears across cyber-physical systems is not a particular peripheral interface or application domain, but a finite set of coordination problems: urgency, precedence, exclusion, availability, notification, ownership, state transfer and temporal release.

Those problems are independent of domain and hardware. RK0 therefore follows an interaction-driven design: it asks whether an interaction is recurrent enough that applications repeatedly reconstruct it, and whether its edge cases are complex enough that application-level reconstruction is likely to obscure the timing contract. If both answers are yes, consider including that interaction as a kernel service.

This does not mean that every recognisable programming pattern belongs in the kernel. The interesting question is not how high-level a service appears, but where its semantics can be implemented most clearly and where its worst cases can be handled most effectively.

An apparent contradiction: MRM and Condition Variables

RK0 provides the high-level Most-Recent Message (MRM) protocol as a kernel service. A Condition Variable, which appears much closer to a conventional primitive, is instead treated as a composition pattern built from a Mutex and a Sleep Queue.

At first glance, this seems backwards.

A Condition Variable under Mesa semantics is deliberately general. Waking a task means only that the protected state may have changed. After waking and reacquiring the Mutex, the task must test the predicate again; another task may already have changed the state, so the awakened task may immediately return to sleep.

That behaviour is correct, but it may cause unnecessary wake-ups, lock acquisitions and context switches. In a general-purpose system, this is often an acceptable consequence of a convenient abstraction. In a real-time design, it deserves explicit consideration. The most efficient policy depends on the application predicate, the number and urgency of the waiters, and how the protected state changes.

RK0 consequently exposes the pieces and supplies helpers for the atomic unlock–sleep–relock sequence. The application retains the predicate and can compose the synchronisation policy it actually needs. The kernel does not pretend that a generic wake-up proves that the predicate is true.

MRM has the opposite shape. It represents a recurring 1:N interaction in which one publisher updates a state and several readers, running at independent rates, require the most recent complete version rather than a history of intermediate samples. This is common in servo-control and hierarchical control loops.

Implementing this correctly with ordinary queues is not straightforward. A queue preserves backlog, while this interaction values freshness. A single shared buffer risks readers observing a partial update. Double- or triple-buffer protocols become more complicated when several readers may retain different versions. The buffer lifetime, reader references and publication point must remain coherent without forcing readers to run at the publisher’s rate.

MRM makes that contract explicit: publication is asynchronous and non-blocking; new readers get the latest complete version; existing readers can safely finish with an older one; obsolete samples do not become work the system must catch up on. MRM does not notify or wake readers—it safely publishes the latest state.

The apparent contradiction is therefore resolved. Condition waiting depends on an application-owned predicate and often benefits from a tailored policy. Most-recent publication has a stable interaction contract but has difficult integrity and lifetime edge cases. RK0 composes the former and provides the latter.

This is the practical meaning of interaction-driven design.

Semantics displacement

When a kernel provides only weak, generic mechanisms, the missing meaning doesn’t disappear. It moves into application code, spreading across control flow, shared variables, buffer ownership, and conventions the kernel cannot see.

RK0 calls this semantics displacement.

Consider a shared buffer coordinated by two binary Semaphores:

/* Visible only within this translation unit. */
#define MESGSIZ (K) /* integer constant K > 0 */

static BYTE sharedBuf[MESGSIZ];
static RK_SEMAPHORE notFull;   /* initially 1 */
static RK_SEMAPHORE notEmpty;  /* initially 0 */

static VOID WriteMessage_(BYTE const * const source)
{
    kSemaphorePend(&notFull, RK_WAIT_FOREVER);
    /* exclusive access might be necessary */
    RK_MEMCPY(sharedBuf, source, MESGSIZ);
    kSemaphorePost(&notEmpty);
}

static VOID ReadMessage_(BYTE * const destination)
{
    kSemaphorePend(&notEmpty, RK_WAIT_FOREVER);
    /* exclusive access might be necessary */
    RK_MEMCPY(destination, sharedBuf, MESGSIZ);
    kSemaphorePost(&notFull);
}

Functionally, this is a blocking Mailbox (one-slot message queue). The first Semaphore records that the slot is available; the second records that a value is pending. A reader consumes the pending occurrence and then registers that the slot is free again. A blocked writer or reader may consequently become READY.

But the kernel sees two unrelated counters. It does not see one message object, one slot, one admission rule or one completion contract. It cannot enforce the relationship between the Semaphores and the buffer, trace them as one interaction, or apply one ownership, priority and timeout policy to the composite protocol. All of that meaning exists only in the application.

Composition is not inherently wrong. This example is small and understandable. The problem appears when a supposedly generic foundation forces applications to rebuild richer protocols whose cancellation, ownership, saturation or priority edge cases are no longer small. At that point, generality has displaced semantics rather than eliminated complexity.

If everything is an event, nothing is

One of the broadest generalisations in real-time software is the concept of an event. We have an intuitive idea of what an event is, but we often understate how its representation changes the system’s meaning.

An event is an occurrence associated with a change in system state. The computer observes that occurrence through some representation. RK0 distinguishes three progressively richer representations:

1. a pure signal—an operation with no retained token;
2. a registered event, or signal token—an occurrence retained for later consumption;
3. a message—application information transferred under a defined retention and completion contract.

These representations are not interchangeable.

Pure signals

The crudest signal is an operation. In RK0, a Sleep Queue provides this form.

Signalling a Sleep Queue may wake the highest-priority waiter, a specified number of waiters, or all current waiters. If the queue is empty, nothing happens, and nothing is retained. A later task cannot discover that the earlier signal occurred.

Conversely, sleep(&sleepqueue, timeout) performs no predicate test. It moves the running task to a WAITING state until a future signal, timeout, or cancellation makes it READY again (RK_NO_WAIT for timeout is an invalid argument). Used without a clear synchronisation point, this is error-prone: a signal that races ahead of the wait is deliberately lost.

That does not make the mechanism inadequate. It makes its semantics precise. Sleep Queues are primarily building blocks for monitor-like mechanisms, where the application tests protected state and uses the queue only for waiting. Pure signal semantics can also be useful when correctness intentionally depends on temporal coincidence—for example, when an external aperiodic occurrence should be ignored unless a receiver is already waiting.

The important point is that a pure signal does not necessarily create state.

Signal tokens: registered events

A registered event creates state that a task may consume later. RK0 offers two principal families, shown here in three useful forms:

Representation	Retained state	Typical meaning
Binary Semaphore	0 or 1	An occurrence happened, or one resource is available
Counting Semaphore	Bounded unsigned count	Units are available, or several occurrences are pending
Task Event Register	Private bit string	One or more named conditions have occurred

The format and the object together compose the information. A binary token may mean that a device is available. A count of three may mean that three requests remain to be serviced. A bit string may record that oil pressure is low, motor temperature is high and throttle position has not changed.

Signal tokens are consumable coordination state. A Semaphore pend consumes a count. A task waiting for Event Register bits consumes the requested bits according to the operation’s rules. Repeated settings of the same bit may coalesce; if every occurrence matters, a bit is the wrong representation.

This is already different from a pure signal: the sender and receiver do not need to coincide in time.

Messages: data and time coordination

A message contains application-defined information. The kernel does not know what a pressure sample or actuator command means, but it defines how that information is retained, transferred and completed.

This makes message passing richer than treating a Boolean, integer or bit string as merely a tiny message. Sending may block because a buffer is full, until a receiver copies the data, or until a server returns a reply. Receiving may consume FIFO history, inspect a value without consuming it, accept transferred ownership, or obtain a shared published version.

Different RK0 message services therefore establish different communication models:

Note: A named, sometimes we say direct, message-passing operation is one that defines a task as the destination or source, not an object. An unbuffered message blocks the sender until the message is retrieved.

Interaction	Sender-side success means	Retained state
Message Queue	The value was admitted or copied to a waiting receiver	Bounded FIFO history
Overwrite Mailbox	The newest pending value replaced or became the single stored value	One newest slot
Named Unbuffered Synchronous Message	The receiver copied the offered payload	No message history
Named Synchronous Request–Reply	The server replied to the accepted call	Pending callers and one accepted call
Named Asynchronous Message	Ownership of the pool-backed object moved to the receiver endpoint	Queued message objects
MRM	A complete version became current	Latest safe version or versions

The word send does not define a single completion point. Replacing one of these services with another changes the operational contract even when the same bytes eventually reach the same task.

The scheduler makes progress observable

Interaction-based services matter because interactions create execution-progress dependencies. A task waits for time, a signal, data, storage, a resource owner, a receiver or a server. The dependency chain emerges from those relationships.

If the interaction exists only as an application convention, the scheduler cannot see the whole chain. If the service represents it, the kernel can preserve it as explicit system state.

RK0 places the scheduler at the centre of this model. It uses fixed-priority pre-emptive scheduling, with one FIFO ready queue per priority and no automatic time slicing. The highest-priority READY task is selected to run. Among tasks of the same priority:

• a pre-empted task returns to the head of its ready queue;
• a task that yields returns to the tail;
• a task released from a wait also enters at the tail.

Equal-priority tasks therefore cooperate by yielding or waiting. The passing of a tick does not invent a reason for another equal-priority task to run.

Execution progress is expressed in the application code.

A static task moves among INITIALISED, READY, RUNNING and service-specific forms of WAITING; a dynamic task may also become TERMINATED. Only the scheduler changes a task from READY to RUNNING.

Every dispatch should consequently answer a simple question:

Why is this task allowed to run now?

The answer must be a visible change in urgency or eligibility: a more urgent task became READY, the current task yielded, a waiting condition was satisfied, a timeout expired, or the current task ended.

Priority follows the dependency

Priority inversion is commonly described as a Mutex problem. The broader problem is a blocked dependency. An urgent task may depend on a less urgent task that owns a lock, must accept a message, must finish a reply, or holds the last block in a bounded pool.

Because RK0 represents these interactions explicitly, urgency can follow them:

• fully transitive priority inheritance propagates through nested Mutex dependencies;
• a receiver receives a priority contribution while a more urgent sender waits for a synchronous hand-off;
• a server carries its active caller’s priority contribution until reply or abandoned-call completion;
• an optional priority ceiling follows ownership of messages allocated from a bounded asynchronous pool.

Effective priority is scheduler state, not merely a value checked at dispatch. When it changes, the task’s ordering must remain correct whether it is READY or waiting on an object. If that task is itself part of another dependency, the change must propagate.

The common rule is:

Urgency follows the dependency that is delaying progress.

Priority handling cannot repair an unbounded critical section or manufacture storage in an exhausted pool. It can prevent unrelated, less urgent work from extending a dependency whose own work and resource use have been bounded by design.

Time is also an interaction

One generic sleep() cannot express every temporal relationship. RK0 distinguishes four meanings:

Service	Expressed temporal relation
Busy Delay	Consume ticks while RUNNING; pre-empted time does not count
Sleep Delay	Wait relative to the instant of the call; lateness may accumulate as drift
Sleep Until	Advance a task-local anchor one period at a time and report an elapsed period
Sleep Release	Follow the scheduler-start phase grid, record overruns and target the next valid release

A timeout has an equally specific meaning: the waiting dependency has expired and the task becomes READY. It does not guarantee that the task executes at that instant; dispatch remains governed by fixed priority.

These services let application code distinguish processor demand, relative delay, activation accounting and phase-aligned periodic release. RK0 does not perform response-time or Rate-Monotonic Analysis for the designer. It supplies explicit release, blocking and scheduling semantics on which such analysis can be based. WCET, interference, resource capacity and critical-section length remain application inputs.

What the RK0 model enables

The result is not merely a larger catalogue of services. It is a common model connecting shared-state coordination and message passing.

It enables:

• execution progress that is explicit rather than produced incidentally by time slicing;
• waits associated with identifiable conditions and release events;
• precise completion, ownership and retention rules for communication;
• scheduler-visible priority dependencies across several kinds of interaction;
• bounded storage whose saturation requires an explicit application policy;
• specialised services where generic composition would displace complex semantics;
• application-specific composition where the kernel cannot know the predicate or best policy.

This makes the kernel useful as a real-time executive rather than only as a multitasking engine. It does not make the application automatically schedulable, and it does not remove the need for design analysis. It makes the assumptions that such analysis depends on easier to state, inspect and test.

At any point in the system, a review should be able to ask:

• What state did this interaction retain?
• What does success mean?
• Who owns the data now?
• Why is this task waiting?
• Which event can make it READY?
• Which priority dependency exists?
• What happens on timeout, saturation or overrun?

If the answers are hidden across unrelated primitives and application conventions, the system still has semantics—but they have been displaced. RK0’s design approach brings recurring, timing-relevant interactions back into the model, where their effect on execution progress becomes explicit.

And the scheduler should always be able to answer the original question:

Why is this task allowed to run now?