RK0 – Embedded Real-Time Kernel '0’

Same Verbs, Different Contracts

Why RK0 has several communication services that appear to overlap

Look at the RK0 API quickly, and one objection is almost immediate.

Why are there so many communication mechanisms?

An Exchange sends and receives data. A Mesg Queue sends and receives data. Rendezvous sends and receives data. Named links move messages/invocations synchronously or asynchronously. At first glance, several of these facilities seem like variations of the same thing.

Why not provide one sufficiently general queue, perhaps a semaphore and a mutex, and let applications construct whatever they need?

This is a reasonable question. It also exposes a design assumption that I think has followed operating systems for too long:

If two mechanisms can implement the same functional result, they are interchangeable abstractions.

They are not.

The distinction RK0 tries to preserve is not primarily what data moved. It is why tasks were allowed to progress.

A queue is not a rendezvous

Consider a producer and a consumer.

With a conventional message queue, the producer can place a message into available storage and continue:

Producer ---- message ----> Queue
Producer continues
Consumer receives later

The queue deliberately decouples the two tasks.

Now consider synchronous rendezvous:

Producer -------- message --------> Consumer
    |                                  |
    +--------- completion <------------+

The same bytes may move from the same producer to the same consumer.

But this is a completely different interaction.

In the first case, progress depends on buffer capacity.

In the second, progress depends on participation by the other task.

That difference is not decoration around the API. It is the concurrency contract.

If rendezvous is instead constructed from shared memory and semaphores, perhaps something like:

wait empty
lock buffer
write data
unlock buffer
signal full
wait acknowledgement

the application may eventually obtain the same logical result.

But the kernel no longer sees “rendezvous.”

It sees a sequence of operations on unrelated synchronisation objects.

The intended progress relationship has disappeared into application protocol.

Expressibility is a poor test for an RTOS abstraction

There is an old temptation to reduce everything to the smallest possible set of mechanisms.

If primitive A can be used to construct B, why provide B?

Taken far enough, this gives wonderfully small primitive sets and wonderfully complicated applications.

The problem is that expressive sufficiency is not the same thing as an appropriate abstraction.

A binary semaphore may be sufficient to construct a surprising number of coordination protocols. That tells us something about the semaphore’s expressive power. It tells us much less about whether each of those protocols should be reconstructed from semaphores in a hard real-time application.

The relevant cost includes more than lines of code.

Composition can introduce additional protocol state, intermediate states, timeout cleanup, priority-propagation problems, ordering constraints, and dependencies that create poltergeists, rotten codebases. The Tower of Babel was an embedded codebase.

Two constructions can therefore be functionally equivalent while having very different operational properties.

For real-time systems, those operational properties are precisely what we care about. Because time emerges from implementation.

Minimal does not mean primitive

RK0 follows a different notion of minimality.

The kernel should provide the minimal semantic abstraction necessary. Anything the application can add cheaply and transparently should remain application policy.

Take a message queue.

RK0 doesn’t need a sophisticated variable-sized message storage system just because such a queue would be more general.

For a particular queue, the application generally knows what it carries.

If it contains 24-byte sensor records, then the useful contract is something like:

element size: 24 bytes
capacity:     8 elements

The kernel can provide bounded ordered transfer. The application provides the element size because it knows it best.

Making payload size dynamically variable would force the queue to acquire another responsibility: storage management.

Suddenly questions appear about allocation, fragmentation, admission policy, copy bounds, storage exhaustion and whether capacity means bytes or messages.

That is not merely a more flexible queue.

It is a queue plus a memory-management policy.

If an application really needs variable-sized objects, it may be better served by fixed-size descriptors, application-managed pools, or buffer ownership transfer.

The queue need not solve a problem that belongs somewhere else.

But minimal does not mean bare either.

There is an opposite mistake: assuming that once the basic mechanism exists, any additional feature represents unwanted complexity.

That is also wrong.

