Worst-case analysis of heap allocations

Wolfgang Puffitsch; Benedikt Huber; Martin Schoeberl

doi:10.1007/978-3-642-16561-0_42

Worst-case analysis of heap allocations

Wolfgang Puffitsch
, Benedikt Huber
, Martin Schoeberl

Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review

690 Downloads (Orbit)

Abstract

In object oriented languages, dynamic memory allocation is a fundamental concept. When using such a language in hard real-time systems, it becomes important to bound both the worst-case execution time and the worst-case memory consumption. In this paper, we present an analysis to determine the worst-case heap allocations of tasks. The analysis builds upon techniques that are well established for worst-case execution time analysis. The difference is that the cost function is not the execution time of instructions in clock cycles, but the allocation in bytes. In contrast to worst-case execution time analysis, worst-case heap allocation analysis is not processor dependent. However, the cost function depends on the object layout of the runtime system. The analysis is evaluated with several real-time benchmarks to establish the usefulness of the analysis, and to compare the memory consumption of different object layouts.

Original language	English
Title of host publication	Leveraging Applications of Formal Methods, Verification and Validation : 4th International Symposium On Leveraging Applications (ISoLA 2010)
Number of pages	498
Volume	2
Publisher	Springer
Publication date	2010
Edition	1
Pages	464-478
ISBN (Print)	978-3-642-16560-3
DOIs	https://doi.org/10.1007/978-3-642-16561-0_42
Publication status	Published - 2010
Event	4th International Symposium On Leveraging Applications of Formal Methods, Verification and Validation - Amirande, Heraklion, Greece Duration: 18 Oct 2010 → 20 Oct 2010 Conference number: 4 http://www.isola-conference.org/isola2010/

Conference

Conference	4th International Symposium On Leveraging Applications of Formal Methods, Verification and Validation
Number	4
Location	Amirande
Country/Territory	Greece
City	Heraklion
Period	18/10/2010 → 20/10/2010
Internet address	http://www.isola-conference.org/isola2010/

Series	Lecture Notes in Computer Science
Number	6416
ISSN	0302-9743

Access to Document

10.1007/978-3-642-16561-0_42

WcmemSubmitted manuscript, 321 KB

OpenUrl availability

Full text

Cite this

@inproceedings{d62447869a2146098d79de91b82bc92c,

title = "Worst-case analysis of heap allocations",

abstract = "In object oriented languages, dynamic memory allocation is a fundamental concept. When using such a language in hard real-time systems, it becomes important to bound both the worst-case execution time and the worst-case memory consumption. In this paper, we present an analysis to determine the worst-case heap allocations of tasks. The analysis builds upon techniques that are well established for worst-case execution time analysis. The difference is that the cost function is not the execution time of instructions in clock cycles, but the allocation in bytes. In contrast to worst-case execution time analysis, worst-case heap allocation analysis is not processor dependent. However, the cost function depends on the object layout of the runtime system. The analysis is evaluated with several real-time benchmarks to establish the usefulness of the analysis, and to compare the memory consumption of different object layouts.",

author = "Wolfgang Puffitsch and Benedikt Huber and Martin Schoeberl",

year = "2010",

doi = "10.1007/978-3-642-16561-0\_42",

language = "English",

isbn = "978-3-642-16560-3",

volume = "2",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

number = "6416",

pages = "464--478",

booktitle = "Leveraging Applications of Formal Methods, Verification and Validation",

edition = "1",

note = "4th International Symposium On Leveraging Applications of Formal Methods, Verification and Validation, ISoLA 2010 ; Conference date: 18-10-2010 Through 20-10-2010",

url = "http://www.isola-conference.org/isola2010/",

}

Puffitsch, W, Huber, B & Schoeberl, M 2010, Worst-case analysis of heap allocations. in Leveraging Applications of Formal Methods, Verification and Validation: 4th International Symposium On Leveraging Applications (ISoLA 2010). 1 edn, vol. 2, Springer, Lecture Notes in Computer Science, no. 6416, pp. 464-478, 4th International Symposium On Leveraging Applications of Formal Methods, Verification and Validation, Heraklion, Greece, 18/10/2010. https://doi.org/10.1007/978-3-642-16561-0_42

Worst-case analysis of heap allocations. / Puffitsch, Wolfgang; Huber, Benedikt; Schoeberl, Martin.
Leveraging Applications of Formal Methods, Verification and Validation: 4th International Symposium On Leveraging Applications (ISoLA 2010). Vol. 2 1. ed. Springer, 2010. p. 464-478 (Lecture Notes in Computer Science; No. 6416).

Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review

TY - GEN

T1 - Worst-case analysis of heap allocations

AU - Puffitsch, Wolfgang

AU - Huber, Benedikt

AU - Schoeberl, Martin

N1 - Conference code: 4

PY - 2010

Y1 - 2010

N2 - In object oriented languages, dynamic memory allocation is a fundamental concept. When using such a language in hard real-time systems, it becomes important to bound both the worst-case execution time and the worst-case memory consumption. In this paper, we present an analysis to determine the worst-case heap allocations of tasks. The analysis builds upon techniques that are well established for worst-case execution time analysis. The difference is that the cost function is not the execution time of instructions in clock cycles, but the allocation in bytes. In contrast to worst-case execution time analysis, worst-case heap allocation analysis is not processor dependent. However, the cost function depends on the object layout of the runtime system. The analysis is evaluated with several real-time benchmarks to establish the usefulness of the analysis, and to compare the memory consumption of different object layouts.

AB - In object oriented languages, dynamic memory allocation is a fundamental concept. When using such a language in hard real-time systems, it becomes important to bound both the worst-case execution time and the worst-case memory consumption. In this paper, we present an analysis to determine the worst-case heap allocations of tasks. The analysis builds upon techniques that are well established for worst-case execution time analysis. The difference is that the cost function is not the execution time of instructions in clock cycles, but the allocation in bytes. In contrast to worst-case execution time analysis, worst-case heap allocation analysis is not processor dependent. However, the cost function depends on the object layout of the runtime system. The analysis is evaluated with several real-time benchmarks to establish the usefulness of the analysis, and to compare the memory consumption of different object layouts.

U2 - 10.1007/978-3-642-16561-0_42

DO - 10.1007/978-3-642-16561-0_42

M3 - Article in proceedings

SN - 978-3-642-16560-3

VL - 2

T3 - Lecture Notes in Computer Science

SP - 464

EP - 478

BT - Leveraging Applications of Formal Methods, Verification and Validation

PB - Springer

T2 - 4th International Symposium On Leveraging Applications of Formal Methods, Verification and Validation

Y2 - 18 October 2010 through 20 October 2010

ER -

Worst-case analysis of heap allocations

Abstract

Conference

Access to Document

OpenUrl availability

Fingerprint

Cite this