Real-Time Systems
Multicore Real-Time Scheduling
A modern vehicle contains up to 100 ECUs. The AUTOSAR Adaptive Platform combines ABS (ASIL-D), transmission control (ASIL-C), and navigation (QM) on a single multicore processor. Without cache partitioning and mixed-criticality scheduling, ISO 26262 certification is impossible - and the vehicle cannot reach the market.
- **AUTOSAR (automotive)** - ECU standard defining multicore scheduling and memory protection requirements for ISO 26262
- **Intel RDT (Resource Director Technology)** - CAT + MBA (Memory Bandwidth Allocation) for cache and memory control in cloud and embedded RTS
- **ARINC 653 (avionics)** - spatial/temporal partitioning in IMA (Integrated Modular Avionics), the precursor to mixed-criticality concepts
Partitioned Scheduling: one task, one core
Moving from single-core to multicore RTS is not simply "more cores". Shared L2/L3 caches create **cache interference**: a task on core 0 evicts task core 1's data from the shared L3. This makes WCET (Worst-Case Execution Time) unpredictable - the foundation of RTS analysis. **Partitioned scheduling** solves this: each task is statically assigned to one core, and each core runs as an independent uniprocessor scheduler.
**Bin packing in partitioned scheduling:** optimal task assignment across cores is NP-hard. In practice, heuristics are used: First Fit Decreasing (FFD), Worst Fit. The criterion: CPU utilization must not exceed the schedulability bound (typically <= 69% for RM on each core).
The main advantage of partitioned scheduling over global scheduling is:
Global Scheduling: Dhall's Effect and utilization bounds
**Global scheduling** allows tasks to migrate across cores - the scheduler selects the m highest-priority tasks from a global queue for m cores. Flexibility is high, but utilization is surprisingly bounded: **Dhall's Effect** shows that G-EDF cannot guarantee schedulability even at utilization close to 1.
| Approach | Utilization bound | WCET predictability | Task migration |
|---|---|---|---|
| Partitioned (RM) | <= 69% per core | High | No |
| Global EDF (G-EDF) | <= m - (m-1)*u_max | Low | Yes (overhead) |
| Partitioned EDF | <= 100% per core (theory) | High | No |
| Semi-partitioned | Compromise | Medium | Limited |
Dhall's Effect shows G-EDF can fail even at utilization close to 1. Why?
Mixed-Criticality Systems: different guarantees for different tasks
A modern automotive ECU combines tasks of different criticality: ABS (safety-critical, ASIL-D), navigation (non-critical), multimedia (best-effort). **Mixed-Criticality Systems (MCS)** formalize this: tasks have a criticality level, and under overload, less critical tasks can be dropped.
**Core idea of MCS:** instead of worst-case planning for ALL tasks (pessimistic), use optimistic WCET in normal mode and switch to safety mode only under real overload. This allows more tasks to be hosted on one processor.
In a Mixed-Criticality system when switching to HI-mode, what happens to LO-criticality tasks?
Cache Partitioning: cache isolation for predictable WCET
The shared L3 cache is the main source of WCET unpredictability in multicore systems. A task on core 0 loads its data into L3; a task on core 1 evicts it. For cache-intensive tasks, WCET with interference can be 10x higher than without it. **Cache partitioning** divides the cache between cores, eliminating interference.
| Method | Hardware requirements | Granularity | Use case |
|---|---|---|---|
| Intel CAT | Intel Xeon with RDT | Cache ways (16-32) | Server RTS, automotive on x86 |
| Page Coloring | None (software) | Cache sets | Embedded Linux RTOS |
| WCSA Analysis | None | Analytical | Static WCET analysis |
**AUTOSAR in practice:** ISO 26262 (automotive safety) requires proof of no interference between ASIL-D and QM tasks. Intel CAT or Page Coloring are the standard tools for obtaining this proof. Without cache partitioning, ASIL-D certification on a multicore processor is impossible.
On a multicore processor it is sufficient to run N uniprocessor RTOSes on N cores without additional measures.
Shared caches (L2/L3), DRAM bus contention, and interconnect interference make WCET unpredictable without cache partitioning and careful memory scheduling. Directly scaling a uniprocessor RTOS to multicore breaks RTS guarantees.
Uniprocessor WCET analysis assumes an isolated system. In multicore systems, common resources (cache, memory, bus) create contention - a task's WCET depends on neighboring core activity, making timing analysis impossible without additional measures.
Why is cache partitioning needed in safety-critical multicore systems?
Multicore Real-Time Scheduling
- **Partitioned scheduling:** task bound to one core; deterministic WCET; assignment is NP-hard bin packing
- **Global scheduling (G-EDF):** tasks migrate; Dhall's Effect bounds utilization; high migration overhead
- **Mixed-Criticality:** two WCETs per task (LO/HI); under overload LO tasks are dropped; Vestal model underlies AUTOSAR
- **Cache partitioning:** Intel CAT or Page Coloring; eliminates interference; mandatory for ASIL-D certification on multicore
Related Topics
Multicore RTS builds on uniprocessor scheduling algorithms and schedulability theory.
- Priority Inversion and Protocols — On multicore systems, priority inversion is more complex due to shared locks and task migration
- Rate Monotonic Scheduling — RM schedulability analysis is applied to each core independently in the partitioned scheme
Вопросы для размышления
- Why does Dhall's Effect make G-EDF impractical for heavy tasks with high utilization, and how does semi-partitioned scheduling attempt to resolve this trade-off?
- How does Mixed-Criticality scheduling change the traditional approach to WCET analysis - why are two different WCETs better than one conservative estimate?
- What are the trade-offs between Intel CAT and Page Coloring for cache partitioning in safety-critical embedded systems?