Hard real-time garbage collection on chip multi-processors

Abstract

Automatische Speicherbereinigung, auch bekannt als Garbage Collection, ist ein geeignetes Mittel um die Produktivität bei der Entwicklung von Computerprogrammen zu erhöhen. Da sie dabei hilft, häufige Fehler im Bereich der Speicherverwaltung wie Speicherlecks und ungültige Referenzen zu vermeiden, hilft sie auch dabei, Programme sicherer zu machen. Herkömmliche Techniken zur automatischen Speicherbereinigung sind jedoch nicht für den Einsatz in harten Echtzeitsystemen geeignet. Da ein Fehlverhalten in solchen Systemen katastrophale Auswirkungen -- wie den Verlust von Menschenleben -- haben kann, ist die Einhaltung der zeitlichen Anforderungen des betreffenden Systems von höchster Bedeutung. In den letzten Jahren wurden Methoden zur automatischen Speicherbereinigung entwickelt, die auch für den Einsatz in harten Echtzeitsystemen geeignet sind. Diese Methoden sind jedoch nur für den Einsatz in Einzelprozessoren geeignet. Auf Multiprozessoren erfüllt automatische Speicherbereinigung bisher noch nicht die Anforderungen für harte Echtzeitsysteme.<br />Automatische Speicherbereinigung gibt Speicherobjekte wieder frei, auf die die Anwendung erwiesenermaßen nicht mehr zugreifen kann. Die Applikation kann jederzeit auf Objekte zugreifen auf die globale oder lokale Variablen verweisen. Beginnend bei diesen Objekten wird der Objektgraph von der automatischen Speicherbereinigung durchlaufen, um festzustellen, welche Objekte erreichbar sind. Da die Möglichkeit besteht, dass die Anwendung auf erreichbare Objekte zugreift, dürfen diese nicht freigegeben werden. Die Bestimmung der Referenzen in lokalen Variablen ist dabei in harten Echtzeitsystemen eine Herausforderung, da die zeitlichen Anforderungen es üblicherweise nicht erlauben, die Anwendung dafür anzuhalten. Die Entwicklung entsprechender Techniken ist einer der Schwerpunkte dieser Dissertation.<br />In harten Echtzeitsystemen kann eine Fragmentierung des Speichers nicht toleriert werden, weil sich sonst der maximale Speicherverbrauch einer Applikation nicht sinnvoll begrenzen lassen würde. Für die Defragmentierung von Speicher ist es notwendig, Objekte im Speicher zu verschieben. Um dies ohne Unterbrechung der Anwendung zu bewerkstelligen, wurde eine Hardware-Einheit entwickelt, die ein transparentes Verschieben von Objekten auf Multiprozessoren ermöglicht.<br />In Multiprozessoren kommen oftmals Speicher-Modelle zum Einsatz, die nur wenige Garantien bezüglich der Ordnung von Speicherzugriffen bieten. Die Auswirkungen solcher Speichermodelle auf die automatische Speicherbereinigung werden im Rahmen dieser Dissertation untersucht. Ebenso wird eine Analyse vorgestellt, die es erlaubt, die maximale Größe von Speicheranforderungen eines Tasks zu bestimmen. Eine solche Analyse ist notwendig, um zu berechnen ob die Speicheranforderungen der Applikation unter allen Umständen erfüllt werden können.<br />Im Rahmen dieser Dissertation werden Lösungen aufgezeigt, die es erlauben, automatische Speicherbereinigung mit den Anforderungen für harte Echtzeitsysteme auf Multiprozessoren miteinander zu vereinbaren. Die theoretischen Ergebnisse werden durch Messungen bestätigt, die demonstrieren, dass auch in Multiprozessor-Systemen mit automatischer Speicherbereinigung die Abweichungen der Task-Startzeiten gering gehalten werden können.<br />

Automatic memory management, also known as garbage collection, is a suitable means to increase productivity in the development of computer programs. As it helps to avoid common errors in memory management, such as memory leaks or dangling pointers, it also helps to make programs safer. Conventional garbage collection techniques are however not suited for use in hard real-time systems. As a failure in these systems can have catastrophic consequences---such as the loss of human life---it is of utmost importance to meet the timely requirements of the respective system. In the past few years, methods for garbage collection that are suitable for use in hard real-time systems have been developed. However, these techniques are suited only for uniprocessors. On multi-processors, garbage collection does not yet meet the requirements for hard real-time systems.<br />Garbage collection reclaims memory objects that are provably inaccessible to the application. Objects that are referenced by global or local variables can be accessed at any time. Starting at these objects, the object graph is traversed by the garbage collector to determine which objects are reachable. As there is the possibility that reachable objects are accessed by the application, they must not be reclaimed. Determining the object references in local variables is challenging in hard real-time systems, because the timely requirements usually do not permit stopping the application to do so. The development of appropriate techniques is one of the core areas of this dissertation.<br />Memory fragmentation cannot be tolerated in hard real-time systems, because otherwise, it would be impossible to determine reasonable bounds on the maximum memory consumption. In order to defragment memory, it is necessary to relocate objects. To achieve this without interrupting the application, a hardware unit has been developed, which enables transparent object relocation on chip multi-processors.<br />Multi-processors often use memory models that provide only few guarantees on the ordering of memory accesses. The effects of such memory models on garbage collection are investigated in this thesis. Also, an analysis to determine the maximum size of memory allocations of tasks is presented. Such an analysis is necessary to compute whether the allocation requests of an application can be met even in the worst case.<br />This thesis points out solutions which enable the reconciliation of garbage collection with the requirements of hard real-time systems on chip multi-processors. The theoretic results are supported by measurement results, which indicate that low release jitter can be achieved in multi-processor systems in the presence of garbage collection.<br />