Reference topics: CMU 18-549 · independent study notes, not affiliated

Real-Time Systems

Real-time scheduling, priority inversion, WCET analysis, and safety-critical system design.

5Lectures
1Assignments
1Exams
35hDuration
1

Introduction to Real-Time Systems

What is a Real-Time System? A real-time system is one where the correctness of the system depends not only on the logical result of computation, but also on the time at which the result is produced....

⏱ 50 min read

What is a Real-Time System?

A real-time system is one where the correctness of the system depends not only on the logical result of computation, but also on the time at which the result is produced. A late answer is a wrong answer.

Examples:

  • Airbag deployment: must fire within milliseconds of impact
  • Pacemaker: must deliver a pulse at exactly the right moment
  • ABS brakes: must release pressure at the right time
  • Flight control: must respond to pilot input within 50 ms
  • Industrial robots: must complete tasks within cycle time

Hard vs Soft Real-Time

Hard real-time: missing a deadline is catastrophic. Failure modes: airbag doesn't fire, pacemaker misses a beat, plane crashes.

Firm real-time: missing a deadline makes the result useless, but not catastrophic. Example: video frame decoding — a late frame is dropped.

Soft real-time: missing a deadline degrades quality but the system continues. Example: audio streaming — occasional glitches are tolerated.

Why Not Just "Fast"?

Real-time isn't about being fast — it's about being predictable. A system that's usually fast but occasionally takes 100 ms is worse for real-time than one that's always 5 ms.

Deterministic timing is the goal. That's why real-time systems avoid:

  • Garbage collection (unpredictable pauses)
  • Dynamic memory allocation (fragmentation, unpredictable timing)
  • Caches (usually helpful, but can cause timing variability)
  • Complex scheduling algorithms with high overhead

The Real-Time Challenge

Three sources of unpredictability:

  1. Interrupt latency: how long until the CPU responds to an external event
  2. Scheduling latency: how long until the right task runs
  3. Execution time variability: how long a task takes to run

Real-time systems must bound all three.

Deadline Types

  • Absolute deadline: a specific time (e.g., "complete by 3:00:00 PM")
  • Relative deadline: a time from release (e.g., "complete within 50 ms of activation")
  • Periodic tasks: released at regular intervals
  • Aperiodic tasks: released at arbitrary times
  • Sporadic tasks: aperiodic, but with minimum inter-arrival times

A Classic Example: Cruise Control

A car's cruise control is a periodic real-time task:

  • Sample the speed sensor every 10 ms
  • Compute control output
  • Send to throttle actuator
  • Deadline: 10 ms (if missed, control loop becomes unstable)

If the deadline is missed occasionally, the car may jerk. If missed frequently, the car oscillates dangerously.

Key Takeaways

  • Real-time = correctness depends on timing
  • Hard, firm, soft categories based on consequences of missing deadlines
  • Predictability > raw speed
  • Interrupt latency, scheduling latency, execution variability are the three unpredictability sources
  • Periodic, aperiodic, sporadic tasks are the basic types
2

Task Scheduling: RM and EDF

The Scheduling Problem Given a set of tasks with deadlines, how do we schedule them on one (or more) CPUs to meet all deadlines? For periodic tasks, a schedule is a repeating pattern. If all...

⏱ 50 min read

The Scheduling Problem

Given a set of tasks with deadlines, how do we schedule them on one (or more) CPUs to meet all deadlines?

For periodic tasks, a schedule is a repeating pattern. If all deadlines are met in the first "hyperperiod" (LCM of periods), they'll be met forever.

Task Model

Each task Ti is characterized by:

  • Period Ti: release interval
  • Execution time Ci: worst-case compute time
  • Deadline Di: usually = Ti (implicit deadlines)
  • Utilization Ui = Ci / Ti

Total utilization: U = Σ Ui.

If U > 1, no schedule can meet all deadlines. If U ≤ 1, we need the right algorithm.

Rate Monotonic (RM) Scheduling

Priority = 1 / period. Shorter period = higher priority. Static priorities (fixed at design time).

For RMS, we assign priorities based on rate. Faster tasks get higher priority.

Utilization bound: RMS is guaranteed to meet all deadlines if:

U ≤ n × (2^(1/n) - 1)

where n is the number of tasks. This bound approaches ln(2) ≈ 0.693 as n grows.

For 2 tasks: bound = 0.828
For 3 tasks: bound = 0.780
For large n: bound = 0.693

If U ≤ 0.693, RMS always works. If U > bound but ≤ 1, RMS may or may not work (depends on specific task parameters).

