DE69903496T2

DE69903496T2 - Flexibles Löschen von Objekten in einer Umgebung mit beschränkten Resourcen

Info

Publication number: DE69903496T2
Application number: DE69903496T
Authority: DE
Inventors: Michael Baentsch; Peter Buhler; Thomas Eirich; Frank Hoering; Marcus Oestreicher
Original assignee: International Business Machines Corp
Current assignee: International Business Machines Corp
Priority date: 1998-05-07
Filing date: 1999-04-22
Publication date: 2003-12-04
Anticipated expiration: 2019-04-23
Also published as: DE69903496D1; US6272504B1

Description

TECHNISCHES GEBIET

Die Erfindung betrifft einen neuartigen Ansatz zum Nachweisen · von "Datenmüll" (Speicherbereiche, die nicht mehr benötigte Daten enthalten) und zur Speicherbereinigung. Dieser Ansatz eignet sich gut für den Einsatz in Systemen mit begrenzter Speichergröße, wie beispielsweise Karten mit integrierten Schaltkreisen (z. B. Smartcards).

HINTERGRUND DER ERFINDUNG

Objektbasierte Anwendungsprogramme (in Java, C++ o. ä. geschrieben) bedienen sich für gewöhnlich gerichteter Graphen. Diese Graphen umfassen Stammobjekte und normale Objekte, die mittels Zeigern untereinander verknüpft sind. Während der Ausführung eines objektbasierten Anwendungsprogramms verändert sich der Graph dynamisch, wenn Objekte und/oder Zeiger hinzugefügt, verändert oder entfernt werden.
Objektbasierte Ausführungsumgebungen unterstützen den Programmentwickler oft bei einer der aufwendigsten und fehlerträchtigsten Programmieraufgaben, der Speicherzuordnung. Bei vielen Systemen werden Objekte durch das Anwendungsprogramm nur zugewiesen, aber nie wieder ausdrücklich entfernt. Bei diesen Systemen besteht die Aufgabe eines so genannten Speicherreinigers (garbage collector, GC) darin, die nicht mehr benötigten Objekte zu ermitteln. Weiterhin leert der Speicherreiniger die betreffenden Speicherbereiche und führt sie dem freien Speicherbereich zu. Ein Speicherreiniger muss ab und zu ungenutzte Speicherbereiche reinigen. Außerdem könnte der Speicherreiniger zum Zusammenführen der Speicherbereiche verwendet werden, um die durch Fragmentierung entstandenen Lücken zu beseitigen.
Das Entfernen von Datenmüll aus einem Speicher erfolgt üblicherweise in zwei Schritten, die als Markieren und Leeren bezeichnet werden. Auch der aktuelle Speicherreiniger unter SUN Java bedient sich des Konzepts Markieren und Leeren, nach dem zunächst jedes Stammobjekt im System markiert wird. Dann werden alle Objektverweise innerhalb dieser Objekte auf andere noch nicht markierte Objekte fortschreitend verfolgt. Abschließendwerden dann, wenn keine zu verfolgenden Objektverweise mehr vorliegen, alle nicht markierten Objekte gelöscht.
Die Patentschrift US 5 485 613 beschreibt ein Verfahren zum automatischen Wiederherstellen von Speicherbereichen in objektorientierten Systemen unter Echtzeitbedingungen. Das Wiederherstellen der Speicherressourcen in objektorientierten Systemen erfolgt segmentweise in diskreten Echtzeitabschnitten, die so überwacht werden, dass sich die Speicherbereinigung nicht störend auf das System auswirkt, während die Speicherbereiche etwa genauso schnell wiedergewonnen werden, wie sie zugewiesen werden. Die von anderen Objekten her querverwiesenen Objekte werden mittels eines schrittweisen Markier-/Leerungsverfahrens überprüft. Auch Objekte, auf die von Stapeln her verwiesen wird, werden einbezogen. Wenn ein Stapel nicht nach Objektverweisen in einem Echtzeitabschnitt durchsucht werden kann, wird der Stapel in einen Sicherungsbereich kopiert und während eines oder mehrerer aufeinander folgender Echtzeitabschnitte durchsucht.
Neuere Speicherbereinigungsverfahren sind für die Verwendung in Systemen mit beschränkten Ressourcen nicht sehr geeignet, da diese Speicherreiniger-Verfahren mehr flüchtigen Speicherbereich benötigen als in derartigen Systemen verfügbar ist.
Eine integrierte Schaltkreiskarte (integrated circuit card, ICC), bekannter unter der Bezeichnung Smartcard, stellt ein Beispiel für ein derartiges System mit beschränkten Ressourcen dar. Weitere Beispiele sind: mobile und/oder Handgeräte, wie beispielsweise Mobiltelefone, Pager, digitale Personalassistenten, personengebundene Netzgeräte und so weiter.
Im Folgenden sollen vorwiegend ICCs und insbesondere Smartcards betrachtet werden. Die Entwicklung von Smartcards hat in Europa vor 1985 begonnen, und die Anwendungen liegen heute bei Telefonsystemen, Mautstationen, Spielhallen und Personal Computern, um nur einige Anwendungen zu nennen.
Im Folgenden wird der Begriff integrierte Schaltkreiskarte verwendet, da er von der ISO dazu verwendet wird, alle diejenigen Bauteile zu erfassen, bei denen sich in einem Stück Plastik o. ä. von Kartengröße eine integrierte Schaltung befindet.
Typische ICCs umfassen einen Mikroprozessor (central processing unit, CPU), einen Nur-Lese-Speicher (read only memory, ROM), einen flüchtigen Arbeitsspeicher (random access memory, RAM) und bestimmte nichtflüchtige programmierbare Speicher, wie beispielsweise einen EEPROM (electrically erasable programmable read only memory, elektrisch löschbarer programmierbarer Nur- Lese-Speicher). Außerdem umfasst eine ICC einen bestimmten Bus (wie beispielsweise einen seriellen Bus) und E/A-Anschlüsse zum Verbinden mit einem Kartenterminal.
Der Inhalt eines ROM-Speichers ist festgeschrieben und kann nach der Herstellung durch einen Halbleiterhersteller nicht mehr geändert werden. Hierbei handelt es sich um einen preiswerten Speicher, da er auf dem Substrat nur wenig Platz beansprucht. Es stellt einen Nachteil eines ROM dar, dass er nicht geändert werden kann und seine Herstellung mehrere Monate beansprucht. Im Gegensatz dazu kann ein EEPROM durch den Benutzer vielfach gelöscht und neu beschrieben werden. ROMs und EEPROMs sind nichtflüchtige Speicher, d. h., ihr Inhalt bleibt nach Abschalten der Versorgungsspannung erhalten.
Ein RAM stellt einen flüchtigen Speicher dar, dessen Dateninhalt nach Abschalten der Versorgungsspannung verloren geht. Ein RAM weist jedoch den Vorteil auf, dass er viel schneller als ROMs und EEPROMs ist. Andererseits ist ein RAM bezüglich seiner Größe jedoch teurer. Normalerweise ist der RAM relativ klein. Der RAM wird überhaupt nicht benötigt, wenn Daten zu verarbeiten sind, die dauerhaft erhalten werden sollen. Allerdings weist die Verwendung nichtflüchtiger Speicher stets eine Reihe ernster Nachteile auf. Ein Nachteil besteht in der extrem starken Leistungsminderung, da bei Verwendung eines EEPROMs jeder Schreibzugriff auf den Speicher 500 bis tausendmal langsamer ist als bei einem RAM. Ein noch schwerer wiegendes Problem besteht in der begrenzten Anzahl garantierter Schreibzyklen (100.000-mal für den EEPROM).
Es ist eine Aufgabe der vorliegenden Erfindung, ein neuartiges System zum Nachweisen ungenutzter Daten und zur Speicherbereinigung zur Verfügung zu stellen, insbesondere ein System zum Nachweisen ungenutzter Daten und zur Speicherbereinigung, das für den Einsatz in Systemen mit beschränkten Ressourcen gut geeignet ist.
Es ist eine Aufgabe der vorliegenden Erfindung, eine Lösung zur Speicherbereinigung in Systemen mit beschränkten Ressourcen, wie beispielsweise bei integrierten Schaltkreiskarten, zur Verfügung zu stellen.

ÜBERBLICK ÜBER DIE ERFINDUNG

Die vorliegende Erfindung stellt ein in Anspruch 1 dargelegtes Verfahren sowie eine in Anspruch 15 dargelegte Vorrichtung zum Unterscheiden von erreichbaren und nicht erreichbaren Objekten zur Verfügung, welche sich in einem nichtflüchtigen Speicher befinden, der von einer objektbasierten Anwendung in einem System mit einem flüchtigen Speicher von beschränktem Umfang benutzt wird.
Das Verfahren gemäß der Erfindung verringert den zur Speicherbereinigung erforderlichen Aufwand. Weiterhin ermöglicht das Verfahren gemäß der Erfindung einen Kompromiss bezüglich des Speicherplatzbedarfs für die Ausführungszeit und die Laufzeit.
Das Verfahren eignet sich gut für den Einsatz in Systemen mit beschränkten Ressourcen.

BESCHREIBUNG DER ZEICHNUNGEN

Im Folgenden wird die Erfindung unter Bezug auf die folgenden schematischen Zeichnungen detailliiert beschrieben. Es wird betont, dass die Figuren nicht maßstabgerecht sind.
Fig. 1 ist eine schematische Ansicht einer integrierten Schaltkreiskarte (ICC) gemäß der vorliegenden Erfindung.

BESCHREIBUNG BEVORZUGTER AUSFÜHRUNGSARTEN

Die vorliegende Erfindung kann in beliebigen Systemen eingesetzt werden, in denen eine objektbasierte Anwendung ausgeführt wird. Die Erfindung ist besonders für den Einsatz in Systemen mit beschränkten Ressourcen geeignet. Typische Systeme mit beschränkten Ressourcen sind:
- integrierte Schaltkreiskarten (ICCs)(z. B. Smartcards);
- Telefone;
- Set-top Boxen (Entschlüsselungsgeräte für das Pay-TV);
- eingebettete Controller;
- Handgeräte;
- tragbare Computer;
- Geräte für Privatnetze (personal area network, PAN) usw.
In einem System mit beschränkten Ressourcen ist die Größe des flüchtigen Speichers für gewöhnlich beschränkt; ebenso ist auch die Rechenleistung beschränkt, z. B. weil nur eine kleine CPU (central processing unit, Zentraleinheit) benutzt wird. Solche beschränkten Systeme arbeiten normalerweise mit niedrigen Taktraten.
Das Grundkonzept der vorliegenden Erfindung wird in Verbindung mit einer integrierten Schaltkreiskarte (TCC) 10 beschrieben, die in Fig. 1 veranschaulicht wird. Diese Karte verfügt über einen Mikroprozessor 12, einen ROM 11, einen EEPROM 13 und einen RAM 14, wie dies in den meisten herkömmlichen ICCs der Fall ist. Die ICC 10 umfasst ferner einen internen Bus 19, auf dem Daten und Signale zwischen den Bauteilen der ICC übermittelt werden · können. Die ICC 10 ist eine Kontaktkarte. Die E/A-Anschlüsse stellen die Verbindung zu entsprechenden Mitteln eines Kartenterminals her. Wie in Fig. 1 gezeigt, wird die Versorgungsspannung über Anschluss 17 (Masse, GND) und Anschluss 18 (positive Spannung, VCC) zugeführt.
Die vorliegende Erfindung betrifft ein erfindungsgemäßes Verfahren zur Speicherbereinigung (garbage collection, GC) zum Einsatz in Systemen mit beschränkten Ressourcen. Zu dem System, das das erfindungsgemäße Speicherbereinigungsverfahren ausführt, werden die folgenden Annahmen getroffen:
Es liegen zwei Speichertypen V (volatile, flüchtig) und P (persistent, nichtflüchtig) vor. Der Speicher V weist die folgenden Eigenschaften auf:
- Der verfügbare Umfang dieses Speichers ist begrenzt, weil entweder die physische Speichergröße begrenzt ist oder weil der Speicherbereinigungs-Task nur ein begrenzter Teil des Speicherplatzes zugewiesen werden kann.
- Schreib- und Lesevorgänge verlaufen beim Speicher V schneller als der Schreibzugriff auf den Speicher P.
Der Speicher P weist die folgenden Eigenschaften auf:
- In diesem Speichertyp sind eine Vielzahl von Objekten gespeichert.
- Das Beschreiben dieses Speichertyps ist zeitaufwendiger als das Beschreiben des Speichers V.
- Die in P gespeicherten Objekte können aufgelistet werden.
- Jedes Objekt besteht aus einem Header und Nutzinformationen. Der Header und die Nutzinformationen müssen sich nicht in aufeinander folgenden Speicherzellen befinden.
- Während die Nutzinformationen durch den Programmcode frei genutzt werden können, ist der Header für Systemaufgaben vorgesehen. Für das Sammeln ungenutzter Daten (Speicherbereinigung) muss der Header jedes Objekts bestimmte Informationen enthalten. Der Umfang der im Header für die Speicherbereinigung zu speichernden Daten sollte so gering wie möglich gehalten werden, da der Header nur Verwaltungszwecken dient.
Typische Beispiele für den Speicher V sind der RAM oder Cache und Beispiele für den Speicher P könnten EEPROM, FlashRAM oder Plattenspeicher sein.
In einer objektbasierten Umgebung enthält der Speicher P üblicherweise eine Vielzahl von Objekten. Jedes Objekt kann aufgelistet und mittels eines Zeigers (eine Adresse, anhand der das Objekt gefunden werden kann) aufgerufen werden. In diesem Zusammenhang stellt ein Zeiger einen Datensatz dar, der eine Objektadresse enthält, welche sich auf ein bestimmtes Objekt bezieht. Jedes Objekt enthält eine möglicherweise leere Menge von Objektzeigern und eine möglicherweise leere Menge anderer Informationen, die sich nicht auf Objekte beziehen. Beispielsweise können für ein bestimmtes Objekt A alle in A gespeicherten Zeiger aufgelistet werden, die sich auf (andere) Objekte beziehen. Die Menge der Objekte ist im Speicher P gespeichert, und ihre Zeiger bilden (dementsprechend) einen gerichteten Graphen (directed graph, DG).
Da die Speicherbereinigung Objekte nachweisen soll, auf die kein Bezug mehr genommen wird, müssen bestimmte Ausgangsobjekte (bekannt als Stammobjekte) von besonderer Bedeutung bekannt sein, die nicht entfernt werden sollen. Diese Menge von Objekten ist systemabhängig und beeinflusst nicht das vorliegende Verfahren zum Nachweisen ungenutzter Daten und zur Speicherbereinigung. Diese Menge von Objekten wird als Anfangsstammsatz (initial rootset, IR) bezeichnet.
Definitionsgemäß werden Objekte, die innerhalb des gerichteten Graphen im Speicher P von Objekten im Anfangsstammsatz aus erreicht werden können, nicht als unbenutzte Daten deklariert. Alle von den Objekten im Anfangsstammsatz aus erreichbaren Objekte werden als unbenutzte Daten deklariert. Deren Speicherplatz, der den Header und den Nutzbereich umfasst, kann vom System wieder zurückgewonnen werden.
Mit dem vorliegenden Verfahren zum Nachweisen ungenutzter Daten und zur Speicherbereinigung soll eine Unterscheidung zwischen erreichbaren und nicht erreichbaren Objekten getroffen werden. Zu diesem Zweck werden im Speicher V die folgenden Zustände verwaltet:
- die Anzahl der unbearbeiteten Stammobjekte Z (z. B. mittels eines Zählers)
- das aktuelle Stammobjekt T
- eine Beschreibung eines Pfads TO im gerichteten Graphen, der beim aktuellen Stammobjekt T beginnt und bei einem bestimmten Objekt O endet. Das Objekt T soll das erste Objekt und das Objekt O das letzte Objekt in TO sein.
Im Speicher P könnte jeder Objektheader zwei Bits aufweisen, die dem erfindungsgemäßen Speicherbereinigungsverfahren dienen.
- Bit VF: Dieses Bit zeigt an, ob ein Objekt während der laufenden Ausführung des Speicherbereinigungsalgorithmus bereits besucht worden ist. Die Angabe 0 und 1 (entsprechend, besucht oder nicht besucht) kann geändert werden, damit nach einem Speicherbereinigungsdurchlauf nicht die Bits VF aller Objekte zurückgesetzt werden müssen. "VF gesetzt" bedeutet unabhängig von dem im Speicher enthaltenen aktuellen Wert des Bits VF, dass das Objekt bereits besucht wurde.
- Bit RF (root flag, Stammmarkierung): Diese Markierung zeigt an, dass das Objekt ein Stammobjekt ist und noch nicht verarbeitet wurde. "RF gesetzt" oder "RF = 1" bedeutet, dass das Objekt als Stammobjekt markiert wurde und noch verarbeitet werden muss.
Im Folgenden werden die Schritte einer beispielhaften Implementierung des erfindungsgemäßen Speicherbereinigungsverfahrens angegeben:
1. Alle anfänglichen Stammobjekte im Anfangsstammsatz mit RF = 1 markieren. Z auf die Anzahl der markierten Stammobjekte setzen.
2. Wenn Z gleich Null ist, alle Objekte in P auflisten und den Speicherplatz derjenigen reservieren, bei denen VF nicht gesetzt ist. Speicherplatzsuche beenden.
3. Objekte im Speicher P auflisten und das Erste mit gesetztem RF finden. T soll sich auf dieses Objekt beziehen. Aktuelles Objekt C auf das aktuelle Stammobjekt T setzen.
4. Auflistung aller Zeiger in C starten und für jeden Zeiger, der sich auf ein Objekt O bezieht, die Schritte (a)-(e) ausführen:
a. Wenn VF von 0 gesetzt ist, Auflistung mit Schritt 4 fortsetzen.
b. VF an Objekt O setzen.
c. Wenn Speicher V nicht voll belegt ist, Objekt C dem Pfad TO hinzufügen und C auf das aktuelle Objekt O setzen. Mit Schritt 4 fortfahren.
d. Markierung RF an Objekt O setzen, Z um Eins erhöhen und mit Schritt 4 fortfahren.
5. Wenn Pfad TO leer ist, mit Schritt 2 fortfahren. RF löschen und VF an T setzen. Z um Eins erniedrigen.
6. Letztes Objekt aus TO entfernen. Dieses entfernte Objekt C zuweisen und mit Schritt 4 fortfahren.
Der Speicherbereinigungsalgorithmus benötigt im Speicher V mindestens so viel Speicherplatz, dass Pfade der Länge 2 gespeichert werden können. Je länger der Pfad sein kann, umso schneller verläuft die Ausführung der vorliegenden Speicherbereinigung.
Der Aufwand kann durch die Wahl bestimmter Darstellungen des Pfads TO im Speicher V weiter verringert werden. Eine schnellere, aber auch mehr Speicherplatz belegende Darstellung wäre eine Folge von Zeigern, die sich auf die Objekte des Pfads beziehen. Da die Anzahl möglicher Zeiger normalerweise größer ist als die durchschnittliche Anzahl in Objekten enthaltener Zeiger, kann die folgende Optimierung eingesetzt werden:
- r sei die Anzahl der Zeiger in Objekt O. r' sei die minimale Anzahl, die größer oder gleich r sowie eine Potenz von zwei ist. Um einen Pfadabschnitt von 0 bis zu einem seiner bezogenen Objekte Q darzustellen, werden lediglich log&sub2;(r') Bits benötigt. Wenn man annimmt, dass der Zeiger auf ein Objekt Q der i-te Zeiger in 0 ist, dann werden nur die letzten log&sub2;(r') Bits von i in TO gespeichert.
Die Errechnung des letzten Objekts in einem bestimmten Pfad TO erfolgt, indem man beim Stamm T beginnt und den i-ten Zeigern von Objekt zu Objekt folgt.
Die erfindungsgemäße Speicherbereinigung beginnt, wie auch die standardmäßigen Speicherbereinigungsverfahren mit Markieren und Löschen, bei den Stammobjekten.
Üblicherweise enthalten die Nutzinformationen eines Objekts Zeiger auf andere Objekte. Um bei den Nutzinformationen eines Objekts befindliche Zeiger nachzuweisen, sind Metadaten im Layout der Nutzinformationen erforderlich. Der Umfang der Metadaten kann durch Zusammenfassen der Zeiger in den Nutzinformationen auf ein Minimum beschränkt werden.
Durch die vorliegende Erfindung können herkömmliche ICCs und andere Systeme und insbesondere Systeme mit beschränkten Ressourcen, abgeändert werden, indem einfach die erforderlichen Bauelemente in Form von Hardware, von Software oder in einer Kombination von Hardware und Software eingefügt werden. Durch die Erfindung werden eine Vielzahl von Anwendungen ermöglicht, die diejenigen Objekte nachweisen, welche nicht mehr benötigt werden. Wenn diese Objekte einmal erfolgreich nachgewiesen worden sind, können sie gelöscht werden, um die entsprechenden Speicherbereiche freizugeben. Anstatt diese Objekte zu löschen, können Zeiger in eine Warteschlange eingereiht werden. Die Zeiger in dieser Warteschlange zeigen dann auf Speicherbereiche, die überschrieben werden können. Jedes Mal, wenn zum Speichern eines Objekts Speicherplatz benötigt wird, kann ein Zeiger aus der Warteschlange entfernt werden. Dann wird das Objekt in den durch den entsprechenden Zeiger ermittelten Speicherbereich geschrieben.
Wenn alle nicht erreichbaren Objekte ermittelt worden sind, können die Speicherbereiche auch zusammengeführt werden. Dies ist von Vorteil, wenn der Speicher zuvor fragmentiert war.

Claims

1. Verfahren zum Unterscheiden erreichbarer Objekte und nicht erreichbarer Objekte, die sich in einem nichtflüchtigen Speicher (13) befinden, welches von einer objektbasierten Anwendung in einem System mit einem flüchtigen Speicher (14) mit beschränkter Größe angewendet wird, wobei die objektorientierte Anwendung mit einer Menge von n Objekten arbeitet, von denen eine Teilmenge Z Stammobjekte sind, und das Verfahren die folgenden Schritte umfasst:

für jedes Stammobjekt

- von dem Stammobjekt auf jedes andere Objekt zuzugreifen, das vom Stammobjekt aus erreichbar ist,

- alle Objekte zu markieren, die vom Stammobjekt erreicht wurden, und während des Markierens eine Beschreibung des Pfads vom Stammobjekt zum aktuell besuchten Objekt im flüchtigen Speicher (14) zu speichern,

wenn die Markierungsphase ein Objekt erreicht und der entsprechende Pfad nicht in den flüchtigen Speicher (14) passt,

- dieses Objekt nicht zu markieren, sondern als ein später zu verarbeitendes Objekt zu kennzeichnen,

die Markierungsphase so lange fortzusetzen, bis alle Stammobjekte verarbeitet worden sind und alle von einem Stammobjekt aus erreichten Objekte entweder markiert oder als später noch zu verarbeitende Objekte gekennzeichnet worden sind.

2. Verfahren nach Anspruch 1, bei dem ein später zu verarbeitendes Objekt als ein weiteres Stammobjekt gekennzeichnet wird.

3. Verfahren nach Anspruch 1, bei dem ein Zähler dazu verwendet wird, um die Anzahl der bereits verarbeiteten Stammobjekte zu zählen.

4. Verfahren nach Anspruch 1, bei dem die Beschreibung des Pfads das Stammobjekt und beliebige andere Objekte enthält, auf die vom Stammobjekt aus zugegriffen wurde.

5. Verfahren nach Anspruch 3, bei dem der Zähler im flüchtigen Speicher (14) gespeichert ist.

6. Verfahren nach Anspruch 1, bei dem jedes Objekt Nutzinformationen und einen Header aufweist.

7. Verfahren nach Anspruch 6, bei dem der Header mindestens zwei für das Verfahren reservierte Bits umfasst, mit denen erreichbare Objekte und nicht erreichbare Objekte unterschieden werden.

8. Verfahren nach Anspruch 6, bei dem der Header ein Bit (Bit VF) umfasst, welches anzeigt, ob ein Objekt während des Zugreifens von einem Stammobjekt auf andere Objekte bereits besucht worden ist.

9. Verfahren nach Anspruch 6, bei dem der Header ein Bit (Bit RF) umfasst, welches anzeigt, dass ein Objekt ein Stammobjekt ist.

10. Verfahren nach Anspruch 1, bei dem alle Stammobjekte initialisiert werden, um anzuzeigen, dass sie noch nicht verarbeitet worden sind, wobei diese Initialisierung vor dem Ausführen der in Anspruch 1 aufgeführten Schritte bewirkt wurde.

11. Verfahren nach Anspruch 1, bei dem Bereiche des nichtflüchtigen Speichers (13) zurückgewonnen werden, die unmarkierte Objekte enthalten.

12. Verfähren nach Anspruch 1, bei dem der nichtflüchtige Speicher (13) durch Umordnen derjenigen Speicherbereiche des nichtflüchtigen Speichers (13), die markierte Objekte enthalten, komprimiert wird.

13. Verfahren nach Anspruch 6, bei dem die Nutzinformationen Zeiger auf andere Objekte enthalten.

14. Verfahren nach Anspruch 13, bei dem die Zeiger so im Feld der Nutzinformationen angeordnet werden, dass die Zeiger mit Hilfe von im Objektheader enthaltenen Metadaten gefunden werden können.

15. Vorrichtung zum Unterscheiden von erreichbaren Objekten und nicht erreichbaren Objekten, die sich in einem nichtflüchtigen Speicher (13) befinden, welche von einer objektbasierten Anwendung in einem System mit einem flüchtigen Speicher (14) beschränkter Größe verwendet wird, wobei die objektorientierte Anwendung mit n Objekten arbeitet, von denen Z Objekte Stammobjekte sind, wobei die Vorrichtung Folgendes umfasst:

- Mittel zum Zugreifen von jedem Stammobjekt auf alle anderen Objekte, die von den Stammobjekten aus erreichbar sind,

- Mittel zum Markieren aller vom Stammobjekt aus erreichten Objekte und zum Speichern einer Beschreibung des Pfads vom Stammobjekt zum aktuell besuchten Objekt im flüchtigen Speicher (14), wobei die Mittel zum Markieren ein Objekt dann nicht markieren, wenn der · zugehörige Pfad nicht in den flüchtigen Speicher (14) passt,

- Mittel zum Ermitteln eines Objekts, das nicht markiert wurde, weil dessen Pfad nicht in den flüchtigen Speicher (14) passt, als ein später zu verarbeitendes Objekt.

16. Vorrichtung nach Anspruch 15, bei der die Mittel zum Ermitteln eines Objekts dieses Objekt als ein weiteres Stammobjekt festlegen.

17. Vorrichtung nach Anspruch 16, in der ein Zähler vorhanden ist, der zum Zählen der durch die Zugriffsmittel bereits verarbeiteten Stammobjekte verwendet wird.

18. Vorrichtung nach Anspruch 16, bei der die Beschreibung des Pfads das Stammobjekt sowie beliebige andere vom Stammobjekt aus erreichte Objekte beinhaltet.

19. Vorrichtung nach Anspruch 18, bei der der Zähler im flüchtigen Speicher (14) gespeichert ist.

20. Vorrichtung nach Anspruch 16, bei der jedes Objekt Nutzinformationen und einen Header aufweist.

21. Vorrichtung nach Anspruch 18, bei der der Header mindestens zwei Bits umfasst, die dem Unterscheiden zwischen erreichbaren und nicht erreichbaren Objekten dienen.

22. Vorrichtung nach Anspruch 16, die Mittel zum Wiedergewinnen der Bereiche des nichtflüchtigen Speichers (13) umfassen, welche unmarkierte Objekte enthalten.

23. Vorrichtung nach Anspruch 16, die Mittel zum Komprimieren des nichtflüchtigen Speichers (13) durch Umordnen derjenigen Speicherbereiche des nichtflüchtigen Speichers (13) umfasst, welche markierte Objekte enthalten.

24. Vorrichtung nach Anspruch 16 als Bestandteil eines Systems mit beschränkten Ressourcen.

25. Vorrichtung nach Anspruch 16 als Bestandteil einer integrierten Schaltkreiskarte.