TL;DR
This paper introduces OPAM, a novel coevolutionary algorithm for automatically assigning optimal priorities to real-time tasks. OPAM addresses the challenge of balancing safety margins and engineering constraints, outperforming existing methods and manual assignments in complex industrial systems.
What Problem Does This Paper Address?
Real-time systems, crucial in domains like aerospace and automotive, rely on task priorities to ensure timely execution and meet deadlines. Assigning these priorities is a complex, interactive process between developers and testers, aiming to maximize safety margins (tolerance for unexpected delays) while adhering to engineering constraints. Traditional methods often rely on simplified system models and struggle to handle real-world complexities like task dependencies and multiple objectives. This paper tackles the problem of automating this priority assignment process to find near-optimal solutions that are both effective and practical for industrial systems.
Methods
The core of OPAM is a multi-objective, competitive coevolutionary algorithm. It mimics the interactive nature of priority assignment by evolving two populations simultaneously:
- Task-arrival sequences (Population A): These represent "stress tests" designed to challenge the system and induce deadline misses.
- Priority assignments (Population P): These are the candidate solutions that OPAM aims to optimize.
These two populations evolve competitively. Population A tries to find worst-case task arrival patterns that cause deadline misses, while Population P tries to find priority assignments that maximize safety margins and satisfy engineering constraints. This competitive dynamic drives both populations to improve. OPAM uses a steady-state genetic algorithm for evolving task-arrival sequences and NSGAII (Non-dominated Sorting Genetic Algorithm II) for evolving priority assignments. It also incorporates external fitness evaluation to monitor coevolutionary progress reliably.
Datasets
The paper evaluates OPAM on:
- Six industrial subject systems: These include systems from aerospace, automotive, and avionics domains, with varying numbers of periodic/aperiodic tasks, resource dependencies, triggering relations, and platform cores. One industrial case study (ESAIL) was from the authors' industry partner, LuxSpace.
- 370 synthetic subjects: These were created to systematically investigate OPAM's scalability and performance under controlled conditions, varying parameters like the number of tasks, ratio of aperiodic tasks, range factor for inter-arrival times, and simulation time.
Key Insights and Ideas
- Coevolution as a Natural Fit: The paper strongly suggests that coevolutionary approaches are well-suited for problems that are inherently interactive and involve competing elements, like the developer-tester dynamic in priority assignment.
- Balancing Conflicting Objectives: OPAM effectively handles the trade-off between maximizing safety margins and satisfying engineering constraints, producing a Pareto front of equally viable solutions. This allows engineers to make informed decisions based on their specific needs.
- Beyond Simple Models: OPAM's ability to account for task dependencies (resource, triggering) and multi-core systems makes it more applicable to complex, real-world industrial systems than many prior methods.
- The Power of Competition: The competitive interaction between task-arrival sequences and priority assignments is crucial for driving the search towards robust solutions.
Key Results
- Superior Performance: OPAM significantly outperforms random search (RS) and a sequential approach (SEQ) in terms of finding better priority assignments, as measured by Hypervolume (HV) and Pareto Compliant Generational Distance (GD+).
- Industrial System Success: OPAM achieved better results than manual assignments from engineers for the ESAIL system, increasing safety margins by an average of 5.33%.
- Scalability: OPAM's execution time and memory usage scale linearly with the number of tasks and simulation time, making it suitable for large-scale industrial systems. The maximum execution time for industrial subjects was around 15.5 hours, which is considered acceptable for offline analysis.
- Robustness: OPAM's priority assignments are more robust to uncertainties in task arrivals, especially in systems with a higher number of aperiodic tasks.
Limitations and Future Work
- Schedulability Analysis: The paper notes that exhaustive schedulability analysis techniques (like model checking with UPPAAL) were too computationally expensive to verify ESAIL tasks for a single priority assignment, limiting direct comparison with some existing methods.
- WCET Assumption: OPAM assumes near-worst-case schedule scenarios by assigning tasks' WCETs to their execution times. While this is a common assumption, formal proof of its validity under varying task arrival times and triggering relations requires further complex analysis.
- Future Work: The authors plan to:
- Incorporate dynamic priority assignments.
- Account for WCET value ranges to handle non-deterministic computation times.
- Address interrupt handling routines.
- Support hybrid scheduling policies.
- Develop a real-time task modeling language for system analysis.
- Validate OPAM on more diverse industrial case studies.
Summary updated