CRuntimeJavalike - Bheap - Block Heap with Garbage Collection

CRuntimeJavalike - Bheap - Block Heap with Garbage Collection

Inhalt


1 Referenzen in CRuntimeJavalike

1.1 Referenzen in C und C++

Topic:.ObjectRef_All.ObjectRef_C.

In C++ gibt es zwei Arten von Referenzen, und die Möglichkeit, eine Instanz direkt anzugeben

In C++ kann man ein Object entweder direkt ansprechen:

 Type Object; Object.doSomething();

oder man kann das Object über Referenzen ansprechen:

 Type Object; Type* pObject = &Object; Type& rObject = Object;
 pObject->doSomething; rObject.doSomething;

Dabei verschleiert die Benutzung der Type&-Referenz den Unterschied zwischen direkten Ansprechen eines Objekts und Ansprechen über Refernz.

Eine Referenz kann immer vom Typ einer Basisklasse sein, die eine Instanz (ein Object) von einer abgeleiteten Klasse zeigert:

 BaseType* pObject;
 BaseType& rObject;
 pObject = &Object;
 rObject = Object; //Object ist vom abgeleitetem Typ Type

1.2 In Java werden Instanzen grundsätzlich nur über Referenzen angesprochen

Topic:.ObjectRef_All.ObjectRef_Java.

In Java ist die Welt gegenüber C++ vereinfacht: Es gibt nur Referenzen. Wenn von Java allgemein gesagt wird, es gäbe keine Zeiger, dann stimmt das insoweit: Es gibt nicht die in C /C++ bekannte und durchaus kritikwürdige Zeigerarithmetik. Ansonsten gibt es aber nur Zeiger.

 BaseType object = new Type();

Mit dieser Java-Zeile wird ein Object vom Typ Type angelegt, und ist danach nur über dessen Basisklasse BaseType, und zwar über die Referenz object bekannt. In Java gibt es keine Möglichkeit, eine Instanz (ein Object) direkt anzusprechen. Damit kann ein Object auch keinen Namen haben, es gibt gegebenenfalls mehrere Referenzen auf das Object, die verschiedene Namen haben können. Ein Name kann nur existieren als Eigenschaft (Variableninhalt) des Objects, nicht im Kontext des Compilers.


1.3 Referenzen in CRuntimeJavalike und Java2C

Topic:.ObjectRef_All.ObjectRef_CRuntimeJavalike.

Bei Nutzung der CRuntimeJavalike-Library sind Referenzen (= Zeiger) wie in C zu handhaben, wenn weder dynamisches Binden (virtuelle Methoden) noch der Garbage Collector des Runtimeheap genutzt wird. Wird jedoch mindestens eines dieser Features genutzt, dann ist eine Referenz eine Datenstruktur der Art:

 typedef struct Type_r_t
 { /** The base data of references*/
   ObjectRefValues_c refbase;
   /** The object be referenced from here*/
   struct Type_c_t* ref;
 }Type_r;

Der Zeiger ref ist der eigentliche Zeiger auf die Daten (gegebenenfalls vom Interface- oder Basistyp). refbase enthält weitere Informationen, die nicht in den Daten, sondern in der Referenz gespeichert werden:


1.4 Aufbau einer Referenzstruktur - passt in zwei Prozessor-Register

Topic:.ObjectRef_All.ObjectRef_2Register.

Die Diskussion über die Speichergröße muss deshalb intensiv geführt werden, weil die Effektivität der Maschinencodeabarbeitung stark davon abhängt:


1.4.1 Erweiterte Referenz als return by value

Topic:.ObjectRef_All.ObjectRef_2Register.returnByValue.

Referenzen müssen häufig als Returnwerte von Methoden zurückgegeben werden, und zwar nicht referenziert, sondern "return by value":

 Type_r createObject()
 { Type_r ret;
   DerivatedType* obj = new_DerivatedType();  //Object vom abgeleitetem Typ anlegen
   doSomething_DerivatedType(obj, ...);       //aufbereiten
   setRef_DerivatedType_Type(&ret, obj);      //setzen der Referenz
   return ret;                                //Rückgabe der Referenz
 }

Im Beispiel wird von einer Methode erwartet, dass sie ein Object von einem abgeleitetem Typ anlegt (welcher, ... ggf. in der Methode bestimmt), diesen initialisiert aber dann eine Referenz auf einen Basistyp oder ein Interface zurückliefert, dass außen verwendet werden soll.

Grundsätzlich falsch ist es, zu programmieren:

 Type_r* createObject()
 { Type_r ret;
   ...
   return &ret;                              //Rückgabe der Referenz
 }

Das läuft zwar durch den Compiler, und könnte zunächst sogar funktionieren. Aber die Daten der Referenz liegen im Stack, in einem Bereich, der freigegeben ist und anderweitig wiederverwendet wird (unterhalb der aktuellen Stackgrenze).

Die Frage ist zu stellen: Wie verhält sich ein Compiler bei "return by value" einer Struktur. Zulässig ist dieses Konstrukt in C jedenfalls. Bei einer größeren Struktur wird der Inhalt vom Stackbereich, die im Beispiel von der Variable ret belegt wird, in einen temporären Stackbereich kopiert, der für die Rückgabe reserviert ist. Da in der Regel der Inhalt der Struktur irgendwo gespeichert werden soll, also:

 reference = createObject();

hier in reference, das kann ein Element einer anderen Struktur sein, oder vielleicht wieder eine stacklokale Variable, wird der Inhalt nochmals kopiert. Das heißt, es sind in der Regel zwei Speicherkopier-Befehlssequenzen notwendig.

Viele Compiler können aber ein "return by value" einer einfachen Struktur, die in zwei Prozessorregister passt, über Prozessorregister zurückgeben. Selbst der Visual-Studio-Compiler, der an sich vieles über den Stack erledigt (da im Zielprozessor der i86-Famile effektive Speicherzugriffsmechanismen vorhanden sind), erledigt die Rückgabe einer einfachen Struktur auf diese Weise, über die Prozessorregister eax und edx.


1.4.2 Erweiterte Refenenz in 2 Prozessorregistern abbildbar

Topic:.ObjectRef_All.ObjectRef_2Register.2Register.

Daher gilt, eine Referenz-Struktur muss so einfach aufgebaut sein, dass ein Compiler sie in der Regel über Prozessorregister übergeben kann. Daher besteht die Struktur einer Referenz aus zwei Werten:

 typedef struct Type_r_t
 { /** The base data of references*/
   ObjectRefValues_c refbase;
   /** The object be referenced from here*/
   struct Type_c_t* ref;
 }Type_r;

Der Typ ObjectRefValues_c ist eine einfach int32-Variable, oder eine int16-Varaible, wenn der Einsatz in einem "kleinem" 16-bit-System erfolgen soll. Der Zeiger ist ebenfalls 32 bit (oder 16 bit) breit, beide Werte passen jeweils in ein Prozessor-Register.


1.4.3 Erweiterte Referenz als call by value

Topic:.ObjectRef_All.ObjectRef_2Register.returnByValue.

Bei einem Return besteht schlichtweg die Notwendigkeit eines return by value. Bei einer Argumentübergabe hat man die Auswahl: call-by-value oder call-by-reference. Bei einem call-by-reference wird der Zeiger auf die Referenzstruktur übergeben. Das hat folgenden Nachteil:

Wenn das Aufrufargument in einer Kette als Rückgabeargument einer anderen Subroutine auftritt, dann muss man bei call-by-reference die rückgegebene Referenz in einer Referenzvariable zwischenspeichern. Anderes geht es syntaktisch nicht. Dieser Fall tritt durchaus häufig auf, wie beispielsweise:

String_Jc substring = substring_String_Jc(&myString, 2,5);
callRoutine(&substring);

Einfacher wird es mit

callRoutine(substring_String_Jc(&myString, 2,5));

Solche Kettungen (Aufruf einer weiteren Methode in einer Argumentliste) sind zwar ganz allgemein kein so guter Programmierstil, da beim Debuggen auch unübersichtlich, sie sind aber besser weil einfacher lesbar. Wenn die Funktionalität nicht komplex ist, ist die Verkettung auch problemlos überschaubar. Es spricht also einiges dafür.

Ein anderes Argument spricht für die call-by-value-Methode: Es ist maschinentechnisch kein zusätzlicher Aufwand. Da die Referenzstruktur in zwei Prozessor passt, wird sie auch adäquat übergeben: Als zwei getrennte Einträge im Stack. Dort wird sie direkt verwendet. Bei einem call-by-reference liegt dagegen der Referenzwert noch dazwischen, man braucht also einen Speicherzugriff mehr. Hier schlägt das allgemeine Argument gegen call-by-value: Aufwand beim Aufruf wegen copy des Inhaltes, in das Gegenteil um.

Bei einem call-per-value wird nicht ein Registrieren der Rückwärtsreferenz im referenzierten Objekt ausgeführt (BlockHeap_GarbageCollection). Das ist aber nicht notwendig, denn

Die Konsequente Verwendung des call-by-value für Refernezen ist bisher in der CRuntimeJavalike nicht berücksichtigt (Stand August-2007), wird aber nach und nach eingebaut. Damit enfällt dann auch die Notwendigkeit solch unleserlicher Makros wie REFP_REF_Jc oder der REFP_type, es wird also einfacher.


1.5 Definition von Referenzen

ERROR: not found ---/root//topics:topic[@ident='ObjectRef_All']/topics:topic[@ident='ObjectRef_Definition']---


Define: ReferenceType


1.6 Verwendung der Referenzen

Topic:.ObjectRef_All.ObjectRef_Using.

Im Fall von einfachen Referenzen beschränkt sich deren Verwendung auf das einfache setzen und lesen. Ist aber eine erweiterte Referenz vorhanden, dann muss beim Setzen einer Referenz folgendes beachtet werden:

Beide Aktionen dauern jeweils nur wenige Befehle, deren richtige Programmierung ist aber etwas aufwändig. Daher sind Makros vorhanden zum Setzen und Löschen der Referenzen.

Weitere Makros dienen zum Null-test und sollen die Nutzungsarten kapseln. Ansonsten ist ein Zugriff oder Nulltest auch bei den erweiteren Referenzen ein einfacher Zeigerzugriff.


Define: ReferenceUsing


2 Block Heap mit Garbage Collection

2.1 BlockHeap_c: Speicherverwaltung, Garbage Collection für C

Topic:.Bheap.

In Echtzeitsystemen wird oft auf die dynamische Speicherreservierung während der Laufzeit verzichtet. Dort, wo eine flexiblere Nutzung von Speicher notwendig ist, werden dann meist angepasste Mechanismus (Pool bestimmter Instanzen) angeboten. Diese werden dann manuell programmiert. Das schränkt jedoch die machbaren Funktionen ein. Dafür seien stellvertretend nur zwei Beispiele genannt.

Eine Eventsteuerung verlangt ebenfalls meist eine dynamische Reservierung, damit Speziallösungen.

Das Problem der Speicherreservierung während der Laufzeit ist folgendes:

Die Lösung des Problemes ist wie folgt möglich:

Zusätzlich gibt es noch das Problem der Verwaltung, wann ein Speicherblock freigegeben werden soll. Das Problem tritt dann auf, wenn der Speicherblock von verschiedenen Modulen benutzt wird. In PC-Applikationen wird oft das Freigeben "vergessen", was aber weiter nicht tragisch ist, da PC-Applikationen meist nur eine begrenzte Zeit laufen und das Betriebssystem für eine Freigabe des gesamten von einer Applikation allokierten Speicherplatzes sorgt, wenn diese beendet wird. Bei Echtzeitsteuerungen treffen diese Bedingungen aber nicht zu. Also wird bei solchen Aufgabenstellungen meist "zu Fuß" eine Verwaltung programmiert, diese ist oft einfach da wenige und nur bestimmte Module an bestimmten Daten hängen.

Java gibt mit dem Garbage-Collector eine andere Antwort auf das Problem der Speicherverwaltung bei Mehrfachnutzung. Die Lösung dieses Problems wird auf die Systemebene verlagert (in die Virtuelle Maschine) und ist dort unabhängig von der Anwenderprogrammierung in getesteter und ausgereifter Art vorhanden. Die Speicherverwaltung mit dem RuntimeHeap_c bietet ebenfalls eine Garbage-Collector-Lösung an, alternativ zu einer manuellen Freigabemöglichkeit. Der Garbage Collector ist hier so gebaut, dass er unterbrechbar ist, so dass Echtzeitanforderungen erfüllt werden können.


2.1.1 Leistungsumfang von RuntimeHeap_c

Topic:.Bheap..

====Mehrfache Instanziierbarkeit, mehrere Speicherpools==== RuntimeHeap_c ist mehrfach instanziierbar. Damit ist es möglich, mehrere Speicherpools mit abgestimmten Größen für verschiedene Bereiche einer Echtzeitsteuerung anzubieten. Beispielsweise kann eine Grafikdarstellung dieses Feature ausgiebig nutzen, falls der Speicher ausgeht, wird beispielsweise ein Bildaufbau etwas verlangsamt. Andere Teile, die währenddessen auf dynamischen Speicher angewiesen sind, dürfen aber deshalb nicht blockieren.


2.1.1.1 Init- und Run-Mode

Topic:.Bheap...

Es wird unterschieden zwischen einer Hochlaufphase und der Run-Phase. In der Hochlaufphase führt jeder Aufruf einer Speicherallokierung zum Aufruf der Standard-Speicherallokierung des Systems (malloc). Erst in der Run-Phase werden die gleichgroßen Blöcke benutzt. Der Gesamtspeicher für den Pool der gleichgroßen Blöcke kann auch erst unmittelbar vor dem Umschalten in den Run-Mode allokiert werden, beispielsweise um den gesamten "Rest" des vorhandenen Speichers dafür zuzuweisen.


2.1.1.2 Normale Blöcke, kleine Blöcke und MapEntry-Blöcke

Topic:.Bheap...

Die Größe eines "normalen" Blockes ist begrenzt. Größere Speicherblöcke als ein "normaler" Block können zur Runtime nicht reserviert werden. Wenn das System möglichst flexibel sein soll, dann muss ein "normaler" Block möglichst groß sein. Die Größe eines "normalen" Blockes ist in der vorliegenden Implementierung auf 4096 Bytes begrenzt, ein sinnvoller Wert ist aber beispielsweise 1024 Byte.

Werden in einem System typisch weniger Bytes für dynamische Reservierung benötigt, dann liegt hier ein hoher Overhead ("Verschnitt") vor. Beispielsweise wird typisch für eine Eventsteuerung etwas um die 30 Bytes benötigt, aber selten auch einmal knapp 512 Bytes. Dann muss ein "normaler" Block 512 Bytes umfassen, aber bei jedem Event werden dann auch 512 Bytes verbraucht. Das ist nicht günstig. Für den RuntimeHeap werden deshalb drei verschiedene Blockgrößen angeboten:

Wird ein "kleiner" Block benötigt, dann wird dieser immer innerhalb eines "normalen" Blocks angelegt, der bereits kleine Blöcke verwaltet. Umorganisiert wird grundsätzlich nicht. Dann kann es zwar theoretisch Im extermen Fall kann passieren, dass der gesamte Pool nur von "kleinen" Blöcken belegt wird und diese dann so ungünstig freigegeben werden, dass alle normalen Blöcke irgendwie mit kleinen Blöcken belegt bleiben, also nicht als freie "normale" Blöcke zur Verfügung stehen. Das ist aber eher ein theoretischer Fall. Immer dann, wenn alle kleinen Blöcke zur Runtime irgendwann auch wieder freigegeben werden, ist die Wahrscheinlichkeit hoch, dass ein normaler Block vollkommen freigeräumt von kleinen Blöcken ist. Das nächst darauf folgende Allokieren eines kleinen Blocks wird in jedem Fall dort erfolgen wo bereits andere kleine Blöcke innerhalb eines Normalblocks vorhanden sind, also keinen Normalblock erneut neu belegen.

Das Problem sei bildlich dargestellt. x steht für einen belegten kleinen Block, eine Ketten von X für einen belegten normalen Block. - kennzeichnet einen freien Block.

 --x----- x-------- -------- XXXXXXXX x-xx-xxx --------

Nach Freigabe des linkesten Blocks und Neubelegung:

 -------- x-------- -------- XXXXXXXX xxxx-xxx --------

2.1.1.3 Blockgröße als Potenz von 2

Topic:.Bheap...

Die Speicherverwaltung ist etwas schneller, wenn die Blockgrößen Potenzen von 2 sind. Dann können Maskierungen anstelle Divisionen verwendet werden, was insbesondere bei einfachen Prozessoren ohne Arithmetik-Unit hilfreich ist. Die sich daraus ergebende Beschränkung der freien Wahl von möglichen Blockgrößen sollte unerheblich sein.

Wird beispielsweise in einer vorliegenden Software für typische kleine Blöcke beispielsweise für Events aus einer UML-Implementierung 36 Bytes benötigt, dann muss diese Blockgröße auf 64 Byte festegelegt werden. Das ist ungünstig. Oft ist es aber auch möglich, mittels Anpassung der zugehörigen Software die Blockgröße auf 32 Bytes anzupassen. Insoweit lässt sich ein Kompromiss finden.

Aus ähnlichen Gründen sollte der Speicherbereich des Runtimeheap genau bei einer Adresse beginnen, die durch die Blockgröße teilbar ist. Dann wird bei der Ermittlung des zugehörigen Blockes zu einer beliebigen Speicheradresse im Block etwas Rechenzeit gespart. Bei kleinen Systemen ist das meist kein Problem, wenn ein bestimmtes Segment des physikalischen Speichers per Linker-Einstellung speziell dafür vorgesehen ist. Wird der Speicher bei einem großen System aus dem allgemeinem Heap besorgt, dann gibt es für diesen Zweck eine Korrektur, die einen Block als unnutzbaren "Verschnitt" verschenkt.


2.1.1.4 Referenzen und Rückwärtsreferenzen

Topic:.Bheap...

Wird ein Speicherblock für Garbage Collection freigegeben, dann prüft die Garbage-Collection-Prozedur jeden Speicherblock, ob dieser benutzt wird. Dazu muss er dessen Referenzen kennen. Das wird in der Weise realisiert, dass jede Referenz vom referenzierten Speicherblock aus eine Rückwärtsreferenz besitzt, damit also getestet werden kann. Diese Rückwärtsreferenzen sind entweder im im Speicherblock mit angeordnet, oder in einem extra Speicherblock (oder mehreren) enthalten, wenn es sehr viele sind. Der Garbage-Collection-Algorithmus ist in einem extra Kapitel beschrieben.


2.1.1.5 Zeitpunkt der Speicherfreigabe - Priorität des Garbage Collectors

Topic:.Bheap...

xxx


2.1.2 Arbeitsweise des Garbage Collectors

Topic:.Bheap..

Die Methode

 garbageCollector_RuntimeHeap();

prüft alle Blöcke des Runtimeheap in Adressreihenfolge. Erreicht sie das Ende des Runtimeheap, dann wird diese Methode beendet. Diese Methode muss zyklisch gerufen werden, damit der garbage Collector immer arbeitet /citiation not found:JavaCppRuntimeHeap_CallgarbageCollector/

Blöcke, die nicht benutzt sind, bleiben unberührt. Blöcke, die benutzt sind aber nie referenziert worden sind, bleiben ebenfalls unberührt. Das sind diejenigen Blöcke, die mit new reserviert worden sind und mit delete wieder freigegeben werden sollen.

Blöcke, die mindestens einmal referenziert worden sind, haben in ihren Kopfbytes einen Eintrag der Länge, aus der die Lage der Referenztabelle ermittelt wird. Die Referenztabelle enthält die Rückwärts-Zeiger auf die Referenzen. Ist diese Referenztabelle leer, dann ist dieser Block mindestens einmal referenziert worden und ist nunmehr nicht mehr referenziert. Er wird daher freigegeben, da keine Referenzen auf ihn zeigen, er also unbenutzt ist.

