Project 16: Real-Time Embedded Simulator

A deterministic simulator for real-time embedded tasks, timers, and interrupt-driven workflows.

Quick Reference

Attribute	Value
Difficulty	Level 5 - Master
Time Estimate	3-4 weeks
Main Programming Language	C
Alternative Programming Languages	None
Coolness Level	Level 5 - Pure Magic
Business Potential	Level 3 - Service & Support
Prerequisites	Concurrency basics, timing, state machines
Key Topics	Real-time scheduling, timers, deterministic simulation

1. Learning Objectives

By completing this project, you will:

Model real-time tasks with deadlines and priorities.
Implement scheduling policies (rate monotonic, EDF).
Simulate timers and interrupt events deterministically.
Measure jitter, latency, and deadline misses.
Produce a report that explains scheduling outcomes.

2. All Theory Needed (Per-Concept Breakdown)

Concept 1: Real-Time Scheduling, Deadlines, and Jitter

Fundamentals

Real-time systems must meet timing constraints, not just produce correct outputs. Tasks have deadlines, periods, and priorities. Scheduling policies such as Rate Monotonic (RM) and Earliest Deadline First (EDF) determine which task runs at any given time. Jitter is the variation in timing of task execution. Understanding these concepts is essential for designing reliable real-time systems.

Deep Dive into the concept

A real-time task is defined by its period (how often it should run), its execution time (how long it takes), and its deadline (by when it must finish). In a hard real-time system, missing a deadline is catastrophic. In a soft real-time system, occasional misses degrade quality but are tolerable. Scheduling policies determine which task runs when. Rate Monotonic scheduling assigns higher priority to tasks with shorter periods, and it is optimal for fixed-priority systems under certain conditions. EDF scheduling is dynamic: it always runs the task with the earliest deadline, and it is optimal in the sense that if any schedule can meet deadlines, EDF can.

Schedulability analysis uses utilization bounds. For RM, the Liu and Layland bound provides a sufficient condition: the sum of C_i / T_i for each task must be below a threshold. EDF can theoretically achieve 100% utilization if tasks are preemptible and deadlines equal periods. But real systems have context-switch overhead, interrupt latency, and resource contention, which reduce effective utilization. Your simulator must account for these overheads if you want realistic behavior.

Jitter arises when tasks do not start or finish exactly at their intended times. It can be caused by preemption, interrupt handling, or resource contention. Measuring jitter is important because it affects control loops and signal processing. In your simulator, you will track the difference between scheduled and actual execution times for each task, and report max/mean jitter. This will show how different scheduling policies affect timing predictability.

In this project, you will model tasks, run them under RM and EDF, and analyze deadline misses and jitter. You will build the intuition needed to reason about real-time systems and to design schedulers that meet constraints.

A deeper real-time analysis includes blocking times and priority inversion. If a high-priority task waits on a resource held by a lower-priority task, the system can miss deadlines even if utilization appears safe. Priority inheritance and priority ceiling protocols are common mitigations. In your simulator, you can model resource locks and show how priority inversion affects jitter and deadlines. Another important concept is worst-case execution time (WCET). Real-time systems are designed based on WCET, not average execution time. Your simulator can include a per-task WCET parameter and compare schedules based on that, illustrating why average-case benchmarks are insufficient in real-time contexts.

To operationalize this concept in a real codebase, create a short checklist of invariants and a set of micro-experiments. Start with a minimal, deterministic test that isolates one rule or behavior, then vary a single parameter at a time (inputs, flags, platform, or data layout) and record the outcome. Keep a table of assumptions and validate them with assertions or static checks so violations are caught early. Whenever the concept touches the compiler or OS, capture tool output such as assembly, warnings, or system call traces and attach it to your lab notes. Finally, define explicit failure modes: what does a violation look like at runtime, and how would you detect it in logs or tests? This turns abstract theory into repeatable engineering practice and makes results comparable across machines and compiler versions.

How this fits on projects

It defines scheduler logic in §4.4 and §5.10.
It drives metrics reporting in §3.7 and §6.2.
Also used in: Project 5: Control Flow Pattern Library.

Definitions & key terms

Deadline: Time by which a task must complete.
Period: Interval between task releases.
Execution time: CPU time required to complete a task.
Jitter: Variation in task timing.
RM/EDF: Scheduling policies for real-time systems.

