More Web Proxy on the site http://driver.im/

research-article

Semantics-preserving implementation of multirate mixed-criticality synchronous programs

Author:

Sanjoy BaruahAuthors Info & Claims

RTNS '12: Proceedings of the 20th International Conference on Real-Time and Network Systems

Pages 11 - 19

https://doi.org/10.1145/2392987.2392989

Published: 08 November 2012 Publication History

Abstract

Model-based design methodologies such as Simulink/ State-flow, that are based on the synchrony assumption, are widely used in many safety-critical application domains including avionics and automotive systems. The synchrony assumption asserts that actions (such as the execution of code) occur instantaneously. However, actual platforms obviously do not satisfy the synchrony assumption. This paper considers the problem of obtaining resource-efficient implementations of programs that are written under the synchrony assumption on actual platforms, such that these implementations execute in a manner that is semantically consistent with the execution sequences that would occur if the synchrony assumption were to hold.

References

[1]

N. C. Audsley. Optimal priority assignment and feasibility of static priority tasks with arbitrary start times. Technical report, The University of York, England, 1991.

[2]

S. Baruah and G. Fohler. Certification-cognizant time-triggered scheduling of mixed-criticality systems. In Proceedings of the IEEE Real-Time Systems Symposium (RTSS), Vienna, Austria, 2011. IEEE Computer Society Press.

Digital Library

[3]

S. Baruah, H. Li, and L. Stougie. Towards the design of certifiable mixed-criticality systems. In Proceedings of the IEEE Real-Time Technology and Applications Symposium (RTAS). IEEE, April 2010.

Digital Library

[4]

S. K. Baruah, V. Bonifaci, G. D'Angelo, H. Li, A. Marchetti-Spaccamela, N. Megow, and L. Stougie. Scheduling real-time mixed-criticality jobs. IEEE Transactions on Computers. To appear.

Digital Library

[5]

S. Bensalem, P. Caspi, C. Parent-Vigouroux, and C. Dumas. A methodology for proving control systems with Lustre and PVS. Dependable Computing for Critical Applications, 1999.

Digital Library

[6]

A. Benveniste and G. Berry. The synchronous approach to reactive and real-time systems. Proceedings of the IEEE, 79(9):1270--1282, sep 1991.

[7]

G. Fohler. Changing operational modes in the context of pre run-time scheduling. IEICE Transactions on Information and Systems (Special Issue on Responsive Computer Systems), E76--D(11):1333--1340, 1993.

[8]

M. Garey and D. Johnson. Complexity results for multiprocessor scheduling under resource constraints. SIAM Journal of Computing, 4:397--411, 1975.

[9]

N. Halbwachs. Synchronous programming of reactive systems. Kluwer Academic Publisherss, 1993.

Digital Library

[10]

N. Halbwachs and P. Raymond. Validation of synchronous reactive systems: from formal verification to automatic testing. In ASIAN'99, Asian Computing Science Conference, Phuket (Thailand), Dec. 1999. LNCS 1742, Springer Verlag.

Digital Library

[11]

T. Henzinger and J. Sifakis. The embedded systems design challenge. In Proceedings of the 14th International Symposium on Formal Methods (FM), Lecture Notes in Computer Science. Springer, August 2006.

Digital Library

[12]

L. J. Jagadeesan, C. Puchol, and J. E. Olnhausen. A formal approach to reactive systems software: A telecommunications application in Esterel. Formal Methods in System Design, 8:123--151, 1996.

Digital Library

[13]

H. Kopetz. Real-Time Systems - Design Principles for Distributed Embedded Applications. Springer, 2011.

Digital Library

[14]

T.-W. Kuo and A. K. Mok. Load adjustment in adaptive real-time systems. In Proceedings of the IEEE Real-Time Systems Symposium, pages 160--171, 1991.

[15]

C. Liu and J. Layland. Scheduling algorithms for multiprogramming in a hard real-time environment. Journal of the ACM, 20(1):46--61, 1973.

Digital Library

[16]

A. Mok. Fundamental Design Problems of Distributed Systems for The Hard-Real-Time Environment. PhD thesis, Laboratory for Computer Science, Massachusetts Institute of Technology, 1983. Available as Technical Report No. MIT/LCS/TR-297.

Digital Library

[17]

M. D. Natale and H. Zeng. Task implementation and schedulability analysis of synchronous finite state machines. In Work in Progress (WiP) session of the IEEE Real-Time and Embedded Technology And Applications Symposium, pages 21--24, Apr. 2011.

[18]

E. Vecchié and R. de Simone. Syntax-driven behavior partitioning for model-checking of Esterel programs. Electron. Notes Theor. Comput. Sci., 153:19--35, June 2006.

Digital Library

Cited By

Marron ACohen IFrankel GHarel DSzekely S(2024)Challenges in Modeling and Unmodeling Complex Reactive Systems: Interaction Networks, Reaction to Emergent Effects, Reactive Rule Composition, and Multiple Time ScalesModel-Driven Engineering and Software Development10.1007/978-3-031-66339-0_7(137-157)Online publication date: 6-Sep-2024
https://doi.org/10.1007/978-3-031-66339-0_7
Jiang XSha TLiu DChen JChen CHuang K(2022)Flexible and Dynamic Scheduling of Mixed-Criticality SystemsSensors10.3390/s2219752822:19(7528)Online publication date: 4-Oct-2022
https://doi.org/10.3390/s22197528
Naderlinger ASon YHaas P(2019)Harnessing concurrency in synchronous block diagrams to parallelize simulation on multi-core hostsProceedings of the Winter Simulation Conference10.5555/3400397.3400451(702-713)Online publication date: 8-Dec-2019
https://dl.acm.org/doi/10.5555/3400397.3400451
Show More Cited By

