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

Article

Live heap space bounds for real-time systems

Authors:

Paweł Pietrzak,

Johan NordlanderAuthors Info & Claims

APLAS'10: Proceedings of the 8th Asian conference on Programming languages and systems

Pages 287 - 303

Published: 28 November 2010 Publication History

Abstract

Live heap space analyses have so far been concerned with the standard sequential programming model. However, that model is not very well suited for embedded real-time systems, where fragments of code execute concurrently and in orders determined by periodic and sporadic events. Schedulability analysis has shown that the programming model of real-time systems is not fundamentally in conflict with static predictability, but in contrast to accumulative properties like time, live heap space usage exhibits a very state-dependent behavior that renders direct application of schedulability analysis techniques unsuitable.

In this paper we propose an analysis of live heap space upper bounds for real-time systems based on an accurate prediction of task execution orders. The key component of our analysis is the construction of a nondeterministic finite state machine capturing all task executions that are legal under given timing assumptions. By adding heap usage information inferred for each sequential task, our analysis finds an upper bound on the inter-task heap demands as the solution to an integer linear programming problem. Values so obtained are suitable inputs to other analyses depending on the size of a system's persistent state, such as running time prediction for a concurrent tracing garbage collector.

References

[1]

Albert, E., Arenas, P., Genaim, S., Puebla, G., Zanardini, D.: Cost Analysis of Java Bytecode. In: 16th European Symposium on Programming (2007).

Digital Library

[2]

Albert, E., Genaim, S., Gómez-Zamalloa, M.: Live heap space analysis for languages with garbage collection. In: ISMM (2009).

Digital Library

[3]

Albert, E., Genaim, S., Gómez-Zamalloa, M.: Parametric inference of memory requirements for garbage collected languages. In: ISMM (2010).

Digital Library

[4]

Alur, R.: Timed automata. In: Halbwachs, N., Peled, D.A. (eds.) CAV 1999. LNCS, vol. 1633, pp. 8-22. Springer, Heidelberg (1999).

Digital Library

[5]

Alur, R., Dill, D.: A theory of timed automata. Journal of Theoretical Computer Science 126(2) (1994).

Digital Library

[6]

Baker, T.P.: Stack-based scheduling for realtime processes. Real-Time Syst. 3(1), 67-99 (1991).

Digital Library

[7]

Bengtsson, J., Yi, W.: Timed automata: Semantics, algorithms and tools. In: Lectures on Concurrency and Petri Nets (2003).

[8]

Benoy, F., King, A.: Inferring argument size relationships with CLPR. In: Workshop on Logic-based Program Synthesis and Transformation (1997).

Digital Library

[9]

Chin, W.N., Nguyen, H.H., Popeea, C., Qin, S.: Analysing memory resource bounds for low-level programs. In: ISMM (2008).

Digital Library

[10]

Courcoubetis, C., Yannakakis, M.: Minimum and maximum delay problems in real-time systems. Formal Methods in System Design 1(4) (1992).

Digital Library

[11]

Cousot, P., Halbwachs, N.: Automatic discovery of linear restraints among variables of a program. In: POPL (1978).

Digital Library

[12]

Jaffar, J., Maher, M., Marriott, K., Stuckey, P.: The semantics of constraint logic programs. Journal of Logic Programming 37 (1-3) (1998).

[13]

Jaffar, J., Maher, M.J.: Constraint logic programming: A survey. Journal of Logic Programming 19 & 20 (1994).

[14]

Jost, S., Loid, H.W., Hammond, K., Hofmann, M.: Static determination of quantitative resource usage for higher-order programs. In: POPL (2010).

Digital Library

[15]

Kero, M., Aittamaa, S.: Scheduling garbage collection in real-time systems. In: CODES (2010).

Digital Library

[16]

Krishna, C.M., Shin, K.G.: Real-Time Systems. McGraw-Hill, New York (1997).

Digital Library

[17]

Nordlander, J., Carlsson, M., Gill, A., Lindgren, P., von Sydow, B.: The Timber home page (2008), http://timber-lang.org

[18]