Example: RMS Utilization Test

Tasks:

  • T1: C=2, P=5 (U1 = 0.4)
  • T2: C=2, P=7 (U2 = 0.286)
  • T3: C=1, P=10 (U3 = 0.1)

Total U = 0.786 < 3 × (2^(1/3) - 1) = 0.780... Actually 0.786 > 0.780.

So RMS bound is not satisfied. But RMS might still work — need to check the schedule explicitly.

Earliest Deadline First (EDF)

Priority = earliest deadline. Dynamic priorities (change every release).

The currently-executing task is the one with the earliest absolute deadline.

Utilization bound: EDF is optimal for single-processor scheduling. If U ≤ 1, EDF meets all deadlines.

This is a stronger guarantee than RMS.

RMS vs EDF

| Property | RMS | EDF |
|----------|-----|-----|
| Priority | Static | Dynamic |
| Bound | n(2^(1/n)-1) | 1 |
| Optimality | Optimal for static priorities | Optimal overall |
| Overhead | Low | Moderate |
| Predictability | High | Moderate |
| Implementation | Simple | More complex |

RMS is used in small embedded systems (predictable, low overhead). EDF is used when utilization is high (> 70%) or when tasks are aperiodic.

Priority Inversion

A famous problem in real-time systems. Scenario:

  • Low-priority task L holds a mutex
  • High-priority task H needs the mutex, blocks
  • Medium-priority task M preempts L
  • H is now waiting on M, even though H >> M

This famously caused the Mars Pathfinder mission to reset repeatedly in 1997.

Priority Inheritance

Solution: when H blocks on a mutex held by L, temporarily boost L to H's priority. This prevents M from preempting L. When L releases the mutex, restore its original priority.

The Mars Pathfinder fix was to enable priority inheritance.

Priority Ceiling

Alternative solution: assign each mutex a ceiling priority = max priority of any task that might use it. When a task acquires the mutex, boost to the ceiling.

Prevents deadlock and reduces blocking.

Key Takeaways

  • RMS: static priorities, bound ≈ 0.693, easy to implement
  • EDF: dynamic priorities, bound = 1, optimal for single CPU
  • Priority inversion: high-priority task blocked by low-priority via medium task
  • Priority inheritance: temporarily boost blocker's priority
  • Priority ceiling: prevent deadlock too
3

FreeRTOS: Practical RTOS on Microcontrollers

Why an RTOS? For simple projects, a superloop (main while loop) works fine. But as complexity grows, you need: Task isolation Priority-based scheduling Inter-task communication Timing guarantees A ...

⏱ 50 min read

Why an RTOS?

For simple projects, a superloop (main while loop) works fine. But as complexity grows, you need:

  • Task isolation
  • Priority-based scheduling
  • Inter-task communication
  • Timing guarantees

A real-time operating system (RTOS) provides all of this with minimal overhead.

FreeRTOS is the most popular embedded RTOS:

  • Tiny footprint (6-12 KB)
  • Portable across dozens of architectures (ARM, ESP32, AVR, RISC-V)
  • MIT license
  • Rich ecosystem

Tasks

A FreeRTOS task is a function that runs "forever":

void vTaskBlinkLED(void *pvParameters) {
while (1) {
gpio_set_level(LED_PIN, 1);
vTaskDelay(pdMS_TO_TICKS(500));
gpio_set_level(LED_PIN, 0);
vTaskDelay(pdMS_TO_TICKS(500));
}
}

xTaskCreate(vTaskBlinkLED, "Blink", 2048, NULL, 1, NULL);

Key parameters:

  • Name: for debugging
  • Stack size: in words (2048 = 8 KB on 32-bit)
  • Parameters: void pointer passed to task
  • Priority: 0 (lowest) to configMAX_PRIORITIES-1
  • Handle: returns a TaskHandle_t

Scheduling

FreeRTOS uses preemptive priority scheduling:

  • Higher priority task always runs
  • Equal-priority tasks share CPU round-robin (if time slicing enabled)
  • If no task is ready, the idle task runs

Key insight: no task blocks the CPU waiting. Instead, tasks delay, block on queues, or wait for notifications.

vTaskDelay vs vTaskDelayUntil

vTaskDelay(ticks): delay from now. Not suitable for periodic tasks — the period drifts by execution time.

vTaskDelayUntil(&lastWake, period): delay until a specific time. Used for periodic tasks.

