Chapter 4: The Preemptive Scheduler#

What this chapter answers: why do other apps keep running while one does heavy work?

On a PC, you can leave a heavy computation running and the other apps keep working. The OS forcibly switches the running program on every timer interrupt. In this chapter you build that same mechanism yourself.

The difference from a PC is that the UNO R4 has only one CPU core. A PC has several, so even if one heavy job uses up a core, the others are free. With one core, if nothing switches, everything really does stop. You can watch it stop in Break it at the end of this chapter.

Sample code#

Directory: docs/os-on-arduino/code/04_scheduler

uv run pio run -d 04_scheduler -t upload
uv run pio device monitor -b 115200

Source code#

The sketch for this chapter. Click a file name to expand. The code is mirrored automatically from the manuscript repository, so what you see here is always current.

src/main.cpp — 135 lines

Open on GitHub

/**
 * Chapter 4: Preemptive Scheduler Demo
 *
 * Tasks are automatically switched by SysTick timer interrupt.
 * No need to call os_yield() - the scheduler runs every TIME_SLICE_MS.
 */

#include <Arduino.h>
#include "os_kernel.h"
#include "Arduino_LED_Matrix.h"

// Arduino UNO R4 WiFi は基板上に "L" と印字された LED を持っています。
// 追加部品なしで動かせるよう、これを主 LED として使います。
#define LED1_PIN LED_BUILTIN

// 2個目以降の LED は外付けせず、基板内蔵の 12×8 LED マトリクスで代用します。
// 左半分を LED2、右半分を LED3 として丸ごと点灯・消灯します。
// マトリクス制御の仕組みは第7章で学びます。ここではライブラリに任せます。
static ArduinoLEDMatrix matrix;
static uint8_t matrix_frame[8][12];

static void matrix_led(int led, bool on)
{
    int col_start = (led == 3) ? 6 : 0;
    for (int row = 0; row < 8; row++) {
        for (int col = col_start; col < col_start + 6; col++) {
            matrix_frame[row][col] = on ? 1 : 0;
        }
    }
    matrix.renderBitmap(matrix_frame, 8, 12);
}

// Task 1: Fast LED blink
void task_led1(void)
{
    pinMode(LED1_PIN, OUTPUT);
    while (1) {
        digitalWrite(LED1_PIN, HIGH);
        os_sleep(100);  // Sleep 100ms
        digitalWrite(LED1_PIN, LOW);
        os_sleep(100);
    }
}

// Task 2: Slow blink on LED2 (matrix left half)
void task_led2(void)
{
    while (1) {
        matrix_led(2, true);
        os_sleep(500);  // Sleep 500ms
        matrix_led(2, false);
        os_sleep(500);
    }
}

// Task 3: Serial output with system info
void task_serial(void)
{
    int count = 0;
    while (1) {
        Serial.print("[");
        Serial.print(os_get_tick());
        Serial.print("ms] Count: ");
        Serial.print(count++);
        Serial.print(" | Current task: ");
        Serial.println(os_get_current_task());

        os_sleep(1000);  // Sleep 1 second
    }
}

// Task 4: Heavy computation (demonstrates preemption)
void task_heavy(void)
{
    volatile uint32_t sum = 0;
    while (1) {
        // Heavy computation - will be preempted
        for (volatile int i = 0; i < 1000000; i++) {
            sum += i;
        }
        Serial.print("Heavy task completed iteration, sum=");
        Serial.println(sum);
        sum = 0;

        // 計算完了をマトリクス右半分（LED3 相当）のトグルで示す
        static bool led3_on = false;
        led3_on = !led3_on;
        matrix_led(3, led3_on);
    }
}

