PatentDe  


Dokumentenidentifikation DE60034702T2 17.01.2008
EP-Veröffentlichungsnummer 0001234238
Titel VERFAHREN UND VORRICHTUNG ZUR VERBESSERUNG DER WIRKSAMKEIT VON KOPIERENDER SPEICHERBEREINIGUNG
Anmelder Sun Microsystems, Inc., Palo Alto, Calif., US
Erfinder KESSLER, Peter B., Palo Alto, CA 94306, US;
GRARUP, Steffen, Palo Alto, CA 94303, US;
UNGAR, David M., Palo Alto, CA 94303, US
Vertreter HOFFMANN & EITLE, 81925 München
DE-Aktenzeichen 60034702
Vertragsstaaten DE, FR, GB, IE, NL
Sprache des Dokument EN
EP-Anmeldetag 28.11.2000
EP-Aktenzeichen 009921685
WO-Anmeldetag 28.11.2000
PCT-Aktenzeichen PCT/US00/42329
WO-Veröffentlichungsnummer 2001038986
WO-Veröffentlichungsdatum 31.05.2001
EP-Offenlegungsdatum 28.08.2002
EP date of grant 02.05.2007
Veröffentlichungstag im Patentblatt 17.01.2008
IPC-Hauptklasse G06F 12/00(2006.01)A, F, I, 20051017, B, H, EP

Beschreibung[de]
HINTERGRUND DER ERFINDUNG 1. Gebiet der Erfindung

Die vorliegende Erfindung bezieht sich allgemein auf Verfahren und Vorrichtung zum Verbessern des Leistungsverhaltens von Softwareanwendungen. Genauer bezieht sich die vorliegende Erfindung auf Verfahren und Vorrichtung zum Reduzieren des Overhead, der mit Durchführung von Speicherzuordnung in Verbindung steht.

2. Beschreibung des Standes der Technik

Der Umfang von verfügbarem Speicher ist in Berechnungssystemen, wie etwa objekt-basierten Berechnungssystemen, typischerweise begrenzt. Daher muss Speicher allgemein bewahrt und wiederverwendet werden. Viele Computerprogrammiersprachen ermöglichen Softwareentwicklern, Speicher innerhalb eines Computersystems dynamisch zuzuordnen. Einige Programmiersprachen erfordern explizite manuelle Freigabe von zuvor zugeordnetem Speicher, was kompliziert und fehleranfällig sein kann. Sprachen, die explizites manuelles Speichermanagement erfordern, enthalten die Programmiersprachen C und C++. Andere Programmiersprachen nutzen automatische Speicherrückgewinnung, um Speicher zurückzugewinnen, der nicht länger notwendig ist, um die richtige Operation von Computerprogrammen sicherzustellen, die Speicher von dem Rückgewinnungssystem zuordnen. Derartige automatische Speicherrückgewinnungssysteme gewinnen Speicher ohne explizite Instruktionen oder Aufrufe von Computerprogrammen zurück, die zuvor den Speicher genutzt haben.

In objektorientierten oder objektbasierten Systemen wird die typische Einheit von Speicherzuordnung gewöhnlich als ein Objekt oder ein Speicherobjekt bezeichnet, wie durch einen Fachmann erkannt wird. Objekte, die in Gebrauch sind, werden allgemein als "lebendige" ("live") Objekte bezeichnet, wohingegen Objekte, die nicht länger benötigt werden, um Computerprogramme richtig auszuführen, typischerweise als "Müll"-Objekte oder "tote" Objekte bezeichnet werden. Der Akt zum Wiedergewinnen von Müllobjekten wird typischerweise als Speicherbereinigung (garbage collection) bezeichnet, während ein automatisches Speicherrückgewinnungssystem häufig als ein Speicherbereiniger (Müllsammler, garbage collector) bezeichnet wird. Computerprogramme, die automatische Speicherrückgewinnungssysteme verwenden, sind als Mutatoren wegen der Tatsache bekannt, dass derartige Computerprogramme zum Ändern von lebendigen Speicherobjekten während der Ausführung fähig sind. Computerprogramme, die in Sprachen geschrieben sind, wie etwa der Programmiersprache JavaTM (entwickelt durch Sun Microsystems, Inc. of Palo Alto, California), und der Programmiersprache Smalltalk, verwenden Speicherbereinigung, um Speicher automatisch zu verwalten.

Um die Rechenlast zu reduzieren, die mit Speicherbereinigung in Verbindung steht, wird allgemein ein verwalteter Speicherbereich in kleinere Sektionen unterteilt um zu ermöglichen, dass Speicherbereinigung zu einem Zeitpunkt lokal in einem Bereich durchgeführt wird. Ein Speicherpartitionierungsschema ist Generationsspeicherbereinigung. In Generationsspeicherbereinigung werden Objekte basierend auf ihrer Lebensdauer getrennt, wie von dem Zeitpunkt gemessen, in dem die Objekte erstellt wurden. Generationsspeicherbereinigung wird detaillierter in Garbage Collection: Algorithms for Automatic Dynamic Memory Management von Richard Jones und Rafael Lins (John Wiley & Sons Ltd., 1996) beschrieben. Es wurde beobachtet, dass "jüngere" Objekte wahrscheinlicher Müll werden als "ältere" Objekte. Als solches kann Generationsspeicherbereinigung verwendet werden, um die Gesamteffizienz von Speicherrückgewinnung zu erhöhen.

Stefanovic D., KcKinley K. S. und Moss J. E. B "Age-based Garbage Collection", Sigplan Notices, New York, NY, US, Vol. 34, Nr. 10, Seiten 370-381, Oktober 1999 beschreibt eine Reihe von Müllsammlern zum Rückgewinnen von Speicher. Es wird ein nicht-generationsmäßiger "ältere zuerst" kopierender Sammlungsalgorithmus beschrieben. Dieser Algorithmus unterhält die Objekte innerhalb des Heap nach Alter linear. Neue Objekte werden der Spitze des Heap hinzugefügt, bis der Heap voll ist. Wenn der Heap voll ist, betrachtet der Algorithmus die ältesten Objekte in einem Fenster fixierter Breite in dem Boden des Heap, um ältere Objekte vor jüngeren Objekten zu sammeln, wobei dadurch die Sammlung der jüngsten Objekte verschoben wird. Die toten Objekte in dem Heap werden entfernt, und die lebendigen Objekte werden verschoben, um die Stellen aufzufüllen, die die toten Objekte verlassen haben. Das Fenster gleitet dann den Heap aufwärts zu den jüngsten Objekten, und es wird die nächste Gruppe von Objekten benachbart zu den Objekten, die die vorherige Speicherbereinigung überlebt haben, gesammelt. Der Bereich des Heap, der jedes Mal gesammelt wird, wenn eine Speicherbereinigung durchgeführt wird, tastet sich allmählich von dem älteren Ende des Heap zu dem jüngeren Ende des Heap voran, und wird zu dem älteren Ende zurückgesetzt, sobald die jüngsten Objekte gesammelt wurden. Es wird auch ein generationsmäßiger "nur jüngste" Algorithmus beschrieben. Ein Stapel von Objekten in Bereiche für Hort und alte Generation unterteilt. Wenn der Hortbereich gefüllt wurde, werden alle Objekte als Müll gesammelt und lebendige Objekte werden in den Bereich der alten Generation verschoben. Es werden dann neue Objekte zusammenhängend in der Reihenfolge des Alters zu dem gleichen Hortbereich hinzugefügt, bis er erneut voll ist. Wenn die alte Generation auch voll ist, dann wird der gesamte Stapel Speicherrückgewinnung unterzogen.

Wilson Pr et al "Design of the opportunistic garbage collector", Proceedings of the Object Oriented Programming Systems Languages and Applications Conference (OOPSLA), New Orleans, 1.-6. Oktober 1989, Special Issue of Sigplan Notices, Vol. 24, Nr. 10, Oktober 1989, Reading, ACM, US, Vol. Conf. 4, 1. Oktober 1989 (1989-10-01), Seiten 23-35 beschreibt einen Opportunistic Garbage Collector (OGC), der verschiedene alternative Verfahren zum Durchführen von Generationsspeicherbereinigung vorsieht, und insbesondere verschiedene Verfahren zum Verbessern von Vorgehensrichtlinien, Heap-Organisation, Planung und Zeigerunterhaltung.

1 ist eine schematische Darstellung eines Bereiches eines Computerspeichers, der Objekte enthält und für Generationsspeicherbereinigung geeignet ist. Ein verwalteter Bereich von Speicher 102, der typischerweise ein Heap ist, der mit einem Computersystem in Verbindung steht, ist in eine neue Generation 104 und eine alte Generation 106 unterteilt. Die neue Generation 104 enthält kürzlich erstellte Objekte 110, z.B. Objekte 110a-110e, während die alte Generation 106 Objekte 110 enthält, die weniger kürzlich erstellt wurden, z.B. Objekte 110f und 110g. Wenn ein Objekt 110 im Speicher 102 zu erstellen ist, wird das Objekt in der neuen Generation 104 erstellt. In dem Fall, dass die neue Generation 104 zu dem Ausmaß voll wird, dass ein neues Objekt 110 in der neuen Generation 104 nicht zugeordnet werden kann, kann eine reinigende Speicherbereinigung in der neuen Generation 104 durchgeführt werden, um Speicherraum freizusetzen.

Im allgemeinen kann ein Objekt 110 durch andere Objekte 110 referenziert werden. Auf dem Weg eines Beispiels hat Objekt 110b einen Zeiger 114a zu einem Objekt 110a. Wie durch einen Fachmann verstanden wird, kann Objekt 110b betrachtet werden lebendig zu sein, wenn eine Wurzel (root) auf Objekt 110b transitiv zeigt. Das heißt wenn auf Objekt 110b durch eine Liste von Zeigern gezeigt wird, die wiederum durch eine Wurzel identifiziert wird, dann kann das Objekt 110b als lebendig betrachtet werden.

Wenn ein Objekt der neuen Generation 110d lebendig ist und auf ein Objekt der alten Generation 110f zeigt, "sammelt" eine Speicherbereinigung, die in der alten Generation 106 durchgeführt wird, im allgemeinen das Objekt 110f nicht, da es durch ein lebendiges Objekt referenziert wird. Falls jedoch ein Objekt der neuen Generation 110d tot ist, kann eine Speicherbereinigung, die in der neuen Generation 104 durchgeführt wird, dazu führen, dass das Objekt der alten Generation 110f unerreichbar wird, falls auf das Objekt der alten Generation 110f nicht durch irgend ein anderes Objekt gezeigt wird. Falls das Objekt der alten Generation 110f unerreichbar ist, dann wird Speicherbereinigung, die in der alten Generation 106 durchgeführt wird, zu der Bereinigung des Objektes der alten Generation 110f führen. Wenn ein Zeiger 114b von dem Objekt der neuen Generation 110d zu dem Objekt der alten Generation 110f zeigt, wird das Objekt der alten Generation 110f betrachtet, gepachteter Müll zu sein, da das Objekt der alten Generation 110f unter Verwendung von Speicherbereinigung der neuen Generation nicht bereinigt werden kann, d.h. einer Speicherbereinigung, die in der neuen Generation 104 durchgeführt wird.

Während eines reinigenden Speicherbereinigungsprozesses in der neuen Generation 104, werden, wenn die neue Generation 104 voll wird, wie nachstehend mit Bezug auf 2 erörtert, lebendige Objekte 110 in der neuen Generation 104 von der neuen Generation 104 in die alte Generation 106 kopiert. Neu zugeordnete Objekte 110 in der neuen Generation 104 sind häufig lebendig, und müssen daher während einer reinigenden Speicherbereinigung von der neuen Generation 104 in die alte Generation 106 kopiert werden. Im allgemeinen sind kopierende Operationen langsam und aufwändig. Als ein Ergebnis ist der gesamte Speicherbereinigungsprozess aufwändig.

Einige generationsmäßige Speicherbereiniger kopieren lebendige Objekte von einer neuen Generation in einen Zwischenbereich, bevor die Objekte zu einer alten Generation in Pacht genommen werden. 1b ist eine schematische Darstellung eines Speicherraums, der in eine neue Generation, einen Zwischenbereich und eine alte Generation unterteilt ist. Ein Speicherraum 202 enthält eine neue Generation 204, einen "von-Raum" und "zu-Raum" 205 und eine alte Generation 206. Neu zugeordnete Objekte 210 sind in der neuen Generation 204 zugeordnet. Wenn die neue Generation 204 voll wird, werden lebendige Objekte 210 aus der neuen Generation 204 heraus und in den von-Raum und zu-Raum 205 kopiert. Objekten 210 wird erlaubt, in dem von-Raum und zu-Raum 205 für eine gewisse Zeitperiode zu bleiben, z.B. für eine vorbestimmte Zeitdauer oder bis der von-Raum und zu-Raum 205 voll ist, um zu ermöglichen, dass Objekte 210 in dem von-Raum und zu-Raum 205 sterben. Periodisch wird, wie z.B., wenn der von-Raum und zu-Raum 205 voll ist, Speicherbereinigung in dem von-Raum und zu-Raum 205 durchgeführt. Während der Speicherbereinigung in dem von-Raum und zu-Raum 205 werden lebendige Objekte in dem von-Raum und zu-Raum 205 in die alte Generation 206 kopiert oder in Pacht genommen.

Mit Bezug auf 2 wird ein konventionelles Verfahren zum Durchführen einer reinigenden Speicherbereinigung in einem verwalteten Bereich eines Speichers beschrieben, der in eine neue Generation und eine alte Generation unterteilt ist, z.B. der verwaltete Bereich 102 von 1. Speziell wird ein Prozess zum Durchführen einer reinigenden Speicherbereinigung in einer neuen Generation erörtert. Ein Prozess 252 zum Durchführen von Speicherbereinigung beginnt in Schritt 256, in dem eine Liste lebendiger Objekte in der neuen Generation erhalten wird. Eine Liste lebendiger Objekte kann unter Verwendung einer Vielfalt unterschiedlicher Verfahren erhalten werden. Z.B. involviert ein Verfahren, das verwendet werden kann, um eine Liste lebendiger Objekte zu erhalten, Untersuchung globaler Objekte, oder Wurzeln, die Objekte innerhalb entweder einer von beiden oder beider einer neuen Generation und einer alten Generation referenzieren, um Objekte zu identifizieren, die gegenwärtig in Gebrauch sind.

Nachdem eine Liste lebendiger Objekte erhalten ist, wird ein lebendiges Objekt, das in der Liste identifiziert ist, von der neuen Generation in Schritt 258 erhalten. Während einer reinigenden Speicherbereinigung werden im allgemeinen lebendige Objekte in der neuen Generation in die alte Generation in der Bemühung kopiert, Speicherraum in der neuen Generation freizusetzen. Daher wird in Schritt 260 das lebendige Objekt zu der alten Generation kopiert. Wie durch einen Fachmann verstanden werden sollte, enthält Kopieren eines lebendigen Objektes in die alte Generation Kopieren von Objekten, die durch das lebendige Objekte referenziert werden, zusätzlich zum Ändern beliebiger Zeiger, die das lebendige Objekt identifizieren, derart, dass die Zeiger stattdessen die Kopie des Objektes identifizieren. Ferner setzt Kopieren des lebendigen Objektes von der neuen Generation in die alte Generation effektiv Speicherraum in der neuen Generation, der mit dem lebendigen Objekt in Verbindung stand, für andere Zwecke frei.

Sobald das lebendige Objekte in Schritt 260 in die alte Generation kopiert ist, wird in Schritt 262 eine Bestimmung bezüglich dessen durchgeführt, ob es zusätzliche lebendige Objekte gibt, die in der neuen Generation bleiben. D.h. es wird bestimmt, ob es mehr lebendige Objekte gibt, die in der Liste lebendiger Objekte identifiziert sind. Wenn bestimmt wird, dass es zusätzliche lebendige Objekte in der Liste lebendiger Objekte gibt, dann kehrt der Prozessfluss zu Schritt 258 zurück, wo das nächste lebendigen Objekt, das in der Liste identifiziert ist, erhalten wird. Wenn es keine zusätzlichen lebendigen Objekte in der neuen Generation gibt, ist die Angabe alternativ, dass es keine lebendigen Objekte gibt, die in der neuen Generation bleiben, und der Prozess zum Durchführen einer reinigenden Speicherbereinigung in der neuen Generation wird abgeschlossen.

Eine reinigende Speicherbereinigung ist häufig ein aufwändiger Prozess. Wie oben erwähnt, ist speziell das Kopieren eines lebendigen Objektes während einer reinigenden Speicherbereinigung eine langsame und aufwändige Operation. Wenn viele lebendige Objekte während einer reinigenden Speicherbereinigung kopiert werden, oder wenn einige große Objekte während einer reinigenden Speicherbereinigung kopiert werden, wird daher der Speicherbereinigungsprozess selbst sowohl langsam als auch teuer.

Was gewünscht wird, ist deshalb ein Verfahren zum Reduzieren der Kosten, die mit einer generationsmäßigen reinigenden Speicherbereinigung in Verbindung stehen. D.h. was benötigt wird, sind ein Verfahren und eine Vorrichtung zum Reduzieren der Zahl lebendiger Objekte, die während einer generationsmäßigen reinigenden Speicherbereinigung zu einer alten Generation kopiert werden.

Die vorliegende Erfindung bezieht sich auf einen Speicherraum, der eine Durchführung effizienter generationsmäßiger reinigender Speicherbereinigung ermöglicht. Gemäß einem Aspekt der vorliegenden Erfindung wird vorgesehen ein Computer-implementiertes Verfahren zum Rückgewinnen von Speicherraum in einem verwalteten Speicherbereich folgend einer generierten reinigenden Speicherbereinigung (Freispeichersammlung), wobei der verwaltete Speicherbereich einen neuen Generationsbereich und einen alten Generationsbereich enthält, der neue Generationsbereich, der der Hort ist, angeordnet ist, die zuletzt zugeordneten Objekte zu speichern, der alte Generationsbereich angeordnet ist, ältere Objekte zu speichern, das Computer-implementierte Verfahren umfassend: Bestimmen, wann eine erste Sektion der neuen Generation gefüllt ist, derart, dass die erste Sektion unzureichenden Speicherraum für die Zuordnung eines neuen Objektes hat, wobei die erste Sektion anfangs angeordnet ist, Speicherzuordnung für neu erstellte Objekte zu unterstützen; Durchführen einer generationsmäßigen reinigenden Speicherbereinigung in einer zweiten Sektion des neuen Generationsbereiches, wenn bestimmt ist, dass die erste Sektion gefüllt ist durch Kopieren aller Live-Objekte von der zweiten Sektion in den alten Generationsbereich; Einstellen der zweiten Sektion des neuen Generationsbereiches derart, dass die zweite Sektion angeordnet ist, Speicherzuordnung für neu erstellte Objekte zu unterstützen, nachdem die reinigende Speicherbereinigung durchgeführt ist; und Einstellen der ersten Sektion derart, dass die erste Sektion nicht länger angeordnet ist, Speicherzuordnung für neu erstellte Objekte zu unterstützen, nachdem die reinigende Speicherbereinigung durchgeführt ist, und die Sektion des neuen Generationsbereiches wird, in dem Bereinigen durchgeführt wird.

In einer anderen Ausführungsform enthält das Verfahren auch einen Versuch, ein neues Objekt in der zweiten Sektion zuzuordnen, nachdem die erste Sektion eingestellt ist, Zuordnung eines neuen Objektes zu unterstützen, und Bestimmen, wann die zweite Sektion gefüllt ist. Wenn bestimmt wird, dass die zweite Sektion nicht gefüllt ist, wird ein neues Objekt in der zweiten Sektion zugeordnet. Wenn bestimmt wird, dass die zweite Sektion gefüllt ist, wird alternativ in der ersten Sektion Speicherbereinigung durchgeführt. In einer derartigen Ausführungsform kann, wenn bestimmt wird, dass die zweite Sektion gefüllt ist, das Verfahren ferner enthalten Rücksetzen der zweiten Sektion derart, dass die zweite Sektion nicht länger angeordnet ist, Zuordnung eines neuen Objektes zu unterstützen, Rücksetzen der ersten Sektion derart, dass die erste Sektion erneut angeordnet ist, Zuordnung eines neuen Objektes zu unterstützen, und Zuordnen des neuen Objektes in der ersten Sektion.

Gemäß einem weiteren Aspekt der vorliegenden Erfindung wird vorgesehen ein Computersystem zum Rückgewinnen von Speicherraum in einem verwalteten Speicherbereich, folgend einer generationsmäßigen reinigenden Speicherbereinigung, wobei der verwaltete Speicherbereich einen neuen Generationsbereich und einen alten Generationsbereich enthält, der neue Generationsbereich, der der Hort ist, angeordnet ist, die zuletzt zugeordneten Objekte zu speichern, der alte Generationsbereich angeordnet ist, ältere Objekte zu speichern, das Computersystem umfassend: einen Prozessor; eine Bestimmungseinrichtung zum Bestimmen, wann eine erste Sektion des neuen Generationsbereiches gefüllt ist, derart, dass die erste Sektion unzureichenden Speicherraum für die Zuordnung eines neuen Objektes hat, wobei die erste Sektion anfangs angeordnet ist, Speicherzuordnung für neu erstellte Objekte zu unterstützen; einen generationsmäßigen reinigenden Speicherbereiniger, der angeordnet ist, eine zweite Sektion des neuen Generationsbereiches zu bereinigen, wenn bestimmt ist, dass die erste Sektion gefüllt ist durch Kopieren aller Live-Objekte von der zweiten Sektion zu dem alten Generationsbereich; und einen Verfolgungsmechanismus, der angeordnet ist, die zweite Sektion des neuen Generationsbereiches derart einzustellen, dass die zweite Sektion angeordnet ist, Speicherzuordnung für neu erstellte Objekte zu unterstützen, wobei der Verfolgungsmechanismus weiter angeordnet ist, die erste Sektion derart einzustellen, dass die erste Sektion nicht angeordnet ist, Speicherzuordnung für neu erstellte Objekte zu unterstützen, nachdem der Speicherbereiniger die zweite Sektion des neuen Generationsbereiches bereinigt und die Sektion des neuen Generationsbereiches wird, in dem Bereinigen durchgeführt wird.

Diese und andere Vorteile der vorliegenden Erfindung werden beim Lesen der folgenden detaillierten Beschreibung und Untersuchen der verschiedenen Figuren der Zeichnungen offensichtlich.

Die Erfindung kann am besten durch Verweis auf die folgende Beschreibung verstanden werden, die in Verbindung mit den begleitenden Zeichnungen aufgenommen wird, in denen:

1a eine schematische Darstellung eines konventionellen Speicherraums ist;

1b eine schematische Darstellung eines zweiten konventionellen Speicherraums ist;

2 ein Prozessflussdiagramm ist, das einen Prozess zum Durchführen einer Speicherbereinigung in einem konventionellen Speicherraum, d.h. Speicherraum 102 von 1a, veranschaulicht;

3 eine schematische Darstellung eines Speicherraums mit einer partitionierten neuen Generation in Übereinstimmung mit einer Ausführungsform der vorliegenden Erfindung ist;

4 ein Prozessflussdiagramm ist, das einen Prozess zum Durchführen einer Speicherbereinigung in einem Speicherraum mit einer partitionierten neuen Generation, d.h. Speicherraum 302 von 3, in Übereinstimmung mit einer Ausführungsform der vorliegenden Erfindung veranschaulicht;

5 ein Prozessflussdiagramm ist, das einen Prozess zum Zuordnen eines Objektes in einem Speicherraum in Übereinstimmung mit einer Ausführungsform der vorliegenden Erfindung veranschaulicht;

6 eine schematische Darstellung eines Allzweck-Computersystems ist, das zum Implementieren der vorliegenden Erfindung geeignet ist; und

7 eine schematische Darstellung einer virtuellen Maschine ist, die durch das Computersystem von 6 unterstützt wird, und zum Implementieren der vorliegenden Erfindung geeignet ist.

Eine generationsmäßige reinigende Speicherbereinigung involviert typischerweise Bereinigung einer neuen Generation eines verwalteten Speicherbereiches, der auch eine alte Generation enthält, wenn die neue Generation zu dem Ausmaß gefüllt ist, dass ein neues Objekt in der neuen Generation nicht zugeordnet werden kann. Während der Bereinigung werden, wie in Garbage Collection: Algorithms for Automatic Dynamic Memory Management von Richard Jones und Rafael Lins (John Wiley & Sons Ltd., 1996) beschrieben wird, lebendige Objekte von der neuen Generation in die alte Generation kopiert. Da Kopieren lebendiger Objekte aufwändig und langsam ist, ist eine reinigende Speicherbereinigung typischerweise ineffizient. Da Kopieren lebendiger Objekte während einer reinigenden Speicherbereinigung bewirkt, dass die Speicherbereinigung langsam und aufwändig ist, kann Reduzieren der Zahl lebendiger Objekte, die während einer Speicherbereinigung von einer neuen Generation zu einer alten Generation kopiert werden, die Effektivität und Effizienz von Speicherbereinigung erhöhen.

