research-article

Scheduling for Embedded Real-Time Systems

Authors:

Felice Balarin,

Luciano Lavagno,

Praveen Murthy,

Alberto Sangiovanni-vincentelliAuthors Info & Claims

IEEE Design & Test, Volume 15, Issue 1

Pages 71 - 82

https://doi.org/10.1109/54.655185

Published: 01 January 1998 Publication History

Publisher Site

Abstract

Embedded systems are loosely defined as electronic subsystems immersed in a larger physical system (e.g., a car, an airplane, a washing machine, a cellular phone) that implement a given functionality (i.e. a set of tasks) using one or more software-programmable device (e.g. a microcontroller, a Digital Signal Processor). Hence implementing the given functionality in an embedded system involves the partitioning of the tasks into hardware and software components. Since the software has to be executed on a limited set of processing units and several embedded systems are safety critical, deciding the execution sequence for the tasks on the processing units (scheduling) is an important problem to guarantee that the embedded system functions correctly.In this article we review several approaches to software scheduling for real-time embedded computing. In particular, we illustrate scheduling methods for reactive systems (her, the main concern is the speed of response to different inputs from the environment) and for Digital Signal Processing systems (the main concern is the efficient utilization of the processor(s), in the presence of a semi-regular stream of inputs).Given the characteristics of embedded systems, we focus on the scheduling validation problem that aims at answering the question whether a given schedule is guaranteed to satisfy a given set of constraints (deadlines, throughput, and so on).

References

[1]

C. Liu and J.W Layland, "Scheduling Algorithms for Multiprogramming in a Hard Real-Time Environment," ACM J., Jan. 1973, Vol. 20, No. 1, pp. 44-61.

Digital Library

Google Scholar

[2]

N.C. Audsley K.W. Tindell and A. Burns, "The End of the Line for Static Cyclic Scheduling?" Proc. Fifth Euromicro Workshop on Real-Time Systems, IEEE Computer Society Press, Los Alamitos, Calif., 1993, pp. 36-41.

Google Scholar

[3]

N.C. Audsley, et al., "Applying New Scheduling Theory to Static Priority Preemptive Scheduling," Software Engineering J., Vol. 8, No. 5, Sept. 1993, pp. 284-292.

Crossref

Google Scholar

[4]

F. Balarin and A. Sangiovanni-Vincentelli, "Schedule Validation for Embedded Reactive Real-Time Systems," Proc. 34th ACM/IEEE Design Automation Conf., IEEE Computer Society Press, Los Alamitos, Calif., June 1997, pp. 568-571.

Digital Library

Google Scholar

[5]

N. Halbwachs, Synchronous Programming of Reactive Systems, Kluwer Academic Publishers, Dordrect, Boston, 1993.

Digital Library

Google Scholar

[6]

G. Berry P. Couronné and G. Gonthier, "The Synchronous Approach to Reactive and Real-Time Systems," Proc. IEEE, Vol. 79, No. 9, Sept. 1991, pp. 1270-1282.

Crossref

Google Scholar

[7]

R. Reiter, "Scheduling Parallel Computations," ACM J., Vol. 15, No. 4, Oct. 1968.

Digital Library

Google Scholar

[8]

P.K. Murthy and E.A. Lee, "On the Optimal Blocking Factor for Blocked, Non-Overlapped Schedules," Proc. 28th Asilomar Conf. Signals, Systems, and Computers, IEEE CS Press, Vol. 2, Nov. 1994, pp. 1052-1057.

Google Scholar

[9]

G. Liao, et al., "A Comparative Study of Multiprocessor List Scheduling Heuristics," Proc. 27th Hawaii Int'l Conf. System Sciences, Vol. 1, Jan. 1994, pp. 68-77.

Google Scholar

[10]

S.M. Heemstra de Groot S.H. Gerez and O.E. Herrman, "Range-Chart-Guided Iterative Data-Flow Graph Scheduling," IEEE Trans. Circuits and Systems-I Fundamental Theory and Applications, May 1992, Vol. 39, No. 5, pp. 351-364.

Google Scholar

[11]

J.T. Buck, et al., "Ptolemy: A Framework for Simulating and Prototyping Heterogeneous Systems," Int'l J. Computer Simulation, Vol. 4, Apr. 1994.

Google Scholar

[12]

S. Ritz M. Pankert and H. Meyr, "Optimum Vectorization of Scalable Synchronous Dataflow Graphs," Proc. Int'l Conf. Application-Specific Array Processors, IEEE CS Press, 1993.

Google Scholar

[13]

S.S. Bhattacharyya P.K. Murthy and E.A. Lee, Software Synthesis from Dataflow Graphs, Kluwer Academic Publishers, 1996.

Digital Library

Google Scholar

Cited By

View all

Didier KPotop-Butucaru DIooss GCohen ASouyris JBaufreton PGraillat A(2019)Correct-by-Construction Parallelization of Hard Real-Time Avionics Applications on Off-the-Shelf Predictable HardwareACM Transactions on Architecture and Code Optimization10.1145/332879916:3(1-27)Online publication date: 8-Jul-2019
https://dl.acm.org/doi/10.1145/3328799
Pop TPop PEles PPeng Z(2019)Analysis and optimisation of hierarchically scheduled multiprocessor embedded systemsInternational Journal of Parallel Programming10.1007/s10766-007-0059-936:1(37-67)Online publication date: 27-Jan-2019
https://dl.acm.org/doi/10.1007/s10766-007-0059-9
Hamad MHammadeh ZSaidi SPrevelakis VErnst RHaddad HWainwright RChbeir R(2018)Prediction of abnormal temporal behavior in real-time systemsProceedings of the 33rd Annual ACM Symposium on Applied Computing10.1145/3167132.3167172(359-367)Online publication date: 9-Apr-2018
https://dl.acm.org/doi/10.1145/3167132.3167172
Show More Cited By

