23а. A device without an OS: state machines, an event queue, non-blocking drivers

Section 23 ended with the rule "a superloop as long as it is readable" — and an honest list of its limits. Before reaching for a kernel, it is worth seeing how far those limits can be pushed back without one. The technique has been known for decades: events are put into a queue, the logic is written as state machines, waiting turns into a software timer, and between events the CPU sleeps. The result is the same architecture as an operating system — but made of three pages of your own code whose workings you can see straight through.

Everything in this section was built with two compilers and run in QEMU; the queue was additionally tested on a PC with two threads under ThreadSanitizer (the same way as in section 139).

Terms used in the documentation

Term	Meaning
finite state machine (FSM)	a program described as states and transitions
state / event / transition	where the machine is, what happened, where it goes
transition table	the "state × event" table of next states
action	the work attached to a transition
event queue	the buffer that carries events to the main loop
ring buffer / circular buffer	a buffer whose indices wrap around
single producer, single consumer	one writer and one reader
lock-free	without locks or disabling interrupts
non-blocking	the call returns immediately
busy-wait / polling	waiting by checking in a loop
event loop / dispatcher	the loop that hands events to their handlers
software timer	a timer kept in software on top of one tick
run to completion	a machine step always runs to its end
data race	unsynchronized access to shared data

23а.1 A state machine: the transition table first, then the code

The example for the whole section is a button. The requirements sound harmless: suppress bounce, tell a short press from a long one, report a long press as soon as the time runs out without waiting for release. Written with if and flags, this turns into a mess by the third requirement — because the flags list not states but scraps of history.

A state machine brings order in one move: first you write out all the states and all the events, then the table "state × event → new state and action". The code is written last, mechanically, from the table.

The button has four states and three events. The events here are not levels on the pin but edges (pressed, released) and the timer firing: in an event-driven program time is just as much an event as everything else.

A dash means "stay where you are and do nothing" — and that is a useful part of the table: it says explicitly that a repeated "press" in the DOWN state means nothing. In flag-based code such cases are usually simply not considered.

Note: in no state does the machine wait. "Wait 20 ms" is not a loop with a delay but a timer armed on entry; its firing will arrive as an event. The action belongs to the transition, not to the state: the "short press" is announced on the arrow DOWN → UP, and only on it.

In C the header of the machine is three enumerations and two constants:

enum state { ST_UP, ST_DEBOUNCE, ST_DOWN, ST_LONG, N_STATES };
enum event { EV_PRESS, EV_RELEASE, EV_TIMEOUT, N_EVENTS };
enum out   { OUT_SHORT = 1, OUT_LONG };

#define T_DEBOUNCE 20u                  /* мс: дребезг закончился */
#define T_LONG    780u                  /* мс: дальше — длинное нажатие */

From here the table can be written in code in three ways — and they differ noticeably in size, speed and ease of maintenance.

23а.2 Three ways to write it in C: switch, table, function pointer

The first way — a nested switch. The most familiar one: the outer switch is on the state, the inner one on the event.

static uint8_t st = ST_UP;

void fsm_step(uint8_t ev)
{
    switch (st) {
    case ST_UP:
        if (ev == EV_PRESS)   { timer_start(T_DEBOUNCE); st = ST_DEBOUNCE; }
        break;
    case ST_DEBOUNCE:
        if (ev == EV_RELEASE) { timer_stop(); st = ST_UP; }   /* дребезг */
        if (ev == EV_TIMEOUT) { timer_start(T_LONG); st = ST_DOWN; }
        break;
    case ST_DOWN:
        if (ev == EV_RELEASE) { timer_stop(); report(OUT_SHORT); st = ST_UP; }
        if (ev == EV_TIMEOUT) { report(OUT_LONG); st = ST_LONG; }
        break;
    case ST_LONG:
        if (ev == EV_RELEASE) { st = ST_UP; }
        break;
    }
}

The second way — a transition table in read-only memory. There is one dispatcher for any machine; only the data grows. Each cell is a new state plus an action:

static void a_none(void)   { }
static void a_debounce(void) { timer_start(T_DEBOUNCE); }
static void a_cancel(void) { timer_stop(); }                  /* дребезг */
static void a_hold(void)   { timer_start(T_LONG); }
static void a_short(void)  { timer_stop(); report(OUT_SHORT); }
static void a_long(void)   { report(OUT_LONG); }

struct cell {
    uint8_t next;                       /* новое состояние */
    void (*action)(void);               /* что сделать на переходе */
};

static const struct cell tab[N_STATES][N_EVENTS] = {
    [ST_UP] = {
        [EV_PRESS]   = { ST_DEBOUNCE, a_debounce },
        [EV_RELEASE] = { ST_UP,       a_none },
        [EV_TIMEOUT] = { ST_UP,       a_none },
    },
    [ST_DEBOUNCE] = {
        [EV_PRESS]   = { ST_DEBOUNCE, a_none },
        [EV_RELEASE] = { ST_UP,       a_cancel },
        [EV_TIMEOUT] = { ST_DOWN,     a_hold },
    },
    [ST_DOWN] = {
        [EV_PRESS]   = { ST_DOWN,     a_none },
        [EV_RELEASE] = { ST_UP,       a_short },
        [EV_TIMEOUT] = { ST_LONG,     a_long },
    },
    [ST_LONG] = {
        [EV_PRESS]   = { ST_LONG,     a_none },
        [EV_RELEASE] = { ST_UP,       a_none },
        [EV_TIMEOUT] = { ST_LONG,     a_none },
    },
};

void fsm_step(uint8_t ev)
{
    const struct cell *c = &tab[st][ev];
    c->action();                        /* действие принадлежит переходу */
    st = c->next;
}

This is a literal transfer of the table from 23а.1 — down to the fact that you can check that all cells are filled by eye, and the dashes have become a_none.

The third way — the state as a function pointer. There is no dispatcher at all: the current state is a function address, a transition is an assignment.

typedef void (*state_fn)(uint8_t ev);

static state_fn st = s_up;

static void s_down(uint8_t ev)
{
    if (ev == EV_RELEASE) { timer_stop(); report(OUT_SHORT); st = s_up; }
    if (ev == EV_TIMEOUT) { report(OUT_LONG); st = s_long; }
}

void fsm_step(uint8_t ev)
{
    st(ev);
}

All three were built for Cortex-M3 with size optimization by two compilers; the sizes are taken from the linkers' map files. The speed was measured in QEMU by counting instructions step by step on the same scenario of nine events (bounce, a short press, a long one):

The conclusions from the table weigh more than the table itself.

On size. With switch and with the pointer the code grows with every transition; with the table the code is finished (82 bytes — for good), and the data grows: 8 bytes per cell. Eight, not five: a state byte, three bytes of padding, four bytes of pointer — for this arithmetic see Pitfalls.

On speed. The function pointer is the fastest — the branch on the state is gone. The table is more interesting: seven events out of nine are handled in exactly 17 instructions — the path through the dispatcher is the same whichever cell comes up. For a program where predictable response time matters, this argument is no weaker than the average.

On maintenance. In a switch all the logic reads from top to bottom — for three or four states it is the best. The table forces you to list all the cells and so does not let you forget a case; with dozens of states it has no rival. The pointer is good where the states differ a lot in behaviour, but remember: to the debugger's question "which state am I in" it answers with a function address.

⚠️ QEMU counts instructions, not cycles. On a real F103 flash wait states are added (section 6), so "17 instructions" is an order-of-magnitude estimate: a few microseconds at 72 MHz. For comparing the variants with each other the instruction count is fair: the scenario is the same.

23а.3 A ring queue: from the interrupt to the loop without disabling interrupts

The state machine needs events, and they are born in interrupts: an edge on a pin, a timer tick, a byte over I²C. A handler must be short (section 7), so events are not processed inside it but stored — and taken apart later, in the main loop. Between the interrupt and the loop you need a queue.

The classic solution is a ring buffer with two indices that has one writer and one reader: only the interrupt writes, only the loop reads. With this split the queue is correct with no disabling of interrupts at all — each index is changed by exactly one side:

#define Q_SIZE 32u                      /* степень двойки: маска вместо деления */
#define Q_MASK (Q_SIZE - 1u)

struct ev {
    uint8_t  code;                      /* какое событие */
    uint8_t  arg;                       /* от кого */
    uint16_t stamp;                     /* когда, мс */
};

static volatile struct ev q_buf[Q_SIZE];
static volatile uint32_t q_head;        /* пишет ТОЛЬКО прерывание */
static volatile uint32_t q_tail;        /* пишет ТОЛЬКО главный цикл */
static volatile uint32_t q_dropped;     /* сколько событий потеряно на переполнении */

/* Из прерывания. Один слот всегда пуст: head == tail означает «пусто»,
 * поэтому догнать хвост головой нельзя. */
static int q_push(uint8_t code, uint8_t arg, uint16_t stamp)
{
    uint32_t h = q_head;
    uint32_t next = (h + 1u) & Q_MASK;
    if (next == q_tail) {               /* полна: потерю считаем, а не молчим */
        q_dropped++;
        return 0;
    }
    q_buf[h].code = code;
    q_buf[h].arg = arg;
    q_buf[h].stamp = stamp;
    q_head = next;                      /* индекс — последним: слот уже заполнен */
    return 1;
}

/* Из главного цикла. */
static int q_pop(struct ev *e)
{
    uint32_t t = q_tail;
    if (t == q_head)                    /* пусто */
        return 0;
    e->code = q_buf[t].code;
    e->arg = q_buf[t].arg;
    e->stamp = q_buf[t].stamp;
    q_tail = (t + 1u) & Q_MASK;         /* освободить слот — тоже последним */
    return 1;
}

Correctness rests on three pillars, and each one is mandatory:

1. The order of writes. The slot is filled before q_head is advanced; the slot is read out before q_tail is advanced. Until the index has moved, the other side does not see the slot.
2. volatile on everything, including the buffer. It forbids the compiler both to cache the indices in registers and to reorder the slot write with the index write: accesses to volatile objects are performed in program text order (section 124). An index without volatile — see Pitfalls: the loop freezes forever.
3. Atomicity of the index. An aligned write of a 32-bit word on Cortex-M is one instruction; you cannot read "half an index".

Full and empty differ by one free slot: head == tail means empty, so a queue of 32 slots has 31 usable places. And a mandatory detail of a grown-up device: overflow is counted. Silent loss of events is the worst of the non-reproducible bugs; the q_dropped counter costs one instruction, and during debugging it is the first to answer the main question: are we losing events or not.

A run in QEMU (Cortex-M3, the producer is the SysTick interrupt, the consumer is the main loop). For two thousand ticks the interrupt puts one event each, every tenth tick two in a row; then the reader deliberately stops for a hundred ticks while the interrupt keeps putting:

A pushed=2200 popped=2200 maxfill=2 order_err=0
B fit=31 dropped=69 maxfill=31
C first=2200 last=2230 order_err=0
TOTAL pushed=2300 popped=2231 dropped=69

While the reader was alive, 2200 events arrived strictly in order, and even on the double ticks the queue never filled deeper than two. When the reader stopped, exactly 31 events fit into the queue, the other 69 were honestly counted in q_dropped, and the surviving numbers 2200…2230 arrived in sequence — the arithmetic adds up to the last one: 2231 + 69 = 2300.

A run on a PC. On two real threads the role of volatile is played by C11 atomics (section 140): the index write uses release ordering, reading the other side's index uses acquire:

static uint32_t buf[Q_SIZE];
static _Atomic uint32_t head, tail;

static int push(uint32_t v)
{
    uint32_t h = atomic_load_explicit(&head, memory_order_relaxed);
    uint32_t next = (h + 1u) & Q_MASK;
    if (next == atomic_load_explicit(&tail, memory_order_acquire))
        return 0;                       /* полна */
    buf[h] = v;
    atomic_store_explicit(&head, next, memory_order_release);
    return 1;
}

Two million numbers passed through 32 slots without a single violation of order, and ThreadSanitizer stayed silent: items=2000000 order_err=0. And in the version with ordinary, non-atomic indices it showed exactly what it had to: WARNING: ThreadSanitizer: data race with the addresses of all three reads in pop.

⚠️ "One writer" means one interrupt, not "all interrupts". If two handlers with different priorities write to the queue, one can preempt the other in the middle of q_push — and two events will land in one slot. Either all sources go through one interrupt (in the examples of this section it is the tick that polls the button and the timers), or q_push runs with interrupts disabled, or each writer has its own queue.

23а.4 Software timers on one tick

The state machine from 23а.1 needs "20 ms" and "780 ms", the sensor from 23а.5 — "30 ms", the display — "once a second". A hardware timer for every wait is wasteful; one SysTick tick (section 12) and an array of deadlines are enough:

struct sw_timer {
    uint32_t deadline;                  /* срок в миллисекундах g_ms */
    uint8_t armed;
    uint8_t code;                       /* какое событие положить в очередь */
};

static volatile struct sw_timer timers[N_TIMERS];

void timer_arm(uint8_t i, uint32_t ms, uint8_t code)
{
    timers[i].armed = 0;                /* пока поля меняются, таймер выключен */
    timers[i].deadline = g_ms + ms;
    timers[i].code = code;
    timers[i].armed = 1;                /* включить — последней записью */
}

static void timers_poll(void)           /* из прерывания тика */
{
    for (unsigned i = 0; i < N_TIMERS; i++) {
        if (timers[i].armed && (int32_t)(g_ms - timers[i].deadline) >= 0) {
            timers[i].armed = 0;        /* одноразовый: перевзведёт автомат */
            q_push(timers[i].code, (uint8_t)i, (uint16_t)g_ms);
        }
    }
}

These twenty lines contain three decisions, and each deserves to be named.

A deadline, not a remainder. The moment of firing is stored, and the comparison is by a signed difference: (int32_t)(g_ms - deadline) >= 0 survives the overflow of the millisecond counter (the same arithmetic as in 23.7, the trap is from section 3).

The order of writes when arming. timer_arm is called from the main loop (it is a machine action), and timers_poll from the interrupt. While deadline and code are being changed, the timer is off; the armed flag is set by the last write, and the interrupt will never see a timer with the new flag and the old deadline.

The timer does not call, it reports. Firing is a q_push of the EV_TIMEOUT event from the tick interrupt. The queue still has one writer, and the state machine receives time the same way as everything else.

The whole construction — in the diagram:

The main loop degenerates into a dispatcher:

    for (;;) {
        while (q_pop(&e))
            fsm_step(e.code);
        if (g_ms > 1400u)
            break;
        idle();
    }

(the stop condition is for the test bench: on a device the loop is endless). A run of the whole framework in QEMU — the interrupt "presses" the button following the scenario from 23а.2 — gives exactly what is expected and not one event more:

OUT short t=100
OUT long t=1000
loops=1401 ms=1401 maxfill=1 dropped=0 outs=2

(from run to run you may also get loops=1402: the first pass of the loop sometimes manages to run before the first tick — this is not an extra wake-up.)

The short press is announced in the millisecond of release, the long one exactly 20 + 780 ms after the press, and the bounce produced nothing. Throughout the run the queue never filled deeper than one event.

23а.5 🔧 A non-blocking driver: an I²C sensor instead of waiting 30 ms

A classic scene: on request, a sensor starts a conversion and only after 30 ms is ready to hand over the result. A "head-on" driver repeats the documentation word for word:

    i2c_write(SENS_ADDR, &cmd, 1);      /* команда «начать» */
    delay_ms(30);                       /* прибор мёртв 30 мс */
    i2c_read(SENS_ADDR, raw, 2);        /* забрать результат */