Es wurde beobachtet, dass Objekte in einem jüngeren Ende, oder neueren Ende, einer neuen Generation mehr einer Tendenz aufweisen lebendig zu sein als Objekte in einem älteren Ende einer neuen Generation. Das heißt es wurde beobachtet, dass die zuletzt zugeordneten Objekte in einer neuen Generation wahrscheinlicher lebendig sind als die weniger kürzlich zugeordneten Objekte in der neuen Generation. Während sich der Besitz eines Objektes in der neuen Generation verlängert, d.h. während ein Objekt ein älteres Objekt in der neuen Generation wird, erhöht sich daher die Wahrscheinlichkeit, dass das Objekt sterben wird.

In einer Ausführungsform der vorliegenden Erfindung wird eine neue Generation eines verwalteten Bereiches eines Speicherraums, der in eine neue Generation und eine alte Generation unterteilt ist, partitioniert. Speziell wird die neue Generation in zwei Sektionen partitioniert. Die zuletzt zugeordneten Objekte in der neuen Generation werden in einer "jüngeren" Sektion gehalten, während die weniger kürzlich zugeordneten Objekte in der neuen Generation in einer "älteren" Sektion gehalten werden. Wenn die neue Generation zu dem Ausmaß gefüllt wird, dass es nicht möglich ist, ein zusätzliches Objekt in der neuen Generation zuzuordnen, wird nur die ältere Sektion der neuen Generation bereinigt. Da die Objekte in der älteren Sektion älter als die Objekte in der jüngeren Sektion sind, sind die Objekte in der älteren Sektion typischerweise tot. Deshalb ist der Umfang von Kopieren, das mit einer reinigenden Speicherbereinigung in Verbindung steht, relativ gering. Indem die jüngere Sektion nicht bereinigt wird, wird ferner den Objekten in der jüngeren Sektion mehr Zeit gegeben zu sterben. Nachdem die Bereinigung der älteren Sektion abgeschlossen ist, wird die ältere Sektion effektiv die aktuelle jüngere Sektion, während die jüngere Sektion effektiv die aktuelle ältere Sektion wird, in der Bereinigung durchgeführt wird, wenn sich die aktuelle jüngere Sektion auffüllt.

Durch Bereinigung nur einer Sektion der neuen Generation wird nur eine Sektion der neuen Generation für Objektzuordnung verfügbar sein. Deshalb wird sich die Zahl von gesamten reinigenden Speicherbereinigungen gegenüber der Zahl erhöhen, die mit einer konventionellen ungeteilten neuen Generation in Verbindung steht. Da jedoch allgemein weniger Objekte in die alte Generation während einer Speicherbereinigung kopiert werden müssen, die in der partitionierten neuen Generation durchgeführt wird, werden der Zeitumfang und Berechnungsressourcen, die durch eine Speicherbereinigung verwendet werden, allgemein gering sein. Das heißt obwohl typischerweise mehr Speicherbereinigungen auftreten werden, werden die Speicherbereinigungen allgemein rascher und weniger aufwändig sein.

Bezug nehmend auf 3 wird ein verwalteter Bereich von Speicherraum mit einer partitionierten neuen Generation in Übereinstimmung mit einer Ausführungsform der vorliegenden Erfindung beschrieben. Ein Speicherraum 302, der häufig ein Heap ist, der mit einem Computersystem in Verbindung steht, ist in eine neue Generation 306 und eine alte Generation 310 unterteilt. Die neue Generation 306 ist angeordnet, die zuletzt zugeordneten Objekte 314 im Speicher zu enthalten, während die alte Generation 306 angeordnet ist, Objekte 314 zu enthalten, die nicht kürzlich zugeordnet wurden.

In der beschriebenen Ausführungsform ist die neue Generation 306, die auch als ein "Hort" oder "Eden" bezeichnet wird, in zwei Sektionen 318 partitioniert. Sektion 318a ist eine jüngere Sektion der neuen Generation 306, während Sektion 318b eine ältere Sektion der neuen Generation 306 ist. Sektion 318a enthält die jüngeren Objekte 314 in der neuen Generation 306, während Sektion 318b die älteren Objekte 314 in der neuen Generation 306 enthält. Wenn Objekte 314 in der neuen Generation 306 zugeordnet werden, werden deshalb Objekte 314 in Sektion 318a zugeordnet.

Zur Vereinfachung der Erläuterung können Sektion 318a und Sektion 318b effektiv betrachtet werden, zwei getrennte Horte zu sein. Mit anderen Worten kann jede Sektion 318 als eine getrennte neue Generation behandelt werden. Wenn Sektionen 318 als getrennte Horte betrachtet werden, wird, sobald die Sektion, in der Objekte zuzuordnen sind, z.B. Sektion 318a, voll ist, die andere Sektion, z.B. Sektion 318b, bereinigt und wird der neue Hort, in dem Objekte zugeordnet werden. Wenn Sektion 318b der Hort ist, in dem Objekte zugeordnet sind, wird ähnlich, sobald Sektion 318b voll ist, eine Speicherbereinigung in Sektion 318a durchgeführt, die dann der Hort wird, in dem Objekte zuzuordnen sind.

Ein Versuch, ein Objekt in Sektion 318a zuzuordnen, kann nicht erfolgreich sein, wenn es nicht ausreichenden Speicherraum in Sektion 318a gibt, um ein neues Objekt zuzuordnen. Als solche kann eine Speicherbereinigung durchgeführt werden, um Speicherraum zurückzugewinnen, derart, dass ein neues Objekt zugeordnet werden kann. Es sollte erkannt werden, dass wenn Sektion 318a ausreichenden Speicherraum nicht enthält, um die Zuordnung eines neuen Objektes zu unterstützen, Sektion 318b typischerweise auch effektiv voll ist. In einer Ausführungsform wird, wenn Sektion 318a voll ist, eine generationsmäßige reinigende Speicherbereinigung in Sektion 318b durchgeführt. Da es wahrscheinlich ist, dass Objekte 314 in Sektion 318b Müllobjekte sind, z.B. Objekt 314e, ist die Zahl von Objekten 314, die in die alte Generation 310 während der Speicherbereinigung kopiert werden, typischerweise relativ gering. Wie gezeigt, ist Objekt 314g ein lebendiges Objekt in Sektion 318b, und würde während einer Speicherbereinigung in die alte Generation 310 kopiert. Da allgemein wenige lebendige Objekte 314 von Sektion 318b in die alte Generation 310 kopiert werden, kann der Overhead, der mit Speicherbereinigung in Verbindung steht, relativ gering sein. Als solche wird die Speicherbereinigung allgemein effizient geschehen. Sobald Speicherbereinigung in Sektion 318b durchgeführt ist, wird der wiedergewonnene Speicherraum für die Zuordnung von Objekten 314 allgemein verfügbar sein, wie nachstehend mit Verweis auf 4 und 5 beschrieben wird.

Eine Grenze 322, die die neue Generation 306 in Sektionen 318 unterteilt, ist eine flexible, oder bewegliche, Grenze. Mit anderen Worten kann die Grenze 322 effektiv verschoben werden, um die relativen Größen von Sektionen 318 zu ändern. Z.B. kann in einer Ausführungsform die Grenze 322 derart positioniert sein, dass die Sektion 318a und die Sektion 318b jede im wesentlichen den gleichen Umfang von Speicherraum enthalten.

Es sollte erkannt werden, dass die Positionierung der Grenze 322 ein dynamischer Prozess sein kann. Speziell kann die Grenze 322 je nach Notwendigkeit während einer Verarbeitung neu positioniert werden, um das Leistungsverhalten eines Berechnungssystems effektiv zu optimieren. Auf dem Weg eines Beispiels kann, falls beobachtet wird, dass während Speicherbereinigung eine beträchtliche Zahl lebendiger Objekte 314 von Sektion 318b in die alte Generation 310 kopiert wird, dann die Grenze 322 positioniert werden, die Größe von Sektion 318a relativ zu Sektion 318b derart zu erhöhen, dass lebendige Objekte 314 wahrscheinlicher in Sektion 318b bleiben, bis sie sterben. Wenn sehr wenige lebendige Objekte 314 während Speicherbereinigung in die alte Generation 310 kopiert werden, kann alternativ die Grenze 322 derart neu positioniert werden, dass die relative Größe von Sektion 318b erhöht wird, um die Häufigkeit von Bereinigungen zu verringern. Obwohl die Verfahren, die verwendet werden um zu bestimmen, ob die Grenze 322 neu positioniert wird oder nicht, stark variieren können, kann ein geeignetes Verfahren auf dem Umfang von Overhead beruhen, der mit Speicherbereinigung in Verbindung steht, z.B. kann die Position von Grenze 322 derart abgestimmt werden, dass der Umfang von zugehörigem Berechnungsoverhead innerhalb eines gewünschten Bereiches ist.

Wie durch einen Fachmann verstanden wird, werden Objekte in Speicherraum 302 typischerweise durch eine feste Wurzel (nicht gezeigt) referenziert, die zu Speicherraum 302 extern ist und Zeiger zu einigen Objekten 314 enthält, die sich in Speicherraum 302 befinden. Beliebige Objekte 314, die durch folgende Verweise von der feste Wurzel erreicht werden können, sind als lebendige Objekte zu betrachten. Um in einem einzelnen Speicherbereich, wie etwa Sektion 318b, zu arbeiten, muss ein Speicherbereiniger Kenntnis über alle Verweise in die Sektion 318b haben. Verweise auf einen spezifischen Bereich werden als Wurzeln für diesen Bereich bezeichnet. Es sollte erkannt werden, dass Wurzeln sowohl externe Verweise, z.B. feste Wurzeln, als auch Verweise von anderen Bereichen eines Computerspeichers enthalten können. Entsprechend sehen Speicherbereiniger allgemein Mechanismen zum Finden und Verfolgen von Wurzeln, oder Verweisen, vor.

Einige Objekte innerhalb der neuen Generation 306 können auch als Wurzeln bezeichnet werden, wenn von ihnen angenommen wird, dass sie lebendig sind und einen Zeiger zu einem anderen Objekt 314 enthalten. Auf dem Weg eines Beispiels kann das Objekt 314g als eine Wurzel betrachtet werden. Wenn das Objekt 314g lebendig ist und auf Objekt 314i in der alten Generation 310 zeigt, "sammelt" eine Speicherbereinigung, die in der alten Generation 310 durchgeführt wird, Objekt 314i nicht. Falls jedoch Objekt 314g tot ist, wird eine Speicherbereinigung, die in Sektion 318b durchgeführt wird, dazu führen, dass Objekt 314i unerreichbar wird, da auf Objekt 314inicht durch ein beliebiges anderes Objekt 314 gezeigt wird. Falls Objekt 314i unerreichbar ist, wird dann eine Speicherbereinigung, die in der alten Generation 310 durchgeführt wird, zu der Bereinigung von Objekt 314i führen.

4 ist ein Prozessflussdiagramm, das einen Prozess zum Durchführen einer reinigenden Speicherbereinigung in einem Speicherraum mit einer partitionierten neuen Generation, d.h. Speicherraum 302 von 3, in Übereinstimmung mit einer Ausführungsform der vorliegenden Erfindung veranschaulicht. Ein Prozess 402 zum Durchführen einer Speicherbereinigung in einem Abschnitt einer neuen Generation beginnt in Schritt 406, in dem eine Liste lebendiger Objekte in einem Speicherraum erhalten wird. Ein Verfahren, das verwendet wird, um eine Liste lebendiger Objekte zu erhalten, involviert Verfolgen von Wurzeln, oder globalen Objekten, die auf Objekte innerhalb von entweder einer von beiden oder beiden einer neuen Generation und einer alten Generation verweisen, um zu bestimmen, welche Objekten noch in Gebrauch sind. Wurzeln können sich z.B. in einem Stapel oder innerhalb einer neuen Generation befinden.

In Schritt 408 wird ein lebendiges Objekt von der neuen Generation erhalten. Erhalten eines lebendigen Objektes enthält in einer Ausführungsform Erhalten des ersten lebendigen Objektes, das in der Liste lebendiger Objekte identifiziert ist. Sobald das lebendige Objekt von der neuen Generation erhalten ist, wird in Schritt 410 eine Bestimmung bezüglich dessen durchgeführt, ob das lebendige Objekt in der älteren Sektion der neuen Generation ist. Falls die Bestimmung ist, dass das lebendige Objekt in der älteren Sektion ist, dann wird in Schritt 412 das lebendige Objekt von der älteren Sektion in die alte Generation kopiert. Im allgemeinen enthält Kopieren eines Objektes von der älteren Sektion in die alte Generation Kopieren von Bits, die mit dem Objekt in Verbindung stehen, ebenso wie Rücksetzen beliebiger Zeiger auf das Objekt derart, dass die Zeiger das kopierte Objekt identifizieren. Zusätzlich enthält Kopieren eines Objektes Ändern eines beliebigen Zeigers, der von dem Objekt entspringt, um von dem kopierten Objekt zu entspringen.

Nachdem das lebendige Objekt von der älteren Sektion in die alte Generation in Schritt 412 kopiert ist, wird in Schritt 414 bestimmt, ob es zusätzliche lebendige Objekte in der neuen Generation gibt. Mit anderen Worten wird eine Bestimmung hinsichtlich dessen durchgeführt, ob es zusätzliche lebendige Objekte gibt, die in der Liste lebendiger Objekte identifiziert sind, die zu erhalten sind. Wenn bestimmt wird, dass es zusätzliche lebendige Objekte gibt, die zu erhalten sind, dann kehrt der Prozessfluss zu Schritt 408 zurück, wo ein anderes lebendiges Objekt von der neuen Generation erhalten wird.

Wenn in Schritt 414 bestimmt wird, dass es keine lebendigen Objekte mehr gibt, die in der neuen Generation bleiben, z.B. dass alle lebendigen Objekte in der älteren Sektion der neuen Generation in die alte Generation kopiert wurden, dann wird alternativ die ältere Sektion effektiv eingestellt, die aktuelle jüngere Sektion zu sein, und die jüngere Sektion effektiv eingestellt, die aktuelle ältere Sektion zu sein, indem Buchführungsinformation für den Zuordner derart aktualisiert wird, dass Zuordnungen in der aktuellen jüngeren Sektion geschehen werden. Das heißt die ältere Sektion wird die neu definierte jüngere Sektion, und die jüngere Sektion wird die neu definierte ältere Sektion. Wie durch einen Fachmann erkannt wird, wird, nachdem eine Bereinigung in einer Sektion abgeschlossen ist, diese Sektion nicht länger lebendige Objekte enthalten. Während einer Bereinigung, die in einer Sektion durchgeführt wird, werden die lebendigen Objekte aus der Sektion heraus kopiert.

Beim effektiven Austausch der älteren Sektion und der jüngeren Sektion werden beliebige Zeiger und Variablen, die mit einer Verfolgung der neuen Generation in Verbindung stehen, derart zurückgesetzt, dass beliebige neue Objekte, die in der neuen Generation zugeordnet werden, wie nachstehend mit Bezug auf 5 erörtert wird, in der leeren aktuellen jüngeren Sektion zugeordnet werden. In einer Ausführungsform können nicht-lebendige Objekte, die in der aktuellen jüngeren Sektion, oder der neu definierten jüngeren Sektion, bleiben, verworfen oder anderenfalls auf Null gesetzt werden, derart, dass der Speicherraum in der aktuellen jüngeren Sektion freigesetzt wird. Sobald die aktuelle jüngere Sektion, die effektiv leer ist, und die aktuelle ältere Sektion, die voll ist, der neuen Generation im wesentlichen eingestellt sind, ist der Speicherbereinigungsprozess abgeschlossen.

Zurückkehrend zu Schritt 410 und der Bestimmung, ob ein lebendiges Objekt, das von der neuen Generation erhalten wird, in der älteren Sektion ist, wenn bestimmt wird, dass das lebendige Objekt nicht in der älteren Sektion ist, ist die Implikation dann, dass das lebendige Objekt in der jüngeren Sektion ist. Als solches wird das lebendige Objekt nicht in die alte Generation kopiert und ihm wird stattdessen erlaubt, in der jüngeren Sektion zu bleiben. Entsprechend fährt der Prozessfluss zu Schritt 414 fort, wo eine Bestimmung bezüglich dessen durchgeführt wird, ob es zusätzliche lebendige Objekte gibt, die von der neuen Generation zu erhalten sind.

Obwohl eine Speicherbereinigung in im wesentlichen einem beliebigen geeigneten Zeitpunkt während der Verarbeitung einer Anwendung geschehen kann, geschieht eine Speicherbereinigung typischerweise entweder, wenn ein Versuch durchgeführt wird, ein Objekt zuzuordnen, oder während einer Pause in der Verarbeitung. Eine Speicherbereinigung kann während einer Pause in der Verarbeitung geschehen, da während einer Pause allgemein Berechnungsressourcen verfügbar sind. Auf dem Weg eines Beispiels kann eine Speicherbereinigung während eines Sicherungspunktes (safepoint) geschehen. Ein Sicherungspunkt tritt auf, wie durch einen Fachmann erkannt wird, wenn im wesentlichen jeder Thread in einem System in einer sicheren Region ist oder anderenfalls vom Arbeiten abgehalten wird, derart, dass die Threads effektiv keine Probleme für das Leistungsverhalten einer globalen Operation, wie etwa einer Speicherbereinigung, verursachen.

Mit Bezug auf 5 werden die Schritte, die mit einer Durchführung einer Objektzuordnung in Verbindung stehen, die den Speicherbereinigungsprozess 402 von 4 verwendet, wenn es notwendig ist, Speicherraum freizusetzen, in Übereinstimmung mit einer Ausführungsform der vorliegenden Erfindung beschrieben. Wie zuvor erwähnt, geschieht Speicherbereinigung häufig, um zusätzlichen Speicherraum freizusetzen, wenn es nicht ausreichenden Speicherraum gibt, der verfügbar ist, um Zuordnung eines Objektes zu gestatten.

Ein Prozess 502 zum Beantworten eines Versuches, ein Objekt in der neuen Generation eines Speicherraums zuzuordnen, beginnt in Schritt 504, in dem eine Bestimmung bezüglich dessen durchgeführt wird, ob die jüngere Sektion, z.B. der jüngere Hortbereich, der neuen Generation voll ist. D.h. es wird bestimmt, ob die jüngere Sektion der neuen Generation ausreichend freien Raum hat um zu ermöglichen, dass ein Objekt in der jüngeren Sektion zugeordnet wird. Falls die Bestimmung ist, dass die jüngere Sektion nicht voll ist, ist die Angabe, dass es ausreichenden Raum in der jüngeren Sektion gibt, um die Zuordnung eines Objektes zu unterstützen. Entsprechend bewegt sich der Prozessfluss von Schritt 504 zu Schritt 510, wo ein Objekt in der jüngeren Sektion zugeordnet wird. Sobald das Objekt in der jüngeren Sektion zugeordnet ist, ist der Prozess zum Beantworten eines Versuches, ein Objekt zuzuordnen, abgeschlossen.

Wenn alternativ in Schritt 504 bestimmt wird, dass nicht ausreichender Raum in der jüngeren Sektion verfügbar ist, um Zuordnung eines Objektes zu ermöglichen, wird dann eine reinigende Speicherbereinigung in der älteren Sektion der neuen Generation in Schritt 506 durchgeführt. Ein reinigender Speicherbereinigungsprozess, der verwendet werden kann, wurde zuvor mit Bezug auf 4 erörtert.

Durchführung der reinigenden Speicherbereinigung in Schritt 506 bewirkt effektiv, dass die ältere Sektion geleert wird, d.h. Speicherraum in der älteren Sektion freigesetzt wird. Wie zuvor mit Bezug auf 4 beschrieben, werden, sobald die ältere Sektion geleert ist, die ältere Sektion und die jüngere Sektion effektiv ausgetauscht. D.h. die ältere Sektion, die effektiv leer ist, wird als eine aktuelle jüngere Sektion behandelt, während die jüngere Sektion, die voll ist, als eine aktuelle ältere Sektion behandelt wird. Obwohl im wesentlichen ein beliebiges Verfahren verwendet werden kann, um die frühere ältere Sektion als eine aktuelle jüngere Sektion zu behandeln, enthalten Verfahren allgemein Einstellen verschiedener Variablen und Flags um anzuzeigen, dass eine beliebige Zuordnung eines neuen Objektes in dieser aktuellen jüngeren Sektion zu geschehen hat.

Nachdem die reinigende Speicherbereinigung abgeschlossen ist, wird ein Objekt in der aktuellen jüngeren Sektion in Schritt 508 zugeordnet. Mit anderen Worten wird ein Objekt in dem Speicherbereich zugeordnet, der während der reinigenden Speicherbereinigung geleert wurde. Sobald das Objekt in Schritt 508 zugeordnet ist, ist der Prozess zum Beantworten eines Versuches, ein Objekt zuzuordnen, abgeschlossen.

6 veranschaulicht ein typisches Allzweck-Computersystem, das zum Implementieren der vorliegenden Erfindung geeignet ist. Das Computersystem 1030 enthält eine beliebige Zahl von Prozessoren 1032 (auch als zentrale Verarbeitungseinheiten oder CPUs bezeichnet), die mit Speichereinrichtungen gekoppelt sind, die primäre Speichereinrichtungen 1034 (typischerweise ein Speicher mit wahlfreiem Zugriff oder RAM) und primäre Speichereinrichtungen 1036 (typischerweise ein Nur-Lesespeicher oder ROM) gekoppelt sind.

Das Computersystem 1030, oder genauer die CPU 1032, kann angeordnet sein, eine virtuelle Maschine zu unterstützen, wie durch einen Fachmann erkannt wird. Ein Beispiel einer virtuellen Maschine, die in Computersystem 1030 unterstützt wird, wird nachstehend mit Bezug auf 7 beschrieben. Wie in der Technik gut bekannt ist, agiert ROM, um Daten und Instruktionen zu der CPU 32 unidirektional zu transferieren, während RAM typischerweise verwendet wird, um Daten und Instruktionen auf eine bidirektionale Art und Weise zu transferieren. Die CPU 1032 kann allgemein eine beliebige Zahl von Prozessoren enthalten. Beide primären Speichereinrichtungen 1034, 1036 können beliebige geeignete computerlesbare Medien enthalten. Ein sekundäres Speichermedium 1038, das typischerweise eine Massenspeichereinrichtung ist, ist mit CPU 1032 auch bidirektional gekoppelt und stellt zusätzliche Datenspeicherkapazität bereit. Die Massenspeichereinrichtung 1038 ist ein computerlesbares Medium, das verwendet werden kann, um Programme einschließlich Computercode, Daten und dergleichen zu speichern. Typischerweise ist Massenspeichereinrichtung 1038 ein Speichermedium, wie etwa eine Festplatte oder ein Band, die/das allgemein langsamer als primäre Speichereinrichtungen 1034, 1036 ist. Die Massenspeichereinrichtung 1038 kann die Form eines magnetischen oder Papierbandlesegerätes oder einer beliebigen anderen gut bekannten Einrichtung annehmen. Es wird erkannt, dass die Information, die innerhalb der Massenspeichereinrichtung 1038 gehalten wird, in geeigneten Fällen auf eine standardmäßige Weise als Teil von RAM 1036 als virtueller Speicher einbezogen werden kann. Eine spezifische primäre Speichereinrichtung 1034, wie etwa ein CD-ROM, kann auch Daten unidirektional zu den CPU 1032 weitergeben.

Die CPU 1032 ist auch mit einer oder mehr Eingabe-/Ausgabeeinrichtungen 1040 gekoppelt, die enthalten können, aber nicht darauf begrenzt sind, Einrichtungen, wie etwa Videomonitore, Track Balls, Mäuse, Tastaturen, Mikrofone, berührungsempfindliche Anzeigen, Geberkartenlesegeräte, magnetische oder Papierbandlesegeräte, Tablets, Stylus, Sprach- oder Handschriftleseerkennungseinrichtungen oder andere gut bekannten Eingabeeinrichtungen, wie etwa natürlich andere Computer. Schließlich kann die CPU 1032 optional mit einem Computer oder Telekommunikationsnetz gekoppelt sein, z.B. einem Lokalbereichsnetz, einem Internet-Netz oder einem Intranet-Netz, unter Verwendung einer Netzverbindung, die allgemein in 1012 gezeigt wird. Mit einer derartigen Netzverbindung wird betrachtet, dass die CPU 1032 Information von dem Netz empfangen kann, oder Information zu dem Netz ausgeben kann, im Verlauf einer Durchführung der oben beschriebenen Verfahrensschritte. Derartige Information, die häufig als eine Sequenz von Instruktionen dargestellt wird, die unter Verwendung von CPU 1032 auszuführen sind, kann empfangen werden von und ausgegeben werden zu dem Netz, z.B. in der Form eines Computerdatensignals, das in einer Trägerwelle verkörpert ist. Die oben beschriebenen Einrichtungen und Materialien werden einem Fachmann von Computerhardware und Softwaretechnik vertraut sein.

Wie zuvor erwähnt, kann eine virtuelle Maschine in Computersystem 1030 ausgeführt werden. 7 ist eine schematische Darstellung einer virtuellen Maschine, die durch Computersystem 1030 von 6 unterstützt wird, und ist zum Implementieren der vorliegenden Erfindung geeignet. Wenn ein Computerprogramm, z.B. ein Computerprogramm, das in der Programmiersprache JavaTM geschrieben ist, die durch Sun Microsystems von Palo Alto, Kalifornien, entwickelt wird, ausgeführt wird, wird Quellcode 1110 einem Compiler 1120 innerhalb einer Kompilierzeitumgebung 1105 bereitgestellt. Compiler 1120 übersetzt Quellcode 1110 in Bytecodes 1130. Allgemein wird Quellcode 1110 in Bytecodes 1130 in der Zeit übersetzt, in der Quellcode 1110 durch einen Softwareentwickler erstellt wird.

Bytecodes 1130 können allgemein durch ein Netz, z.B. Netz 1012 von 6, reproduziert, heruntergeladen oder anderweitig verteilt werden, oder in einer Speichereinrichtung gespeichert werden, wie etwa dem Primärspeicher 1034 von 6. In der beschriebenen Ausführungsform sind Bytecodes 1130 plattformunabhängig. D.h. Bytecodes 1030 können auf im wesentlichen einem beliebigen Computersystem ausgeführt werden, das eine geeignete virtuelle Maschine 1140 betreibt. Auf dem Weg eines Beispiels können in einer JavaTM-Umgebung Bytecodes 1130 in einem Computersystem ausgeführt werden, das eine virtuelle JavaTM-Maschine betreibt.

Bytecodes 1130 werden einer Laufzeitumgebung 1135 bereitgestellt, die eine virtuelle Maschine 1140 enthält. Die Laufzeitumgebung 1135 kann allgemein unter Verwendung eines Prozessors, wie etwa CPU 1032 von 6, ausgeführt werden. Die virtuelle Maschine 1140 enthält einen Compiler 1142, einen Interpreter 1144 und ein Laufzeitsystem 1146. Bytecodes 1130 können allgemein entweder Compiler 1142 oder Interpreter 1144 bereitgestellt werden.

Wenn Bytecodes 1130 Compiler 1142 bereitgestellt werden, werden Methoden, die in Bytecodes 1130 enthalten sind, in Maschineinstruktionen kompiliert, wie oben beschrieben wird.

Wenn andererseits Bytecodes 1130 Interpreter 1144 bereitgestellt werden, werden Bytecodes 1130 in Interpreter 1144 einen Bytecode in einem Zeitpunkt gelesen. Interpreter 1144 führt dann die Operation durch, die durch jeden Bytecode definiert wird, während jeder Bytecode in den Interpreter 1144 gelesen wird. Im allgemeinen verarbeitet Interpreter 1144 Bytecodes 1130 und führt Operationen, die mit Bytecodes 1130 in Verbindung stehen, im wesentlichen kontinuierlich durch.

Wenn eine Methode von einem Betriebssystem 1160 aufgerufen wird, kann, falls bestimmt wird, dass die Methode als eine interpretierte Methode aufzurufen ist, das Laufzeitsystem 1146 die Methode von Interpreter 1144 erhalten. Falls andererseits bestimmt wird, dass die Methode als eine kompilierte Methode aufzurufen ist, aktiviert das Laufzeitsystem 1146 den Compiler 1142. Der Compiler 1142 generiert dann Maschineninstruktionen aus Bytecodes 1130, und führt die Maschinenspracheninstruktionen aus. Im allgemeinen werden die Maschinenspracheninstruktionen verworfen, wenn die virtuelle Maschine 1140 terminiert. Die Operation von virtuellen Maschinen, oder genauer virtuellen JavaTM-Maschinen, werden in The JavaTM Virtual Machine Specification von Tim Lindholm und Frank Yellin (ISBN 0-201-63452-X) detaillierter beschrieben.

Obwohl nur wenige Ausführungsformen der vorliegenden Erfindung beschrieben wurden, sollte verstanden werden, dass die vorliegende Erfindung in vielen anderen spezifischen Formen verkörpert werden kann. Auf dem Weg eines Beispiels können Schritte, die mit einer Durchführung einer generationsmäßigen reinigenden Speicherbereinigung in der älteren Sektion einer neuen Generation in Verbindung stehen, geändert, hinzugefügt und entfernt werden. Z.B. kann eine generationsmäßige reinigende Speicherbereinigung einen Schritt zum Einstellen von Speicherbits, die mit der aktuellen jüngeren Sektion, d.h. der vorherigen älteren Sektion, in Verbindung stehen, auf Null enthalten.

Während die Grenze, die die jüngere Sektion einer neuen Generation von der älteren Sektion der neuen Generation trennt, als flexibel beschrieben wurde, sollte erkannt werden, dass in einigen Ausführungsformen die Grenze stationär sein kann. Mit anderen Worten kann die Grenze derart fixiert sein, dass die relativen Größen der jüngeren Sektion und der älteren Sektion konstant sind. Z.B. kann die Grenze derart fixiert sein, dass die jüngere Sektion und die ältere Sektion von im wesentlichen der gleichen Größe sind. Wenn die Grenze fixiert ist, kann es effektiv zwei getrennte neue Generationen geben, die abwechselnd eine jüngere neue Generation und eine ältere neue Generation sind.

Im allgemeinen kann eine neue Generation in viele Sektionen derart unterteilt werden, dass neue Objekte in einer Sektion zugeordnet werden, während mindestens einige der anderen Sektionen bereinigt werden, wenn sich die eine Sektion auffüllt. Es sollte erkannt werden, dass eine neue Generation einer Multisektion ermöglicht, einen Ausgleich zwischen der Zeitdauer zwischen Bereinigungen und der Länge einer Bereinigung zu erreichen, indem erlaubt wird, dass die Zahl von bereinigten Sektionen abgestimmt wird. In einer derartigen Ausführungsform können die Grenzen zwischen einer jüngeren Sektion und verschiedenen älteren Sektionen einer neuen Generation flexibel sein, derart, dass sie verschoben werden können, um die relativen Größen der Sektionen abzustimmen. Auf dem Weg eines Beispiels kann, falls eine jüngere Sektion größer als eine bestimmte ältere Sektion ist, bevor eine Speicherbereinigung durchgeführt wird, und daher die jüngere Sektion und die ältere Sektion "ausgetauscht" werden, sobald eine Speicherbereinigung durchgeführt wird, die neue ältere Sektion nicht genug Raum haben, um alle Objekte zu enthalten, die in der vorherigen jüngeren Sektion waren. D.h. die neue ältere Sektion kann voll sein oder sogar in die neue jüngere Sektion überlaufen. Falls dies der Fall ist, können einige Objekte in der neuen älteren Sektion zu der neuen jüngeren Sektion relegiert werden.

Wenn die Grenze flexibel ist und die Größen der Sektionen nicht im wesentlichen gleich sind, kann alternativ die Grenze derart bewegt werden, dass die neue ältere Sektion immer von der gleichen Größe wie eine vorherige jüngere Sektion ist. Um Probleme zu vermeiden, die mit einem Überlaufen einer neuen älteren Sektion in Verbindung steht, sobald Speicherbereinigung aufgetreten ist, kann speziell die Grenze derart bewegt werden, dass die neue ältere Sektion die gleiche Größe wie die vorherige jüngere Sektion ist.

Wie zuvor erwähnt, kann die Bemessung der Sektionen einer neuen Generation ein dynamischer Prozess sein. Falls z.B. beobachtet wird, dass Speicherbereinigung häufiger als erwünscht auftritt, kann die Größe der jüngeren Sektion erhöht werden, um den Objekten in der älteren Sektion mehr einer Änderung zu geben um zu sterben, bevor eine Speicherbereinigung initiiert wird. Auch kann die Größe einer jüngeren Sektion erhöht werden, wenn bestimmt wird, dass während Speicherbereinigung in der älteren Sektion eine beträchtliche Zahl lebendiger Objekte in die alte Generation kopiert wird. Andererseits kann die Größe einer jüngeren Sektion verringert werden, wenn Speicherbereinigung in der älteren Sektion nicht häufig auftritt, und Kopieren einer beträchtlichen Zahl lebendiger Objekte nicht einbezieht.

Deshalb sind die vorliegenden Beispiele als veranschaulichend und nicht einschränkend zu betrachten, und die Erfindung ist nicht auf die hierin angegebenen Details zu begrenzen, sondern kann innerhalb des Bereiches der angefügten Ansprüche modifiziert werden.


Anspruch[de]
Ein Computer-implementiertes Verfahren zum Rückgewinnen von Speicherraum in einem verwalteten Speicherbereich (302) folgend einer generierten reinigenden Speicherbereinigung (Freispeichersammlung), wobei der verwaltete Speicherbereich einen neuen Generationsbereich (306) und einen alten Generationsbereich (310) enthält, der neue Generationsbereich, der der Hort ist, angeordnet ist, die zuletzt zugeordneten Objekte zu speichern, der alte Generationsbereich angeordnet ist, ältere Objekte zu speichern, das Computer-implementierte Verfahren umfassend:

Bestimmen (504), wann eine erste Sektion (318a) der neuen Generation (306) gefüllt ist, derart, dass die erste Sektion unzureichenden Speicherraum für die Zuordnung eines neuen Objektes hat, wobei die erste Sektion anfangs angeordnet ist, Speicherzuordnung für neu erstellte Objekte zu unterstützen;

Durchführen (506) einer generationsmäßigen reinigenden Speicherbereinigung in einer zweiten Sektion (318b) des neuen Generationsbereiches, wenn bestimmt ist, dass die erste Sektion gefüllt ist durch Kopieren (412) aller lebendigen Objekte von der zweiten Sektion in den alten Generationsbereich;

Einstellen (416) der zweiten Sektion des neuen Generationsbereiches derart, dass die zweite Sektion angeordnet ist, Speicherzuordnung für neu erstellte Objekte zu unterstützen, nachdem die reinigende Speicherbereinigung durchgeführt ist; und

Einstellen (416) der ersten Sektion derart, dass die erste Sektion nicht länger angeordnet ist, Speicherzuordnung für neu erstellte Objekte zu unterstützen, nachdem die reinigende Speicherbereinigung durchgeführt ist, und die Sektion des neuen Generationsbereiches (306) wird, in dem Bereinigen durchgeführt wird.
Ein Computer-implementiertes Verfahren, wie in Anspruch 1 vorgetragen, wobei die erste Sektion (318a) und die zweite Sektion (318b) durch eine Grenze (322) getrennt sind, und das Computer-implementierte Verfahren ferner Abstimmen der Grenze enthält, um die relativen Größen der ersten Sektion und der zweiten Sektion zu ändern. Ein Computer-implementiertes Verfahren, wie in beliebigen der vorangehenden Ansprüche vorgetragen, ferner enthaltend:

Versuchen, ein neues Objekt in der zweiten Sektion (318b) zuzuordnen, nachdem die zweite Sektion eingestellt ist, Speicherzuordnung für neu erstellte Objekte zu unterstützen;

Bestimmen, wann die zweite Sektion gefüllt ist;

Zuordnen des neuen Objektes in der zweiten Sektion, wenn bestimmt ist, dass die zweite Sektion nicht gefüllt ist; und

Durchführen einer generationsmäßigen reinigenden Speicherbereinigung in der ersten Sektion durch Kopieren von mindestens einem lebendigen Objekt von der ersten Sektion in den alten Generationsbereich, wenn bestimmt ist, dass die zweite Sektion gefüllt ist.
Ein Computer-implementiertes Verfahren, wie in Anspruch 3 vorgetragen, wobei wenn bestimmt ist, dass die zweite Sektion (318b) gefüllt ist, das Computer-implementierte Verfahren weiter enthält:

Einstellen der zweiten Sektion derart, dass die zweite Sektion nicht angeordnet ist, Speicherzuordnung für neu erstellte Objekte zu unterstützen;

Einstellen der ersten Sektion (318a) derart, dass die erste Sektion angeordnet ist, Speicherzuordnung für neu erstellte Objekte zu unterstützen; und

Zuordnen von Speicher für das neue Objekt in der ersten Sektion.
Ein Computerprogrammprodukt, das auf einem Computer-lesbaren Medium gespeichert ist, zum Rückgewinnen von Speicherraum in einem verwalteten Speicherbereich (302) eines Computersystems, wobei der verwaltete Speicherbereich einen neuen Generationsbereich (306) und einen alten Generationsbereich (310) enthält, das Computerprogrammprodukt umfassend computerlesbaren Code zum Durchführen von jedem der Schritte von beliebigen der vorangehenden Ansprüche, wenn der computerlesbare Code in dem Computersystem läuft. Ein Computerprogrammprodukt, wie in Anspruch 5 vorgetragen, wobei das computerlesbare Medium aus einer Gruppe ausgewählt wird, die aus einer CD-ROM, einer Diskette, und einer optischen Platte, einem Band, einer Festplatte und einem Datensignal, das in einer Trägerwelle verkörpert ist, besteht. Ein Computersystem zum Rückgewinnen von Speicherraum in einem verwalteten Speicherbereich (302), folgend einer generationsmäßigen reinigenden Speicherbereinigung, wobei der verwaltete Speicherbereich einen neuen Generationsbereich (306) und einen alten Generationsbereich (310) enthält, der neue Generationsbereich, der der Hort ist, angeordnet ist, die zuletzt zugeordneten Objekte zu speichern, der alte Generationsbereich angeordnet ist, ältere Objekte zu speichern, das Computersystem umfassend:

einen Prozessor;

eine Bestimmungseinrichtung zum Bestimmen, wann eine erste Sektion (318a) des neuen Generationsbereiches gefüllt ist, derart, dass die erste Sektion unzureichenden Speicherraum für die Zuordnung eines neuen Objektes hat, wobei die erste Sektion anfangs angeordnet ist, Speicherzuordnung für neu erstellte Objekte zu unterstützen;

einen generationsmäßigen reinigenden Speicherbereiniger, der angeordnet ist, eine zweite Sektion (318b) des neuen Generationsbereiches zu bereinigen, wenn bestimmt ist, dass die erste Sektion gefüllt ist durch Kopieren aller lebendigen Objekte von der zweiten Sektion zu dem alten Generationsbereich; und

einen Verfolgungsmechanismus, der angeordnet ist, die zweite Sektion des neuen Generationsbereiches derart einzustellen, dass die zweite Sektion angeordnet ist, Speicherzuordnung für neu erstellte Objekte zu unterstützen, wobei der Verfolgungsmechanismus weiter angeordnet ist, die erste Sektion derart einzustellen, dass die erste Sektion nicht angeordnet ist, Speicherzuordnung für neu erstellte Objekte zu unterstützen, nachdem der Speicherbereiniger die zweite Sektion des neuen Generationsbereiches bereinigt und die Sektion des neuen Generationsbereiches (306) wird, in dem Bereinigen durchgeführt wird.
Ein Computersystem, wie in Anspruch 7 vorgetragen, wobei die erste Sektion (318a) und die zweite Sektion (318b) durch eine Grenze (322) getrennt sind, und das Computersystem ferner eine Abstimmungseinrichtung zum Ändern der relativen Größen der ersten Sektion und der zweiten Sektion durch Verschieben der Grenze enthält. Ein Computersystem, wie in Anspruch 7 oder 8 vorgetragen, ferner enthaltend:

eine Objektzuordnungseinrichtung zum Versuchen einer Zuordnung eines neuen Objektes in der zweiten Sektion (318b), nachdem die zweite Sektion eingestellt ist, Speicherzuordnung für neu erstellte Objekte zu unterstützen; und

eine Bestimmungseinrichtung zum Bestimmen, wann die zweite Sektion gefüllt ist, wobei die Objektzuordnungseinrichtung das neue Objekt in der zweiten Sektion zuordnet, wenn bestimmt ist, dass die zweite Sektion nicht gefüllt ist, und wobei der Speicherbereiniger die erste Sektion (318a) generationsmäßig bereinigt durch Kopieren mindestens eines lebendigen Objektes von der ersten Sektion in den alten Generationsbereich, wenn bestimmt ist, dass die zweite Sektion gefüllt ist.
Ein Computersystem, wie in Anspruch 9 vorgetragen, wobei der Verfolgungsmechanismus ferner angeordnet ist, die zweite Sektion (318b) derart einzustellen, dass die zweite Sektion nicht angeordnet ist, Speicherzuordnung für neu erstellte Objekte zu unterstützen, und die erste Sektion (318a) derart einzustellen, dass die erste Sektion angeordnet ist, Speicherzuordnung für neu erstellte Objekte zu unterstützen, und die Objektzuordnungseinrichtung Speicher für das neue Objekt in der ersten Sektion zuordnet.






IPC
A Täglicher Lebensbedarf
B Arbeitsverfahren; Transportieren
C Chemie; Hüttenwesen
D Textilien; Papier
E Bauwesen; Erdbohren; Bergbau
F Maschinenbau; Beleuchtung; Heizung; Waffen; Sprengen
G Physik
H Elektrotechnik

Anmelder
Datum

Patentrecherche

Patent Zeichnungen (PDF)

Copyright © 2008 Patent-De Alle Rechte vorbehalten. eMail: info@patent-de.com