Advanced

Scheduling Garbage Collection in Embedded Systems

Henriksson, Roger LU (1998)
Abstract
The complexity of systems for automatic control and other safety-critical applications grows rapidly. Computer software represents an increasing part of the complexity. As larger systems are developed, we need to find scalable techniques to manage the complexity in order to guarantee high product quality. Memory management is a key quality factor for these systems. Automatic memory management, or garbage collection, is a technique that significantly reduces the complex problem of correct memory management. The risk of software errors decreases and development time is reduced.



Garbage collection techniques suitable for interactive and soft real-time systems exist, but few approaches are suitable for systems with hard... (More)
The complexity of systems for automatic control and other safety-critical applications grows rapidly. Computer software represents an increasing part of the complexity. As larger systems are developed, we need to find scalable techniques to manage the complexity in order to guarantee high product quality. Memory management is a key quality factor for these systems. Automatic memory management, or garbage collection, is a technique that significantly reduces the complex problem of correct memory management. The risk of software errors decreases and development time is reduced.



Garbage collection techniques suitable for interactive and soft real-time systems exist, but few approaches are suitable for systems with hard real-time requirements, such as control systems (embedded systems). One part of the problem is solved by incremental garbage collection algorithms, which have been presented before. We focus on the scheduling problem which forms the second part of the problem, i.e. how the work of a garbage collector should be scheduled in order to disturb the application program as little as possible. It is studied how a priori scheduling analysis of systems with automatic memory management can be made. The field of garbage collection research is thus joined with the field of scheduling analysis in order to produce a practical synthesis of the two fields.



A scheduling strategy is presented that employs the properties of control systems to ensure that no garbage collection work is performed during the execution of critical processes. The hard real-time part of the system is thus never disturbed by garbage collection work. Existing incremental garbage collection algorithms are adapted to the presented strategy. Necessary modifications of the algorithms and the real-time kernel are discussed. A standard scheduling analysis technique, rate monotonic analysis, is extended in order to make a priori analysis of the schedulability of the garbage collector possible.



The scheduling algorithm has been implemented in an industrially relevant real-time environment in order to show that the strategy is feasible in practice. The experimental evaluation shows that predictable behaviour and sub-millisecond worst-case delays can be achieved on standard hardware even by a non-optimized prototype garbage collector. (Less)
Please use this url to cite or link to this publication:
author
opponent
  • Professor Jul, Eric, Dept. of Computer Science, University of Copenhagen, Denmark
organization
publishing date
type
Thesis
publication status
published
subject
keywords
memory management, garbage collection, real-time, embedded systems, hard deadlines, run-time systems, Systems engineering, scheduling analysis, Data- och systemvetenskap, computer technology
pages
164 pages
publisher
Department of Computer Science, Lund University
defense location
Room E:1406, building E, Lund Institute of Technology, Lund
defense date
1998-09-18 10:15
external identifiers
  • Other:ISRN: LUTEDX/(TECS-1008)/1-164/(1998)
language
English
LU publication?
yes
id
875967b6-fe80-433a-a2bd-82bf1b147848 (old id 18921)
date added to LUP
2007-05-24 12:43:24
date last changed
2016-09-19 08:45:12
@phdthesis{875967b6-fe80-433a-a2bd-82bf1b147848,
  abstract     = {The complexity of systems for automatic control and other safety-critical applications grows rapidly. Computer software represents an increasing part of the complexity. As larger systems are developed, we need to find scalable techniques to manage the complexity in order to guarantee high product quality. Memory management is a key quality factor for these systems. Automatic memory management, or garbage collection, is a technique that significantly reduces the complex problem of correct memory management. The risk of software errors decreases and development time is reduced.<br/><br>
<br/><br>
Garbage collection techniques suitable for interactive and soft real-time systems exist, but few approaches are suitable for systems with hard real-time requirements, such as control systems (embedded systems). One part of the problem is solved by incremental garbage collection algorithms, which have been presented before. We focus on the scheduling problem which forms the second part of the problem, i.e. how the work of a garbage collector should be scheduled in order to disturb the application program as little as possible. It is studied how a priori scheduling analysis of systems with automatic memory management can be made. The field of garbage collection research is thus joined with the field of scheduling analysis in order to produce a practical synthesis of the two fields.<br/><br>
<br/><br>
A scheduling strategy is presented that employs the properties of control systems to ensure that no garbage collection work is performed during the execution of critical processes. The hard real-time part of the system is thus never disturbed by garbage collection work. Existing incremental garbage collection algorithms are adapted to the presented strategy. Necessary modifications of the algorithms and the real-time kernel are discussed. A standard scheduling analysis technique, rate monotonic analysis, is extended in order to make a priori analysis of the schedulability of the garbage collector possible.<br/><br>
<br/><br>
The scheduling algorithm has been implemented in an industrially relevant real-time environment in order to show that the strategy is feasible in practice. The experimental evaluation shows that predictable behaviour and sub-millisecond worst-case delays can be achieved on standard hardware even by a non-optimized prototype garbage collector.},
  author       = {Henriksson, Roger},
  keyword      = {memory management,garbage collection,real-time,embedded systems,hard deadlines,run-time systems,Systems engineering,scheduling analysis,Data- och systemvetenskap,computer technology},
  language     = {eng},
  pages        = {164},
  publisher    = {Department of Computer Science, Lund University},
  school       = {Lund University},
  title        = {Scheduling Garbage Collection in Embedded Systems},
  year         = {1998},
}