Resource Efficient Isolation Mechanisms in Mixed-Criticality Scheduling

Xiaozhe Gu, Arvind Easwaran, Kieu-My Phan, Insik Shin

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 TL is 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 TL is 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 TL to the total number of HC tasks in a component is equivalent to reservation-based methods, while setting TL=0 mimics 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 TL parameter offers a tunable knob between the extreme pessimism of classical models and the potential risks of ignoring WCET violations. A higher TL allows 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 TL value. Higher TL values lead to better LC support but lower schedulability. The paper demonstrates that for TLH up to 0.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

Abstract

Mixed-criticality real-time scheduling has been developed to improve resource utilization while guaranteeing safe execution of critical applications. These studies use optimistic resource reservation for all the applications to improve utilization, but prioritize critical applications when the reservations become insufficient at runtime. Many of them however share an impractical assumption that all the critical applications will simultaneously demand additional resources. As a consequence, they under-utilize resources by penalizing all the low-criticality applications. In this paper we overcome this shortcoming using a novel mechanism that comprises a parameter to model the expected number of critical applications simultaneously demanding more resources, and an execution strategy based on the parameter to improve resource utilization. Since most mixed criticality systems in practice are component-based, we design our mechanism such that the component boundaries provide the isolation necessary to support the execution of low-criticality applications, and at the same time protect the critical ones. We also develop schedulability tests for the proposed mechanism under both a flat as well as a hierarchical scheduling framework. Finally, through simulations, we compare the performance of the proposed approach with existing studies in terms of schedulability and the capability to support low-criticality applications.
BibTeX
@inproceedings{gu2015resource,
  author = {Xiaozhe Gu and Arvind Easwaran and Kieu-My Phan and Insik Shin},
  title = {{Resource Efficient Isolation Mechanisms in Mixed-Criticality Scheduling}},
  booktitle = {ECRTS},
  year = {2015},
  url = {https://openreview.net/forum?id=xsioauk8MT},
}
Figure