Dr. Fridtjof Siebert
Program Committees / Review Committees2011: ISMM, JTRES
2009: ISMM, JTRES
ProjectsJEOPARD: Technical Leader
Limits of Parallel Marking Garbage Collection
ISMM'08 - International Symposium on Memory Management - 7-8 June 2008, Tucson, Arizona, USA
More and more, parallel multicore systems will be used even in low-end devices such as embedded controllers that require realtime guarantees. When garbage collection is used in these systems, parallel or concurrent garbage collection brings important performance advantages. In the context of realtime systems, it has to be shown that a parallel garbage collector implementation not only performs well in most cases, but guarantees on its performance in the worst case are required.
This paper analyses the difficulties a parallel mark-and-sweep garbage collector faces during a parallel mark phase. The performance of such a garbage collector degrades when only some of the available processors can perform scanning work in the mark phase. Whenever the $grey$ set contains fewer elements than the number of available processors, some processors may be stalled waiting for new objects to be added to the $grey$ set. This paper gives an upper bound for the number of stalls that may occur as a function of simple properties of the memory graph.
This upper bound is then determined for the Java applications that are part of the SPECjvm98 benchmark suite and the theoretical worst-case scalability of a parallel mark phase is analysed. The presented approach is then applied to a Java virtual machine that has uniform mark steps, which at first results in poor worst-case scalability. A small change in the implementation is then proposed and analysed to achieve good scalability even in the worst case.
Download: PDF (231kB)
Realtime Garbage Collection in the JamaicaVM 3.0
JTRES'07 - The 5th International Workshop on Java Technologies for Real-time and Embedded Systems - JTRES 2007, 26-28 September 2007, Vienna, Austria
This paper provides an overview of the realtime garbage collector used by the RTSJ Java Virtual Machine JamaicaVM. A particular emphasis will be made on the improvements made in with release 3.0 JamaicaVM.
The JamaicaVM garbage collector is incremental to an extreme extent: single incremental steps of the garbage collector correspond to scanning only 32 bytes of memory and have a worst-case execution time in the order of one usec. The JamaicaVM garbage collector uses automatic pacing, making the system easier to configure than a garbage collector using explicit pacing that requires information on the application's allocation rate.
The recent improvements of the garbage collector that will be present in this paper include support for automatic heap expansion; reduction of the memory overhead for garbage collector internal structures; and significant performance optimisation such as a faster write-barrier and a sweep phase that does not need to touch the objects and therefore reduces the number of cache misses caused during sweep.
Download: PDF (226kB)
Proving the Absence of RTSJ Related Runtime Errors through Data Flow Analysis
JTRES'06 - The 4th International Workshop on Java Technologies for Real-time and Embedded Systems - JTRES 2006, 11-13 October 2006, Paris, France
The Real-Time Specification for Java (RTSJ) introduces region based memory management to avoid the need for garbage collection. This region based memory management, however, introduces new possible runtime errors. To ensure that an application developed with the Real-Time Specification for Java executes correctly, it has to be proven that no runtime errors occur.
The use of program-wide pointer analysis for the proof of absence of runtime error conditions such as null pointer uses or illegal casts is still not widespread. Current uses of program-wide pointer analysis focus on applying the results for optimisations in compilers, where a low accuracy of the results leads to missed opportunities for optimisation, which is often tolerable.
This papers presents the application of a program-wide data flow analysis to prove the absence of memory related runtime errors such as those introduced by the RTSJ.
Download: PDF (136kB)
Analysis Tools for the HIJA Safety-Critical Java Model
DASIA'05 - Data Systems In Aerospace - 30th May to 2nd June 2005, Edinburgh, Scotland.
The European project HIJA (High-Integrity Java) started its work on defining and implementing a new High-Integrity Java for future networked real-time embedded systems in June 2004. Based on the features of the Realtime Specification for Java (RTSJ), a safety-critical profile is defined. This profile provides a restricted subset with the aim to permit certification up the DO178B level A.
The aspects covered by the profile address the supported thread model, synchronization mechanism, memory model and annotations that permit tools to perform correctness verification. In parallel, formal verification tools are developed to proof the functional and non-functional (resource use, etc.) correctness of an application.
Download: PDF (133k)
The Impact of Realtime Garbage Collection on Realtime Java Programming
ISORC'04 - The 7th IEEE International Symposium on Object-oriented Real-time distributed Computing, May 12-14, 2004, Vienna, Austria
Extensions like the Real-Time Specification for Java (RTSJ) enable the use of Java in more and more time-critical application domains. The RTSJ enables the development of realtime code in Java even though a classical garbage collector causes unpredictable pauses to non-realtime code.
This presentation gives an overview of how a modern realtime garbage collectors operates. It presents the impact this has on the developer of complex applications that need to perform time-critical and non-time-critical tasks. The use of realtime garbage collection technology simplifies the application development even in systems that do not use dynamic memory allocation within realtime code.
Download: PDF (306k)
Bringing the Full Power of Java Technology to Embedded Realtime Applications
MSy'02 Embedded Systems in Mechatronics, 3.-4. Oct 2002, Winterthur, Switzerland
Download: PDF (320k)
Bringing the full power of Java Technology to embedded realtime applications.
Embedded Systems Show, London, 15-16 May 2002
Java technology brings a variety of advantages for the development of software for embedded systems. Nevertheless, features like automatic memory management (garbage collection) in Java pose challenges that need to be solved by a Java implementation that is to be used in realtime systems. This presentation gives an overview over different techniques used by Java implementations and their usefulness for realtime system development. It will be explained how a deterministic Java implementation can work and how it can bring the full power of Java's features even to time critical code.
Download: PDF (303k)
Bringing Java Technology to embedded realtime applications.
Bits&Chips, Eindhoven, 16 April 2002
Download: PDF (268k)
JamaicaVM -- Java Technology for Embedded Realtime Systems
Java User Group Stuttgart (JUGS), Hohenheim, 25 Oct 2001
João Ventura, Fridtjof Siebert, Andy Walter and James Hunt
Download: PDF (228k)
HIDOORS - A High Integrity Distributed Deterministic Java Environment
Seventh IEEE International Workshop on Object-oriented Real-time Dependable Systems (WORDS), San Diego, 7.-9. January 2002
Fridtjof Siebert (aicas GmbH)
This paper presents the design of HIDOORS, an intergrated deveopment environment suitable for embedded distributed real-time sytems, based on the Java programming language. HIDOORS will cover all the life-cycle of real-time software development with extensions to existing tools (UML modeling, Java compiler, Java Virtual Machine, and a worst case execution time analysis tool) that will all be integrated into a single integrated development environment. The sytem will also assist the developer in distributing the application, by providing faster RMI and a distributed event managert that provides strict timing guarantees. This paper is written at the beginning of HIDDORS development, and as such, it presents only the defined objectives and the early architecture of the sytem; further developments will be the subject of future work.
paper (gzip'ed Postscript, 108KB)
slides (PDF, 1,8Meg)
Hard Realtime Garbage Collection in Modern Object Oriented Programming Languages.
PhD thesis, University of Karlsruhe, 2002
Fridtjof Siebert (aicas GmbH) and Andy Walter (aicas GmbH)
Modern object oriented programming languages rely on the concept of automatic garbage collection to provide safe memory management. Even though a lot of research in the area of automatic memory management has been carried out in recent decades, typical implementations of garbage collectors still fail to give useful or proven realtime guarantees on their runtime performance.
The author presents techniques that enable one to give these guarantees. He provides solutions for the problem areas of memory fragmentations, accurate root scanning, limiting garbage collection overhead, and ensuring that memory is recycled sufficiently fast.
Download: available here (EUR 49,-)
Deterministic Execution of Java's Primitive Bytecode Operations
Java Virtual Machine Research & Technology Symposium '01 (JVM01), Monterey, CA, April 2001
Fridtjof Siebert (aicas GmbH)
For the application of Java in realtime and safety critical domains, an analysis of the worst-case execution times of primitive Java operations is necessary. All primitive operations must either execute in constant time or have a reasonable upper bound for their execution time. The difficulties that arise for a Java virtual machine and a Java compiler in this context will be presented here. This includes the implementation of Javas class and interface model, class initialization, monitors and automatic memory management.A new Java virtual machine and compiler that solves these difficulties has been implemented and its performance has been analysed.
Download: PDF (392kB)
Constant-Time Root Scanning for Deterministic Garbage Collection
10th International Conference on Compiler Construction (CC2001), Genova, April 2001
Fridtjof Siebert (aicas GmbH)
Root scanning is the task of identifying references to heap objects that are stored outside of the heap itself, in global and local variables and on the execution stack. Root scanning is particularly difficult within an incremental garbage collector that needs to be deterministic or give hard real-time guarantees. Here, a method that allows exact root scanning is presented. The basic idea is to ensure that copies of all root references exist on the heap whenever the garbage collector might become active. This approach reduces the root scanning phase of the garbage collection cycle to an efficient constant-time operation. A Java virtual machine and a static Java byte-code compiler that use this technique have been implemented and analysed using the SPECjvm98 benchmark suite. This Java implementation allows for deterministic memory management as needed in real-time systems that is difficult to achieve with traditional methods to perform root scanning.
Download: PDF (370kB)
Eliminating External Fragmentation in a Non-Moving Garbage Collector for Java
Compilers, Architectures and Synthesis for Embedded Systems (CASES2000), San Jose, November 2000
Fridtjof Siebert (aicas GmbH)
Fragmentation can cause serious loss of memory in systems that are using dynamic memory management. Any useful memory management system must therefore provide means to limit fragmentation. Today¹s garbage collector implementations often do this by moving objects in a way that free memory is non-fragmented. This paper presents a new object model that is based on fixed size blocks. The model eliminates external fragmentation without the need to move objects. A Java virtual machine and a static Java bytecode compiler that use this object model have been implemented and analysed using the SPECjvm98 benchmark suite. This Java implementation allows for deterministic memory management as needed in real-time systems that is difficult to achieve with moving collectors and unparalleled by current implementations.
Download: PDF (386kB)
Hard Real-Time Garbage Collection in the Jamaica Virtual Machine
The Sixth International Conference on Real-Time Computing Systems and Applications (RTCSA'99), Hong Kong, December 1999
Fridtjof Siebert (aicas GmbH)
Java's automatic memory management is the main reason that prevents Java from being used in hard real-time environments. We present the garbage collection mechanism that is used by the Jamaica Virtual Machine, an implementation of the Java Virtual Machine Specification. This mechanism differs significantly from existing implementations in the way threads are implemented, root references are found and in the object layout that is used. The implementation provides hard real-time guarantees while it allows unrestricted use of the Java language. Even dynamic allocation of normal garbage-collected Java objects is possible with hard real-time guarantees.
Download: PDF (258kB) PS (1267kB)
Real-Time Garbage Collection in Multi-Threaded Systems on a Single Processor
20th IEEE Real-Time Systems Symposium (RTSS'99), Phoenix, Arizona, December 1999
Fridtjof Siebert (aicas GmbH)
We show the difficulties that arise for the implementation of a real-time garbage collector in a multi-threaded system. A mechanism for synchronization between threads and the garbage collector activities is proposed for a single processor system. It is shown how this mechanism can be used to maintain exact information on roots, to implement efficient write-barriers, to do incremental or even constant-time root-scanning and to guarantee short pre-emption time of garbage collector activity. Special aspects of an implementation for Java that are affected by this mechanism will also be addressed. Finally, experimental data is presented to show that the proposed mechanisms can efficiently be used in real programs.
Download: PDF (17kB) PS (70kB) HTML (13kB)
long: PDF (257kB) PS (1035kB)
Guaranteeing Non-Disruptiveness and Real-Time Deadlines in an Incremental Garbage Collector (corrected version)
ACM SIGPLAN Notices Vol 34 number 3, March 1999, International Symposium on Memory Management 1998 (ISMM'98)
Michael Weiss, Fridtjof Siebert (aicas GmbH), et. al.
For Garbage Collection (GC) to be a generally accepted means of memory management it is required to prove its efficiency. This paper presents a scheme that guarantees that an incremental Garbage Collector will have completed its collection cycle before the system runs out of memory. Furthermore, it is shown that the work that has to be done by the collector in one incremental step is limited by a small constant depending on the percentage of total memory used by the application program. This result then allows a suitable trade-off between memory demand and GC overhead to be found.
Download: corrected version PDF (172kB) (original version contains serious error: PDF (132kB)
TurboJ, a Java Bytecode-to-Native Compiler
ACM SIGPLAN Workshop on Languages, Compilers, and Tools for Embedded Systems 1998 (LCTES'98), 1998
Fridtjof Siebert (aicas GmbH)
TurboJ is an off-line Java compiler, translating Java byte-codes to native code. TurboJ operates in conjunction with a Java Virtual Machine (JVM); among the supported JVMs are those on HPUX, Linux, and Wind River's Tornado for Java (running under VxWorks). Interfacing with a standard JVM entails benefits not enjoyed by the alternate "standalone" approach; particularly important for embedded systems is the opportunity to reduce the memory footprint via mixed-mode execution. In this paper, we discuss the characteristics of TurboJ as currently implemented, focusing on two aspects of TurboJ: its interactions with the JVM, and the optimizations it makes. We then briefly summarize TurboJ's current status, compare it with some other Java off-line compilers, and outline future plans.
Download: PS part 1 (125kB), PS part 2 (22kB)
Implementierung eines Eiffel-Compilers für SUN/SPARC
Diplomarbeit Nr. 1484 (1997)
107 Seiten, deutsch
Ziel der Arbeit war es, einen Compiler für die Programmiersprache Eiffel zu entwickeln. Als Zielcode wird direkt SPARC-Maschinencode erzeugt, so dass eine bei bisherigen Eiffel-Implementierungen nötige C-Compilation wegfällt. So wird auch die Erzeugung effizienten Maschinencodes für Besonderheiten der Sprache Eiffel moeglich, wie dynamisch gebundene Aufrufe und die effiziente Implementierung eines Garbage-Collectors.
Der Compiler selbst sollte bei konsequenter Verwendung von objektorientierten Techniken entwickelt werden. Die Beschreibung des objektorientierten Aufbaus des Compilers nimmt daher auch einen großen Teil der Ausarbeitung ein.
Eiffel besitzt eine Reihe an leistungsstarken Konstrukten, wie die flexible Mehrfachvererbung und Generizität, deren effiziente Implementierung eine gute Wahl der im Zielcode benutzten Strukturen verlangt. Diesen Strukturen wurde daher ein wichtiger Teil dieser Arbeit gewidmet.
Schließlich ist die Speicherverwaltung durch einen Garbage-Collector in Eiffel unerlässlich. Auch wenn er im Rahmen dieser Arbeit nicht implementiert werden konnte, so befasst sich doch ein eigenes Kapitel ausführlich mit der detaillierten Beschreibung einer effizienten Implementierung der Speicherverwaltung.
Download: PDF Text (494kB) Compiler Source and Executable (1.4MB)