Regionsbasierte Speicherverwaltung - Region-based memory management

In der Informatik , bereichsbasierte Speicherverwaltung ist eine Art der Speicherverwaltung , in dem jedes Objekt zugewiesen zu einem zugeordneten Bereich . Eine Region, auch Zone , Arena , Area oder Speicherkontext genannt , ist eine Sammlung von zugewiesenen Objekten, die auf einmal effizient neu zugewiesen oder freigegeben werden können. Wie bei der Stack-Zuweisung erleichtern Regionen die Zuweisung und Aufhebung der Zuweisung von Speicher mit geringem Overhead; Sie sind jedoch flexibler, sodass Objekte länger leben als der Stapelrahmen, in dem sie zugewiesen wurden. In typischen Implementierungen werden alle Objekte in einem Bereich in einem einzigen zusammenhängenden Bereich von Speicheradressen zugewiesen, ähnlich wie Stapelrahmen typischerweise zugewiesen werden.

Beispiel

Betrachten Sie als einfaches Beispiel den folgenden C- Code, der eine Linked-List-Datenstruktur zuordnet und dann wieder freigibt: 

Region *r = createRegion();
ListNode *head = NULL;
for (int i = 1; i <= 1000; i++) {
    ListNode* newNode = allocateFromRegion(r, sizeof(ListNode));
    newNode->next = head;
    head = newNode;
}
// ...
// (use list here)
// ...
destroyRegion(r);

Obwohl viele Operationen erforderlich waren, um die verknüpfte Liste aufzubauen, kann sie schnell in einer einzigen Operation freigegeben werden, indem die Region zerstört wird, in der die Knoten zugewiesen wurden. Die Liste muss nicht durchlaufen werden.

Implementierung

Einfache explizite Regionen sind einfach zu implementieren; die folgende Beschreibung basiert auf Hanson. Jeder Bereich ist als eine verkettete Liste großer Speicherblöcke implementiert ; jeder Block sollte groß genug sein, um viele Zuweisungen zu bedienen. Der aktuelle Block behält einen Zeiger auf die nächste freie Position im Block, und wenn der Block gefüllt ist, wird ein neuer zugewiesen und der Liste hinzugefügt. Wenn der Bereich freigegeben wird, wird der Zeiger für die nächste freie Position auf den Anfang des ersten Blocks zurückgesetzt, und die Liste der Blöcke kann für den nächsten zugewiesenen Bereich wiederverwendet werden. Alternativ kann, wenn eine Region freigegeben wird, ihre Liste von Blöcken an eine globale freie Liste angehängt werden, aus der andere Regionen später neue Blöcke zuweisen können. In beiden Fällen dieses einfachen Schemas ist es nicht möglich, einzelne Objekte in Regionen freizugeben.

Die Gesamtkosten pro zugewiesenem Byte dieses Schemas sind sehr gering; fast alle Zuweisungen beinhalten nur einen Vergleich und eine Aktualisierung auf den Zeiger auf die nächste freie Position. Das Aufheben der Zuordnung einer Region ist ein Vorgang mit konstanter Zeit und wird selten durchgeführt. Anders als bei typischen Garbage-Collection- Systemen ist es nicht erforderlich, Daten mit ihrem Typ zu kennzeichnen.

Geschichte und Konzepte

Das Grundkonzept der Regionen ist sehr alt und tauchte erstmals 1967 im AED Free Storage Package von Douglas T. Ross auf, bei dem der Speicher in eine Hierarchie von Zonen unterteilt war; jede Zone hatte ihren eigenen Allocator, und eine Zone konnte auf einmal freigegeben werden, wodurch Zonen als Regionen nutzbar wurden. 1976 enthielt der PL/I- Standard den Datentyp AREA. 1990 demonstrierte Hanson, dass explizite Regionen in C (die er Arenen nannte) eine Zeitleistung pro zugewiesenem Byte erreichen konnten, die sogar dem schnellsten bekannten Heap-Zuweisungsmechanismus überlegen war. Explizite Regionen waren maßgeblich am Design einiger früher C-basierter Softwareprojekte beteiligt, darunter der Apache HTTP Server , der sie als Pools bezeichnet, und das PostgreSQL- Datenbankverwaltungssystem, das sie als Speicherkontexte bezeichnet. Wie die herkömmliche Heap-Zuweisung bieten diese Schemata keine Speichersicherheit ; Es ist möglich, dass ein Programmierer auf eine Region zugreifen kann, nachdem sie durch einen baumelnden Zeiger freigegeben wurde , oder die Freigabe einer Region vergisst, was zu einem Speicherverlust führt .

Regionsinferenz

Im Jahr 1988 begannen Forscher zu untersuchen, wie Regionen für eine sichere Speicherzuweisung verwendet werden können, indem sie das Konzept der Regionsinferenz einführten , bei dem die Erstellung und Freigabe von Regionen sowie die Zuweisung einzelner statischer Zuordnungsausdrücke zu bestimmten Regionen vom Compiler at . eingefügt werden Kompilierungszeit. Der Compiler ist in der Lage, dies so zu tun, dass er baumelnde Zeiger garantieren kann und keine Lecks auftreten.

In einem Frühwerk von Ruggieri und Murtagh wird zu Beginn jeder Funktion eine Region angelegt und am Ende wieder freigegeben. Anschließend ermitteln sie mithilfe der Datenflussanalyse eine Lebensdauer für jeden statischen Zuordnungsausdruck und weisen ihn der jüngsten Region zu, die seine gesamte Lebensdauer enthält.

Im Jahr 1994 wurde diese Arbeit in einer bahnbrechenden Arbeit verallgemeinert von Tofte und Talpin zu Unterstützung Typ Polymorphismus und Funktionen höherer Ordnung in Standard ML , eine funktionale Programmierung Sprache, einen anderen Algorithmus , basierend auf Typinferenz und die theoretischen Konzepte der polymorphen Region Typen und die Regionsrechnung . Ihre Arbeit führte eine Erweiterung des Lambda-Kalküls einschließlich Regionen ein und fügte zwei Konstrukte hinzu:

e 1 at ρ: Berechne das Ergebnis des Ausdrucks e 1 und speichere es im Bereich ρ;
letregion ρ in e 2 end: Erzeuge eine Region und binde sie an ρ; e 2 auswerten ; Dann die Region freigeben.

Aufgrund dieser syntaktischen Struktur sind Regionen verschachtelt , dh wenn r 2 nach r 1 erstellt wird , muss es auch vor r 1 freigegeben werden ; Das Ergebnis ist ein Stapel von Regionen. Darüber hinaus müssen Regionen in derselben Funktion, in der sie erstellt wurden, freigegeben werden. Diese Beschränkungen wurden von Aiken et al.

Dieser erweiterte Lambda-Kalkül sollte als nachweislich speichersichere Zwischendarstellung für die Kompilierung von Standard-ML-Programmen in Maschinencode dienen, aber der Aufbau eines Übersetzers, der bei großen Programmen gute Ergebnisse liefert, war mit einer Reihe praktischer Einschränkungen konfrontiert, die mit neuen Analysen, einschließlich des Umgangs mit rekursiven Calls, Tail Calls und Eliminieren von Regionen, die nur einen einzigen Wert enthielten. Diese Arbeit wurde 1995 abgeschlossen und in das ML-Kit integriert, eine Version von ML, die auf der regionalen Zuordnung anstelle der Garbage Collection basiert. Dies ermöglichte einen direkten Vergleich zwischen den beiden auf mittelgroßen Testprogrammen, wobei je nach "regionaler" Ausrichtung des Programms sehr unterschiedliche Ergebnisse ("zwischen 10 mal schneller und vier mal langsamer") erzielt wurden; Die Kompilierungszeiten lagen jedoch in der Größenordnung von Minuten. Das ML-Kit wurde schließlich mit zwei Ergänzungen auf große Anwendungen skaliert: ein Schema für die separate Kompilierung von Modulen und eine Hybridtechnik, die Regionsinferenz mit Tracing-Garbage-Collection kombiniert.

Verallgemeinerung auf neue Sprachumgebungen

Nach der Entwicklung von ML Kit wurden die Regionen auf andere Sprachumgebungen verallgemeinert:

  • Verschiedene Erweiterungen der Programmiersprache C:
    • Der sichere C-Dialekt Cyclone , der neben vielen anderen Funktionen Unterstützung für explizite Regionen bietet, und bewertet die Auswirkungen der Migration vorhandener C-Anwendungen, um diese zu verwenden.
    • Es wurde eine Erweiterung von C namens RC implementiert, die explizit verwaltete Regionen verwendet, aber auch Referenzzählungen auf Regionen verwendet, um die Speichersicherheit zu gewährleisten, indem sichergestellt wird, dass keine Region vorzeitig freigegeben wird. Regionen verringern den Aufwand für das Zählen von Referenzen, da Referenzen innerhalb von Regionen keine Aktualisierung der Zählungen erfordern, wenn sie geändert werden. RC enthält ein explizites statisches Typsystem für Regionen, das es ermöglicht, einige Aktualisierungen der Referenzanzahl zu eliminieren.
    • Eine Einschränkung von C namens Control-C beschränkt Programme auf die Verwendung von Regionen (und nur eine einzelne Region gleichzeitig), als Teil ihres Designs, um die Speichersicherheit statisch zu gewährleisten.
  • Regionen wurden für eine Teilmenge von Java implementiert und wurden zu einer kritischen Komponente der Speicherverwaltung in Real time Java , die sie mit Eigentumstypen kombiniert , um die Objektkapselung zu demonstrieren und Laufzeitprüfungen bei der Aufhebung der Regionszuordnung zu eliminieren. Vor kurzem wurde ein halbautomatisches System zum Ableiten von Regionen in eingebetteten Echtzeit-Java-Anwendungen vorgeschlagen, das eine statische Analyse zur Kompilierzeit, eine Zuweisungsrichtlinie für Laufzeitregionen und Programmierhinweise kombiniert. Regionen eignen sich gut für Echtzeit-Computing, da ihr Zeitaufwand statisch vorhersehbar ist, ohne die Komplexität einer inkrementellen Garbage Collection.
  • Sie wurden für die implementierte Logik der Programmierung Sprachen Prolog und Merkur der Modellregion Inferenz Rückzieher und Schnitte Unterstützung durch die Erweiterung Tofte und Talpin.
  • Die regionenbasierte Speicherverwaltung wird in der gesamten parallelen Programmiersprache ParaSail verwendet . Aufgrund des Fehlens expliziter Zeiger in ParaSail ist keine Referenzzählung erforderlich.

Nachteile

Bei Systemen, die Regionen verwenden, können Probleme auftreten, bei denen Regionen sehr groß werden, bevor sie freigegeben werden, und einen großen Anteil toter Daten enthalten. diese werden allgemein als "Leckagen" bezeichnet (auch wenn sie schließlich freigesetzt werden). Die Beseitigung von Lecks kann eine Umstrukturierung des Programms erfordern, in der Regel durch die Einführung neuer Regionen mit kürzerer Lebensdauer. Das Debuggen dieser Art von Problem ist besonders schwierig in Systemen, die Regionsinferenz verwenden, bei denen der Programmierer den zugrunde liegenden Inferenzalgorithmus verstehen oder die ausführliche Zwischendarstellung untersuchen muss, um das Problem zu diagnostizieren. Tracing Garbage Collectors sind effektiver bei der rechtzeitigen Freigabe dieser Art von Daten ohne Programmänderungen; dies war eine Rechtfertigung für hybride Region/GC-Systeme. Auf der anderen Seite kann das Tracing von Garbage Collectors auch subtile Lecks aufweisen, wenn Verweise auf Daten aufbewahrt werden, die nie wieder verwendet werden.

Regionsbasierte Speicherverwaltung funktioniert am besten, wenn die Anzahl der Regionen relativ klein ist und jede viele Objekte enthält; Programme, die viele Sparse-Regionen enthalten, weisen eine interne Fragmentierung auf , was zu verschwendetem Speicher und einem Zeitaufwand für die Regionsverwaltung führt. Auch hier kann dieses Problem bei Vorliegen einer Regionsinferenz schwieriger zu diagnostizieren sein.

Hybride Methoden

Wie oben erwähnt, verwendet RC eine Mischung aus Regionen und Referenzzählung , wodurch der Aufwand für die Referenzzählung begrenzt wird, da Referenzen innerhalb von Regionen keine Aktualisierung der Zählungen erfordern, wenn sie geändert werden. In ähnlicher Weise kombinieren einige Markierungsregion- Hybridmethoden die Nachverfolgung von Garbage Collection mit Regionen; diese funktionieren, indem sie den Heap in Regionen unterteilen, einen Mark-Sweep-Durchlauf durchführen, in dem alle Regionen, die lebende Objekte enthalten, markiert werden, und dann alle unmarkierten Regionen freigeben. Diese erfordern eine kontinuierliche Defragmentierung, um wirksam zu bleiben.

Verweise