Contiki, RIOT and the Other Sensor Operating Systems

A running system. "A running Contiki system consists of the kernel, libraries, the program loader, and a set of processes." A process is an application program or a service, and "All processes, both application programs and services, can be dynamically replaced at run-time." A process is defined by an event handler function and an optional poll handler, all processes share one address space, and "Interprocess communication is done by posting events."

The core and the loaded programs. A Contiki system is split, at compile time, into two parts. The core (typically the kernel, the program loader, the most used parts of the C run-time and libraries, and the communication stack with its radio drivers) is one binary image stored in the node before deployment and normally not changed afterwards. Loaded programs are brought in later by the program loader, either over the network or from attached storage such as EEPROM. This split is what lets a deployed network be reprogrammed one program at a time.

Figure 31.1 Contiki: the core, fixed before deployment, and a program loaded at run time

The kernel: events, polling and one stack

The Contiki kernel "consists of a lightweight event scheduler that dispatches events to running processes and periodically calls processes' polling handlers". It never preempts an event handler, so event handlers must run to completion. It has two kinds of event:

1. Asynchronous events are "a form of deferred procedure call": queued by the kernel and delivered to the target process later.
2. Synchronous events immediately schedule the target process, and control returns to the poster only when the target has finished, like a procedure call between processes.

Polling is the third mechanism: polls "can be seen as high priority events that are scheduled in-between each asynchronous event", used by processes close to the hardware to check a device's status. The kernel uses a single shared stack for all processes, rewound between event handlers.

Interrupts never post events. Contiki "never disables interrupts", so that it can run on top of a real-time executive. Posting an event from an interrupt handler would then race with the event handlers, so Contiki does not allow it: an interrupt sets a polling flag, and the poll handlers do the work. The survey sums it up: since events run to completion and interrupts cannot post events, Contiki "provides serialized access to all resources".

Power saving is left to the application. "The Contiki kernel contains no explicit power save abstractions." Instead, the event scheduler exposes the size of its event queue, so the application can put the processor to sleep when no event is waiting.

Loadable programs, services and libraries

Loadable programs carry relocation information. The loader allocates memory for the program (or aborts if it cannot), relocates it, and calls its initialisation function, which may start or replace processes.

Services are processes that implement something other processes use: communication stacks, sensor drivers, data-handling algorithms. The paper describes a service as "a form of a shared library" that can be replaced at run time. A service layer next to the kernel keeps track of the running services, each named by a text string. A service's interface is a version number and a table of function pointers; an application calls it through a small stub that finds the service once, caches its process ID, and checks the version. When a service is replaced, the kernel tells the old one to remove itself, and the old one can hand its state to its replacement, tagged with its version number.

Libraries can be linked in three ways: statically with the core, statically with a loaded program, or called as a service. Frequently used functions (the paper's example is memcpy()) belong in the core; rarely used ones (atoi()) travel inside the program that needs them.

Communication is a service too, so a stack or a routing protocol can be replaced at run time, and two stacks can be loaded at once for comparison. Because synchronous event handlers run to completion, the whole stack can share one packet buffer, with no copying. According to the 2011 survey, Contiki provides uIP, "a TCP/IP protocol stack for small 8 bit micro-controllers", a lighter layered stack called Rime, and ContikiRPL, an implementation of the RPL routing protocol of [Sensor Networks in the Internet of Things: 6LoWPAN, RPL and CoAP]. Contiki networks are simulated with Cooja.

Threads, when a program really needs them

Preemptive multithreading in Contiki "is implemented as a library on top of the event-based kernel", linked only into programs that ask for it. Each thread gets its own stack, and preemption uses a timer interrupt that saves the registers and switches back to the kernel's stack. The platform-specific part is small: for the MSP430 it "consists of 25 lines of C code". A thread uses six calls: mt_yield(), mt_post(), mt_wait() and mt_exit() from inside a running thread, and mt_start() and mt_exec() to set one up and run it; mt_exec() is called from an event handler. A thread suits one long computation, such as cryptography, that would otherwise hold up every event.

Worked example: how big is Contiki?

Table 1 of the Contiki paper gives the compiled size of each part of the system, with an example service (a sensor data replicator), for the two processors it ran on. In bytes:

The AVR column adds up as 1,044 + 128 + 678 + 90 + 182 + 1,752 = 3,874, and the MSP430 column as 810 + 110 + 658 + 582 + 60 + 98 + 1,558 = 3,876. On the MSP430 the kernel and service layer together are 810 + 110 = 920 bytes.

The paper places this between its neighbours: Contiki's code size is "larger than that of TinyOS" but "smaller than that of the Mantis system". Its kernel is larger than TinyOS's because it offers more: TinyOS's kernel has only a FIFO task queue, while Contiki's has events and prioritised poll handlers, and its flexibility at run time needs code that TinyOS resolves when it compiles.

What run-time loading bought in practice. The authors built a 40-node alarm system. Its application was about 6 kilobytes, and the complete system image with the core and the C library nearly 30 kilobytes. Reprogramming one node by wire took just over 30 seconds, and the whole network "at least 30 minutes of work". Loading one changed component over the radio took about two minutes, "a reduction in an order of magnitude", with the nodes left where they were.

Protothreads

Event-driven code has one great weakness: a handler cannot wait. Anything that needs several steps with waits in between (switch the radio on, wait, send, wait for an acknowledgement, switch it off) must be written as a state machine, with the current step stored in a variable and a switch on it in every handler. The protothreads paper says this style "makes many programs difficult to write, maintain, and debug".

The idea. A protothread lets the programmer write the steps in order, with a blocking wait, PT_WAIT_UNTIL(condition), between them, while the program remains event-driven underneath. "A protothread is stackless": it has no stack of its own, "all protothreads in a system run on the same stack, which is rewound every time a protothread blocks". It is driven by repeated calls to the function it lives in, and each call carries on from where the last one waited.

What it costs. The memory overhead is "only two bytes per protothread". In the programs the authors rewrote, "the majority of the state machines could be entirely removed", and "the number of lines of code was reduced by one third", for an execution time overhead "on the order of a few processor cycles".

How it works. In the paper's portable version, the two bytes hold a line number. PT_BEGIN opens a C switch statement on that number, with case 0 for a fresh start. Each wait stores its own line number (the C macro __LINE__) and places a case label for that number right there. So a later call jumps straight back to the wait and tests the condition again: if it is still false, the function returns; if true, it carries on. A case label inside a loop inside a switch is legal C, a trick the paper traces to Duff's device.

The program. Here is that mechanism in full, written for this book: two protothreads, a radio that is on for 2 ticks and off for 6, and a sensor that takes a reading every 5 ticks and must wait for the radio to be on before sending it. The loop in main is the event loop, calling each protothread once per tick.

#include <stdio.h>

/* All a protothread keeps between calls: the line to carry on from. */
struct pt { unsigned short resume; };

#define PT_BEGIN(p)  switch ((p)->resume) { case 0:
#define PT_WAIT_UNTIL(p, cond)                                            \
    (p)->resume = __LINE__; __attribute__((fallthrough)); /* meant */   \
    case __LINE__: if (!(cond)) return 0
#define PT_END(p)    } (p)->resume = 0; return 1

static int now;             /* the clock, in ticks, advanced by main */
static int radio_on;        /* shared by the two protothreads */

/* The radio's duty cycle: on for 2 ticks, off for 6, for ever. */
static int radio(struct pt *p)
{
    static int until;       /* static, so it survives a wait */
    PT_BEGIN(p);
    for (;;) {
        radio_on = 1;
        printf("%2d  radio on\n", now);
        until = now + 2;
        PT_WAIT_UNTIL(p, now >= until);
        radio_on = 0;
        printf("%2d  radio off\n", now);
        until = now + 6;
        PT_WAIT_UNTIL(p, now >= until);
    }
    PT_END(p);
}

/* A reading every 5 ticks, sent as soon as the radio is on. */
static int sensor(struct pt *p)
{
    static int next = 1, reading;
    PT_BEGIN(p);
    for (;;) {
        PT_WAIT_UNTIL(p, now >= next);
        reading = 20 + now % 7;
        printf("%2d  sensor reads %d and waits for the radio\n", now, reading);
        PT_WAIT_UNTIL(p, radio_on);
        printf("%2d  sensor sends %d\n", now, reading);
        next += 5;
    }
    PT_END(p);
}

int main(void)
{
    struct pt r = {0}, s = {0};
    printf("a protothread's state: %zu bytes\n", sizeof r);
    for (now = 0; now < 18; now++) {    /* one call of each per tick */
        radio(&r);
        sensor(&s);
    }
    return 0;
}

a protothread's state: 2 bytes
 0  radio on
 1  sensor reads 21 and waits for the radio
 1  sensor sends 21
 2  radio off
 6  sensor reads 26 and waits for the radio
 8  radio on
 8  sensor sends 26
10  radio off
11  sensor reads 24 and waits for the radio
16  radio on
16  sensor sends 24
16  sensor reads 22 and waits for the radio
16  sensor sends 22

Reading the run. The sensor's code reads like a thread: read, wait for the radio, send, repeat. At tick 1 the radio happens to be on, so the reading goes at once. At tick 6 it is off, so the sensor protothread returns at its wait on every call until tick 8, when the radio comes on and the same call carries straight on to the send. At tick 16 two readings go together: the one taken at 11, which waited 5 ticks, and the one due at 16. Neither function has a stack of its own; between calls each protothread is 2 bytes, the line to carry on from. The reading itself is made up (20 plus the tick modulo 7), to keep the example short.

The limits, stated by the paper. "Automatic variables are not saved across a blocking wait", because the stack is rewound; a variable that must survive a wait has to be static, as until, next and reading are above. The switch-based version also "limits the use of the C switch statement together with protothread statements", since the protothread's own switch would be confused by another. And a protothread can block only in its own function, never inside a function it calls.

Protothreads against threads, in numbers. The MANTIS figures later in this chapter give a default thread stack of 128 bytes on a MICA2 mote with 4 KB of RAM. Five threads would reserve 5 × 128 = 640 bytes of stack, which is 640 / 4,096 = 0.15625, about 16 per cent of the RAM; five protothreads need 5 × 2 = 10 bytes, 10 / 4,096 = 0.00244140625, about 0.24 per cent.

RIOT

RIOT is a free and open source operating system for low-end IoT devices, written from scratch for them. Its 2018 overview paper says it runs in memory of the order of 10 kilobytes, "on devices with neither MMU (memory management unit) nor MPU (memory protection unit)", on 8-bit, 16-bit and 32-bit microcontrollers. It calls such devices "very constrained", citing RFC 7228, whose device classes appear in [Sensor Networks in the Internet of Things: 6LoWPAN, RPL and CoAP].

Structure. RIOT is a modular system "built around a minimalistic kernel". Modules are chosen when the system is compiled: core (the kernel), hardware abstraction (cpu, boards, drivers and periph), sys (system libraries such as networking and file systems), pkg (third-party libraries) and the application. The minimal configuration "requires 3.2 kBytes of ROM and 2.8 kBytes of RAM on 32-bit Cortex-M platforms", and one compliant with 6LoWPAN "requires 38.5 kBytes of ROM and 10 kBytes of RAM".

Real threads. "A thread in RIOT is akin to a thread in Linux", each with a priority. The price of a thread is its control block, its stack and its saved registers; on a Cortex-M the thread control block is 36 bytes (12 without messaging), and a thread with simple logic can run "starting from 128 bytes of RAM in total". The kernel provides mutexes, semaphores and messaging, each compiled only if used. Multithreading is optional: a single-threaded application can drop most of the scheduler.

Scheduling. The scheduler is "based on fixed priorities and preemption with O(1) operations, allowing for soft real-time capabilities". The highest-priority ready thread runs, interrupted only by interrupt service routines, and threads of equal priority are not time-sliced. The scheduler is tickless: "It does not depend on CPU time slices and periodic system timer ticks", so the system wakes only when something happens. When no thread is ready, the lowest-priority idle thread runs and puts the processor into the most energy-saving mode possible.

Standards and licence. RIOT follows open network standards, supporting the low-power IP stack (6LoWPAN, IPv6, UDP and CoAP) in its default network stack, GNRC, and it aims to comply with ANSI C (C99). Its code is under the LGPLv2.1, "a non-viral copyleft license", while applications built on it may use other licences.

Why RIOT is not Contiki. Contiki keeps an event kernel and adds threads as a library; RIOT makes preemptive, prioritised threads the kernel's basic abstraction, and relies on keeping each thread small instead of avoiding threads.

MANTIS, Nano-RK and LiteOS

These three appear in the survey by Farooq and Kunz, whose figures are given here as it reports them.

MANTIS (the MultimodAl system for NeTworks of In-situ wireless Sensors) is a multithreaded OS written in C, with a layered architecture: hardware; the kernel and scheduler, the MAC and physical layer (the COMM layer) and the device drivers; the system API; and on top, the network stack, a command server and the user threads. The survey reports a footprint of 500 bytes for the kernel, scheduler and network stack. Scheduling is preemptive and priority-based, with five priority classes (kernel, sleep, high, normal and idle), round robin within a class, and a default time slice of 10 ms. Each thread's stack comes from the heap, 128 bytes by default, and each context switch costs about 60 microseconds, which against a 10 ms slice is 0.06 / 10 = 0.006, under 1 per cent. Threads synchronise with mutexes and semaphores, a Unix-like shell runs on the node, and applications can be tested on a PC before being moved to the mote. The Contiki paper names the cost: "every Mantis program must have stack space allocated from the system heap, and locking mechanisms must be used to achieve mutual exclusion of shared variables".

Nano-RK is a real-time OS: "a fixed, preemptive multitasking real-time OS for WSNs", in the survey's words. It supports reservations of CPU time, network bandwidth and sensors, so that a task cannot use more than its share, and schedules periodic tasks by rate monotonic scheduling (the shorter a task's period, the higher its priority), with the priority ceiling protocol against priority inversion. Memory is managed statically only. Networking uses a socket-like interface and RT-Link, a TDMA link protocol. The survey reports that it "uses 2 Kb of RAM and 18 Kb of ROM".

LiteOS, from the University of Illinois at Urbana-Champaign, is Unix-like: a thread-based programming model (with callbacks for events), a hierarchical file system (LiteFS), a shell (LiteShell) that runs on a base station or PC and sends commands to the nodes over the radio, and object-oriented programming in LiteC++. The survey's table credits it with dynamic memory management and memory protection for processes.

Other approaches: virtual machines and scripts

The Contiki paper's related work names systems that load code a different way:

• Maté is "a virtual machine for TinyOS devices"; code for it can be downloaded at run time. Virtual-machine code is smaller, so it costs less energy to send, but running it costs more, and "for long running programs the energy saved during the transport of the binary code is instead spent in the overhead of executing the code".
• MagnetOS "uses a virtual Java machine to distribute applications across the sensor network".
• SensorWare "provides an abstract scripting language for programming sensors", for platforms less constrained than Contiki's, and EmStar is likewise meant for larger systems.
• SOS is, with TinyOS and Contiki, one of the systems the protothreads paper lists as "based on an event-driven model".

Worked comparison: six systems, one table

Sources, row by row: the survey's Tables 1 and 2 for TinyOS, Contiki, MANTIS, Nano-RK and LiteOS, and the RIOT paper for RIOT. RIOT native, in its paper's words, compiles and runs RIOT applications "as user processes in a host OS", so that "up to hundreds of RIOT instances can run in parallel"; the paper also names Cooja among the emulators RIOT can be tested with. For Nano-RK the survey lists no simulator.

How to use the table in an answer. Pick the rows the question is about. A question asking to compare TinyOS and Contiki is answered from the architecture, programming model, memory and networking rows; one asking which OS suits a real-time application is answered from the real-time row, which points to Nano-RK, and to RIOT for soft real time.

Distinctions

What it does not mean

Contiki is not multithreaded at its core. Its kernel is event-driven; threads are a library that only the programs needing them link in.

Protothreads are not threads. They cannot be preempted, have no stack, and lose their local variables at a wait. They are a way of writing an event-driven state machine in sequential style.

Dynamic loading does not mean the whole system can be replaced cheaply. The core stays fixed; the saving comes from sending one program instead of the whole image.

More features are not free. Every row of the comparison table that adds convenience (threads, dynamic memory, a file system, a shell) adds bytes of RAM or ROM, which is why TinyOS, the smallest, stayed the reference for the most constrained motes.

Quick revision

• Architectures (survey): monolithic, microkernel, virtual machine, layered; TinyOS monolithic, Contiki and LiteOS modular, MANTIS layered.
• Contiki (2004): event-driven kernel, optional preemptive multithreading as a library, dynamic loading of programs and services; core fixed, programs loaded later; asynchronous and synchronous events, polling; one shared stack; interrupts never post events; services with version number and function table; uIP, Rime, ContikiRPL; Cooja.
• Contiki sizes: 3,874 bytes (AVR), 3,876 bytes (MSP430) with an example service; reprogramming a 40-node network by wire at least 30 minutes, one component over the air about 2 minutes.
• Protothreads: sequential code with PT_WAIT_UNTIL, stackless, 2 bytes each, lines of code cut by one third; built on a switch and __LINE__; automatic variables not kept across a wait.
• RIOT: minimal kernel, modules, threads with fixed priorities, preemption, O(1), tickless, idle thread; minimal 3.2 kB ROM, 2.8 kB RAM (Cortex-M), with 6LoWPAN 38.5 kB ROM, 10 kB RAM; 6LoWPAN, IPv6, UDP, CoAP; LGPLv2.1.
• MANTIS: multithreaded, layered, five priority classes, round robin, 10 ms slice, 128-byte stacks. Nano-RK: real-time, reservations, rate monotonic. LiteOS: Unix-like, LiteFS, LiteShell, LiteC++.
• Virtual machines: Maté, MagnetOS; scripts: SensorWare.

Test yourself

1. Describe the architecture of the Contiki operating system. A Contiki system consists of the kernel, libraries, a program loader and processes, which are applications or services. The kernel is a lightweight event scheduler that dispatches asynchronous and synchronous events to processes and calls their poll handlers, all on one shared stack. The system is split into a core, fixed before deployment, and programs loaded at run time over the network or from EEPROM. Services, such as communication stacks, are called through a version-checked interface and can be replaced at run time. Preemptive multithreading is an optional library, and communication is provided by uIP and Rime.

2. Compare TinyOS and Contiki. Both have event-driven kernels whose handlers run to completion on one stack. TinyOS is written in nesC and linked statically into one image, with a FIFO task scheduler and active-message networking; Contiki is written in C, loads and replaces individual programs and services at run time, adds polling and an optional thread library, supports protothreads, and provides TCP/IP through uIP. TinyOS is smaller; Contiki is more flexible. TinyOS is simulated with TOSSIM, Contiki with Cooja.

3. What are protothreads? Give their advantages and limitations. Protothreads let event-driven code be written in a sequential, thread-like style with a blocking wait, PT_WAIT_UNTIL, while using no stack of their own. Each costs two bytes and adds only a few processor cycles; in the authors' programs most state machines disappeared and code shrank by a third. Their limits: local (automatic) variables are not kept across a wait, a switch statement cannot be mixed with them in the switch-based version, and they can block only in their own function.

4. What features make RIOT suitable for low-end IoT devices? A small modular system built around a minimal kernel, needing 3.2 kB of ROM and 2.8 kB of RAM in its minimal configuration; real multithreading with small thread control blocks; a fixed-priority, preemptive scheduler with O(1) operations for soft real time; a tickless design with an idle thread that puts the processor into its deepest sleep; and support for the standard IoT protocols 6LoWPAN, IPv6, UDP and CoAP.

5. Name three other sensor operating systems and one distinguishing feature of each. MANTIS: a multithreaded, layered OS with preemptive priority scheduling in five classes. Nano-RK: a real-time OS with reservations of CPU, network and sensors and rate monotonic scheduling. LiteOS: a Unix-like OS with a hierarchical file system, a shell on the base station and LiteC++.

6. Five threads with 128-byte stacks, or five protothreads: how much RAM does each need on a 4 KB mote? The threads need 5 × 128 = 640 bytes of stack, about 16 per cent of 4,096 bytes; the protothreads need 5 × 2 = 10 bytes, about 0.24 per cent.