Thirty milliseconds is the first superloop limit from 23.1 in its pure form: buttons are not polled, the display stands still, a second such sensor brings the dead time up to 60 ms. In the event framework the same thing is a three-state machine, where waiting has become an armed timer, and the end of the bus transfer an event from the I²C interrupt (section 17):

enum s_state { S_IDLE, S_MEASURING, S_READING };

void sensor_step(uint8_t ev)
{
    switch (s_st) {
    case S_IDLE:
        if (ev == SEV_POLL) {           /* пора мерить */
            i2c_start_write(SENS_ADDR, &cmd_measure, 1);
            timer_arm(TIMER_SENSOR, 30, SEV_TIMEOUT);
            s_st = S_MEASURING;
        }
        break;
    case S_MEASURING:
        if (ev == SEV_TIMEOUT) {        /* 30 мс прошли — забрать результат */
            i2c_start_read(SENS_ADDR, raw, 2);
            s_st = S_READING;
        }
        break;
    case S_READING:
        if (ev == SEV_I2C_DONE) {       /* прочитано: обработать и спать */
            sensor_value = (uint16_t)(((uint16_t)raw[0] << 8) | raw[1]);
            s_st = S_IDLE;
        }
        break;
    }
}

The recipe for converting any blocking driver is always the same:

1. Every delay_ms(N) → a state plus timer_arm(N).
2. Every flag poll in a loop → a state plus an event from an interrupt.
3. Every call that "does everything at once" → ..._start(), which only starts the operation and returns.

The CPU is free between the steps: while the sensor converts, the button machine handles presses, and with an empty queue the device sleeps. There is nowhere left to wait — and this is a property of the architecture, not of how carefully a particular driver was written.

23а.6 Sleeping between events: WFI without a lost wake-up

If events are born only in interrupts, between events the CPU has nothing to do — and the loop can sleep. The naive if (empty) __WFI(); contains the "lost wake-up" race analysed in 84.6: an event that arrives between the check and the sleep has nobody left to wake. The cure is the same as there — check and fall asleep with interrupts disabled:

static void idle(void)
{
    __asm volatile("cpsid i");
    if (q_tail == q_head)               /* очередь пуста — можно спать */
        __asm volatile("wfi");          /* ожидающее прерывание всё равно разбудит */
    __asm volatile("cpsie i");
}

WFI wakes up on a pending interrupt even with PRIMASK = 1; the handler runs after cpsie i, puts the event — and the next pass of the loop picks it up. The compiler builds this without a single extra instruction — the emptiness check is squeezed between cpsid and wfi:

 8000352:   cpsid   i
 8000354:   ldr r2, [r5, #0]
 8000356:   ldr r3, [r7, #0]
 8000358:   cmp r2, r3
 800035a:   bne.n   800035e <main+0xce>
 800035c:   wfi
 800035e:   cpsie   i

The "queue + WFI" pair at work can be seen in the run from 23а.4: loops=1401 with ms=1401 — the main loop woke up exactly once per tick, with not a single idle pass and not a single lost event in 1401 ms. Without idle() the same loop would spin millions of times, burning current polling an empty queue; how much current sleep saves and which modes go deeper — section 10.

23а.7 When an OS after all: an honest comparison with 23.6

The bench from 23а.4 — the queue, four timers, the button machine as a table and sleep — built into 1216 bytes of code including the bench printout; the framework keeps 176 bytes in RAM (128 for the queue, 32 for the timers, 12 for the indices and the loss counter, 4 for the time). The device from 23.4 on FreeRTOS took 6836 bytes of code and ≈ 2.4 KB of RAM plus the heap. The difference is an order of magnitude: on the F103C8, where the kernel and heap from 23.4 took more than half of the 20 KB, the framework leaves memory practically untouched.

At the same time the event framework really does remove the main superloop limits from 23.1: there are no more long waits (23а.5), the response does not depend on the slowest branch, there are no time counters in the loop — time has become events. What it does not remove:

The row about long computation is the key one. A machine step runs to completion: if recalculating a filter takes 40 ms, all events wait those 40 ms, and no queue will help — there is nobody to preempt it. The "code of a job" row is the price in readability: a job that in an RTOS task would be ten lines in a row, a state machine cuts into states, and coherence is lost (that very fourth limit from 23.1 has not gone anywhere — it has only been pushed back).

So the rule of section 23.6 is refined as follows: an event framework — as long as every step is short and there are fewer than a dozen jobs. Once long computations appear that cannot be cut up, or real priorities are needed, or the state machines start exchanging events so densely that the tables are no longer readable — it is time for section 24. All the more so because you will not have to relearn: the queue with waiting is called xQueueReceive there (section 27 — the button from this section is repeated there in 27.7, now on the kernel), and the timers are the kernel's timer service. The mechanics are already familiar; only the names change.

23а.8 Pitfalls

A queue index without volatile — and the loop freezes forever. The compiler hoists the read of a variable that (in its opinion) never changes out of the loop: on the bench the version without atomics, built with −O1, hung — the reader always saw an empty queue (killed by timeout). The same program with −O0 worked, but ThreadSanitizer showed the race. "Works in the debug build, hangs in the release build" — this is it (section 124).

A transition table half made of thin air. A {uint8_t, pointer} cell takes 8 bytes: three bytes are padding (section 126). The 96 bytes of the button table are tolerable; on a large machine replace the pointer with an action number from an enum — the cell shrinks to 2 bytes.

Two interrupts write to one queue. The higher-priority one preempts q_push in the middle of its work — two events in one slot. One writer, or disabling interrupts around q_push (23а.3).

The slot is written after the index. Remove volatile from the buffer — and the compiler is entitled to move the slot fill past the write to q_head; the reader gets garbage. Order is guaranteed only between volatile accesses (section 124).

The timer is armed in two steps — and fires with the old deadline. If armed is not cleared while the fields are being edited, the interrupt may catch the new flag with the old deadline. The flag goes last (23а.4).

"Wait 30 ms" inside a machine action. The action runs in the dispatcher: delay_ms in it stops the whole device — a wait is expressed as a state and a timer (23а.5).

The emptiness check is before cpsid. A lost wake-up: the event arrived between the check and WFI, and the device sleeps until the next interrupt (84.6, bench 23а.6).

23а.9 Summary

• A state machine starts with the "state × event" table, not with code; the dashes in it are decisions too. Time is an event just like an edge on a pin: "we wait" means "a timer is armed".
• The three ways to write the machine in C were measured: switch — 100 bytes of code, the table — 82 bytes of code and 96 bytes of data, the function pointer — 160 bytes (gcc −Os, Cortex-M3). In speed on nine events: 166, 156 and 141 instructions; with the table the time is almost constant — seven events out of nine take 17 instructions each.
• A "one writer, one reader" ring queue is correct without disabling interrupts thanks to three pillars: the index is the last write, volatile on the indices and the buffer, atomicity of an aligned word. In QEMU 2300 events passed without any violation of order; the overflow was counted to the last one (31 fit, 69 went to q_dropped).
• On real threads the role of volatile is played by C11 atomics (release/acquire): two million events — and ThreadSanitizer is silent; without atomics it shows a race, and −O1 turns it into a permanent hang.
• Software timers: one tick, an array of deadlines, comparison by a signed difference, armed as the last write, firing as an event into the same queue.
• A non-blocking driver comes out mechanically: delay_ms → a state plus a timer, a flag poll → an event from an interrupt, "do everything" → "start and return".
• Sleeping between events is the check and WFI under cpsid (84.6): in the run the loop woke up exactly once per tick, 1401 passes in 1401 ms, zero lost events.
• The whole framework is 1216 bytes of code and 176 bytes of RAM versus 6836 bytes and ≈ 2.4 KB for the same device on the kernel. But the framework will not preempt a long computation and will not bring back linear code: when it gets cramped — section 24.

Next: section 24 "How FreeRTOS is organized" — which files the kernel consists of, how its types and functions are named and what it takes for it to start on a board.