Some extensions are valuable precisely because the kernel already occupies the correct semantic point to provide them.

A send callback is a good example.

The kernel already knows when a message has successfully crossed a particular transition in the queue operation. Exposing a narrowly defined callback at that point can provide useful behaviour without turning the queue into a different abstraction.

That is fundamentally different from adding variable-sized allocation.

One exposes an existing semantic transition.

The other introduces a new resource-management problem.

So the design question is not:

Can this API have fewer features?

It is:

Does this feature strengthen the existing abstraction, or does it quietly make the abstraction responsible for another problem?

That distinction matters.

Apparent overlap is not necessarily redundancy.

This is why looking at an RTOS API by verb names can be misleading.

Several RK0 services may contain operations that resemble:

send()
receive()
wait()
reply()

But you shouldn’t classify an API by its verbs alone.

The important questions are:

• What allows the caller to continue?
• Does the counterpart have to participate?
• Is data buffered independently of the receiver?
• Who owns the resource while the operation is pending?
• Does another task execute on the caller’s behalf?
• Does priority have to propagate through the interaction?
• What exactly does timeout cancel?
• What state transition constitutes completion?

A queue, rendezvous and synchronous client/server channel may all transfer a word from task A to task B.

That does not make them redundant.

For example, a client/server channel represents something stronger than two message transfers:

Client ---- request ----> Server
Client <---- reply ------ Server

The server is executing work on behalf of the client.

That relationship can justify scheduler-visible behaviour such as the server adopting the caller’s priority until the transaction is completed.

A request queue followed by a reply semaphore may mimic the dataflow. It does not automatically communicate that relationship to the scheduler.

The missing information is the important part.

The alternative is not attractive.

There are two easy ways to make an API appear smaller.

One is to reduce everything to generic primitives:

mutex
semaphore
condition variable
queue

Applications then implement their actual coordination semantics themselves.

The other is to produce one enormously configurable abstraction:

ipc_send(object,
         BUFFERED |
         SYNCHRONOUS |
         REPLY_REQUIRED |
         DONATE_PRIORITY |
         DIRECT_DELIVERY |
         DEEZ_NUTZ |
         ...);
 

Now the API technically contains one service, but that service contains dozens of implicit protocols.

This is the synchronisation equivalent of ioctl().

The interface becomes smaller syntactically while becoming less meaningful semantically.

RK0 takes the opposite position: different progress contracts can have different names.

Implementation machinery may still be shared internally. That is an implementation concern.

API identity should follow semantics, not code reuse.

Where should the kernel stop?

This does not mean every application pattern deserves a kernel service.

That would merely replace generic primitives with application-specific syscall clutter.

The rule I use is simpler.

If the application can extend an existing service with little burden, leave the extension in the application.

If the required interaction demands substantial protocol machinery, obscures the intended progress relationship, or requires scheduler behaviour the application cannot implement itself, then a new kernel service is justified.

The resulting service should still describe an application-independent concurrency contract.

“Synchronously transfer a message and complete only when the receiving task participates” is such a contract.

“Send command 7 to my motor controller and wait for the inverter” is not.

This gives the kernel a middle ground between two extremes:

Too generic                                      Too application-specific
    │                                                       │
    ▼                                                       ▼
semaphore     mutex     condvar              application-defined syscall
    │           │          │                           │
    └───────────┴──────────┘                           │
           
    -  -  -  -      -  -  -  -           -  -  -  -             
                 
    INTERESTING REGION:
    
    recurring patterns, optimised for for worst case
    are a kernel corcern:
     Service A. implements
       └─ buffered / asynchronous communication 
          not prone to priority inversion 
     Service B. implements
       └─ no message is deposited and waits
      Service C. implements
       └─ non-blocking last-message 1:N comm
      Sercie D. implements
       └─ synchronous invocation keeping caller urgency
       

The goal, therefore, is not to have the fewest possible services.

It is to have few services with high semantic density.