Component-based analysis of hierarchical scheduling using linear hybrid automata
- 1 August 2014
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 23251271,p. 1-10
Abstract
Formal methods (e.g. Timed Automata or Linear Hybrid Automata) can be used to analyse a real-time system by performing a reachability analysis on the model. The advantage of using formal methods is that they are more expressive than classical analytic models used in schedulability analysis. For example, it is possible to express state-dependent behaviour, arbitrary activation patterns, etc. In this paper we use the formalism of Linear Hybrid Automata to encode a hierarchical scheduling system. In particular, we model a dynamic server algorithm and the tasks contained within, abstracting away the rest of the system, thus enabling component-based scheduling analysis. We prove the correctness of the model and the decidability of the reachability analysis for the case of periodic tasks. Then, we compare the results of our model against classical schedulability analysis techniques, showing that our analysis performs better than analytic methods in terms of resource utilisation. We further present two case studies: a component with state-dependent tasks, and a simplified model of a real avionics system. Finally, through extensive tests with various configurations, we demonstrate that this approach is usable for medium-size components.Keywords
This publication has 18 references indexed in Scilit:
- Parametric Schedulability Analysis of Fixed Priority Real-Time Distributed Systems2014
- The scheduling problem of self-suspending periodic real-time tasks2012
- On Reachability for Hybrid Automata over Bounded Time2011
- A Formal Approach to Design and Verification of Two-Level Hierarchical Scheduling Systems2011
- Transitioning from federated avionics architectures to Integrated Modular Avionics2007
- Scheduling with timed automataTheoretical Computer Science, 2006
- Schedulability Analysis Using Two Clocks2003
- A theory of timed automataTheoretical Computer Science, 1994
- On the complexity of fixed-priority scheduling of periodic, real-time tasksPerformance Evaluation, 1982
- Scheduling Algorithms for Multiprogramming in a Hard-Real-Time EnvironmentJournal of the ACM, 1973