Real-Time Systems: Scheduling, Timing Analysis, and Design Patterns

What Is a Real-Time System?

A real-time system must produce correct results within specified time constraints — the correctness of the output depends on both the logical result and the time at which it is delivered. In hard real-time systems, missing a single deadline constitutes system failure with potentially catastrophic consequences: an automotive airbag that deploys 10 milliseconds too late offers no protection to the occupant, and a braking system that takes 100 ms longer than specified may not stop the vehicle in time to avoid a collision. Soft real-time systems can tolerate occasional deadline misses with degraded quality of service — a video streaming application that drops frames during network congestion, or a voice-over-IP call with occasional audio glitches. Firm real-time systems fall between the two: occasional missed deadlines are tolerable but reduce the usefulness of the result, as in a stock trading system where a late trade might still execute but at a worse price.

Real-Time vs General-Purpose Systems

General-purpose operating systems such as standard Linux and Windows optimize for average-case throughput and fairness among user processes. The Linux Completely Fair Scheduler, for example, distributes CPU time proportionally among competing processes and provides excellent average performance, but cannot guarantee that a high-priority task will execute within a specific time window because kernel code may disable interrupts for extended periods. Real-time executive kernels such as FreeRTOS and Zephyr use priority-based preemptive scheduling where the highest-priority ready task always runs, with bounded dispatch latency measured in microseconds. The difference becomes critical when a system must respond to an external event within a hard deadline.

Scheduling Algorithms

Rate Monotonic Scheduling

Rate Monotonic Scheduling (RMS) assigns fixed priorities to tasks inversely proportional to their periods — the shortest-period task receives the highest priority. RMS is provably optimal among fixed-priority scheduling algorithms for periodic independent tasks where deadlines equal periods, as proven by Liu and Layland in their 1973 IEEE Transactions on Computers paper. The utilization bound for RMS with n tasks is U = n × (2^(1/n) − 1). As n approaches infinity, this bound converges to ln(2) ≈ 69.3%. This means that even with RMS, a set of tasks with total CPU utilization below 69% is guaranteed to be schedulable, but tasks exceeding this bound require individual feasibility analysis. For a system with three tasks at 30%, 25%, and 20% utilization, total utilization is 75%, which exceeds the 78% three-task bound, so the system may miss deadlines under worst-case conditions.

Earliest Deadline First

EDF assigns dynamic priorities — the task with the earliest absolute deadline executes at any given time. EDF is optimal for uniprocessor systems: it can schedule any task set with total utilization less than 100%, achieving perfect utilization in theory. However, EDF is harder to implement in practice because priorities change dynamically, requiring a sorted ready queue that is more complex than the simple fixed-priority scheduling used by most RTOS kernels. Under overload conditions where utilization exceeds 100%, EDF suffers from a domino effect where a cascade of deadline misses propagates through the task set because late tasks push subsequent deadlines further into the past. RMS degrades more gracefully — only the lowest-priority tasks miss deadlines while higher-priority tasks continue to meet theirs.

Priority Inversion

Priority inversion occurs when a high-priority task is blocked waiting for a mutually exclusive resource that is held by a lower-priority task. The problem becomes unbounded when a medium-priority task preempts the low-priority task, preventing it from releasing the resource and extending the high-priority task’s blocking time indefinitely. The 1997 Mars Pathfinder mission experienced a classic priority inversion bug that caused the spacecraft to repeatedly reset, documented in the JPL report by task lead Mike Jones. The solution was the priority inheritance protocol: when a low-priority task holds a mutex that a higher-priority task needs, the low-priority task temporarily inherits the waiting task’s priority, allowing it to complete the critical section and release the mutex without interference from medium-priority tasks.

Resource Sharing Protocols

Beyond priority inheritance, the Priority Ceiling Protocol (PCP) prevents deadlock and chained blocking by assigning each resource a priority ceiling equal to the highest priority of any task that might request it. A task can only lock a resource if its priority is higher than the ceiling of any currently locked resource. The Stack Resource Protocol (SRP) simplifies PCP by using a single preemption level per task rather than per-resource ceilings. Both protocols bound the blocking time a task can experience, which is essential for schedulability analysis in multi-resource real-time systems.

Worst-Case Execution Time Analysis

Worst-Case Execution Time (WCET) analysis determines the maximum time a task can take to execute on a given hardware platform with worst-case inputs, worst-case cache state, and worst-case interference from other hardware. Measurement-based approaches run the task repeatedly with different inputs and hardware states, recording the maximum observed execution time — this is practical but only finds observed worst cases, not theoretical worst cases. Static analysis tools such as aiT from AbsInt examine the program binary and hardware microarchitecture model to compute bounds without executing the code. WCET is affected by pipeline depth and hazards (deeper pipelines have more potential stalls), cache hits and misses (a cache miss can add dozens of cycles), branch prediction accuracy (mispredictions flush the pipeline), and interrupt latency (higher-priority interrupts delay lower-priority handlers). The ARM Cortex-M7 with its L1 caches and branch predictor presents particular challenges for WCET analysis compared to the simpler Cortex-M3.

Multiprocessor Scheduling

Multi-core systems introduce additional complexity because tasks running on different cores can interfere through shared caches, memory buses, and peripherals. Partitioned scheduling assigns each task to a specific core, simplifying analysis because each core’s schedule can be analyzed independently, but may waste capacity when one core is overloaded while others are idle. Global scheduling allows any task to run on any core, potentially achieving higher utilization but introducing migration overhead, cache pollution, and more complex schedulability analysis. Clustered scheduling groups cores and partitions task groups among clusters, providing a middle ground. The choice depends on the application’s communication patterns and sensitivity to cache interference.

Real-Time Design Patterns

Common design patterns simplify real-time system development. The cyclic executive runs a fixed sequence of tasks in a main loop at a rate determined by a periodic timer interrupt — simple but inflexible for complex systems. The task pipeline pattern divides processing into stages connected by queues, where each stage runs at its own priority level. The watchdog pattern uses a hardware watchdog timer to detect and recover from task overruns and deadlocks. The rate-monotonic pattern structures task periods as harmonic multiples of the base tick (10 ms, 20 ms, 40 ms, 80 ms) to minimize jitter and simplify scheduling analysis.

Formal Verification of Real-Time Systems

Safety-critical real-time systems increasingly use formal verification to prove timing properties mathematically rather than relying solely on testing. Model checking tools like UPPAAL model the system as timed automata and verify properties such as “all tasks meet their deadlines” or “priority inversion is bounded.” Response-time analysis (RTA) calculates the worst-case response time for each task by considering interference from higher-priority tasks and blocking from lower-priority tasks holding shared resources. Tools like MAST (Modeling and Analysis Suite for Real-Time Applications) automate RTA for complex task sets with offsets, precedence constraints, and multiple resources.

Frequently Asked Questions

What is the difference between a cyclic executive and an RTOS? A cyclic executive runs a fixed task sequence in a timed loop — simple but wastes CPU cycles if tasks finish early. An RTOS uses priority-based preemptive scheduling that only runs tasks when they are ready, improving CPU utilization and event response time.

What is the difference between hard and soft real-time? Hard real-time requires deterministic deadline guarantees where missing a deadline is catastrophic — airbag deployment, braking systems, medical implants. Soft real-time tolerates occasional missed deadlines with degraded quality — video streaming, audio playback.

How do I calculate WCET for my tasks? Measure execution time on actual hardware using the DWT cycle counter on Cortex-M or by toggling a GPIO pin and measuring with a logic analyzer. Add a safety margin of 20–50% for measurement-based approaches. For safety-critical systems, use a certified static analysis tool.

Can standard Linux be used for real-time applications? Standard Linux is not suitable for hard real-time because interrupt disabling in drivers introduces unbounded latency. Use the PREEMPT_RT kernel patch for soft real-time with bounded latency around 100 microseconds.

What is the utilization bound and why does it matter? The utilization bound is the maximum CPU utilization at which all tasks are guaranteed to meet deadlines. Exceeding the bound does not guarantee failure but means the system could miss deadlines under worst-case phasing and execution time conditions.

Related: RTOS Concepts | Embedded Systems Guide