TickType_t lastWake = xTaskGetTickCount();
while (1) {
do_work();
vTaskDelayUntil(&lastWake, pdMS_TO_TICKS(100));
}

This guarantees exactly 100 ms period regardless of do_work() duration.

Queues

Inter-task communication:

QueueHandle_t xQueue = xQueueCreate(10, sizeof(int));

// Producer
int value = 42;
xQueueSend(xQueue, &value, portMAX_DELAY);

// Consumer
int received;
if (xQueueReceive(xQueue, &received, pdMS_TO_TICKS(100))) {
// got a value
}

Queues are thread-safe, block-based, and can have any item size.

Semaphores

Binary semaphore: like a flag, used for signaling.

Counting semaphore: counts events.

Mutex: mutual exclusion, with priority inheritance.

SemaphoreHandle_t xMutex = xSemaphoreCreateMutex();

if (xSemaphoreTake(xMutex, pdMS_TO_TICKS(100)) == pdTRUE) {
// critical section
xSemaphoreGive(xMutex);
}

Task Notifications

Faster than queues/semaphores for simple cases:

// From ISR:
vTaskNotifyGiveFromISR(taskHandle, &higherPriorityWoken);

// In task:
ulTaskNotifyTake(pdTRUE, portMAX_DELAY);

No allocation, no queue overhead, ~45% faster than a binary semaphore.

Interrupts and ISRs

ISRs must be short. Do minimal work, then notify a task:

void IRAM_ATTR buttonISR() {
BaseType_t xHigherPriorityTaskWoken = pdFALSE;
vTaskNotifyGiveFromISR(buttonTaskHandle, &xHigherPriorityTaskWoken);
portYIELD_FROM_ISR(xHigherPriorityTaskWoken);
}

Use FromISR versions of FreeRTOS API in interrupts.

Memory Management

FreeRTOS offers 5 heap implementations (heap_1 to heap_5):

  • heap_1: static, no free
  • heap_2: free, but no coalescing
  • heap_3: wraps malloc/free
  • heap_4: coalescing, common choice
  • heap_5: multiple memory regions

For hard real-time, prefer static allocation (xTaskCreateStatic).

Real-World Example: ESP32 Data Logger

Tasks:

  1. Sensor task (priority 3): reads sensor every 100 ms
  2. Storage task (priority 2): writes to SD card
  3. Wi-Fi task (priority 1): uploads to server every 5 min
  4. Button task (priority 4): handles user input

Queue between sensor and storage. Notification between button and Wi-Fi. Mutex protects SD card.

Key Takeaways

  • FreeRTOS is a small, portable RTOS
  • Tasks are functions running "forever"
  • Preemptive priority scheduling
  • Use vTaskDelayUntil for periodic tasks
  • Queues, semaphores, notifications for IPC
  • Keep ISRs short, defer to tasks
  • Static allocation for hard real-time
4

Timing Analysis and WCET

Why WCET Matters To prove a real-time system meets deadlines, you need the worst-case execution time (WCET) of each task. Not the average, not the best — the worst. WCET analysis is hard because:...

⏱ 50 min read

Why WCET Matters

To prove a real-time system meets deadlines, you need the worst-case execution time (WCET) of each task. Not the average, not the best — the worst.

WCET analysis is hard because:

  • Inputs affect execution time (loop bounds, branches)
  • Caches make timing input-dependent
  • Pipelines and out-of-order execution complicate analysis
  • Interrupts can occur at any time

Sources of Timing Variability

Instruction count: depends on data (branches, loops).

Cache behavior: a cache hit is fast, a miss is ~100× slower.

Pipeline stalls: data dependencies, branch mispredicts.

Memory latency: DRAM access is slow, but predictable if prefetched.

Interrupts: add delay but bounded.

WCET Analysis Techniques

Static analysis: analyze the binary, compute upper bounds on execution time by:

  • Counting instructions
  • Modeling cache behavior
  • Modeling pipeline behavior
  • Summing worst-case contributions

Tools: aiT, Bound-T, RapiTime.

Pros: sound (guaranteed upper bound). Cons: pessimistic (overestimates).

Measurement-based: run the task many times, take the maximum observed time. Multiply by a safety factor.

Pros: realistic, easy. Cons: not guaranteed (may miss rare worst cases).

Hybrid: use static analysis for critical paths, measurement for others.

Loop Bounds

The analyzer must know how many times each loop runs:

for (int i = 0; i < 100; i++) { ... } // bound = 100

for (int i = 0; i < n; i++) { ... } // bound = ? (n unknown)

For dynamic loops, add annotations:

#pragma loop_bound(100)
for (int i = 0; i < n; i++) { ... }

Cache Analysis

Worst-case: every access is a miss (upper bound) — pessimistic.

Better: analyze cache behavior using abstract interpretation. Classify each access as always hit, always miss, or unknown.

Some real-time systems disable caches to make WCET deterministic. This slows the average case but improves predictability.

Interrupt Latency

Time from interrupt assertion to first ISR instruction. Bounded by:

  • Hardware interrupt processing (~10 cycles)
  • Saving context (~20-50 cycles)
  • Vector table lookup (~5 cycles)

On ARM Cortex-M: ~12 cycles best case, ~30 typical.

For hard real-time, interrupt latency must be < the tightest deadline in the system.

Response Time Analysis

For a task Ti, the worst-case response time is:

R_i = C_i + Σ_{j ∈ hp(i)} ceil(R_i / T_j) × C_j

where hp(i) is the set of higher-priority tasks.

Solve by iteration:

  • Start with R_i = C_i
  • Compute new R_i
  • Repeat until convergence or R_i > deadline (failure)

If R_i ≤ D_i for all i, the system is schedulable.

Example

Tasks:

  • T1: C=1, T=4 (high priority)
  • T2: C=2, T=6 (medium)
  • T3: C=3, T=12 (low)

For T3:

  • R = 3
  • R = 3 + ceil(3/4)×1 + ceil(3/6)×2 = 3 + 1 + 2 = 6
  • R = 3 + ceil(6/4)×1 + ceil(6/6)×2 = 3 + 2 + 2 = 7
  • R = 3 + ceil(7/4)×1 + ceil(7/6)×2 = 3 + 2 + 4 = 9
  • R = 3 + ceil(9/4)×1 + ceil(9/6)×2 = 3 + 3 + 4 = 10
  • R = 3 + ceil(10/4)×1 + ceil(10/6)×2 = 3 + 3 + 4 = 10 (converged)

R_3 = 10 ≤ D_3 = 12. So T3 is schedulable.

Key Takeaways

  • WCET is essential for real-time guarantees
  • Static analysis is sound but pessimistic
  • Measurement is realistic but not guaranteed
  • Loop bounds must be provided
  • Response time analysis computes worst-case delay per task
  • Iterate R = C + Σ interference until convergence
  • If R ≤ D for all tasks, system is schedulable
5

Real-Time Communication and Safety