void setup()
{
    Serial.begin(115200);
    while (!Serial) { }

    // LEDマトリクスを初期化（LED2 / LED3 の代用）
    matrix.begin();

    Serial.println("=== Preemptive Scheduler Demo ===");
    Serial.println();
    Serial.println("Tasks are automatically switched every 10ms by SysTick.");
    Serial.println("The heavy_task demonstrates that even long-running");
    Serial.println("computations don't block other tasks.");
    Serial.println();

    // Initialize OS
    os_init();

    // Create tasks
    os_create_task(task_led1, "LED1", 512);
    os_create_task(task_led2, "LED2", 512);
    os_create_task(task_serial, "Serial", 1024);
    os_create_task(task_heavy, "Heavy", 512);

    Serial.println("Tasks created:");
    for (int i = 0; i < os_get_task_count(); i++) {
        Serial.print("  ID ");
        Serial.print(i);
        Serial.print(": ");
        Serial.println(os_get_task_name(i));
    }
    Serial.println();
    Serial.println("Starting preemptive scheduler...");
    Serial.flush();
    delay(100);

    // Start OS
    os_start();
}

void loop()
{
    // Never reached
}

src/os_kernel.cpp — 287 lines

Open on GitHub

/**
 * os_kernel.cpp - Mini OS Kernel Implementation
 * Chapter 4: Preemptive Scheduler with SysTick
 */

#include "os_kernel.h"
#include <Arduino.h>
#include <string.h>

// Global variables
TCB g_tasks[MAX_TASKS];
volatile int g_task_count = 0;
volatile int g_current_task = -1;
volatile int g_next_task = -1;
volatile uint32_t g_system_ticks = 0;
static volatile uint32_t g_tick_count = 0;

const uint32_t g_tcb_size = sizeof(TCB);

// Stack areas
static uint32_t g_stack_pool[STACK_POOL_SIZE / 4];
static uint32_t g_stack_used;   // 切り出し済みのワード数

// Idle task
static void idle_task(void)
{
    while (1) {
        __WFI();
    }
}

// Initialize stack for a task
// タスク関数が return したときの受け皿。例外フレームの LR スロットは
// ここを指す (第3章 3.4)。EXC_RETURN を置く場所ではない。
static void task_exit(void)
{
    g_tasks[g_current_task].state = TASK_TERMINATED;
    os_yield();
    while (1) { }  // ここには到達しない
}

static uint32_t* init_task_stack(uint32_t *stack_top, void (*entry)(void))
{
    uint32_t *sp = stack_top;

    // Hardware auto-saved registers
    *(--sp) = 0x01000000;        // xPSR: Thumb bit
    *(--sp) = (uint32_t)entry;   // PC
    *(--sp) = (uint32_t)task_exit;  // LR: タスクが return したときの戻り先
    *(--sp) = 0;                 // R12
    *(--sp) = 0;                 // R3
    *(--sp) = 0;                 // R2
    *(--sp) = 0;                 // R1
    *(--sp) = 0;                 // R0

    // Software saved registers
    *(--sp) = 0;  // R11
    *(--sp) = 0;  // R10
    *(--sp) = 0;  // R9
    *(--sp) = 0;  // R8
    *(--sp) = 0;  // R7
    *(--sp) = 0;  // R6
    *(--sp) = 0;  // R5
    *(--sp) = 0;  // R4

    return sp;
}

void os_init(void)
{
    memset(g_tasks, 0, sizeof(g_tasks));
    g_task_count = 0;
    g_current_task = -1;
    g_next_task = -1;
    g_system_ticks = 0;

    // Create idle task (ID=0)
    os_create_task(idle_task, "idle", IDLE_STACK_SIZE);
}

int os_create_task(void (*entry)(void), const char *name, uint32_t stack_size)
{
    if (g_task_count >= MAX_TASKS) {
        return -1;
    }

    int id = g_task_count;
    TCB *task = &g_tasks[id];

    task->id = id;
    task->state = TASK_READY;
    task->priority = id;
    task->entry = entry;
    task->wake_tick = 0;
    task->cpu_ticks = 0;
    strncpy(task->name, name, sizeof(task->name) - 1);

    if (stack_size == 0) {
        stack_size = DEFAULT_STACK_SIZE;
    }
    uint32_t words = (stack_size + 3) / 4;
    if (g_stack_used + words > STACK_POOL_SIZE / 4) {
        return -1;          // プールが尽きた。黙って縮めず、失敗として返す
    }
    g_stack_used += words;
    task->stack_size = stack_size;
    task->stack_base = &g_stack_pool[g_stack_used];   // スタックは上端から下へ伸びる
    task->sp = init_task_stack(task->stack_base, entry);

    g_task_count++;
    return id;
}