Unnikrishnan, L., Stoller, S.D., Liu, Y.A.: Optimized live heap bound analysis. In: Zuck, L.D., et al. (eds.) VMCAI 2003. LNCS, vol. 2575, pp. 70-85. Springer, Heidelberg (2002).

Digital Library

Cited By

Albert ECorreas JPuebla GRomán-Díez GKiselyov OThompson S(2012)Incremental resource usage analysisProceedings of the ACM SIGPLAN 2012 workshop on Partial evaluation and program manipulation10.1145/2103746.2103754(25-34)Online publication date: 23-Jan-2012
https://dl.acm.org/doi/10.1145/2103746.2103754
Albert EGenaim SGómez-Zamalloa MJohnsen ESchlatte RTarifa S(2011)Simulating concurrent behaviors with worst-case cost boundsProceedings of the 17th international conference on Formal methods10.5555/2021296.2021333(353-368)Online publication date: 20-Jun-2011
https://dl.acm.org/doi/10.5555/2021296.2021333
Albert EArenas PGenaim SGómez-Zamalloa MPuebla G(2011)Cost analysis of concurrent OO programsProceedings of the 9th Asian conference on Programming Languages and Systems10.1007/978-3-642-25318-8_19(238-254)Online publication date: 5-Dec-2011
https://dl.acm.org/doi/10.1007/978-3-642-25318-8_19

Live heap space bounds for real-time systems
1. Software and its engineering
  1. Software organization and properties
    1. Software system structures

Recommendations

Live heap space analysis for languages with garbage collection
ISMM '09: Proceedings of the 2009 international symposium on Memory management

The peak heap consumption of a program is the maximum size of the live data on the heap during the execution of the program, i.e., the minimum amount of heap space needed to run the program without exhausting the memory. It is well-known that garbage ...
Bounding Worst Case Garbage Collection Time for Embedded Real-Time Systems
RTAS '00: Proceedings of the Sixth IEEE Real Time Technology and Applications Symposium (RTAS 2000)

Execution of programs with various data structures often requires dynamic memory management based on garbage collection for better productivity, robustness, and program integrity. In spite of its benefits, garbage collection has not been widely used in ...
Controlling garbage collection and heap growth to reduce the execution time of Java applications

In systems that support garbage collection, a tension exists between collecting garbage too frequently and not collecting it frequently enough. Garbage collection that occurs too frequently may introduce unnecessary overheads at the risk of not ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Guide Proceedings

APLAS'10: Proceedings of the 8th Asian conference on Programming languages and systems

November 2010

456 pages

ISBN:364217163X

Editor:
Kazunori Ueda
Dept. of Computer Science and Engineering, Waseda University, Tokyo, Japan

Sponsors

AAFS: Asian Association for Foundation of Software
Shanghai Jiao Tong University: Shanghai Jiao Tong University

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 28 November 2010

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

3
Total Citations
View Citations
0
Total Downloads

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

Reflects downloads up to 04 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Albert ECorreas JPuebla GRomán-Díez GKiselyov OThompson S(2012)Incremental resource usage analysisProceedings of the ACM SIGPLAN 2012 workshop on Partial evaluation and program manipulation10.1145/2103746.2103754(25-34)Online publication date: 23-Jan-2012
https://dl.acm.org/doi/10.1145/2103746.2103754
Albert EGenaim SGómez-Zamalloa MJohnsen ESchlatte RTarifa S(2011)Simulating concurrent behaviors with worst-case cost boundsProceedings of the 17th international conference on Formal methods10.5555/2021296.2021333(353-368)Online publication date: 20-Jun-2011
https://dl.acm.org/doi/10.5555/2021296.2021333
Albert EArenas PGenaim SGómez-Zamalloa MPuebla G(2011)Cost analysis of concurrent OO programsProceedings of the 9th Asian conference on Programming Languages and Systems10.1007/978-3-642-25318-8_19(238-254)Online publication date: 5-Dec-2011
https://dl.acm.org/doi/10.1007/978-3-642-25318-8_19

View Options

View options

Media

Figures

Other

Tables

View Table of Contents