Article

AADL modeling and analysis of hierarchical schedulers

Authors:

Frank Singhoff,

Alain PlantecAuthors Info & Claims

SIGAda '07: Proceedings of the 2007 ACM international conference on SIGAda annual international conference

Pages 41 - 50

https://doi.org/10.1145/1315580.1315593

Published: 04 November 2007 Publication History

Abstract

A system based on a hierarchical scheduler is a system in which the processor is shared between several collaborative schedulers. Such schedulers exist since 1960 and they are becoming more and more investigated and proposed in real-life applications. For example, the ARINC 653 international standard which defines an Ada interface for avionic real time operating systems provides such a kind of collaborative schedulers. This article focuses on the modeling and the performance analysis of hierarchical schedulers. We investigate the modeling of hierarchical schedulers with AADL. Hierarchical scheduler timing and synchronization relationships are expressed with a domain specific language based on timed automata: the Cheddar language. With the meta CASE tool Platypus, we generate Ada packages implementing the Cheddar language. These Ada packages are part of Cheddar, a real time scheduling simulator. With these Ada packages, Cheddar is able to perform analysis by scheduling simulation of AADL systems composed of hierarchical schedulers. An AADL model of the ARINC 653 hierarchical scheduling is described as an illustration.

References

[1]

L. Almeida and P. Pedreiras. Scheduling within Temporal Partitions: response-time analysis and server design. Proceedings of the EMSOFT'04 conference. September 27-29, Pisa, Italy pages 95--103,2004.

Digital Library

[2]

K. Altisen, G. Gossler, and J. Sifakis. Scheduler Modeling Based on the Controller Synthesis Paradigm. Real Time Systems journal 23(1):55--84,2002.

Digital Library

[3]

R. Alur and D. L. Dill. Automata for modeling real time systems. Proc. of Int. Colloquium on Algorithms, Languages and Programming, Vol 443 of LNCS (1990) 322--335, 1990.

Digital Library

[4]

T. E. Anderson, B. N. Bershad, E. D. Lazowska, and H. M. Levy. Scheduler activations: Effective kernel support for the user-level management of parallelism. ACM Transactions on Computer Systems 10(1):53--79, February 1992.

Digital Library

[5]

G. Behrmann, A. David, and K. G. Larsen. A Tutorial on UPPAAL. Technical Report Updated the 17th November 2004, Department of Computer Science, Aalbord University, Denmark, 2004.

[6]

G. Berry. Getting Started with Esterel Studio 5. 3. Technical report, Esterel technologies SA. Available from http://www. esterel-technologies. com/technology/getting-started/, April 2005.

[7]

A. Burns, M. Harbour, and A. Wellings. A round robin scheduling policy for Ada. In Reliable Software Technologies, Proceedings of the Ada Europe Conference 2003.

Digital Library

[8]

D. Chemouil and N. Pontisso. Vérification formelle d'un modèle AADL à l'aide de l'outil UPPAAL. Revue Génie Logiciel (80):36--40, March 2007.

[9]

F. Cottet, J. Delacroix, C. Kaiser, and Z. Mammeri. Scheduling in Real Time Systems John Wiley and Sons Ltd editors, 2002.

[10]

R. I. Davis and A. Burns. Hierarchical Fixed Priority Pre-Emptive Scheduling. In the 26th IEEE International Real-Time Systems Symposium (RTSS'05). Miami, Florida, USA. pages 389--398, December 2005.

Digital Library

[11]

D. Drusinsky. Modeling and Verification using UML State Charts Elsevier inc. editor, 2006.

Digital Library

[12]

M. G. Harbour and J. C. Palencia. Response Time Analysis for Tasks Scheduled under EDF within Fixed Priorities. In Proceedings of the 24th IEEE Real-Time Systems Symposium, Cancun, Mexico December 2003.

Digital Library

[13]

J. E. Hopcroft and J. D. Ullman. Introduction of Automata Theory, Languages and Computation. Addison-Wesley editor, 2001.

Digital Library

[14]

SAE Inc. Architecture Analysis and Design Language (AADL) AS 5506. Technical report, The Engineering Society For Advancing Mobility Land Sea Air and Space, Aerospace Information Report, Version 0.994, August 2004.

[15]

SAE Inc. AADL Annex Behavior (draft V1. 6), AS 5506. Technical report, The Engineering Society For Advancing Mobility Land Sea Air and Space, Aerospace Information Report, March 2007.

[16]

ISO. Ada Reference Manual ISO/IEC 8652:1995(E) with Technical Corrigendum 1 and Amendment 1 (Draft 16).

[17]

ISO 10303-1. Part 1: Overview and fundamental principles 1994.

[18]

ISO 10303-11. Part 11: EXPRESS Language Reference Manual, 1994.

[19]

T. K. Iversen, K. J. Kristoffersen, K. G. Larsen, R. G. Madsen, M. Laursen, S. K. Mortensen, P. Pettersson, and C. B. Thomasen. Model-Checking Real Time Control Programs: Verifying LEGO Mindstorm Systems Using UPPAAL. Technical report, BRICS RS-99-53, December 1999.

[20]

J. Kay and P. Lauder. A Fair Share Scheduler. In Communications of the ACM volume 31, pages 44--45, January 1988.

Digital Library

[21]

J. L. Lawall, G. Muller, and H. Duchesne. Language Design for implementing Process Scheduling Hierarchies. Proceedings of the PEPM'04 conferences. August 24-26, Veronna Italy pages 80--90,2004.

Digital Library

[22]

J. Y. T Leung and M. L. Merril. A note on preemptive scheduling of periodic real time tasks. Information processing Letters 3(11):115--118,1980.

[23]

C. L. Liu and J. W. Layland. Scheduling Algorithms for Multiprogramming in a Hard Real-Time Environnment. Journal of the Association for Computing Machinery 20(1):46--61, January 1973.

Digital Library

[24]

A. Plantec and F. Singhoff Refactoring of an Ada 95 Library with a Meta CASE Tool. Proceedings of the International ACM SIGAda Conference, Albuquerque, USA, November 2006.

Digital Library

[25]

Platypus Technical Summary and download. http://cassoulet.univ-brest.fr/mme/.

[26]

J. A. Pulido, S. Uruena, J. Zamorano, T. Vardanega, and J. A. De la Puente. Hierarchical Scheduling with Ada 2005. Proceedings of the 11th International Conference on Reliable Software Technologies, Porto, Portugal June 2006.

Digital Library

[27]

J. Regehr and J. A. Stankovic. HLS: a Framework for Composing Soft Real-Time Schedulers. In the 22th IEEE International Real-Time Systems Symposium (RTSS'01). London, UK. pages 3--14, December 2001.

Digital Library

[28]

M. Rivas and M. G. Harbour. POSIX-compatible application-defined scheduling in MaRTE OS. In Proceedings of the 14th IEEE Euromicro Conference on Real-Time Systems, Wien, Austria June 2002.

Digital Library

[29]

M. Rivas and M. G. Harbour. Application Defined Scheduling in Ada. Proceedings of the 12th international workshop on Real-time Ada. Viana do Castelo, Portugal. pages 42--51,2003.

Digital Library

[30]

I. Shin and I. Lee. Periodic resource model for compositional real-time guarantees. In 4th IEEE International Real-Time Systems Symposium (RTSS'03)2003.

Digital Library

[31]

F. Singhoff Cheddar Release 2. 0 User's Guide. Technical report, number singhoff-01-2007, Available at http://beru.univ-brest.fr/~./cheddar, February 2007.

[32]

F. Singhoff, J. Legrand, L. Nana, and L. Marcé. Cheddar: a Flexible Real Time Scheduling Framework. Proceedings of the International ACM SIGAda Conference, Atlanta, USA, November 2004.

Digital Library

[33]

F. Singhoff, J. Legrand, L. Nana, and L. Marcé. Scheduling and Memory requirements analysis with AADL. Proceedings of the International ACM SIGAda Conference, Atlanta, USA, November 2005.

Digital Library

[34]

F. Singhoff and A. Plantec. Towards User-Level extensibility of an Ada library: an experiment with Cheddar. Proceedings of the 12th International Conference on Reliable Software Technologies, Ada-Europe. Geneva, LNCS springer-Verlag, June 2007.

Digital Library

[35]

V. Subraminian, C. Gill, C. Sanchez, and H. B. Sipma. Reusable Models for Timing and Liveness Analysis of Middleware for Distributed Real-Time and Embedded systems. Proceedings of the 6th ACM and IEEE International conference on Embedded software EMSOFT '06, October 2006.

Digital Library

[36]

U. Vahalia. UNIX Internals: the new frontiers Prentice Hall, 1996.

Digital Library

Cited By

Feng ZYongwang ZYang LJun S(2024)A Comprehensive Formal Specification of ARINC 653 With Conformity ProofSoftware Testing, Verification and Reliability10.1002/stvr.190135:1Online publication date: Oct-2024
https://doi.org/10.1002/stvr.1901
Zhang FZhang LZhao YLiu YSun J(2023)Refinement-based Specification and Analysis of Multi-core ARINC 653 Using Event-BFormal Aspects of Computing10.1145/361718335:4(1-29)Online publication date: 21-Nov-2023
https://dl.acm.org/doi/10.1145/3617183
Bhushan RYadav D(2022)A Survey on Formal Verification of Separation KernelsRecent Advances in Computer Science and Communications10.2174/266625581366620120715423015:6Online publication date: Jul-2022
https://doi.org/10.2174/2666255813666201207154230
Show More Cited By

Index Terms

AADL modeling and analysis of hierarchical schedulers
1. General and reference
  1. Cross-computing tools and techniques
    1. Validation
2. Software and its engineering
  1. Software creation and management
    1. Software verification and validation
      1. Empirical software validation
      2. Process validation

Recommendations

Validate, simulate, and implement ARINC653 systems using the AADL
SIGAda '09: Proceedings of the ACM SIGAda annual international conference on Ada and related technologies

Safety-critical systems are widely used in different domains and lead to an increasing complexity. Such systems rely on specific services such space and time isolation as in the ARINC653 avionics standard. Their criticality requires a carefully driven ...
AADL modeling and analysis of hierarchical schedulers
SIGAda '07

A system based on a hierarchical scheduler is a system in which the processor is shared between several collaborative schedulers. Such schedulers exist since 1960 and they are becoming more and more investigated and proposed in real-life applications. ...
An Ada design pattern recognition tool for AADL performance analysis

This article deals with performance verification of architecture models of real-time embedded systems. Although real-time scheduling theory provides numerous analytical methods called feasibility tests for scheduling analysis, their use is a complicated ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

SIGAda '07: Proceedings of the 2007 ACM international conference on SIGAda annual international conference

November 2007

116 pages

ISBN:9781595938763

DOI:10.1145/1315580

General Chair:
Alok Srivastava
Northrop Grumman Corporation
,
Program Chair:
Leemon C. Baird
US Air Force Academy

ACM SIGAda Ada Letters Volume XXVII, Issue 3
SIGAda '07
December 2007
93 pages
ISSN:1094-3641
DOI:10.1145/1315607
Issue’s Table of Contents

Copyright © 2007 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 04 November 2007

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

SIGAda '07

Sponsor:

SIGAda '07: ACM SIGAda Annual International Conference

November 4 - 8, 2007

Virginia, Fairfax, USA

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

32
Total Citations
View Citations
445
Total Downloads

Downloads (Last 12 months)4
Downloads (Last 6 weeks)0

Reflects downloads up to 09 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Feng ZYongwang ZYang LJun S(2024)A Comprehensive Formal Specification of ARINC 653 With Conformity ProofSoftware Testing, Verification and Reliability10.1002/stvr.190135:1Online publication date: Oct-2024
https://doi.org/10.1002/stvr.1901
Zhang FZhang LZhao YLiu YSun J(2023)Refinement-based Specification and Analysis of Multi-core ARINC 653 Using Event-BFormal Aspects of Computing10.1145/361718335:4(1-29)Online publication date: 21-Nov-2023
https://dl.acm.org/doi/10.1145/3617183
Bhushan RYadav D(2022)A Survey on Formal Verification of Separation KernelsRecent Advances in Computer Science and Communications10.2174/266625581366620120715423015:6Online publication date: Jul-2022
https://doi.org/10.2174/2666255813666201207154230
Syed AIqbal J(2020)PAD-A: performance antipattern detector for AADLInternational Journal of Information Technology10.1007/s41870-020-00558-xOnline publication date: 22-Nov-2020
https://doi.org/10.1007/s41870-020-00558-x
Wang SLiu BZhang Q(2016)Approach for integrated modular avionics reconfiguration modelling and reliability analysis based on AADLIET Software10.1049/iet-sen.2014.017910:1(18-25)Online publication date: 1-Feb-2016
https://doi.org/10.1049/iet-sen.2014.0179
Zabolotnyi RLeitner PSchulte SDustdar S(2015)SPEEDL - A Declarative Event-Based Language to Define the Scaling Behavior of Cloud ApplicationsProceedings of the 2015 IEEE World Congress on Services10.1109/SERVICES.2015.19(71-78)Online publication date: 27-Jun-2015
https://dl.acm.org/doi/10.1109/SERVICES.2015.19
Wang YMa D(2013)An Automatic Development Process for Integrated Modular Avionics SoftwareJournal of Networks10.4304/jnw.8.5.1088-10958:5Online publication date: 30-May-2013
https://doi.org/10.4304/jnw.8.5.1088-1095
Åsberg MNolte T(2013)Towards a user-mode approach to partitioned scheduling in the seL4 microkernelACM SIGBED Review10.1145/2544350.254435210:3(15-22)Online publication date: 1-Oct-2013
https://dl.acm.org/doi/10.1145/2544350.2544352
Dong YCheng YWu TYe H(2013)On Schedulability Analysis for Embedded Systems with AADL ModelProceedings of the 2013 13th International Conference on Quality Software10.1109/QSIC.2013.28(320-325)Online publication date: 29-Jul-2013
https://dl.acm.org/doi/10.1109/QSIC.2013.28
Pautet L(2013)Introduction to Distributed Embedded and Real‐time SystemsDistributed Systems10.1002/9781118601365.ch6(105-116)Online publication date: 13-Feb-2013
https://doi.org/10.1002/9781118601365.ch6
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents