Event-driven or Multithreaded: The Two Execution Models

The event-driven model

In an event-driven system, the program is a set of handlers: pieces of code that run when something happens (a timer fires, a packet arrives, a conversion finishes) and then return. The Contiki paper states the three consequences: "processes are implemented as event handlers that run to completion"; "because an event handler cannot block, all processes can use the same stack, effectively sharing the scarce memory resources between all processes"; and "locking mechanisms are generally not needed because two event handlers never run concurrently with respect to each other".

Split-phase work. A handler cannot wait for the ADC. Instead it starts the conversion and returns; when the conversion finishes, a completion event calls another handler with the result. The same loop as above becomes:

on timer fired:      start the ADC; return
on ADC done(value):  start sending value; return
on send done:        return                       # nothing left: the node sleeps

This is the split-phase style of [Commands, Events and Split-phase Operation].

Deferred work: tasks. A handler must be short, because nothing else runs while it runs. Work that takes longer is posted as a task, a function to be run later by the scheduler. TinyOS's scheduler runs tasks one at a time in the order they were posted, and a task is never interrupted by another task: it runs to completion. That is the non-preemptive scheduler the practical asks about.

The problems, also in the Contiki authors' words. "The state driven programming model can be hard to manage for programmers", and "not all programs are easily expressed as state machines". Their example is "the lengthy computation required for cryptographic operations", which can take several seconds on a small processor, and in a purely event-driven system "a lengthy computation completely monopolizes" the processor.

Worked example: a long task and a timer, run

A node's timer needs a 1 ms handler every 10 ms (for example to sample a sensor on schedule). At time 2 ms, a 35 ms computation is posted (a compression, or a cryptographic operation). In a run-to-completion scheduler the timer's handler is itself a task, so it must wait for whatever task is running. The program simulates the scheduler twice: with the computation as one task, and with it split into seven tasks of 5 ms, each posting the next when it finishes.

# A run-to-completion task scheduler, the model of TinyOS's tasks.
# Tasks run one at a time, in the order they were posted, and none is ever
# interrupted by another. A timer posts a 1 ms handler task every 10 ms; at
# time 2 ms a 35 ms computation is posted, either whole or in 5 ms pieces.
from collections import deque

def simulate(pieces):
    queue = deque()
    ticks = [10, 20, 30, 40, 50]
    pending = list(ticks)                      # timer ticks not yet posted
    queue.append(("compute", pieces[0], 1))    # posted at time 2
    now, latency = 2, {}
    while queue or pending:
        while pending and pending[0] <= now:   # the timer posts its handler
            t = pending.pop(0)
            queue.append(("tick", 1, t))
        if not queue:                          # nothing to do: sleep until the next tick
            now = pending[0]
            continue
        kind, length, info = queue.popleft()
        if kind == "tick":
            latency[info] = now - info
        now += length                          # run to completion
        if kind == "compute" and info < len(pieces):
            while pending and pending[0] <= now:
                t = pending.pop(0)
                queue.append(("tick", 1, t))
            queue.append(("compute", pieces[info], info + 1))   # repost next piece
    return latency, now

for label, pieces in (("one 35 ms task", [35]), ("seven 5 ms tasks", [5] * 7)):
    latency, end = simulate(pieces)
    shown = ", ".join("%d ms" % latency[t] for t in sorted(latency))
    print("%-17s delays of the timer handler: %s (worst %d ms)"
          % (label + ":", shown, max(latency.values())))

one 35 ms task:   delays of the timer handler: 27 ms, 18 ms, 9 ms, 0 ms, 0 ms (worst 27 ms)
seven 5 ms tasks: delays of the timer handler: 2 ms, 3 ms, 4 ms, 0 ms, 0 ms (worst 4 ms)

