Article

Free access

Schedule validation for embedded reactive real-time systems

Authors:

Felice Balarin,

Alberto Sangiovanni-VincentelliAuthors Info & Claims

DAC '97: Proceedings of the 34th annual Design Automation Conference

Pages 52 - 57

https://doi.org/10.1145/266021.266034

Published: 13 June 1997 Publication History

PDF eReader

Abstract

Task scheduling for reactive real time systems is adifficult problem due to tight constraints that theschedule must satisfy.A static priority schemeis proposed here that can be formally validated.The method is applicable both for preemptiveand non-preemptive schedules and is conservativein the sense that a valid schedule may bedeclared invalid, but no invalid schedule may bedeclared valid.Experimental results show thatthe run time of our validation method is negligiblewith respect to other steps in system designprocess, and compares favorably with othermethods of schedule validation.

References

[1]

Neil C. Audsley, Alan Burns, M. Richardson, Ken W. Tindell, and Andy J. Wellings. Applying new scheduling theory to static priority pre-emptive scheduling. Software Engineering Journal, pages 284-292, September 1993.

Crossref

Google Scholar

[2]

Felice Balarin, Harry Hsieh, Attila Jurecska, Luciano Lavagno, and Alberto Sangiovanni-Vincentelli. Formal verification of embedded systems based on CFSM networks. In Proceedings of the 33th A CM/IEEE Design Automation Conference, pages 568-571, June 1996.

Digital Library

Google Scholar

[3]

Felice Balarin, Karl Petty, Alberto L. Sangiovanni- Vincentelli, and Pravin Varaiya. Formal verification of the PATHO real-time operating system. In Proceedings of 33rd Conference on Decision and Control, CDC'94, December 1994.

Crossref

Google Scholar

[4]

Felice Balarin and Alberto Sangiovanni-Vincentelli. Schedule validation for embedded reactive real-time systems. Technical report, Cadence Berkeley Laboratories, October 1996.

Google Scholar

[5]

Massimiliano Chiodo, Paolo Giusto, Harry Hsieh, Attila Jurecska, Luciano Lavagno, and Alberto Sangiovanni- Vincentelli. A formal methodology for hardware/software codesign of embedded systems. IEEE Micro, August 1994.

Digital Library

Google Scholar

[6]

Michael Gonzalez Harbour, Mark H. Klein, and John Lehoczky. Timing analysis for fixed-priority scheduling of hard real-time systems. IEEE Transaction on Software Engineering, 20(1), January 1994.

Digital Library

Google Scholar

[7]

C. L. Liu and James W. Layland. Scheduling algorithms for multiprogramming in a hard-realtime environment. Journal of the Association for Computing Machinery, 20(1):46-61, January 1973.

Digital Library

Google Scholar

Cited By

View all

Zompakis NCatthoor FSoudris D(2016)Efficient Configurations for Dynamic Applications in Next Generation Mobile SystemsHandbook of Research on Next Generation Mobile Communication Systems10.4018/978-1-4666-8732-5.ch006(112-147)Online publication date: 2016
https://doi.org/10.4018/978-1-4666-8732-5.ch006
Balarin FChiodo MGiusto PHsieh HJurecska ALavagno LSangiovanni-Vincentelli ASentovich ESuzuki K(2006)Synthesis of software programs for embedded control applicationsIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/43.76673118:6(834-849)Online publication date: 1-Nov-2006
https://dl.acm.org/doi/10.1109/43.766731
Azzedine ADiguet JPillippe JHenkel JHu XGupta RParameswaran S(2002)Large exploration for HW/SW partitioning of multirate and aperiodic real-time systemsProceedings of the tenth international symposium on Hardware/software codesign10.1145/774789.774807(85-90)Online publication date: 6-May-2002
https://dl.acm.org/doi/10.1145/774789.774807
Show More Cited By

Index Terms

Schedule validation for embedded reactive real-time systems
1. Computer systems organization
  1. Embedded and cyber-physical systems
  2. Real-time systems
2. Theory of computation
  1. Design and analysis of algorithms
    1. Approximation algorithms analysis
      1. Scheduling algorithms
    2. Online algorithms
      1. Online learning algorithms
        Scheduling algorithms
  2. Theory and algorithms for application domains
    1. Machine learning theory
      1. Reinforcement learning
        Sequential decision making

Recommendations

ERfair Scheduler with Processor Suspension for Real-Time Multiprocessor Embedded Systems

Proportional fair schedulers with their ability to provide optimal schedulability along with hard timeliness and quality-of-service guarantees on multiprocessors form an attractive alternative in real-time embedded systems that concurrently run a mix of ...
Experimental Analysis of Timing Validation Methods for Distributed Real-Time Systems

Scheduling jobs dynamically on processors is likely to achieve better performance in multiprocessor and distributed real-time systems. Exhaustive methods for determining whether all jobs complete by their deadlines, in systems that use modern priority-...
Schedulability analysis of EDF-scheduled embedded real-time systems with resource sharing

Earliest Deadline First (EDF) is the most widely studied optimal dynamic scheduling algorithm for uniprocessor real-time systems. In the existing literature, however, there is no complete exact analysis for EDF scheduling when both resource sharing and ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

DAC '97: Proceedings of the 34th annual Design Automation Conference

June 1997

788 pages

ISBN:0897919203

DOI:10.1145/266021

Chairmen:
Ellen J. Yoffa
IBM T. J. Watson Research Center, Yorktown Heights, NY
,
Giovanni De Micheli
Stanford Univ., Stanford, CA
,
Jan M. Rabaey
Univ. of California, Berkeley

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]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 13 June 1997

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

DAC97

Sponsor:

EDAC
SIGDA
IEEE-CAS

DAC97: The 34th Design Automation Conference

June 9 - 13, 1997

California, Anaheim, USA

Acceptance Rates

DAC '97 Paper Acceptance Rate 139 of 400 submissions, 35%;

Overall Acceptance Rate 1,770 of 5,499 submissions, 32%

Upcoming Conference

DAC '25

Sponsor:
sigda

62nd ACM/IEEE Design Automation Conference

June 22 - 26, 2025

San Francisco , CA , USA

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

9
Total Citations
View Citations
74
Total Downloads

Downloads (Last 12 months)41
Downloads (Last 6 weeks)7

Reflects downloads up to 22 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Zompakis NCatthoor FSoudris D(2016)Efficient Configurations for Dynamic Applications in Next Generation Mobile SystemsHandbook of Research on Next Generation Mobile Communication Systems10.4018/978-1-4666-8732-5.ch006(112-147)Online publication date: 2016
https://doi.org/10.4018/978-1-4666-8732-5.ch006
Balarin FChiodo MGiusto PHsieh HJurecska ALavagno LSangiovanni-Vincentelli ASentovich ESuzuki K(2006)Synthesis of software programs for embedded control applicationsIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/43.76673118:6(834-849)Online publication date: 1-Nov-2006
https://dl.acm.org/doi/10.1109/43.766731
Azzedine ADiguet JPillippe JHenkel JHu XGupta RParameswaran S(2002)Large exploration for HW/SW partitioning of multirate and aperiodic real-time systemsProceedings of the tenth international symposium on Hardware/software codesign10.1145/774789.774807(85-90)Online publication date: 6-May-2002
https://dl.acm.org/doi/10.1145/774789.774807
Liu HHu XErnst R(2001)Efficient performance estimation for general real-time task systemsProceedings of the 2001 IEEE/ACM international conference on Computer-aided design10.5555/603095.603192(464-470)Online publication date: 4-Nov-2001
https://dl.acm.org/doi/10.5555/603095.603192
Di Natale MSangiovanni-Vincentelli ABalarin F(2001)Scheduling reactive task graphs in embedded control systemsProceedings Seventh IEEE Real-Time Technology and Applications Symposium10.1109/RTTAS.2001.929886(191-201)Online publication date: 2001
https://doi.org/10.1109/RTTAS.2001.929886
Di Natale MSangiovanni-Vincentelli ABalarin FDe Micheli G(2000)Task scheduling with RT constraintsProceedings of the 37th Annual Design Automation Conference10.1145/337292.337551(483-488)Online publication date: 1-Jun-2000
https://dl.acm.org/doi/10.1145/337292.337551
Hsieh HBalarin FWhite JSentovich E(1999)Synchronous equivalence for embedded systemsProceedings of the 1999 IEEE/ACM international conference on Computer-aided design10.5555/339492.340068(505-510)Online publication date: 7-Nov-1999
https://dl.acm.org/doi/10.5555/339492.340068
Balarin FJerraya ALavagno LVahid F(1999)Worst-case analysis of discrete systems based on conditional abstractionsProceedings of the seventh international workshop on Hardware/software codesign10.1145/301177.301502(115-119)Online publication date: 1-Mar-1999
https://dl.acm.org/doi/10.1145/301177.301502
Balarin FLavagno LMurthy PSangiovanni-vincentelli A(1998)Scheduling for Embedded Real-Time SystemsIEEE Design & Test10.1109/54.65518515:1(71-82)Online publication date: 1-Jan-1998
https://dl.acm.org/doi/10.1109/54.655185

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

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

Cited By

Index Terms

Recommendations

ERfair Scheduler with Processor Suspension for Real-Time Multiprocessor Embedded Systems

Experimental Analysis of Timing Validation Methods for Distributed Real-Time Systems

Schedulability analysis of EDF-scheduled embedded real-time systems with resource sharing