A Model-Based Framework for the Specification and Analysis of Hierarchical Scheduling Systems

Mounir Chadli, Jin Hyun Kim, Axel Legay, Louis-Marie Traonouez, Stefan Naujokat, Bernhard Steffen, Kim Guldstrand LarsenFMICS-AVoCS 2016 · DOI

TL;DR

This paper introduces a novel model-based framework for analyzing the schedulability of complex Cyber-Physical Systems (CPS). By extending existing formal verification tools with probabilistic features, the authors enable more flexible and realistic modeling of scheduling policies, going beyond the limitations of traditional analytical methods. This work is crucial for ensuring the safety and reliability of mission-critical systems.

What Problem Does This Paper Address?

Modern Cyber-Physical Systems (CPS) are increasingly complex, integrating software-controlled physical components into high-performance platforms. A critical aspect of ensuring their correctness is schedulability analysis, which guarantees that tasks meet their deadlines. Traditionally, this has been done using analytical methods, but these are often limited to specific, simpler scheduling policies. This paper addresses the challenge of analyzing more complex and realistic scheduling scenarios, especially those involving stochastic (probabilistic) behavior in task attributes like deadlines, execution times, and periods. Such stochasticity arises naturally in mixed-critical systems and advanced hardware, where precise timing is hard to guarantee. The authors aim to provide a flexible framework that can capture these uncertainties and allow for more accurate schedulability analysis.

Methods

The core of the paper is a model-based framework built upon Stopwatch Automata (SWA) and their probabilistic extension, Probabilistic Timed Automata (PTA). These formalisms allow for the representation of real-time systems with clocks that measure time and transitions that occur based on time and events.

Key methodological contributions include:

  • Stochastic Task Model: The authors introduce a new task model where real-time attributes (period, deadline, execution time) can be defined by probability distributions. This is a significant departure from traditional deterministic models.
  • Stochastic Dispatcher: A component that dynamically assigns these probabilistic attributes to tasks, mimicking real-world variations.
  • Hierarchical Scheduling Systems (HSS): The framework supports organizing scheduling units in a tree structure, allowing for compositional analysis. This means complex systems can be analyzed by breaking them down into smaller, manageable units.
  • Integration with UPPAAL: The models are implemented and analyzed using the UPPAAL model checker and its statistical model checker (UPPAAL-SMC). This leverages existing powerful verification tools.
  • Formal Verification Techniques: The paper utilizes both deterministic model checking (CTL formulas for properties like deadlock absence and schedulability) and statistical model checking (for probabilistic queries like the probability of meeting deadlines or estimating resource budgets).

Datasets

Not discussed in the paper. The authors focus on developing a modeling and analysis framework rather than evaluating it on specific, pre-existing datasets. The "data" comes from the system's specifications and potentially from sampling real-world execution times.

Key Insights and Ideas

  • Probabilistic Modeling is Essential for Realistic CPS: The paper strongly argues that deterministic models are insufficient for capturing the nuances of modern CPS, especially those with mixed criticality or advanced hardware. Probabilistic attributes are key to accurately representing real-world behavior.
  • Flexibility of Model-Based Approaches: By extending formalisms like SWA with probabilistic features, the authors demonstrate that model-based approaches can handle a much wider range of scheduling policies than traditional analytical methods.
  • Compositional Analysis for Scalability: The hierarchical structure and the ability to analyze units independently are crucial for managing the complexity of large-scale CPS. This compositional approach is a cornerstone of making formal verification practical.
  • Bridging the Gap Between Theory and Practice: The framework aims to provide a bridge for designers to use formal methods for analyzing systems that were previously too complex or too stochastic for existing tools.

Key Results

The paper presents a formal framework and demonstrates its application using UPPAAL. While specific quantitative results are not the primary focus, the paper outlines how the framework can be used to answer critical questions:

  • Schedulability Analysis: The framework allows for determining if tasks will meet their deadlines, either deterministically (using A[] not error in UPPAAL MC) or probabilistically (using Pr[<=runTime](<> not error) in UPPAAL SMC).
  • Maximum Response Time: The framework can measure the maximum time from job instantiation to completion for tasks, providing performance insights.
  • Budget Estimation: The probabilistic supplier model allows for determining the minimum resource budget required for a system to be schedulable, by analyzing the probability distribution of unschedulable budget values.

Limitations and Future Work

  • Limitations:
    • The paper acknowledges that the stochastic semantics of PTA, as implemented in UPPAAL, still exhibits non-deterministic behaviors, which can limit analysis to best-case or worst-case scenarios in some contexts.
  • While the framework is presented, the paper doesn't provide extensive experimental results on large-scale industrial systems.
  • Future Work:
    • The authors suggest further exploration of stochastic semantics for more comprehensive average-case analysis.
  • Extending the framework to handle more complex interactions and dependencies between tasks and resources.
  • Investigating the application of this framework to specific domains like avionics or automotive systems.

Summary updated

BibTeX
@inproceedings{chadli2016model,
  author = {Mounir Chadli and Jin Hyun Kim and Axel Legay and Louis-Marie Traonouez and Stefan Naujokat and Bernhard Steffen and Kim Guldstrand Larsen},
  title = {{A Model-Based Framework for the Specification and Analysis of Hierarchical Scheduling Systems}},
  booktitle = {FMICS-AVoCS},
  year = {2016},
  doi = {10.1007/978-3-319-45943-1\_9},
}
Figure