Mental model diagram (ASCII)

Time: 0---5---10---15
Task A (period 5): [A][A][A]
Task B (period 10): [B]   [B]

How it works (step-by-step, with invariants and failure modes)

Define tasks with period, deadline, and execution time.
At each tick, select next task based on policy.
Execute task and update remaining time.
Detect deadline misses and record jitter.

Invariant: Scheduler must obey policy (RM or EDF). Failure mode: Missed deadlines when utilization exceeds bounds.

Minimal concrete example

task_t t = { .period=10, .deadline=10, .exec=2 };

Common misconceptions

“EDF always works.” → Only if utilization and overhead allow.
“Jitter is unimportant.” → It can break control systems.
“Real-time equals fast.” → It means predictable.

Check-your-understanding questions

What is the difference between hard and soft real-time?
Why does EDF perform better than RM in some cases?
What causes jitter?
What is the RM utilization bound?
How do deadline misses affect system behavior?

Check-your-understanding answers

Hard real-time cannot miss deadlines; soft can tolerate misses.
EDF dynamically prioritizes the earliest deadline.
Preemption, interrupts, and contention.
Sum of utilizations must be below a threshold (~0.69 for many tasks).
They cause incorrect or delayed system responses.

Real-world applications

Flight control systems.
Automotive ECUs and industrial control.

Where you’ll apply it

See §4.4 Algorithm Overview for scheduling logic.
See §6.2 for deadline miss tests.
Also used in: Project 15: Performance-Optimized Data Structures.

References

Liu & Layland (1973) scheduling theory paper
“Making Embedded Systems” — Elecia White

Key insights

Real-time systems are about predictability, not just speed.

Summary

Scheduling theory provides the framework for meeting deadlines. Understanding RM, EDF, and jitter is essential for building real-time systems.

Homework/Exercises to practice the concept

Compute utilization for a set of tasks.
Simulate RM scheduling by hand for 3 tasks.
Measure jitter in a simulated schedule.

Solutions to the homework/exercises

Sum C_i / T_i for each task.
Assign priorities by shortest period.
Compare expected vs actual start times.

Concept 2: Timers, Interrupts, and Deterministic Event Simulation

Fundamentals

Embedded systems are driven by timers and interrupts. Timers generate periodic events, while interrupts respond to external stimuli. A simulator must model these events deterministically so results are reproducible. This requires a discrete-event simulation loop that advances time in steps and processes events in a defined order.

Deep Dive into the concept

In real hardware, timers fire based on oscillator ticks and interrupts can arrive at any time. In a simulator, you must model this behavior explicitly. A common approach is a discrete-event simulation: you maintain a priority queue of events sorted by time. The simulator advances time to the next event, processes it, and schedules new events. This yields deterministic behavior if the event ordering is well-defined. For example, if two events occur at the same timestamp, you must define a tie-breaker rule (e.g., higher priority first).

Interrupts introduce preemption. If a high-priority interrupt occurs while a task is running, the task may be paused and the interrupt handler executed. Modeling this requires tracking current execution, remaining time, and interrupt priorities. The simulator can represent interrupts as events that temporarily preempt tasks, then resume them. This adds complexity but is essential for realistic timing analysis.

Determinism is critical for debugging. If the simulator’s results change between runs, it becomes useless as a tool. This means you must fix random seeds, define exact event ordering, and avoid using real wall-clock time. Instead, the simulator should run in “simulated time” with explicit tick counts. Your project will implement a deterministic event loop, configurable timers, and a trace output that logs all events for reproducibility.

Another way to deepen understanding is to map the concept to a small decision table: list inputs, expected outcomes, and the assumptions that must hold. Create at least one negative test that violates an assumption and observe the failure mode, then document how you would detect it in production. Add a short trade-off note: what you gain by following the rule and what you pay in complexity or performance. Where possible, instrument the implementation with debug-only checks so violations are caught early without affecting release builds. If the concept admits multiple approaches, implement two and compare them; the act of measuring and documenting the difference is part of professional practice. This habit turns theoretical understanding into an engineering decision framework you can reuse across projects.

Finally, keep a short field guide that lists typical symptoms when this concept is violated and the quickest diagnostic tool to use. For example, link errors, sanitizer crashes, or unexpected timing. This makes the concept actionable when things break. Repeat the exercise for at least one cross-platform variant so you see which parts are portable and which are not. Over time, this builds intuition that is hard to gain from theory alone.