Es ist ein schwerer Programmfehler, wenn die Nutzung von Blöcken mit JavaCpp-like Referenz und einfacher Zeigerung gemischt wird und der Block nicht mehr JavaCpp-like referenziert aber noch verzeigert ist. Die Verwendung der new/delete - Nutzung und der new-Referenz-Nutzung darf nicht gemischt werden.

Wird bei einem Block mindestens eine Referenzen festgestellt, dann wird dieser Block in eine bisher leere Sammelstruktur des Typs ObjectClumbReferences aufgenommen. Daraufhin werden alle Blöcke in dieser Sammelstruktur (das ist initial nur dieser eine Block) getestet. Es werden alle Referenzen des Blocks getestet. Wird festgestellt, dass es sich um eine Referenz handelt, die von außerhalb des RuntimeHeap kommt, dann ist klar, das dieser Block in Benutzung ist. Der Test wird abgebrochen und der Block bleibt unverändert.

Wird festgestellt, dass eine Referenz auf den betrachteten Block von einem anderen Block des Runtime kommt, dann wird dieser andere Block in die ObjectClumbReferences mit aufgenommen. Nacheinander werden alle Blöcke, die in der ObjectClumbReferences aufgenommen worden sind, getestet.Wird dabei mindestens eine Referenz festgestellt, die von außen kommt, dann wird der Test abgebrochen und der zuerst betrachtete Block gilt als benutzt, da er von einem anderen Block referenziert wird, der aber von außen referenziert wird.

Wird der Test aufgrund einer Außenreferenz nicht abgebrochen, dann sind alle Blöcke, die in der ObjectClumbReferences erfasst worden sind, nicht von außen referenziert sondern referenzieren sich nur gegenseitig. Daher werden sie tatsächlich nicht mehr benutzt und werden daher alle freigegeben.


2.1.2.1 Unterbrechbarkeit des Garbage Collectors

Topic:.Bheap...

Die Unterbrechbarkeit des GarbageCollectors von höherprioren Tasks ist wie folgt gesichert:

Änderungen der Referenzierung von Blöcken, die nicht zu den aktuell getesteten Blöcken in der ObjectClumbReferences gehören, ist unkritisch. Wenn ein vom Garbage Collector bereits behandelter Block freigegeben wird, dann wird er eben beim folgenden Durchlauf des Garbage Collectors erfasst, also etwas später wieder dem freien Pool des RuntimeHeap bereitgestellt.

Kritisch ist, wenn sich innerhalb der Referenzierung der im Test befindlichen Blöcke etwas ändert. Es kann sein, dass einige bereits als nur von Blöcken des RuntimeHeap, also nicht von außen referenziert erkannt wurden, und noch nicht alle Blöcke getestet worden sind. Änderungen in der Referenzierung sind beliebig denkbar. Ein einfacher Fall zeigt bereits die Problematik: Block A wurde getestet und nur von Block B als referenziert erkannt. A und B stehen in der ObjectClumbReferences . B wurde noch nicht getestet. Dann kommt eine Unterbrechung von einer höherprioren Task, die eine Außenreferenz auf A hinzufügt und eine vorhandene Außenreferenz auf B löscht.

Die normale Weiterarbeit des Garbage Collectors bei der Abarbeitung des ObjectClumbReferences würde jetzt feststellen, dass B auch nicht von außen referenziert wird, A wird nicht nochmals getestet, Folge wäre die fälschliche Freigabe der beiden Blöcke.

Diesem Umstand wird abgeholften mit folgender Arbeitsweise: Wird eine neue Referenz auf einen Block gelegt, der sich im Test des Garbage Collectors befindet, dann wird dem Garbage Collector mitgeteilt, dass er den aktuellen Test abzubrechen hat. Alle Blöcke bleiben unberührt. Der Garbage Collector wird fortgesetzt mit dem neu begonnenen Test des folgenden Blockes im RuntimeHeap. Es wird nicht mit dem ursprünglich getestetem Block erneut begonnen, da dann höherpriore zyklische Aktivitäten der Referenzierungsänderung dazu führen können, dass der Garbage Collector an diesem Block stehenbleibt (immer wieder den gleichen Block neu beginnt). Die Folge wäre, dass andere Blöcke nicht freigegeben werden.