Communication in Real-Time Systems Real-time systems communicate over: Shared memory: fastest, but needs synchronization Message passing: safer, but slower Fieldbuses: industrial networks (CA...

⏱ 50 min read

Communication in Real-Time Systems

Real-time systems communicate over:

  • Shared memory: fastest, but needs synchronization
  • Message passing: safer, but slower
  • Fieldbuses: industrial networks (CAN, Profibus, EtherCAT)
  • Time-triggered protocols: deterministic (TTP, FlexRay)

CAN Bus

The Controller Area Network (CAN) is the dominant automotive and industrial bus:

  • 1 Mbps max (CAN FD: 8 Mbps)
  • Multi-master, differential, 120Ω terminated
  • Message IDs determine priority (lower = higher priority)
  • Non-destructive arbitration: higher-priority message always wins
  • CRC + automatic retransmission

CAN messages are small (8 bytes classic, 64 bytes CAN FD). Perfect for sensors, actuators, control commands.

Deterministic Ethernet (TSN, EtherCAT)

Standard Ethernet isn't deterministic (CSMA/CD collisions, best-effort switches). Extensions:

TSN (Time-Sensitive Networking): IEEE 802.1 standards. Time-synchronized scheduling.

EtherCAT: processing-on-the-fly, < 100 µs cycle times.

PROFINET IRT: isochronous real-time, < 1 ms cycles.

These are used in industrial automation where cycle times must be guaranteed.

Safety Standards

IEC 61508: functional safety (general).

ISO 26262: automotive (ASIL A-D).

DO-178C: aerospace (DAL A-E).

IEC 62304: medical devices.

Each defines processes for developing safety-critical software, from requirements through testing and verification.

Safety Integrity Levels (SIL)

SIL 1-4, with SIL 4 being the most stringent:

  • SIL 1: probability of dangerous failure 10⁻⁵ to 10⁻⁶ per hour
  • SIL 2: 10⁻⁶ to 10⁻⁷
  • SIL 3: 10⁻⁷ to 10⁻⁸
  • SIL 4: 10⁻⁸ to 10⁻⁹

ASIL D (automotive) is roughly equivalent to SIL 3.

Redundancy

Safety-critical systems use redundancy:

  • Hot standby: duplicate runs in parallel, output switch on failure
  • Cold standby: backup activated on failure
  • Triple modular redundancy (TMR): three units vote, majority wins
  • 2oo3: two-out-of-three voting

Example: spacecraft use TMR for critical subsystems. Aircraft use dual-channel flight control.

Fail-Safe Design

When a system fails, it should fail to a safe state:

  • Airbag: deploy (safe = fire)
  • Pacemaker: continue at fixed rate (safe = pacing)
  • Industrial robot: stop motion (safe = halt)
  • Elevator: brakes engage (safe = stop)

Fail-safe means "the safest action on failure", not "do nothing".

Watchdog Timers

A hardware counter that resets the CPU if not "fed" periodically:

while (1) {
do_work();
feed_watchdog();
}

If the CPU hangs (infinite loop, deadlock), the watchdog isn't fed and the system resets. Simple but effective.

Advanced: windowed watchdog — must be fed within a specific time window (not too early, not too late). Catches both hang and runaway loop bugs.

Testing Real-Time Systems

  • Unit testing for logic
  • Integration testing for timing
  • Stress testing at maximum load
  • Fault injection to test error paths
  • Hardware-in-the-loop for realistic I/O

Formal verification (model checking, theorem proving) is used at SIL 3-4.

Key Takeaways

  • CAN is the workhorse of automotive/industrial
  • Deterministic Ethernet (TSN, EtherCAT) for high-performance RT
  • Safety standards (IEC 61508, ISO 26262) define development processes
  • SIL/ASIL levels define required reliability
  • Redundancy (TMR, 2oo3) for critical systems
  • Fail-safe design: on failure, go to safest state
  • Watchdog timers detect hangs
  • Testing + formal verification for safety-critical systems

📝 Problem Set 1: RMS, EDF, FreeRTOS

Q1. Three periodic tasks: T1(C=1,T=4), T2(C=2,T=6), T3(C=2,T=12). Check schedulability with RMS.

Show Solution

U = 1/4 + 2/6 + 2/12 = 0.25 + 0.333 + 0.167 = 0.75. RMS bound for n=3: 3×(2^(1/3)-1) = 0.780. U=0.75 < 0.780 → schedulable with RMS.

Q2. Explain priority inversion and how priority inheritance solves it.

Show Solution

Priority inversion: high-priority task H waits on a lock held by low-priority L. Medium-priority M preempts L, blocking H indefinitely. Priority inheritance: when H blocks on L's lock, L is temporarily boosted to H's priority. M can no longer preempt L, so L finishes quickly and releases the lock.

Q3. In FreeRTOS, explain the difference between vTaskDelay and vTaskDelayUntil. Which is used for periodic tasks?

Show Solution

vTaskDelay(n): delays n ticks from now. If loop body takes time T, period = T + n (drifts). vTaskDelayUntil(&last, period): delays until last+period. Period stays constant regardless of body execution time. Use vTaskDelayUntil for periodic control loops.

🎯 Midterm 1: Scheduling, WCET, RTOS

Q1. Response time analysis for T3(C=2,T=10,D=10) with higher-priority tasks T1(C=1,T=4) and T2(C=2,T=6).

Show Solution

R_3 = C_3 + Σ ceil(R_3/T_i) × C_i for i=1,2. Start R=2. R=2+ceil(2/4)×1+ceil(2/6)×2 = 2+1+2 = 5. R=2+ceil(5/4)×1+ceil(5/6)×2 = 2+2+2 = 6. R=2+ceil(6/4)×1+ceil(6/6)×2 = 2+2+2 = 6. Converged: R_3 = 6 ≤ D_3 = 10. Schedulable.

Q2. Design a watchdog-based recovery for a system that must respond within 100 ms. Choose timeout and explain.

Show Solution

Watchdog timeout should be < 100 ms to detect hangs before deadline. Choose 50 ms. If task misses feeding watchdog within 50 ms, CPU resets. Log reset reason to diagnose. Add independent hardware watchdog (external chip) for maximum reliability.

Q3. Explain how CAN bus achieves deterministic communication despite being a shared medium.

Show Solution

CAN uses non-destructive bit-wise arbitration: each message has an ID; when two nodes transmit, lower ID wins. Loser retries without data loss. Priority = message ID. This ensures highest-priority message always wins without collision. Combined with bounded frame size and CRC, CAN is deterministic.