How this fits on projects

It defines the event loop in §4.1 and §5.2.
It informs the deterministic demo in §3.7.
Also used in: Project 5: Control Flow Pattern Library.

Definitions & key terms

Discrete-event simulation: Advance time by processing events in order.
Interrupt: Asynchronous event that preempts execution.
Timer tick: Regular time step generated by hardware or simulator.
Determinism: Same inputs produce same outputs.

Mental model diagram (ASCII)

Event queue: (t=5, TIMER) (t=8, IRQ) (t=10, TASK)

How it works (step-by-step, with invariants and failure modes)

Initialize event queue with task releases and timers.
Pop next event, advance simulated time.
Process event and schedule follow-ups.
Log event and update task state.

Invariant: Event ordering is deterministic. Failure mode: Ambiguous ordering causes non-reproducible results.

Minimal concrete example

event_t e = { .time=10, .type=EV_TIMER };

Common misconceptions

“Real-time simulation must use real time.” → It should use simulated time.
“Interrupts can be ignored.” → They affect timing and jitter.
“Determinism is automatic.” → You must enforce ordering and seeds.

Check-your-understanding questions

Why use a priority queue for events?
How do you model interrupts in a simulator?
What causes non-determinism in simulations?
Why avoid wall-clock time?
How do you handle simultaneous events?

Check-your-understanding answers

To process events in time order efficiently.
As preemptive events with higher priority.
Randomness, undefined ordering, and external time.
It introduces variability across runs.
Use a deterministic tie-break rule.

Real-world applications

RTOS scheduling simulations.
Hardware-in-the-loop testing.

Where you’ll apply it

See §3.7 for deterministic simulation output.
See §5.10 Phase 2 for event queue implementation.
Also used in: Project 8: File I/O System.

References

“Making Embedded Systems” — Elecia White
RTOS scheduling literature

Key insights

A deterministic simulation is a reproducible laboratory for real-time behavior.

Summary

Timers and interrupts drive real-time systems. A deterministic discrete-event simulation lets you model these behaviors accurately and reproducibly.

Homework/Exercises to practice the concept

Implement a priority queue for events.
Simulate a timer interrupt every 10 ticks.
Add a tie-breaker rule for same-time events.

Solutions to the homework/exercises

Use a binary heap with events ordered by time.
Insert events at multiples of 10.
Order by event priority then insertion order.

3. Project Specification

3.1 What You Will Build

A deterministic real-time simulator with task scheduling, timers, and interrupt modeling. It outputs a timeline trace and metrics (deadline misses, jitter, utilization).

3.2 Functional Requirements

Task model: Period, deadline, execution time, priority.
Schedulers: Implement RM and EDF.
Event system: Timer and interrupt events.
Metrics: Deadline misses, jitter, utilization.
Trace output: Deterministic event log.

3.3 Non-Functional Requirements

Performance: Simulate 1e6 ticks in under 5 seconds.
Reliability: Deterministic outputs with fixed seeds.
Usability: CLI options for scheduler selection.

3.4 Example Usage / Output

$ ./rt_sim --scheduler edf --ticks 1000
Task A missed 0 deadlines
Task B missed 1 deadline

3.5 Data Formats / Schemas / Protocols

Trace format (CSV):

time,event,task
10,release,A
12,run,A

3.6 Edge Cases

Simultaneous task releases.
Over-utilized schedules.
Interrupt storms.

3.7 Real World Outcome

What you will see:

A scheduler comparison report.
A deterministic event trace file.
Metrics on jitter and deadline misses.

3.7.1 How to Run (Copy/Paste)

make
./rt_sim --scheduler rm --ticks 500 --trace out.csv

3.7.2 Golden Path Demo (Deterministic)

Run with a fixed task set and verify no missed deadlines.

3.7.3 If CLI: exact terminal transcript

$ ./rt_sim --scheduler rm --ticks 100
Tasks: A,B
Missed deadlines: 0
Exit: 0

Failure demo (deterministic):

$ ./rt_sim --scheduler rm --ticks 100 --task-set overload
ERROR: utilization > 1.0, deadlines will be missed
Exit: 2

4. Solution Architecture

4.1 High-Level Design

