Change search
Link to record
Permanent link

Direct link
BETA
Kero, Martin
Publications (7 of 7) Show all publications
Kero, M. (2010). Garbage collection for reactive real-time systems (ed.). (Doctoral dissertation). Paper presented at . Luleå: Luleå tekniska universitet
Open this publication in new window or tab >>Garbage collection for reactive real-time systems
2010 (English)Doctoral thesis, comprehensive summary (Other academic)
Abstract [en]

Predictable use of resources, such as processor time and memory, is a desirable property for virtually any computer system. In real-time computing, static predictability is of particular concern. A real-time system typically maintains an ongoing interaction with its environment, concurrently executing tasks at predefined intervals or as responses to sporadic external events. Its purpose is often safety-critical, where failures to meet deadlines may have severe consequences - even loss of life. The substantial body of research in real-time scheduling theory has demonstrated that a priori guarantees on schedulability are achievable. What is needed is some carefully chosen restrictions on how tasks may interact and what timing behavior external events may exhibit. Safe use of shared resources in real-time systems are enabled by protocols for preserving mutually exclusive access to critical sections, free of deadlocks and priority inversions. The ability to achieve a priori schedulability guarantees can be preserved by taking the imposed restrictions into account. Nonetheless, allowing real-time tasks to share heap allocated data has far more complex consequences than just being a schedulability issue concerning shared resources. In order to guarantee failure free operation, the system must be free of memory related errors, such as memory leaks and dangling pointers. It is well-known that garbage collection can solve these problems. However, incorporating a garbage collector in a real-time system imposes a set of other requirements related to schedulability. This includes provably safe upper-bounds on required execution time and memory of the garbage collector in the presence of concurrently executing tasks, as well as preserved ability to achieve static schedulability guarantees of the real-time tasks. The body of research work towards establishing a priori schedulability guarantees of garbage collected real-time systems has been growing for the past decade. However, most of the existing work lacks a clear identification of the parameters required for and their impact on establishing a provably safe upper-bound on garbage collection execution time. The lack thereof has often imposed overly simplistic models for the cost of garbage collection; and - probably even more alarming - tractability of finding safe bounds of the involved parameters has not been established. Furthermore, most existing approaches require specialized scheduling policies and schedulability tests, as well as intrusive restrictions on the task model.In this dissertation, we propose the following theses: (1) the key to successful realtime garbage collection is to preserve as much as possible of previous advances in realtime scheduling theory by imposing minimal restrictions on the task model, scheduler, and schedulability test; and (2) the keys to enabling a priori schedulability guarantees are clear identification and tractable analysis of the sources of execution time for the garbage collector. Proofs of our theses are based on the run-time behavior of the real-time programming language Timber and an incremental copying garbage collector running as the lowest priority (idle) process.We identify all parameters needed for establishing a safe and tight upper bound on execution time of our collector, where the major ones (not surprisingly for a copying collector) are related to the amount of live heap space. We present a novel technique for establishing safe upper bounds of live heap space parameters for real-time systems. We rely on existing techniques for finding safe upper-bounds of parameters related to heap allocation of each task. Finally, we present the garbage collection demand analysis, decoupled from the schedulability analysis used for the real-time tasks, which determines if our collector is schedulable in the system.

Place, publisher, year, edition, pages
Luleå: Luleå tekniska universitet, 2010. p. 171
Series
Doctoral thesis / Luleå University of Technology 1 jan 1997 → …, ISSN 1402-1544
National Category
Computer Sciences
Research subject
Dependable Communication and Computation Systems
Identifiers
urn:nbn:se:ltu:diva-16886 (URN)0764e640-c1a2-11df-a707-000ea68e967b (Local ID)978-91-7439-144-2 (ISBN)0764e640-c1a2-11df-a707-000ea68e967b (Archive number)0764e640-c1a2-11df-a707-000ea68e967b (OAI)
Note

Godkänd; 2010; 20100916 (keero); DISPUTATION Ämnesområde: Datalogi/Computer Science Opponent: Associate Professor/Senior Lecturer Roger Henriksson, Lunds universitet Ordförande: Chaired Professor Per Lindgren, Luleå tekniska universitet Tid: Tisdag den 26 oktober 2010, kl 09.30 Plats: D770, Luleå tekniska universitet

Available from: 2016-09-29 Created: 2016-09-29 Last updated: 2018-01-10Bibliographically approved
Kero, M., Pietrzak, P. & Nordlander, J. (2010). Live heap space bounds for real-time systems (ed.). In: (Ed.), (Ed.), Programming languages and systems: 8th Asian symposium, APLAS 2010, Shanghai, China, November28 - December 1 2010 : proceedings. Paper presented at Asian Symposium on Programming Languages and Systems : 28/11/2010 - 01/12/2010 (pp. 287-303). Berlin: Encyclopedia of Global Archaeology/Springer Verlag
Open this publication in new window or tab >>Live heap space bounds for real-time systems
2010 (English)In: Programming languages and systems: 8th Asian symposium, APLAS 2010, Shanghai, China, November28 - December 1 2010 : proceedings, Berlin: Encyclopedia of Global Archaeology/Springer Verlag, 2010, p. 287-303Conference paper, Published paper (Refereed)
Place, publisher, year, edition, pages
Berlin: Encyclopedia of Global Archaeology/Springer Verlag, 2010
Series
Lecture Notes in Computer Science, ISSN 0302-9743 ; 6164
National Category
Embedded Systems Computer Sciences
Research subject
Embedded System; Dependable Communication and Computation Systems
Identifiers
urn:nbn:se:ltu:diva-31616 (URN)10.1007/978-3-642-17164-2_20 (DOI)2-s2.0-78650753664 (Scopus ID)5db77730-c1aa-11df-a707-000ea68e967b (Local ID)978-3-642-17163-5 (ISBN)5db77730-c1aa-11df-a707-000ea68e967b (Archive number)5db77730-c1aa-11df-a707-000ea68e967b (OAI)
Conference
Asian Symposium on Programming Languages and Systems : 28/11/2010 - 01/12/2010
Note
Validerad; 2011; 20100916 (keero)Available from: 2016-09-30 Created: 2016-09-30 Last updated: 2018-07-10Bibliographically approved
Kero, M. & Aittamaa, S. (2010). Scheduling garbage collection in realtime systems (ed.). In: (Ed.), (Ed.), CODES/ISSS '10 Proceedings of the eighth IEEE/ACM/IFIP international conference on Hardware/software codesign and system synthesis: . Paper presented at International Conference on Hardware-Software Codesign and System Synthesis : 24/10/2010 - 29/10/2010 (pp. 51-60). New York, NY: ACM Digital Library
Open this publication in new window or tab >>Scheduling garbage collection in realtime systems
2010 (English)In: CODES/ISSS '10 Proceedings of the eighth IEEE/ACM/IFIP international conference on Hardware/software codesign and system synthesis, New York, NY: ACM Digital Library, 2010, p. 51-60Conference paper, Published paper (Refereed)
Abstract [en]

The key to successful deployment of garbage collection in real-time systems is to enable provably safe schedulability tests of the real-time tasks. At the same time one must be able to determine the total heap usage of the system. Schedulability tests typically require a uniformed model of timing assumptions (inter-arrival times, deadlines, etc.). Incorporating the cost of garbage collection in such tests typically requires both artificial timing assumptions of the garbage collector and restricted capabilities of the task scheduler. In this paper, we pursue a different approach. We show how the reactive object model of the programming language Timber enables us to decouple the cost of a concurrently running copying garbage collector from the schedulability of the real-time tasks. I.e., we enable any regular schedulability analysis without the need of incorporating the cost of an interfering garbage collector. We present the garbage collection demand analysis, which determines if the garbage collector can be feasibly scheduled in the system.

Place, publisher, year, edition, pages
New York, NY: ACM Digital Library, 2010
National Category
Embedded Systems
Research subject
Embedded System
Identifiers
urn:nbn:se:ltu:diva-28516 (URN)10.1145/1878961.1878971 (DOI)2-s2.0-78650669388 (Scopus ID)255107c0-c1ab-11df-a707-000ea68e967b (Local ID)978-1-60558-905-3 (ISBN)255107c0-c1ab-11df-a707-000ea68e967b (Archive number)255107c0-c1ab-11df-a707-000ea68e967b (OAI)
Conference
International Conference on Hardware-Software Codesign and System Synthesis : 24/10/2010 - 29/10/2010
Note
Godkänd; 2010; 20100916 (keero)Available from: 2016-09-30 Created: 2016-09-30 Last updated: 2018-07-10Bibliographically approved
Kero, M., Nordlander, J. & Lindgren, P. (2007). A correct and useful incremental copying garbage collector (ed.). In: (Ed.), (Ed.), Proceedings of the the 2007 International Symposium on Memory Management: Québec, Canada, October 21 - 22, 2007. Paper presented at International Symposium on Memory Management : 21/10/2007 - 22/10/2007 (pp. 129-140). New York: ACM Digital Library
Open this publication in new window or tab >>A correct and useful incremental copying garbage collector
2007 (English)In: Proceedings of the the 2007 International Symposium on Memory Management: Québec, Canada, October 21 - 22, 2007, New York: ACM Digital Library, 2007, p. 129-140Conference paper, Published paper (Refereed)
Abstract [en]

Designing a garbage collector with real-time properties is a particularly difficult task, involving the construction of both an incremental run-time algorithm as well as methods enabling a priori reasoning about schedulability in two dimensions (time and memory usage in conjunction). In order to comply with such ambitious goals with any amount of formal rigor, a comprehensive understanding of the actual algorithm used is of course a fundamental requirement. In this paper we present a formal model of an incremental copying garbage collector, where each atomic increment is modeled as a transition between states of a heap process. Soundness of the algorithm is shown by proving that the garbage collecting heap process is weakly bisimilar to a non-collecting heap with infinite storage space. In addition, we show that our collector is both terminating and useful, in the sense that it actually recovers the unreachable parts of any given heap in a finite number of steps.

Place, publisher, year, edition, pages
New York: ACM Digital Library, 2007
National Category
Computer Sciences Embedded Systems
Research subject
Dependable Communication and Computation Systems; Embedded System
Identifiers
urn:nbn:se:ltu:diva-39218 (URN)10.1145/1296907.1296924 (DOI)2-s2.0-42149094957 (Scopus ID)dddc6810-546d-11dc-8e15-000ea68e967b (Local ID)978-1-59593-893-0 (ISBN)dddc6810-546d-11dc-8e15-000ea68e967b (Archive number)dddc6810-546d-11dc-8e15-000ea68e967b (OAI)
Conference
International Symposium on Memory Management : 21/10/2007 - 22/10/2007
Note
Godkänd; 2007; 20070827 (keero)Available from: 2016-10-03 Created: 2016-10-03 Last updated: 2018-07-10Bibliographically approved
Kero, M. (2007). Garbage collecting reactive real-time systems (ed.). (Licentiate dissertation). Paper presented at . Luleå: Luleå tekniska universitet
Open this publication in new window or tab >>Garbage collecting reactive real-time systems
2007 (English)Licentiate thesis, comprehensive summary (Other academic)
Abstract [en]

As real-time systems become more complex, the need for more sophisticated runtime kernel features arises. One such feature that substantially lessens the burden of the programmer is automatic memory management, or garbage collection. However, incorporating garbage collection in a real-time kernel is not an easy task. One needs to guarantee, not only that sufficient memory will be reclaimed in order to avoid out of memory errors, but also that the timing properties of the systems real-time tasks are unaffected. The first step towards such a garbage collector is to define the algorithm in a manageable way. It has to be made incremental in such way that induced pause times are small and bounded (preferably constant). The algorithm should not only be correct, but also provably useful. That is, in order to guarantee that sufficient memory is reclaimed each time the garbage collector is invoked, one need to define some measure of usefulness. Furthermore, the garbage collector must also be guaranteed to be schedulable in the system. That is, even though the collector is correct and proved useful, it still has to be able to do its work within the system. In this thesis, we present a model of an incremental copying garbage collector based on process terms in a labeled transition system. Each kind of garbage collector step is captured as an internal transition and each kind of external heap access (read, write, and allocate) is captured as a labeled transition. We prove correctness and usefulness of the algorithm. We also deploy the garbage collector in a real-time system, to wit, the runtime kernel of Timber. Timber is a strongly typed, object-oriented, purely reactive, real-time programming language based on reactive objects. We show how properties of the language can be used in order to accomplish very efficient and predictable garbage collection.

Place, publisher, year, edition, pages
Luleå: Luleå tekniska universitet, 2007
Series
Licentiate thesis / Luleå University of Technology, ISSN 1402-1757 ; 2007:56
National Category
Computer Sciences
Research subject
Dependable Communication and Computation Systems
Identifiers
urn:nbn:se:ltu:diva-16802 (URN)01767110-984f-11dc-8ccb-000ea68e967b (Local ID)01767110-984f-11dc-8ccb-000ea68e967b (Archive number)01767110-984f-11dc-8ccb-000ea68e967b (OAI)
Note

Godkänd; 2007; 20071121 (ysko)

