mcsched

Mixed-criticality scheduler for MCU firmware — EDF-VD and AMC-rtb on FreeRTOS.

The problem

Industrial and automotive MCUs run two kinds of tasks: safety-critical ones that must never miss a deadline (brake control, steering), and best-effort ones that tolerate delays (UI refresh, telemetry). FreeRTOS's priority-based scheduler has no formal way to guarantee that the critical tasks still meet their deadlines when the system is under worst-case load — and "the tests passed" is not the same as "mathematically proven schedulable."

IEC 61508 and ISO 26262 require that proof. mcsched adds it.

Architecture

mcsched sits between your application tasks and the FreeRTOS kernel. The algorithm core has no RTOS dependency; the port layer is the only platform-specific piece.

Quick start

1. Describe your tasks

#include "mcsched.h"
#include "mcsched_port.h"

static const mcsched_params_t BRAKE_PARAMS = {
    .name        = "brake_ctrl",
    .criticality = MCSCHED_HIGH,
    .wcet_lo_us  = 2000,   /* measured WCET in LO-mode (µs) */
    .wcet_hi_us  = 5000,   /* conservative bound in HI-mode (µs) */
    .period_us   = 10000,
    .deadline_us = 10000,
};

static const mcsched_params_t UI_PARAMS = {
    .name        = "ui_refresh",
    .criticality = MCSCHED_LOW,
    .wcet_lo_us  = 4000,
    .period_us   = 50000,
    .deadline_us = 50000,
};

2. Register at startup

TaskHandle_t brake_h, ui_h;
xTaskCreate(brake_task, "brake", 512, NULL, 1, &brake_h);
xTaskCreate(ui_task,    "ui",    512, NULL, 1, &ui_h);

mcsched_set_policy(MCSCHED_POLICY_AMC_RTB);  /* or EDF_VD */
mcsched_freertos_register(brake_h, &BRAKE_PARAMS);
mcsched_freertos_register(ui_h,    &UI_PARAMS);
mcsched_freertos_init();

vTaskStartScheduler();

3. Bracket each periodic job

void brake_task(void *arg) {
    TickType_t last = xTaskGetTickCount();
    for (;;) {
        if (mcsched_job_start(brake_h) == MCSCHED_JOB_RUN) {
            do_brake_control();
            mcsched_job_end(brake_h);
        }
        vTaskDelayUntil(&last, pdMS_TO_TICKS(10));
    }
}

4. Wire the tick hook

void vApplicationTickHook(void) {
    mcsched_freertos_tick_hook();
}

Scheduling policies

mcsched implements two algorithms. Both share the same escalation trigger: any HIGH task that runs longer than its wcet_lo budget causes the system to switch to HI-mode. They differ only in what happens to LOW tasks at that moment.

EDF-VD — Earliest Deadline First with Virtual Deadlines

The default. In LO-mode, HIGH tasks receive tighter virtual deadlines so they are always scheduled before LOW tasks when the processor is under load. On escalation, all LOW tasks are immediately suspended via vTaskSuspend().

Optimal virtual deadline factor:

x = U_hi_lo / (1 − U_lo)

where:
  U_hi_lo = Σ (wcet_lo / period)  for HIGH tasks
  U_lo    = Σ (wcet_lo / period)  for LOW tasks

Schedulability requires:

U_hi_lo + U_lo ≤ 1 — LO-mode feasible
U_hi ≤ 1 — HI-mode feasible (HIGH tasks alone)

AMC-rtb — Adaptive Mixed-Criticality, run-to-blocking

Same escalation trigger, but LOW tasks are never forcibly suspended. Instead, mcsched_job_start() returns MCSCHED_JOB_SKIP for LOW tasks in HI-mode; they skip the next job and go back to sleep. The current job always completes cleanly — no task is cut while holding a mutex or mid-write to flash.

AMC-rtb adds a third schedulability condition: HIGH tasks must still meet their deadlines during the transition window while LOW tasks finish their last job:

For each HIGH task i:
  R_i = C_i^HI + Σ_j(LO) C_j^LO  +  Σ_k(HI, k≠i) ⌈R_i / T_k⌉ × C_k^HI  ≤  D_i

Visualised

Offline schedulability analysis

pip install pyyaml

python3 tools/analyze.py tasks.yaml                    # EDF-VD
python3 tools/analyze.py tasks.yaml --policy amc-rtb   # AMC-rtb (stricter)
python3 tools/analyze.py tasks.yaml --out proof.json   # save certificate

Example output:

──────────────────────────────────────────────────────────────
  mcsched EDF-VD Analysis
──────────────────────────────────────────────────────────────
  Task                 Crit    wcet_lo  wcet_hi   period  virt_dl
  brake_ctrl           HIGH      2000µs    3000µs   10000µs    6179µs
  steering_ctrl        HIGH      3000µs    4000µs   20000µs   12359µs
  sensor_fusion        HIGH      1000µs    1000µs    5000µs    3089µs
  ui_refresh           LOW       4000µs    4000µs   50000µs   50000µs
  telemetry            LOW       3000µs    3000µs  100000µs  100000µs
──────────────────────────────────────────────────────────────
  Utilization (LO-mode):  0.6600  (limit 1.0000)  ✓
  Utilization (HI-mode):  0.7000  (limit 1.0000)  ✓
  x_factor (virt dl):     0.6180
──────────────────────────────────────────────────────────────
  ✓  SCHEDULABLE
──────────────────────────────────────────────────────────────

Task definition format (tasks.yaml):

tasks:
  - name:        brake_ctrl
    criticality: high
    wcet_lo:     2ms
    wcet_hi:     3ms      # HIGH tasks only
    period:      10ms

  - name:        ui_refresh
    criticality: low
    wcet_lo:     4ms
    period:      50ms

Time values accept ms, us, or bare integers (µs).

Tests

The core algorithm and FreeRTOS port are both tested on Linux with no hardware required.

make test_core   # 18 core algorithm tests — no RTOS, no hardware
make test_port   # 13 port integration tests — FreeRTOS mock backend
make test        # run both

All 31 tests pass.

Linux standalone example

A minimal example that runs entirely on Linux with no hardware, no QEMU, and no FreeRTOS. It uses a fake time source to demonstrate the same mcsched flow as the QEMU demo — registration, LO-mode execution, overrun detection, HI-mode LOW-skip behaviour, and mode reset.

cd examples/basic
make run

── Phase 1: LO-mode ──────────────────────
tick  mode=LO  B:run  S:run  U:run
── Phase 2: Overrun → HI-mode ────────────
tick  BRAKE overrunning (elapsed > wcet_lo=2ms)...
tick  mode=HI  (overrun detected!)
── Phase 3: HI-mode ──────────────────────
tick  mode=HI  B:run  S:run  U:SKIP
── Phase 4: Reset to LO-mode ─────────────
tick  mode=LO  B:run  S:run  U:run

Use this as a starting point for understanding the API without setting up a cross-compiler or emulator.

QEMU demo

A complete FreeRTOS + mcsched demo running on an emulated ARM Cortex-M3 (MPS2-AN385). Demonstrates LO-mode EDF scheduling, criticality escalation, and AMC-rtb run-to-blocking recovery — all without real hardware.

# Install tools (Ubuntu/Debian)
sudo apt-get install -y qemu-system-arm gcc-arm-none-eabi binutils-arm-none-eabi

cd qemu
make test    # clones FreeRTOS-Kernel, builds, runs, exits automatically

[ 500] Monitor: injecting overrun — brake_ctrl will exceed wcet_lo.
[ 520] BRAKE    RUN  elapsed=8ms  budget=5ms  OVERRUN -> HI-mode
[ 530] Monitor: MODE SWITCH LO -> HI detected!
[ 600] UI       SKIP (mode=HI, AMC-rtb: run-to-blocking)
[1030] Monitor: resetting to LO-mode.
[1630] *** DONE ***
PASS: demo completed

Tools

mcsched ships with seven offline tools for schedulability analysis, validation, visualisation, code generation, and stress testing. All read tasks.yaml and work without any real-time hardware or RTOS.

Tool	Lines	Description
`analyze.py`	391	EDF-VD / AMC-rtb schedulability verdict + formal proof certificate
`validate.py`	207	Check `tasks.yaml` for errors, missing fields, deadline violations
`sensitivity.py`	295	Per-task wcet headroom analysis — identify bottleneck tasks
`visualize.py`	405	Generate SVG Gantt chart of the scheduled timeline
`stress_test.py`	314	Random task set generation + schedulability acceptance ratio
`codegen.py`	185	Generate `tasks_gen.h` — one-call `register_all()` from YAML
`wcet_log.py`	230	Parse QEMU runtime logs, report per-task min/max/P95/P99 timing

Quick tour

Validate first:

python3 tools/validate.py tasks.yaml          # check for errors
python3 tools/validate.py tasks.yaml --strict # warnings → errors

Analyse schedulability:

python3 tools/analyze.py tasks.yaml                    # EDF-VD (default)
python3 tools/analyze.py tasks.yaml --policy amc-rtb   # AMC-rtb (stricter)
python3 tools/analyze.py tasks.yaml --out proof.json   # audit certificate

Check headroom:

python3 tools/sensitivity.py tasks.yaml                # per-task scale factors
python3 tools/sensitivity.py tasks.yaml --json         # machine-readable

Visualise the schedule:

python3 tools/visualize.py tasks.yaml                  # print SVG to stdout
python3 tools/visualize.py tasks.yaml --out timeline.svg

Stress-test at scale:

python3 tools/stress_test.py                           # 5000 samples per step
python3 tools/stress_test.py --samples 10000 --tasks 8 --high-ratio 0.4
python3 tools/stress_test.py --out report.json         # save results

Generate C from YAML:

python3 tools/codegen.py tasks.yaml                    # print to stdout
python3 tools/codegen.py tasks.yaml --out include/tasks_gen.h

Parse runtime logs:

make demo 2>&1 | python3 tools/wcet_log.py
python3 tools/wcet_log.py --log qemu_output.txt --tasks tasks.yaml

Screenshots

Scheduling timeline produced by tools/visualize.py — LO-mode execution (left), overrun detection, HI-mode dispatch, and LOW task skip in HI-mode (hatched blocks).

GitHub social preview / repository card.

File structure

mcsched/
├── include/
│   ├── mcsched.h           # Core API
│   └── mcsched_config.h    # Compile-time limits (MCSCHED_MAX_TASKS)
├── src/
│   └── mcsched.c           # EDF-VD / AMC-rtb algorithm — zero RTOS dependency
├── port/freertos/
│   ├── mcsched_port.h      # FreeRTOS integration API
│   └── mcsched_port.c      # Daemon task, EDF priority updates, suspend/resume
├── examples/
│   └── basic/              # Minimal Linux demo (no FreeRTOS, no hardware)
├── tools/
│   ├── analyze.py          # Offline schedulability analysis (391 lines)
│   ├── visualize.py        # SVG Gantt chart generator (405 lines)
│   ├── validate.py         # Task set validation (207 lines)
│   ├── sensitivity.py      # wcet headroom analysis (295 lines)
│   ├── stress_test.py      # Random task set stress testing (314 lines)
│   ├── codegen.py          # C code generation from YAML (185 lines)
│   └── wcet_log.py         # QEMU runtime log parser (230 lines)
├── tests/
│   ├── test_mcsched.c      # 18 core algorithm tests
│   ├── test_freertos_port.c# 13 port integration tests (mock backend)
│   ├── freertos_mock.h     # FreeRTOS mock declarations
│   └── freertos_mock.c     # Mock state — single definition, no ODR issues
├── qemu/
│   ├── main.c              # Demo application
│   ├── startup_gcc.c       # Cortex-M3 vector table and startup
│   ├── uart.c/h            # CMSDK UART driver (MPS2-AN385)
│   ├── mps2.ld             # Linker script
│   ├── FreeRTOSConfig.h    # FreeRTOS configuration
│   └── Makefile
├── docs/
│   ├── api.md              # API reference
│   ├── PORTING_en.md       # Porting guide (English)
│   ├── PORTING.md          # 移植指南（中文）
│   └── img/                # README diagrams and screenshots (SVG)
│       ├── hero.svg           # Banner image
│       ├── architecture.svg   # Architecture diagram
│       ├── timeline.svg       # Scheduling timeline
│       ├── policy-comparison.svg  # EDF-VD vs AMC-rtb
│       ├── schedule-example.svg   # Generated schedule (from visualize.py)
│       └── social-preview.svg     # GitHub social preview
├── tasks.yaml              # Example task set
└── Makefile                # make test / make analyze / make size

Configuration

Override in mcsched_config.h or via -D compiler flag:

Macro	Default	Meaning
`MCSCHED_MAX_TASKS`	16	Maximum simultaneously registered tasks

FreeRTOS port priority layout:

Macro	Default	Meaning
`MCSCHED_FREERTOS_BASE_PRIORITY`	2	Lowest priority in the managed-task band
`MCSCHED_FREERTOS_DAEMON_PRIORITY`	20	Daemon task priority (above all managed tasks)
`MCSCHED_FREERTOS_DAEMON_STACK`	256	Daemon stack depth in words

Resource usage (Cortex-M3, `-Os`)

Metric	Value	Notes
Code (`.text`)	~842 bytes	Core algorithm only; measured with `arm-none-eabi-size`
RAM (`.bss` + `.data`)	~900 bytes	Includes state for `MCSCHED_MAX_TASKS=16`
Per-task incremental RAM	~4 bytes	Additional task slot beyond the slot count

make size    # compile for Cortex-M3 and print section sizes

API reference

Core

Function	Description
`mcsched_set_policy(policy)`	Select `MCSCHED_POLICY_EDF_VD` or `MCSCHED_POLICY_AMC_RTB`
`mcsched_set_time_fn(fn)`	Inject microsecond time source
`mcsched_register(handle, params)`	Register a task
`mcsched_job_start(handle)`	Mark job start; returns `MCSCHED_JOB_RUN` or `MCSCHED_JOB_SKIP`
`mcsched_job_end(handle)`	Mark job end
`mcsched_tick()`	Call every RTOS tick; returns current mode
`mcsched_get_mode()`	Query current mode (`LO` / `HI`)
`mcsched_task_runnable(handle)`	Returns false for LOW tasks in HI-mode
`mcsched_reset_mode()`	Return to LO-mode after recovery

FreeRTOS port

Function	Description
`mcsched_freertos_register(handle, params)`	Register a `TaskHandle_t`
`mcsched_freertos_init()`	Create daemon task, wire time source
`mcsched_freertos_tick_hook()`	Call from `vApplicationTickHook()`
`mcsched_freertos_reset_mode()`	Reset mode and resume suspended LOW tasks
`mcsched_freertos_process()`	One scheduling cycle (also usable directly in tests)

Porting

See docs/PORTING_en.md for instructions on targeting Zephyr, bare-metal super-loops, and other RTOS platforms, including high-precision time sources for STM32, ESP32, and RP2040.

中文移植指南：docs/PORTING.md

References

Vestal, S. (2007). Preemptive Scheduling of Multi-Criticality Systems with Varying Degrees of Execution Time Assurance. RTSS.
Baruah, S., Burns, A., Davis, R.I. (2011). Response-Time Analysis for Mixed Criticality Systems. RTSS.
Burns, A., Davis, R.I. (2013). A Survey of Research into Mixed Criticality Systems. University of York Technical Report.

Name		Name	Last commit message	Last commit date
Latest commit History 1 Commit
.github/workflows		.github/workflows
docs		docs
examples/basic		examples/basic
include		include
port/freertos		port/freertos
qemu		qemu
src		src
tests		tests
tools		tools
.gitignore		.gitignore
CHANGELOG.md		CHANGELOG.md
CMakeLists.txt		CMakeLists.txt
CONTRIBUTING.md		CONTRIBUTING.md
LICENSE		LICENSE
Makefile		Makefile
README.md		README.md
README_zh.md		README_zh.md
tasks.yaml		tasks.yaml

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Repository files navigation

mcsched

The problem

Architecture

Quick start

Scheduling policies

EDF-VD — Earliest Deadline First with Virtual Deadlines

AMC-rtb — Adaptive Mixed-Criticality, run-to-blocking

Visualised

Offline schedulability analysis

Tests

Linux standalone example

QEMU demo

Tools

Quick tour

Screenshots

File structure

Configuration

Resource usage (Cortex-M3, `-Os`)

API reference

Core

FreeRTOS port

Porting

References

About

Uh oh!

Releases

Packages

Uh oh!

Uh oh!

Contributors

Uh oh!

Languages

Folders and files

Latest commit

History

Repository files navigation

mcsched

The problem

Architecture

Quick start

Scheduling policies

EDF-VD — Earliest Deadline First with Virtual Deadlines

AMC-rtb — Adaptive Mixed-Criticality, run-to-blocking

Visualised

Offline schedulability analysis

Tests

Linux standalone example

QEMU demo

Tools

Quick tour

Screenshots

File structure

Configuration

Resource usage (Cortex-M3, -Os)

API reference

Core

FreeRTOS port

Porting

References

About

Topics

Resources

License

Contributing

Uh oh!

Stars

Watchers

Forks

Releases

Packages 0

Uh oh!

Uh oh!

Contributors

Uh oh!

Languages

Resource usage (Cortex-M3, `-Os`)

Packages