+-------------------+
| task model         |
+---------+---------+
          |
          v
+-------------------+     +-------------------+
| scheduler          | -->| event queue       |
+-------------------+     +-------------------+
          |
          v
+-------------------+
| trace + metrics    |
+-------------------+

4.2 Key Components

4.3 Data Structures (No Full Code)

typedef struct { int period; int deadline; int exec; int prio; } task_t;

4.4 Algorithm Overview

Initialize tasks and event queue.
For each tick, select runnable task.
Process timers and interrupts.
Record trace and metrics.

Complexity Analysis:

Time: O(E log E) for event processing
Space: O(T + E)

5. Implementation Guide

5.1 Development Environment Setup

clang -std=c23 -Wall -Wextra -Werror -g

5.2 Project Structure

rt-sim/
├── src/
│   ├── scheduler.c
│   ├── events.c
│   └── main.c
├── include/
│   └── rt.h
├── tests/
└── Makefile

5.3 The Core Question You’re Answering

“How do real-time systems guarantee deadlines under real-world constraints?”

5.4 Concepts You Must Understand First

Scheduling policies and utilization bounds.
Jitter and latency measurement.
Deterministic event simulation.

5.5 Questions to Guide Your Design

How will you represent tasks and deadlines?
How will you model interrupts and preemption?
How will you enforce determinism?

5.6 Thinking Exercise

Compute RM utilization for a three-task system.

5.7 The Interview Questions They’ll Ask

What is EDF scheduling?
Why is jitter important?
How do you model interrupts in software?

5.8 Hints in Layers

Hint 1: Start with a simple tick-based scheduler.
Hint 2: Add EDF and RM selection.
Hint 3: Add event queue for interrupts.

5.9 Books That Will Help

| Topic | Book | Chapter | |——-|——|———| | Embedded systems | “Making Embedded Systems” — White | Ch. 7-9 |

5.10 Implementation Phases

Phase 1: Foundation (1 week)

Build task model and basic scheduler.
Checkpoint: Tasks execute in expected order.

Phase 2: Core Functionality (1 week)

Add EDF and event queue.
Checkpoint: Trace output deterministic.

Phase 3: Polish & Edge Cases (1 week)

Add jitter metrics and deadline analysis.
Checkpoint: Metrics report correct values.

5.11 Key Implementation Decisions

6. Testing Strategy

6.1 Test Categories

6.2 Critical Test Cases

RM schedule meets deadlines under bound.
EDF handles dynamic deadlines.
Interrupt storm increases jitter.

6.3 Test Data

Task set: A(5,2), B(10,3)

7. Common Pitfalls & Debugging

7.1 Frequent Mistakes

7.2 Debugging Strategies

Print trace logs and visualize timeline.
Compare RM vs EDF outputs.

7.3 Performance Traps

Simulating at too fine a granularity can be slow; choose tick size wisely.

8. Extensions & Challenges

8.1 Beginner Extensions

Add a Gantt chart ASCII output.

8.2 Intermediate Extensions

Add resource locking and priority inversion simulation.

8.3 Advanced Extensions

Add multi-core scheduling simulation.

9. Real-World Connections

9.1 Industry Applications

RTOS scheduler validation.
Automotive and aerospace system simulations.

FreeRTOS scheduling docs.
Zephyr RTOS simulations.

9.3 Interview Relevance

Scheduling and real-time constraints are common systems interview topics.

10. Resources

10.1 Essential Reading

“Making Embedded Systems” — White
Liu & Layland scheduling paper

10.2 Video Resources

Talks on real-time scheduling and RTOS design

10.3 Tools & Documentation

QEMU (optional for embedded simulation)

11. Self-Assessment Checklist

11.1 Understanding

I can explain RM and EDF scheduling.
I can measure jitter and latency.
I can implement a deterministic event loop.

11.2 Implementation

Simulator runs deterministically.
Metrics are reported correctly.
Trace output is reproducible.

11.3 Growth

I can reason about schedulability bounds.
I can extend the simulator with new policies.

12. Submission / Completion Criteria

Minimum Viable Completion:

Task model and scheduler implementation.
Deterministic event loop.
Metrics for deadline misses.

Full Completion:

All minimum criteria plus:
EDF and RM comparison with jitter metrics.

Excellence (Going Above & Beyond):

Multi-core scheduling and priority inversion simulation.