void os_schedule(void)
{
    // Guard: don't schedule before OS is initialized
    if (g_task_count == 0) return;

    // Wake up blocked tasks
    for (int i = 0; i < g_task_count; i++) {
        if (g_tasks[i].state == TASK_BLOCKED) {
            if (g_system_ticks >= g_tasks[i].wake_tick) {
                g_tasks[i].state = TASK_READY;
            }
        }
    }

    // Round-robin scheduling
    int next = g_current_task;
    do {
        next = (next + 1) % g_task_count;
        if (g_tasks[next].state == TASK_READY ||
            g_tasks[next].state == TASK_RUNNING) {
            break;
        }
    } while (next != g_current_task);

    if (next != g_current_task || g_current_task < 0) {
        if (g_current_task >= 0) {
            if (g_tasks[g_current_task].state == TASK_RUNNING) {
                g_tasks[g_current_task].state = TASK_READY;
            }
        }
        g_tasks[next].state = TASK_RUNNING;
        g_next_task = next;

        // Trigger PendSV
        SCB->ICSR |= SCB_ICSR_PENDSVSET_Msk;
    }
}

void os_yield(void)
{
    os_schedule();
}

void os_sleep(uint32_t ms)
{
    if (g_current_task > 0) {  // Don't block idle task
        g_tasks[g_current_task].state = TASK_BLOCKED;
        g_tasks[g_current_task].wake_tick = g_system_ticks + ms;
        os_schedule();
    }
}

uint32_t os_get_tick(void)
{
    return g_system_ticks;
}

int os_get_task_count(void)
{
    return g_task_count;
}

const char* os_get_task_name(int id)
{
    if (id < 0 || id >= g_task_count) return "";
    return g_tasks[id].name;
}

TaskState os_get_task_state(int id)
{
    if (id < 0 || id >= g_task_count) return TASK_TERMINATED;
    return g_tasks[id].state;
}

int os_get_current_task(void)
{
    return g_current_task;
}

void os_start(void)
{
    // Set PendSV to lowest priority
    NVIC_SetPriority(PendSV_IRQn, 0xFF);

    // Configure SysTick for TIME_SLICE_MS interval
    SysTick_Config(SystemCoreClock / 1000 * TIME_SLICE_MS);

    g_current_task = -1;
    g_next_task = 0;

    // Do NOT switch CONTROL to PSP here — PSP is not yet initialized.
    // PendSV returns with EXC_RETURN=0xFFFFFFFD, which automatically
    // switches thread mode to PSP after loading the first task's context.
    SCB->ICSR |= SCB_ICSR_PENDSVSET_Msk;

    while (1) { }
}

// SysTick Handler - called every TIME_SLICE_MS
extern "C" void SysTick_Handler(void)
{
    // 実際に経過した時間を、いま走っていたタスクの取り分として計上する。
    // os_schedule() 側で数えると os_yield() の回数まで混ざってしまう。
    if (g_current_task >= 0) {
        g_tasks[g_current_task].cpu_ticks += TIME_SLICE_MS;
    }
    g_system_ticks += TIME_SLICE_MS;
    os_schedule();
}

// PendSV Handler - Context Switch
extern "C" __attribute__((naked)) void PendSV_Handler(void)
{
    __asm volatile (
        "   MRS     R0, PSP              \n"
        "   LDR     R1, =g_current_task  \n"
        "   LDR     R2, [R1]             \n"
        "   CMP     R2, #0               \n"
        "   BLT     _skip_save           \n"
        // Save R4-R11 only when there is a valid current task
        "   STMDB   R0!, {R4-R11}        \n"
        "   LDR     R3, =g_tasks         \n"
        "   LDR     R4, =g_tcb_size      \n"
        "   LDR     R4, [R4]             \n"
        "   MUL     R2, R2, R4           \n"
        "   ADD     R3, R3, R2           \n"
        "   STR     R0, [R3]             \n"
        "_skip_save:                     \n"
        "   LDR     R1, =g_next_task     \n"
        "   LDR     R2, [R1]             \n"
        "   LDR     R1, =g_current_task  \n"
        "   STR     R2, [R1]             \n"
        "                                \n"
        "   LDR     R3, =g_tasks         \n"
        "   LDR     R4, =g_tcb_size      \n"
        "   LDR     R4, [R4]             \n"
        "   MUL     R2, R2, R4           \n"
        "   ADD     R3, R3, R2           \n"
        "   LDR     R0, [R3]             \n"
        "                                \n"
        "   LDMIA   R0!, {R4-R11}        \n"
        "   MSR     PSP, R0              \n"
        "                                \n"
        "   LDR     LR, =0xFFFFFFFD      \n"
        "   BX      LR                   \n"
    );
}

