Compositional Verification for Hierarchical Scheduling of Real-Time Systems
Authors:
- 9 August 2012
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Software Engineering
- Vol. 39 (5) , 638-657
Abstract
Hierarchical Scheduling (HS) techniques achieve resource partitioning among a set of real-time applications, providing reduction of complexity, confinement of failure modes, and temporal isolation among system applications. This facilitates compositional analysis for architectural verification and plays a crucial role in all industrial areas where high-performance microprocessors allow growing integration of multiple applications on a single platform. We propose a compositional approach to formal specification and schedulability analysis of real-time applications running under a Time Division Multiplexing (TDM) global scheduler and preemptive Fixed Priority (FP) local schedulers, according to the ARINC-653 standard. As a characterizing trait, each application is made of periodic, sporadic, and jittering tasks with offsets, jitters, and nondeterministic execution times, encompassing intra-application synchronizations through semaphores and mailboxes and interapplication communications among periodic tasks through message passing. The approach leverages the assumption of a TDM partitioning to enable compositional design and analysis based on the model of preemptive Time Petri Nets (pTPNs), which is expressly extended with a concept of Required Interface (RI) that specifies the embedding environment of an application through sequencing and timing constraints. This enables exact verification of intra-application constraints and approximate but safe verification of interapplication constraints. Experimentation illustrates results and validates their applicability on two challenging workloads in the field of safety-critical avionic systems.Keywords
This publication has 33 references indexed in Scilit:
- A Formal Approach to Design and Verification of Two-Level Hierarchical Scheduling Systems2011
- Oris: a tool for modeling, verification and evaluation of real-time systemsInternational Journal on Software Tools for Technology Transfer, 2010
- Formal verification of real-time systems with preemptive schedulingReal-Time Systems, 2008
- Reachability Problems and Abstract State Spaces for Time Petri Nets with StopwatchesDiscrete Event Dynamic Systems, 2007
- Timed state space analysis of real-time preemptive systemsIEEE Transactions on Software Engineering, 2004
- Static analysis and dynamic steering of time-dependent systemsIEEE Transactions on Software Engineering, 2001
- Scheduling aperiodic tasks in dynamic priority systemsReal-Time Systems, 1996
- Compositional validation of time-critical systems using communicating time Petri netsIEEE Transactions on Software Engineering, 1995
- Priority inheritance protocols: an approach to real-time synchronizationIEEE Transactions on Computers, 1990
- Timing assumptions and verification of finite-state concurrent systems1990