Available from: 2016-09-29 Created: 2016-09-29 Last updated: 2018-01-10Bibliographically approved
Lindgren, P., Nordlander, J., Kero, M. & Eriksson, J. (2006). Robust real-time applications in Timber (ed.). In: (Ed.), (Ed.), 2006 IEEE International Conference on Electro/information Technology: East Lansing. MI, 7 - 10 May 2006. Paper presented at International Conference on Electro/information Technology : 07/05/2006 - 10/05/2006 (pp. 191-196). Piscataway, NJ: IEEE Communications Society
Open this publication in new window or tab >>Robust real-time applications in Timber
2006 (English)In: 2006 IEEE International Conference on Electro/information Technology: East Lansing. MI, 7 - 10 May 2006, Piscataway, NJ: IEEE Communications Society, 2006, p. 191-196Conference paper, Published paper (Refereed)
Abstract [en]

Embedded systems are often operating under hard real-time constraints, for example in automotive applications. For such systems, robustness and reliability are crucial, which calls for rigorous system design and methodologies for validation. In this paper we advocate a design methodology for robust, realtime systems, based on Timber; a pure reactive system model that allows for formal reasoning about various system properties. We outline how system specifications in Timber can be "compiled" into efficient standalone executables for general light-weight microcontroller platforms. Methods for resource analysis and implications to system dimensioning and validation are further discussed.

Place, publisher, year, edition, pages
Piscataway, NJ: IEEE Communications Society, 2006
National Category
Embedded Systems Computer Sciences
Research subject
Embedded System; Dependable Communication and Computation Systems
Identifiers
urn:nbn:se:ltu:diva-35897 (URN)10.1109/EIT.2006.252112 (DOI)000244481700036 ()2-s2.0-34250903486 (Scopus ID)aa0eb5a0-c70b-11db-98d9-000ea68e967b (Local ID)0-7803-9592-1 (ISBN)aa0eb5a0-c70b-11db-98d9-000ea68e967b (Archive number)aa0eb5a0-c70b-11db-98d9-000ea68e967b (OAI)
Conference
International Conference on Electro/information Technology : 07/05/2006 - 10/05/2006
Note
Godkänd; 2006; 20070228 (ysko)Available from: 2016-09-30 Created: 2016-09-30 Last updated: 2018-07-10Bibliographically approved
Kero, M., Lindgren, P. & Nordlander, J. (2005). Timber as an RTOS for small embedded devices (ed.). In: (Ed.), (Ed.), PREALWSN 2005: proceedings of the First Workshop on Real-World Wireless Sensor Network : Stockholm, Sweden, 20-21 June 2005. Paper presented at Workshop on Real-World Wireless Sensor Networks : 20/06/2005 - 21/06/2005. Kista: Swedish Institute of Computer Science
Open this publication in new window or tab >>Timber as an RTOS for small embedded devices
2005 (English)In: PREALWSN 2005: proceedings of the First Workshop on Real-World Wireless Sensor Network : Stockholm, Sweden, 20-21 June 2005, Kista: Swedish Institute of Computer Science , 2005Conference paper, Published paper (Refereed)
Abstract [en]

Software development for small, real-time and resource constrained, embedded systems is becoming increasingly complex. To be able to guarantee robustness and reliability, the underlying infrastructure should not be based upon ad hoc solutions. In this paper we identify three key features of a minimalistic Real-Time Operating System (RTOS), and presents the run-time system of Timber, a reactive deadlinedriven programming language. We scrutinize the functionalities of the run-time system in the light of real-time requirements, and emphasize the importance of integrating an adequate notion of time, both semantically in the programming interface as well as part of the run-time system.

Place, publisher, year, edition, pages
Kista: Swedish Institute of Computer Science, 2005
Series
SICS Technical Report, ISSN 1100-3154 ; T2005:09
National Category
Embedded Systems Computer Sciences
Research subject
Embedded System; Dependable Communication and Computation Systems
Identifiers
urn:nbn:se:ltu:diva-37001 (URN)adf500f0-5f57-11db-8cbe-000ea68e967b (Local ID)adf500f0-5f57-11db-8cbe-000ea68e967b (Archive number)adf500f0-5f57-11db-8cbe-000ea68e967b (OAI)
Conference
Workshop on Real-World Wireless Sensor Networks : 20/06/2005 - 21/06/2005
Note
Godkänd; 2005; 20060921 (ysko)Available from: 2016-10-03 Created: 2016-10-03 Last updated: 2018-01-14Bibliographically approved
Organisations

Search in DiVA

Show all publications