Systeme zur automatischen Speicherbereinigung

Mark & Sweep-Verfahren zur Speicherbereinigung scheinen bei der Entwicklung neuer Systeme stets bevorzugt zu werden. Sie sind theoretisch einfacher als andere Verfahren zu implementieren, wobei allerdings der Begriff einfach äußerst relativ ist. Dieser Algorithmus wurde in zahlreichen frühen Versionen von Java Virtual Machines verwendet und er kommt auch heute noch in vielen modernen Garbage Collectors als Unteralgorithmus vor.

Das Mark & Sweep-Verfahren durchläuft zunächst alle Referenzen, die von einem vorgegebenen Systemobjekt ausgehen. Dieses Objekt erfüllt eine Schlüsselfunktion für die virtuelle Maschine, z.B.: Wenn das Objekt nicht vorhanden ist, wird die virtuelle Maschine unterbrochen (d.h. die Ausführung der Anwendung wird beendet). Jedes im Referenzdurchlauf gefundene Objekt wird dann als besucht markiert. Anschließend erfolgt ein Durchlauf aller gefundenen Objekte. Durch dieses Verfahren wird der gesamte von dem vorgegebenen Systemobjekt ausgehende Referenzbaum durchlaufen, wobei alle besuchten Objekte eine Markierung erhalten.

Nach Abschluss dieses Vorgangs überprüft der Algorithmus seine Gesamtliste der vorhandenen bekannten Objekte. Sollten bestimmte Objekte nicht markiert sein, werden sie als nicht mehr benötigt betrachtet.

Dieser Algorithmus ist zwar klar und einfach aufgebaut, doch enthält er eine Reihe negativer Aspekte. Vor allem muss die Ausführung sämtlicher Anwendungen gestoppt werden, solange der Algorithmus arbeitet, da Änderungen am Referenzbaum während des Durchlaufverfahrens den Algorithmus stören. Auf diesen Algorithmus waren beispielsweise die Ausführungsunterbrechungen zurückzuführen, für die Java in seinen Anfängen berüchtigt war. Außerdem führt die wiederholte Durchführung des Mark & Sweep-Verfahrens zur Fragmentierung des Speichers, was die Zuweisung von Speicherplatz erschwert. Schließlich wird eine Defragmentierung des Speichers erforderlich, wodurch die Ausführung erneut unterbrochen wird.