Heap mit Garbage Collection --------------------------- Vorteile: - Es werden keine Handles benötigt. (ein Dereferenzierungs-Schritt weniger bei jedem Zugriff) - Es wird kein Belegungszähler benötigt. (keine Unterscheidung zw. gezählten und ungeschützten Referenzen. Zähler kann auch nicht überlaufen.) Nachteile: - kompliziertere GC - GC läuft länger - Objekte mit Destructorcode (z.B. Datei schließen) müssen den selbst rechtzeitig selbst aufrufen - Alle Variablen mit Daten auf dem Heap müssen jederzeit auffindbar sein. - Globale Variablen - Lokale Variablen und Temp. Daten auf dem Stack - Daten in Arrays und Structs. (rekursiv) Bei Structs wird eine Liste (Array) aller Offsets benötigt, an denen Data Members mit Heapdaten stehen. Diese können im Programmcode stehen. Da auf einige Daten auch während einer GC zugegriffen werden muss, müssen diese in einen 'geschützten' Bereich. Pointer auf Daten innerhalb von Datenblöcken können von der GC nicht aktualisiert werden und sind nicht erlaubt. -> Immer Array + Index! Garbage Collection: 1. in allen dyn. Variablen wird in ihrem Datenblock ein 'gefunden'-Bit gesetzt. 2. alle noch benutzten Blöcke werden nach unten zusammen geschoben und die Adressen in allen Variablen aktualisiert. Die Laufzeit darf nicht quadratisch ansteigen! Einige Adressen zeigen zeitweise nicht mehr auf ihren Block! Dazu wird ein Hilfsarray bu benutzt, in dem Handles angelegt werden: 1. Für alle Blöcke wird .size in den bu eingetragen und in .size die adresse des Eintrags in bu. 2. Für alle Variablen wird die Adresse mit der Adresse des bu-Eintrags ersetzt. 3. Für alle Blöcke wird der Block runtergeschoben und .size aus bu restauriert und in bu die neue Adresse eingetragen. 4. Für alle Variablen wird die Adresse mit der neuen Adresse aus dem Bu-Eintrag ersetzt. Der Hilfsarray kann entweder im Restfreiraum des Heaps (mindestgröße schützen!) oder auf dem Stack angelegt werden, ggf. jenachdem wo mehr Platz ist. Der Hilfsarray wird aber trotzdem meist zu klein sein. Dann muss man in Schritt 2.1. abbrechen, sobald der bu voll ist und ggf. mehrere Durchläufe machen. In Schritt 2.2. muss man nicht prüfen, ob der Block überhaupt im Heap liegt, sondern ob er im Bereich aus 2.1. liegt. Schritt 2.3. wird entsprechend nur auf den aktuellen Abschnitt ausgeführt. In 2.4. dürfen sowieso nur die Adressen aktualisiert werden, die in den bu zeigen. Einfache Annahmen: Kein Destructor-Code: Nicht mehr referenzierter Speicher wird bloß freigegeben. Nur ein Thread => Nur ein Stack. Heap-Variablen und Zwischenergebnisse werden auf einen separaten 'Schatten'-Stack gepusht, um sie von anderen Daten unterscheiden zu können. Der Structdaten-Descriptor ist ein einfacher uint8-Array mit den Offsets der allozierten Datamembers, gerade die min. Information für den GC, ohne zus. Infos für Reflection oder Datendumps. Heap: heap_s = start des geschützten 'system'-bereichs heap_a = start des normalen heaps heap_p = ende des belegten bereichs (excl.) = start des freien bereichs im heap heap_e = ende des heaps (excl.) (evtl. eine Konstante) Global data: globals: = Basisadresse der globalen Variablen, falls nicht als 'Heap-Variable' auf dem Stack type_descriptor_for_Globals: equ globals: adresse des Arrays. Blöcke im Heap: dw länge_und_flags -> db data[] <- Variablen zeigen hier hin! Variablen: dw address_of_block_data Da bei einer GC die Adressen in allen Variablen aktualisiert werden müssen, müssen alle Heap-Variablen zu finden sein. Es gibt 4 Fälle: globale Variablen lokale Variablen (evtl. für mehrere Threads) data members in Structs data members in Arrays Da man den Adressen nicht ansieht, von welcher Art die Daten im adressierten Block sind, muss am Block dranstehen, was drin ist. Dafür ist der 'descriptor'. Die globalen Variablen werden wie ein Struct behandelt und es muss einen Descriptor für diesen 'Struct' geben. Lokale Heap-Variablen werden auf einem separaten Stack abgelegt, so dass sie én bloc auffindbar sind. Wird nur 1 Thread unterstützt, können die globalen Variablen der erste Eintrag auf dem Stack sein. Länge_und_flags: Die obersten Bits enthalten Flags, die den Datentyp definieren: %1xx… Während der GC: Dieser Block wurde gefunden, wird also noch benutzt. %x0x… Flache Daten: Array mit flachen Daten: Bytes, Chars, Words, Longs, Floats etc. Struct mit flachen Daten. Die max. Größe eines Arrays ist 0x3fff Bytes. (16k-1) %x10… Array von Adressen auf andere Heap-Daten z.B. mehrdim. Array oder Array von Structs Die max. Größe eines solchen Arrays ist 0x1ffe Bytes = 4k-1 Einträge. %x11… Struct. Das erste Data Member ist der Type-Descriptor. Type-Descriptor: Strukturierte Daten haben als erstes Data Member einen Descriptor. (Außer sie bestehen ausschließlich aus flachen Daten, dann können sie wie Arrays abgelegt werden.) Der Descriptor ist ein uint8[] Array mit den Offsets aller Heap-Datamembers. (Der Descr. könnte auch selbst ein Struct sein mit weiteren, zusätzlichen Informationen.) globals: = Basisadresse der globalen Variablen, falls nicht als 'Heap-Variable' auf dem Stack type_descriptor_for_Globals: equ globals: adresse des Arrays. type Type = uint8[]; struct Globals = { // uint8 offsets[] = type_descriptor_for_Globals = implizit, nicht im Source sichtbar ... }; Garbage Collection Sobald eine Speicheranforderung fehlschlägt oder ein bestimmter Mindestfreibereich unterschritten wird oder diese manuell angefordert wird, wird eine Garbage Collection durchgeführt. Step 1: Markiere alle noch referenzierten Heapblöcke void markiere_item(item) { if item == null: continue if item.size.bit15: continue wurde schon bearbeitet if item≥heap_a && item