Scheduling for Embedded Real-Time Systems
1. Computer systems organization
  1. Embedded and cyber-physical systems
2. Software and its engineering
  1. Software organization and properties
    1. Software system structures

Recommendations

Static and Dynamic Variable Voltage Scheduling Algorithms for Real-Time Heterogeneous Distributed Embedded Systems
ASP-DAC '02: Proceedings of the 2002 Asia and South Pacific Design Automation Conference

This paper addresses the problem of static and dynamic variable voltage scheduling of multi-rate periodic task graphs (i.e., tasks with precedence relationships) and aperiodic tasks in heterogeneous distributed real-time embedded systems. Such an ...
Overloads in compositional embedded real-time control systems
RSP '16: Proceedings of the 27th International Symposium on Rapid System Prototyping: Shortening the Path from Specification to Prototype

Component-based design is important for the design of complex embedded software. By properly defining component interfaces, new components can be formed by composing existing components. A newly formed component may be further composed of other ...
Reconfiguration of Synchronous Real-Time Operating System

Real-time scheduling is the theoretical basis of real-time systems engineering. Earliest Deadline first EDF is an optimal scheduling algorithm for uniprocessor real-time systems. The paper deals with Reconfigurable Uniprocessor embedded Real-Time ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

IEEE Design & Test Volume 15, Issue 1

January 1998

88 pages

ISSN:0740-7475

Issue’s Table of Contents

Publisher

IEEE Computer Society Press

Washington, DC, United States

Publication History

Published: 01 January 1998

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

39
Total Citations
View Citations
0
Total Downloads

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

Reflects downloads up to 22 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Didier KPotop-Butucaru DIooss GCohen ASouyris JBaufreton PGraillat A(2019)Correct-by-Construction Parallelization of Hard Real-Time Avionics Applications on Off-the-Shelf Predictable HardwareACM Transactions on Architecture and Code Optimization10.1145/332879916:3(1-27)Online publication date: 8-Jul-2019
https://dl.acm.org/doi/10.1145/3328799
Pop TPop PEles PPeng Z(2019)Analysis and optimisation of hierarchically scheduled multiprocessor embedded systemsInternational Journal of Parallel Programming10.1007/s10766-007-0059-936:1(37-67)Online publication date: 27-Jan-2019
https://dl.acm.org/doi/10.1007/s10766-007-0059-9
Hamad MHammadeh ZSaidi SPrevelakis VErnst RHaddad HWainwright RChbeir R(2018)Prediction of abnormal temporal behavior in real-time systemsProceedings of the 33rd Annual ACM Symposium on Applied Computing10.1145/3167132.3167172(359-367)Online publication date: 9-Apr-2018
https://dl.acm.org/doi/10.1145/3167132.3167172
Mansouri FHuet SHouzet D(2016)A domain-specific high-level programming modelConcurrency and Computation: Practice & Experience10.1002/cpe.362228:3(750-767)Online publication date: 10-Mar-2016
https://dl.acm.org/doi/10.1002/cpe.3622
Qiu MZhang LMing ZChen ZQin XYang L(2013)Security-aware optimization for ubiquitous computing systems with SEAT graph approachJournal of Computer and System Sciences10.1016/j.jcss.2012.11.00279:5(518-529)Online publication date: 1-Aug-2013
https://dl.acm.org/doi/10.1016/j.jcss.2012.11.002
Chen ZQiu MZhang LHu FZhang L(2011)ILP security optimization method for embedded systems with timing constraintsProceedings of the Seventh Annual Workshop on Cyber Security and Information Intelligence Research10.1145/2179298.2179340(1-1)Online publication date: 12-Oct-2011
https://dl.acm.org/doi/10.1145/2179298.2179340
Sirowy SHuang CVahid FSapatnekar S(2010)Online SystemC emulation accelerationProceedings of the 47th Design Automation Conference10.1145/1837274.1837284(30-35)Online publication date: 13-Jun-2010
https://dl.acm.org/doi/10.1145/1837274.1837284
Sirowy SHuang CVahid F(2009)Dynamic acceleration management for SystemC emulationACM SIGBED Review10.1145/1851340.18513456:3(1-4)Online publication date: 1-Oct-2009
https://dl.acm.org/doi/10.1145/1851340.1851345
Ophelders FChakraborty SCorporaal HGebotys CMartin G(2008)Intra- and inter-processor hybrid performance modeling for MPSoC architecturesProceedings of the 6th IEEE/ACM/IFIP international conference on Hardware/Software codesign and system synthesis10.1145/1450135.1450156(91-96)Online publication date: 19-Oct-2008
https://dl.acm.org/doi/10.1145/1450135.1450156
Cheung EHsieh HBalarin FGebotys CMartin G(2008)Software optimization for MPSoCProceedings of the 6th IEEE/ACM/IFIP international conference on Hardware/Software codesign and system synthesis10.1145/1450135.1450146(43-48)Online publication date: 19-Oct-2008
https://dl.acm.org/doi/10.1145/1450135.1450146
Show More Cited By

Abstract

References

Cited By

Recommendations

Static and Dynamic Variable Voltage Scheduling Algorithms for Real-Time Heterogeneous Distributed Embedded Systems

Overloads in compositional embedded real-time control systems

Reconfiguration of Synchronous Real-Time Operating System

Comments

Information

Published In

Publisher

Publication History

Author Tags

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations