Multitasking #

JeeH includes a multitasking core which aims to be simple, small, and effective (doesn’t all software?). It does this with a technique which might well be called time-shifting. The issue is that hardware interrupt requests (IRQs) can happen at any time, even when the running code is not prepared to deal with it (such as when acting on the same data as the interrupt handler).

By using a message-oriented approach, the tricky aspects of IRQs can be queued and postponed to a more suitable moment. When combined with a system call mechanism and device drivers which always run to completion, you end up with a design which tames the most tricky aspect of IRQs: the potential for race conditions.

This is not new. Much of this design was inspired by some old systems: TRIPOS ¹ and Xinu ².

Athough it’s called a multitasker n JeeH, the key concurrency concept is in fact a thread.

Messages #

The Message type is a 16-byte data structure which can be passed around (by reference, never copied) and which can be robustly chained and queued by JeeH:

struct Message {
    int8_t   mDst;
    int8_t   mTag;
    uint16_t mLen;
    uint8_t* mPtr;
    uint32_t mArg;
    Message* mLnk;
};

Everything except the mLnk field can be used as needed, but most fields have very specific meanings in certain contexts. The mLnk field is exclusively managed by JeeH, so that there can be no conflicts or race conditions.

Chains #

The Chain object acts as the head of a list of messages. It has methods to examine or remove the first message (if any), and to insert a message at the front or end of its chain.

When used from system calls (see below), they offer interrupt-safe access and manipulation to their queues. Messages and chains can also be adopted for application-level messaging.

Threads #

A Thread is defined as both a Message and a Chain:

struct Thread : Message, Chain { ... };

Each thread represents an execution context with its own stack area. Threads can be placed on a queue (since each one is also a Message). Threads also act as a queue for incoming messages (since a Thread is also a Chain). Threads are created using the “fork” system call.

System calls #

There are a few system calls which drive the whole multitasking machinery, as well as offering some utility functions. From C++, these look like static methods in the Sys object:

struct Sys {
    ...
    static void send (Message& msg);
    static Message& recv ();
    static Message& fork ( ... );
    ...
    inline static void call (Message& msg) { ... }
    inline static void wait (uint16_t ms) { ... }
};

The wait system call is simply a convenience wrapper (a call to the Ticker driver).

Device drivers #

Device drivers are used to tie threads and IRQ-generating hardware peripherals together using messages. A driver is activated by sending it a request message. It manages its peripheral’s interrupts, and returns messages to its calling thread(s) as reply when the time has come. Between these moments, a driver will keep track of pending messages in its own queue(s).

A device driver does not have its own stack. It runs in the handler mode present on all ARM Cortex CPUs (whereas application code runs in thread mode), and shares a single Main Stack Pointer (MSP). Driver code never blocks: it always runs to completion, just like a function call.

In contrast, threads each have their own stack area, with JeeH’s multitasker adjusting the Process Stack Pointer (PSP) whenever it needs to switch contexts between them.

Each device driver type needs to be implemented as a subclass of the abstract Driver class, and must define at least these four methods:

struct Driver {
    ...
    virtual void start (Message&) =0;
    virtual void abort (Message&) =0;
protected:
    virtual bool interrupt (int) =0;
    virtual void finish () =0;
    ...
};

Device drivers are not accessed directly by application code. The way to activate a driver is to send it a message (with the driver-specific id in the message’s mDst field).

Atomic execution #

In JeeH, only device drivers have to deal with interrupts. Applications just send messages (asynchronously or blocking) and wait for incoming messages (always blocking). These messages can be exchanged between threads or between threads and drivers. A device driver cannot generate messages, it can only send requests back to its callers as replies.

Hardware interrupts can (and will) happen at any time. JeeH never disables IRQs (except on ARM Cortex M0+, which has no atomic test-and-set instructions). It is up to driver code to “make things work properly” with respect to its own IRQs. In practice, this is hardly ever an issue, because of how interrupt handlers are managed in JeeH. Even when an IRQ happens during a driver call, the basic approach is to have that IRQ set a driver-specific “pending” bit when it needs to cooperate with its driver. Using the magic of IRQ priorities and the PENDSV interrupt, the driver will finish what it’s doing and only then will its finish method be called.

It may all sound more complicated than it really is: the interrupt method returns a bool. When true, this means: call my driver’s finish method, but only when it’s not active.

This addresses the key complexity of all those unpredictable hardware interrupts.

For the rest of the system, there is one more essential detail: system calls can’t be suspended (but they can still be temporarily interrupted, just like any other code). So when a driver sends a reply and activates a thread with a higher priority than the current one, it’ll force the current thread to be suspended - but not while that thread is performing a system call.

Every system call (and driver request, which always starts as a send system call) is atomic.

Since all message queues are managed via system calls, they too are protected from IRQs.

Flow of control #

This is an example of how threads, system calls, drivers, and interrupts work together in JeeH:

Higher-priority code is shown at the top, time runs left to right, and suspended code is in gray.

A - Thread #1 is running and calls Sys::fork to launch a second thread.
B - Because thread #2 has a higher priority, thread #1 will be suspended.
C - Thread #2 does a Sys::wait(1) to suspend itself until the next system tick.
D - Because #2 can no longer run, thread #1 will now resume after its fork call.
E - The systick interrupt fires and disovers that it needs to wake up thread #2.
F - On completion of the interrupt, thread #1 is forced to suspend, and #2 resumes.
G - Thread #2 performs some system call, Sys::outf in this example.
H - A systick interrupt fires, but it’s lower priority than SVC and must wait.
I - The outf system call finishes, allowing the systick interrupt to be processed.
J - Thread #2 can now resume where it left off, since there was no reason to switch.
K - Thread #2 performs a Sys::quit (or returns: same thing), because it is done.
L - There’s nothing else going on, thread #1 resumes where it was abruptly suspended.
M - Thread #1 does a Sys::recv system call, which is blocking.
N - The systick fires, but can’t run before the system call ends.
O - A high-priority UART interrupt comes in, which briefly suspends even the system call.
P - The system call resumes, and notes that the recv request can now be serviced.
Q - Before thread #1 actually resumes, the pending systick interrupt is taken care of.
R - Once the system call and interrupt are done, thread #1 can resume its work.

Note that drivers are not being mentioned here: they are always run as part of a system call.

Interrupts #

Interrupt requests (IRQs) are tricky in embedded software development. They do what the name says: interrupt the current code to do something completely different. Then the original code resumes as if nothing happened. Unless the multitasker decides to switch threads …

IRQs can also interrupt driver code. And in both cases, the timing can be awfully inconvenient. Such as a new message for the driver being placed in a queue, while the IRQ just signaled that the pending one is done and should be sent back.

The sledgehammer solution is to briefly disable all interrupts while working on data structures which can be changed by an IRQ. There are usually a lot of such cases, and they slow down all IRQs (increasing their latency), even unrelated ones. JeeH never locks out interrupts this way.³

Another solution is to introduce time-shifting via messages and message queues: when IRQ code runs, it is not allowed to touch any threads or perform any system calls. All an IRQ handler can do is 1) set a pending bit specific for the driver associated with this handler and 2) request a PendSV interrupt. The IRQ handler code still needs to do whatever is really urgent, such as reading out a hardware register before it gets overwritten by new incoming data, but everything else is postponed to when PendSV runs.

The key is that PendSV is the lowest level interrupt, and will never run while a system call is running (which is handled by the SVC interrupt). PendSV can then launch the driver’s finish code to manage messages and queues as needed (and start new hardware activity, if any). Since SVC and PendSV never run at the same time, there is no conflict while altering queues.

Note that IRQs can still interrupt SVC and PendSV code. But these do not touch messages or queues. An IRQ can only ask for a new PendSV to happen later, once current IRQs have ended.

It’s a delicate dance, but this avoids any chance of IRQs messing things up.

Thread fixing and locks #

There is still a scenario where a thread can be abruptly suspended and control handed over to another thread. This will happen when an IRQ leads to a higher-priority thread being resumed. Unfortunately, this prevents threads from safely reading and modifying shared datastructures. But there’s a very lightweight mechanism for a thread to prevent being switched out this way:

Thread::fix();
...
Thread::unfix();  // or: Sys::<whatever>(...)

In other words: fix tells the multitasker not to allow a context switch until the next unfix or system call (whichever comes first). This turns the code between these two calls into a critical section, as far as threads are concerned. Redundant fix and unfix calls are ignored.

A “fixed” thread never suspends. To make threads wait on each other, a more sophisticated approach is available: the Lock datatype provides this (and is based on fix and unfix). It can be used to implement other thread synchronisation mechanisms, with the following API ⁴:

struct Lock {
    bool acquire (bool blocking =true);
    bool isLocked () const;
    void release ();
};

In non-blocking mode, acquire’s return value will indicate whether the lock was acquired. JeeH uses such a lock to guard printf’s shared buffer when called from different threads. For another example, see the Dining Philosophers Problem demo in tests/philo.cpp.