TL;DR
This paper introduces a novel mixed-criticality scheduling mechanism that improves resource utilization by modeling the expected number of high-criticality tasks that might simultaneously exceed their normal execution bounds. This allows for better support of low-criticality tasks without compromising the safety of critical ones, outperforming existing methods in simulations.
What Problem Does This Paper Address?
Modern embedded systems, like those in avionics or automotive, often integrate functionalities with varying levels of criticality. Ensuring the safety of high-criticality functions (e.g., flight control) is paramount, leading to conservative resource allocation that underutilizes system capacity. Traditional mixed-criticality scheduling approaches often assume the worst-case scenario where all high-criticality tasks might simultaneously demand more resources than initially estimated. This leads to penalizing low-criticality tasks by dropping them entirely, even when such a simultaneous demand is highly improbable. The paper addresses this gap by proposing a more realistic approach that leverages component boundaries and a probabilistic parameter to allow more low-criticality tasks to execute.
Methods
The core of the proposed solution is a new mechanism that introduces a "HC Tolerance Limit" (TL) for each component. This parameter models the expected number of high-criticality (HC) tasks within a component that might simultaneously exceed their low-confidence Worst-Case Execution Time (WCET).
Key methodological contributions include:
- Parameter for Expected HC Violations: A parameter
TLis introduced to quantify the acceptable number of simultaneous HC task WCET violations within a component. - Component-Based Isolation: The mechanism leverages component boundaries to isolate the impact of HC task WCET violations. If the number of violating HC tasks stays within the component's
TL, low-criticality (LC) tasks in other components are unaffected. - Execution Strategy: An execution strategy is developed that maximizes LC task executions as long as the
TLis not exceeded. - Schedulability Tests: The paper derives schedulability tests for the proposed mechanism under both flat (single scheduler) and hierarchical (nested schedulers) scheduling frameworks. These tests are based on the demand bound function (dbf) concept.
- Generalization: The proposed mechanism is shown to generalize existing approaches: setting
TLto the total number of HC tasks in a component is equivalent to reservation-based methods, while settingTL=0mimics classical models that drop all LC tasks.
Datasets
Not discussed in the paper. The paper focuses on theoretical modeling and simulation-based evaluation using synthetically generated tasksets.
Key Insights and Ideas
- Probabilistic Worst-Case is Overkill: The assumption that all HC tasks might simultaneously exceed their WCET is often overly pessimistic and leads to significant resource underutilization.
- Component Boundaries as a Resource: Component boundaries are not just for isolation but can be intelligently used to manage resource contention and protect LC tasks.
- Tunable Pessimism: The
TLparameter offers a tunable knob between the extreme pessimism of classical models and the potential risks of ignoring WCET violations. A higherTLallows more LC execution but reduces schedulability guarantees. - Hierarchical vs. Flat Scheduling: While both frameworks are analyzed, the hierarchical approach offers better compositionality but incurs more overhead, leading to slightly lower schedulability ratios in simulations.
Key Results
- Improved Schedulability: Simulations show that the proposed mechanism consistently achieves higher schedulability ratios compared to "Service Adaptation," "Interference Constraint Graph (ICG)," and the "Classical Model" (where LC tasks are dropped).
- Enhanced LC Task Support: The mechanism significantly outperforms others in terms of the "Percentage of Finished LC Jobs" (PFJ), especially as the probability of HC jobs exhibiting HC behavior increases.
- Performance Trade-off: The performance (schedulability and LC job support) is directly influenced by the
TLvalue. HigherTLvalues lead to better LC support but lower schedulability. The paper demonstrates that forTLHup to0.4|H|(40% of HC tasks), the mechanism offers the best balance.
Limitations and Future Work
- Component Allocation: The evaluation primarily considers scenarios where all HC tasks are in one component and all LC tasks in another. The paper acknowledges that further improvements in offline schedulability could be achieved by optimally allocating LC tasks to the same component as HC tasks.
- Fixed Task Parameters: The analysis assumes fixed task parameters (WCETs, periods, deadlines). Real-world systems might have dynamic variations.
- Future Work: The authors suggest exploring optimal allocation of LC tasks to maximize offline schedulability and online performance. They also mention considering scenarios where LC tasks are co-located with HC tasks within the same component.
Summary updated