// CPU使用率を取得（パーセント）
// 直前にこの関数を呼んだ時点からの差分で計算する。
// ps のようにタスクごとにループで呼ぶため、基準時刻もタスクごとに持つ。
int os_get_cpu_usage(int task_id)
{
    if (task_id < 0 || task_id >= g_task_count) {
        return -1;
    }

    static uint32_t last_total[MAX_TASKS] = {0};
    static uint32_t last_task_ticks[MAX_TASKS] = {0};

    uint32_t total = g_system_ticks;
    uint32_t delta_total = total - last_total[task_id];

    if (delta_total == 0) {
        return 0;
    }

    uint32_t delta_task = g_tasks[task_id].cpu_ticks - last_task_ticks[task_id];

    last_total[task_id] = total;
    last_task_ticks[task_id] = g_tasks[task_id].cpu_ticks;

    return (delta_task * 100) / delta_total;
}

On the board#

../_images/ch04_preemption.gif — `Count` keeps appearing exactly once a second while `Heavy` is interrupted in between. It is printed by the `Serial` task (ID 3); `Current task` is that task’s own ID, so it is always 3. Recorded on a real Arduino UNO R4 WiFi.#

The L LED (LED1, every 0.1 s) and the left half of the matrix (LED2, every 0.5 s) keep blinking even while the Heavy task runs its long computation. The right half toggles each time Heavy finishes one round. (Filmed with a webcam at 30 fps.)

In the simulator#

Without the board, the same firmware running in the simulator looks like this.

../_images/sim_ch04_blink.gif — L (LED1) toggles every 100 ms and the left half of the matrix (LED2) every 500 ms; the right half flips each time the busy `Heavy` task finishes a round. While `Heavy` keeps the CPU busy, L and the left half keep their rhythm. (Recorded in the simulator.)#

Break it#

What happens if you change just one place in working code? Predict the result before you change it, then open the answer.

Build the modified code and drop the resulting firmware.elf into the browser version to try it without a board. No flashing needed. To undo the change, run git checkout -- 04_scheduler.

uv run pio run -d 04_scheduler
# drop 04_scheduler/.pio/build/uno_r4_wifi/firmware.elf into the browser version

Note

The outputs in the answers were captured by actually running the modified code in QEMU, the same emulator the browser version uses. They have not been checked on the real board yet; where it stops and the numbers in a dump may differ there.

1. Make the time slice one second#

Change one line in include/os_kernel.h. Tasks now switch every second instead of every 10 ms.

-#define TIME_SLICE_MS 10
+#define TIME_SLICE_MS 1000

Predict: what happens to the L LED blinking and the Count line printed every second?

2. Take task switching out of SysTick#

In SysTick_Handler() in src/os_kernel.cpp, comment out the call to os_schedule(). Time still advances, but the timer interrupt no longer switches tasks.

     g_system_ticks += TIME_SLICE_MS;
-    os_schedule();
+    // os_schedule();

Predict: a task that calls os_sleep() still switches there. Which task keeps running?

3. Stop saving registers R4–R11#

In PendSV_Handler(), replace the instructions that push and pop R4–R11 with ones that only move the stack pointer. The stack layout stays the same; only the contents are no longer saved or restored.

-        "   STMDB   R0!, {R4-R11}        \n"
+        "   SUB     R0, R0, #32          \n"
 ...
-        "   LDMIA   R0!, {R4-R11}        \n"
+        "   ADD     R0, R0, #32          \n"

Predict: the CPU pushes R0–R3, PC and a few others automatically when it enters the exception. What happens if the remaining eight are not saved?

Pitfalls#

(Collected from reader questions — ask via GitHub Issues.)