Index Terms

Semantics-preserving implementation of multirate mixed-criticality synchronous programs
1. Computer systems organization
  1. Embedded and cyber-physical systems
    1. Embedded systems
2. Software and its engineering
  1. Software organization and properties
    1. Software system structures
      1. Embedded software
      2. Real-time systems software

Recommendations

Optimized Implementation of Multirate Mixed-Criticality Synchronous Reactive Models
Special Section of IDEA: Integrating Dataflow, Embedded Computing, and Architecture

Model-based design using Synchronous Reactive (SR) models enables early design and verification of application functionality in a platform-independent manner, and the implementation on the target platform should guarantee the preservation of application ...
Semantics-preserving multitask implementation of synchronous programs

We study the implementation of a synchronous program as a set of multiple tasks running on the same computer, and scheduled by a real-time operating system using some preemptive scheduling policy, such as fixed priority or earliest-deadline first. ...
Multi-task Implementation of Multi-periodic Synchronous Programs

This article presents a complete scheme for the integration and the development of multi-periodic critical embedded systems. A system is formally specified as a modular and hierarchical assembly of several locally mono-periodic synchronous functions ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Other conferences

RTNS '12: Proceedings of the 20th International Conference on Real-Time and Network Systems

November 2012

216 pages

ISBN:9781450314091

DOI:10.1145/2392987

General Chairs:
Liliana Cucu-Grosjean
INRIA Nancy-Grand Est, France
,
Nicolas Navet
University of Luxembourg, Luxembourg
,
Program Chairs:
Christine Rochange
University of Toulouse/IRIT, France
,
James H. Anderson
University of North Carolina

Copyright © 2012 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

University of Lorraine: University of Lorraine
INRIA: Institut Natl de Recherche en Info et en Automatique
GDR ASR: GDR Architecture, Systèmes et Réseaux

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 08 November 2012

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Research-article

Funding Sources

Conference

RTNS '12

Sponsor:

University of Lorraine
INRIA
GDR ASR

RTNS '12: 20th International Conference on Real-Time and Network Systems

November 8 - 9, 2012

Pont à Mousson, France

Acceptance Rates

Overall Acceptance Rate 119 of 255 submissions, 47%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

26
Total Citations
View Citations
219
Total Downloads

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

Reflects downloads up to 12 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Marron ACohen IFrankel GHarel DSzekely S(2024)Challenges in Modeling and Unmodeling Complex Reactive Systems: Interaction Networks, Reaction to Emergent Effects, Reactive Rule Composition, and Multiple Time ScalesModel-Driven Engineering and Software Development10.1007/978-3-031-66339-0_7(137-157)Online publication date: 6-Sep-2024
https://doi.org/10.1007/978-3-031-66339-0_7
Jiang XSha TLiu DChen JChen CHuang K(2022)Flexible and Dynamic Scheduling of Mixed-Criticality SystemsSensors10.3390/s2219752822:19(7528)Online publication date: 4-Oct-2022
https://doi.org/10.3390/s22197528
Naderlinger ASon YHaas P(2019)Harnessing concurrency in synchronous block diagrams to parallelize simulation on multi-core hostsProceedings of the Winter Simulation Conference10.5555/3400397.3400451(702-713)Online publication date: 8-Dec-2019
https://dl.acm.org/doi/10.5555/3400397.3400451
Naderlinger A(2019)Harnessing Concurrency in Synchronous Block Diagrams to Parallelize Simulation on Multi-Core Hosts2019 Winter Simulation Conference (WSC)10.1109/WSC40007.2019.9004866(702-713)Online publication date: Dec-2019
https://doi.org/10.1109/WSC40007.2019.9004866
Socci DPoplavko PBensalem SBozga M(2019)Priority-based scheduling of mixed-critical jobsReal-Time Systems10.1007/s11241-019-09329-9Online publication date: 4-Mar-2019
https://doi.org/10.1007/s11241-019-09329-9
Abdullah JDai GMohaqeqi MYi W(2018)Schedulability Analysis and Software Synthesis for Graph-Based Task Models with Resource Sharing2018 IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS)10.1109/RTAS.2018.00034(261-270)Online publication date: Apr-2018
https://doi.org/10.1109/RTAS.2018.00034
Naderlinger A(2017)Simulating preemptive scheduling with timing-aware blocks in simulinkProceedings of the Conference on Design, Automation & Test in Europe10.5555/3130379.3130563(758-763)Online publication date: 27-Mar-2017
https://dl.acm.org/doi/10.5555/3130379.3130563
Naderlinger A(2017)Simulating preemptive scheduling with timing-aware blocks in SimulinkDesign, Automation & Test in Europe Conference & Exhibition (DATE), 201710.23919/DATE.2017.7927091(758-763)Online publication date: Mar-2017
https://doi.org/10.23919/DATE.2017.7927091
Burns ADavis R(2017)A Survey of Research into Mixed Criticality SystemsACM Computing Surveys10.1145/313134750:6(1-37)Online publication date: 22-Nov-2017
https://dl.acm.org/doi/10.1145/3131347
Behera LBhaduri P(2017)Time-Triggered Scheduling of Mixed-Criticality SystemsACM Transactions on Design Automation of Electronic Systems10.1145/307341522:4(1-25)Online publication date: 15-Jun-2017
https://dl.acm.org/doi/10.1145/3073415
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