Read the first line. The single 35 ms task runs from 2 ms to 37 ms. The ticks at 10, 20 and 30 ms all wait behind it and then run in a burst: delays of 27, 18 and 9 ms. A sample meant to be taken every 10 ms is taken three times in 3 ms. This is Contiki's warning, measured: the long computation "completely monopolizes" the processor.

Read the second line. Split into 5 ms pieces, each piece posts the next at the back of the queue, so a tick that arrives during a piece runs as soon as that piece ends. The worst delay is 4 ms, and it can never exceed the length of one piece. In a run-to-completion system, the responsiveness of the whole node is set by its longest task. That is why TinyOS programs break long work into short tasks, and it is the lesson of the practical's scheduler exercise.

The middle ways

Neither model is perfect, and real systems mix them.

• Contiki: an event-driven kernel, with "optional preemptive multithreading that can be applied to individual processes". Threads are a library, linked only into programs that need them, so the rest of the system keeps its single stack.
• Protothreads, also from Contiki: code written in sequential style, with waits, but compiled into an event-driven state machine that needs no stack of its own ([Contiki, RIOT and the Other Sensor Operating Systems]).
• TinyOS's two levels: tasks never preempt each other, but hardware interrupts do preempt tasks; the 2000 paper describes this as "two level scheduling". Urgent, tiny work runs in interrupt handlers; everything else runs as tasks.
• Preemptive multithreading throughout, as in Mantis, which the Contiki paper describes: "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".

Distinctions

What it does not mean

Event-driven does not mean nothing can interrupt. In TinyOS hardware interrupts preempt tasks; what never happens is one task preempting another.

Run to completion does not mean long-running. It means uninterrupted, which is exactly why each task must be short.

Threads are not wrong for sensor nodes. They cost memory. On a node with more RAM, or for one long computation, a thread can be the better tool, which is why Contiki offers them optionally.

Quick revision

• Event-driven: handlers and tasks run to completion, one shared stack, no locks, split-phase operations; hard for long computations and state-heavy programs.
• Multithreaded: a stack per thread, over-provisioned; blocking and preemption; locking needed.
• Contiki (2004): threads need stacks that "typically has to be over provisioned"; event handlers "cannot block", so "all processes can use the same stack"; a lengthy computation "completely monopolizes" the processor.
• Worked stacks: 5 × 512 = 2,560 bytes, a quarter of 10 kB of RAM.
• Simulation: one 35 ms task delays the timer handler by 27, 18 and 9 ms; seven 5 ms tasks, at worst 4 ms. Responsiveness is set by the longest task.
• Middle ways: Contiki's optional per-process threads, protothreads, TinyOS's two-level scheduling (interrupts preempt tasks); Mantis is preemptive throughout.

Test yourself

1. Compare the event-driven and multithreaded execution models for sensor nodes. Event-driven: handlers and tasks run to completion without blocking, share one stack and need no locks, which saves memory; but long computations must be split and programs become state machines. Multithreaded: each thread has its own over-provisioned stack and can block and be preempted, which allows sequential code, at the cost of memory and locking.

2. What does "run to completion" mean, and what follows for how tasks are written? A task, once started, runs until it finishes and is never interrupted by another task. So every task must be short, and long work is split into several tasks, each posting the next, or the whole node becomes unresponsive while it runs.

3. In the simulation, why did splitting the computation reduce the timer handler's worst delay from 27 ms to 4 ms? Because in a run-to-completion scheduler a waiting task can only start when the running one ends. With one 35 ms task the timer handler waited for most of it; with 5 ms pieces, each piece reposted the next at the back of the queue, so the handler ran after at most one piece.

4. Why does a multithreaded system need locks, and why does an event-driven one generally not? Threads can be interrupted in the middle of updating shared data, so another thread could see or change it half-updated; locks prevent that. Event handlers never run concurrently with each other, so a handler always sees shared data in a consistent state.

5. How does Contiki combine the two models? Its kernel is event-driven with one stack, and preemptive multithreading is provided as a library linked only into the processes that need it, so only those processes pay for stacks.