|
|
|
 |
In Abbildung 7.22 sind zwei Klassen dargestellt, die für die Umsetzung einer Speicherbereinigung in C++ verwendet werden können.
Dabei werden die eigentlichen Objekte (Exemplare der Klasse RefCounted) in so genannten Smart Pointern, in diesem Fall Exemplare der Klasse RefCountBasePtr, gekapselt. Bei Konstruktion und Zuweisungen wird dann nur noch mit RefCountBasePtr gearbeitet. Um auf das eigentliche Objekt durchzugreifen, das über m_pTarget referenziert wird, ist der Operator -> überladen. Dieser wird beim Zugriff das enthaltene Exemplar von RefCounted liefern. In Listing 7.26 ist die Umsetzung dargestellt. Dabei wird ersichtlich, dass der Referenzzähler auf dem eigentlichen Objekt jeweils angepasst wird. class RefCountPtrBase
{
public:
RefCountPtrBase(RefCounted const* pTarget): 1
m_pTarget(pTarget) {
m_pTarget->AddRef();
}
RefCountPtrBase(RefCountPtrBase const& another): 2
m_pTarget(another.m_pTarget) {
m_pTarget->AddRef();
}
~RefCountPtrBase() { 3
m_pTarget->Release();
}
RefCountPtrBase& operator= (RefCountPtrBase const& 4
another) {
another.m_pTarget->AddRef();5
m_pTarget->Release(); 5
m_pTarget = another.m_pTarget;
return *this;
}
// ...
}
class RefCounted
{
signed long mutable m_nRefCount;
// ...
void AddRef() { 6
++m_nRefCount;
}
void Release() { 7
--m_nRefCount;
if (0 == m_nRefCount) {
delete this;
}
}
// ...
}
Listing 7.26 Zählen von Referenzen (Das aufgeführte Listing ist vereinfacht dargestellt. Die komplette Implementierung dieses Verfahrens findet sich auf der Webseite zum Buch.) In Zeile 1 wird ein Konstruktor definiert, dem ein Exemplar von RefCounted übergeben wird. Dabei wird auf ihm auch gleich der Referenzzähler erhöht, da es nun eine weitere Referenz auf das Objekt über den gerade konstruierten neuen Smart Pointer gibt. In Zeile 2 erfolgt das Gleiche für den Konstruktor, in dem eine Kopie angelegt wird. In Zeile 3 wird der Zähler ebenfalls heruntergezählt, weil gerade einer der Smart Pointer gelöscht wird. In Zeile 4 wird ein neues Exemplar von RefCounted auf den Smart Pointer zugewiesen. Deshalb muss der Zähler für das bisher referenzierte Objekt heruntergezählt werden, für das neue Objekt erhöht (Zeilen mit der Markierung 5). Für die Klasse RefCounted sind die Operationen zum AddRef und Release umgesetzt. Dabei zählt AddRef in Zeile 6 ganz einfach den Zähler hoch. Release setzt den Zähler herunter und gibt das Objekt frei, sobald der Zählerstand 0 erreicht. So weit, so einfach. Allerdings hat dieses Verfahren einen großen Haken, der es für den Einsatz in vielen Fällen unbrauchbar macht: Wenn irgendwo in unseren Objekten zyklische Referenzen auftauchen, werden die betroffenen Objekte nie den Zählerstand 0 erreichen und damit auch nie gelöscht werden. In diesem Fall gibt es nämlich auf jedes der beteiligten Objekte immer eine Referenz. Zyklische Referenzen sind aber in objektorientierten Anwendungen etwas sehr Normales und häufig.
In Abbildung 7.23 sind solche zyklischen Verweise dargestellt. Auftreten können sie zum Beispiel, wenn Rückreferenzen bei Aggregationsbeziehungen gepflegt werden. Dabei hält das Aggregat eine Liste der aggregierten Objekte, diese wiederum halten eine Referenz auf das Aggregat. Diese Information ist dann zwar redundant, kann aber aus Gründen der Zugriffseffizienz sinnvoll sein. Im dargestellten Beispiel kennt ein Auftrag die Liste der in ihm enthaltenen Positionen, umgekehrt weiß aber auch jede Position, zu welchem Auftrag sie gehört. Zählen von Referenzen ist nicht vollständig. Was wir aber brauchen, ist ein Verfahren, das konsistent und vollständig ist. Konsistent heißt in diesem Fall: Es wird nie ein Objekt aufgeräumt, das noch gebraucht wird. Diese Anforderung erfüllt das Zählen von Referenzen. Vollständig heißt in diesem Fall: Es werden alle Objekte, die nicht mehr gebraucht werden, auch wirklich weggeräumt. Diese Anforderung wird durch das Zählen von Referenzen nicht erfüllt. Allerdings kann das Zählen von Referenzen für Teile einer Applikation, in denen zyklische Referenzen nicht erwartet werden, eine einfache und ressourcenschonende Methode sein, um Speicher automatisch zu verwalten. So verwenden einige Klassen aus der C++-Standardbibliothek Referenzzähler, um ein automatisches Löschen von Objekten zu ermöglichen. Ein Beispiel dafür ist die string-Klasse. Markieren und Löschen (Mark and Sweep)Wenn also die Möglichkeit von zyklischen Referenzen besteht, ist das reine Mitzählen nicht ausreichend. In diesem Fall müssen alternative Verfahren zum Einsatz kommen. Eine gängige Alternative ist das so genannte Mark-and-Sweep-Verfahren. Wörtlich übersetzt heißt das Verfahren Markieren und Ausfegen. Markierungsphase Der Mark-and-Sweep-Algorithmus sucht zunächst alle Objekte, die von anderen referenziert werden, und markiert sie (Markierungsphase). Dazu ist es notwendig, dass ein Startpunkt (möglicherweise auch mehrere Startpunkte) bekannt ist, also Objekte, von denen wir wissen, dass sie nicht entfernt werden dürfen.3 Zu solchen Objekten gehört zum Beispiel das Applikationsobjekt selbst. Diese Startobjekte werden nun markiert, also in eine Liste von Objekten aufgenommen, die nicht gelöscht werden dürfen. Welche Objekte werden aber nun wiederum von den Startobjekten referenziert? Sie alle müssen wir natürlich auch in die Liste aufnehmen, sofern sie nicht schon dort enthalten sind. Und alle neu hinzugefügten Objekte müssen ebenfalls überprüft werden. Die Suche bedient sich dabei Algorithmen, die zur Lösung des Erreichbarkeitsproblems in Graphen verwendet werden.
In Abbildung 7.24 ist die Markierungsphase für ein Beispiel dargestellt. Ausgehend vom Applikationsobjekt werden alle erreichbaren Objekte markiert. Die fett gezeichneten Linien werden dabei durchlaufen, so dass am Ende die dunkelgrau hinterlegten Objekte markiert sind. Bereits markierte Objekte (wie zum Beispiel Auftrag2) werden nicht mehr angepasst und weiter bearbeitet, wenn sie zum zweiten Mal erreicht werden. Die hellgrau hinterlegten Objekte sind nicht erreichbar und werden somit auch nicht markiert. Löschphase Ist die Markierungsphase abgeschlossen, folgt die so genannte Sweep-Phase. Dabei findet ein erneuter Durchlauf durch die Objektmenge statt, bei dem jedes Objekt, das nicht markiert wurde, gelöscht wird, da es erwiesenermaßen nicht mehr referenziert wird.
In Abbildung 7.25 sind die nach der Sweep-Phase verbleibenden Objekte dargestellt.4 Beim Löschdurchlauf wird außerdem das Flag zurückgesetzt, das die Objekte als bereits markiert gekennzeichnet hat. Komplexität abhängig von Gesamtzahl der Objekte Mark and Sweep hat allerdings ein paar Nachteile. Der Hauptnachteil ist die Komplexität des zugehörigen Algorithmus, also sein Bedarf an Zeit und Speicher. Der Zeitbedarf der Markierungsphase ist linear abhängig von der Anzahl der noch verwendeten Objekte. Der Zeitbedarf der Löschphase ist linear abhängig von der Anzahl der insgesamt vorhandenen Objekte. Kopieren der erreichbaren ObjekteIn vielen Fällen besser als Mark and Sweep arbeitet ein anderer Algorithmus (Copy-Collector), der die noch erreichbaren Objekte direkt in einen neuen Speicherbereich kopiert. Da der Algorithmus die nicht erreichbaren Objekte überhaupt nicht betrachten muss, ist seine Komplexität nur von der Anzahl der wirklich erreichbaren Objekte abhängig. In sehr dynamischen Anwendungen, in denen eine große Zahl von kurzlebigen Objekten erzeugt wird, kann die Anzahl der zu löschenden Objekte im Vergleich zu der Zahl der überlebenden Objekte sehr groß sein, der Vorteil des Algorithmus kann also relevant sein. Beim Kopieren wird der komplette noch erreichbare Bestand an Objekten in einen vorher leeren Speicherbereich kopiert, den so genannten To-Space. Danach wird der bisher genutzte Speicherbereich, der auch From-Space genannt wird, geleert. Die genutzten Speicherbereiche werden also bei jeder durchgeführten Garbage Collection vertauscht. Aktionen Dabei werden für die betroffenen Objekte jeweils die folgenden Aktionen durchgeführt:
Zwischenstand beim Kopieren In Abbildung 7.26 ist der Stand des Kopierens dargestellt, nachdem das Einstiegsobjekt (das Applikationsobjekt) kopiert und der Zeiger darauf umgesetzt wurde. Die von diesem Objekt aus weiterführenden Referenzen sind noch nicht angepasst und zeigen immer noch in den From-Space.
Kopieren von referenzierten Objekten In Abbildung 7.27 ist der nächste Schritt dargestellt, bei dem dann die ersten beiden referenzierten Objekte kopiert wurden. Wieder sind deren weitere Referenzen noch in den From-Space gerichtet. Ganz einfach wird das Verfahren, wenn ein Objekt bereits kopiert wurde. In Abbildung 7.28 ist die Situation dargestellt, dass das bereits kopierte Objekt Position eine Referenz auf das bereits früher kopierte Objekt Auftrag2 hat.
Referenzen umsetzen In diesem Fall ist nichts weiter zu tun, als die Referenz, die von Position aus gehalten wird, auf das bereits kopierte Objekt zu setzen. Wo dieses liegt, haben wir uns im ursprünglichen Objekt Auftrag2 vorher gemerkt. Entfernen Nach Abschluss des Verfahrens sind die noch erreichbaren Objekte im To-Space gelandet, wie in Abbildung 7.29 dargestellt. Der gesamte Speicherbereich im From-Space wird nun auf einen Schwung freigegeben, da alle noch benötigten Objekte bereits kopiert wurden. Die Applikation kann jetzt mit allen noch in Verwendung befindlichen Objekten weiterarbeiten.
Die junge und die alte Generation (Generational Garbage Collection)In der Praxis machen die meisten modernen Verfahren zur Garbage Collection die Tatsache nutzbar, dass die Lebensdauer von Objekten nicht gleichmäßig verteilt ist. Die Speicherverwaltung der virtuellen Maschine von Java nutzt unter anderem auch ein Verfahren, das die Speicherbereinigung vom Alter der betroffenen Objekte abhängig macht. Die Grundidee dabei ist: Wenn ein Objekt die erste Zeit überstanden hat, dann wird es sehr wahrscheinlich auch weiter dabei bleiben. Es macht also Sinn, zwischen jungen und alten Objekten zu unterscheiden. Ältere Objekte bleiben unter sich. Und eine weitere Beobachtung: Ältere Objekte bleiben meist unter sich, sie referenzieren nur selten junge Objekte. Der Dialog zwischen den Generationen findet bei Objekten nur sehr begrenzt statt. Diese Beobachtungen sind für den überwiegenden Teil von Applikationen zutreffend. Wir geben hier einen kurzen Überblick über das Verfahren, wie es von der virtuellen Maschine von Java (Hotspot) angewendet wird.
Verwendete Speicherbereiche In Abbildung 7.30 sind die verwendeten Speicherbereiche jeweils mit typischen Bewohnern abgebildet:
Es finden nun zwei ganz verschiedene Arten der Garbage Collection statt. Der Unterschied zwischen den beiden ist etwa der zwischen dem Aufräumen unserer Wohnung und dem kompletten Entrümpeln. Aufräumen Die erste Variante, das Aufräumen, wird häufiger durchgeführt und arbeitet nur auf dem Bereich der jungen Generation. Wir sprechen dabei von einer kleinen (minor) Garbage Collection. Dabei wird standardmäßig nach dem Copy-Verfahren aus dem Bereich Eden und dem From-Space in den To-Space kopiert. Für die Objekte, die aus dem From-Space kopiert werden, wird zusätzlich ein Zähler hochgezählt. Erreicht dieser einen vordefinierten Wert, haben die Objekte also eine größere Zahl von Durchläufen des Garbage Collectors überstanden, dann dürfen sie sich zur alten Generation gesellen und werden in deren Bereich verschoben. Entrümpeln Ein komplettes Entrümpeln führen wir ja auch im realen Leben eher selten durch, weil das wesentlich aufwändiger ist. So wird auch Garbage Collection im Bereich der alten Generation nur in größeren Abständen durchgeführt. Diese wird dann als große (major) Garbage Collection bezeichnet. So viele Algorithmen und Verfahren: Was geht mich das an?Sofern in unserem gewählten Entwicklungssystem eine gute Garbage Collection zur Verfügung steht, werden wir zumindest kein eigenes Verfahren dafür umsetzen müssen. Das Vorhandensein von erprobten Verfahren zur Garbage Collection ist denn auch ein gutes Argument für die Verwendung einer Sprache wie Java anstelle von C++. Allerdings bietet zum Beispiel die Java-Laufzeitumgebung seit der Version 1.4 gleich vier verschiedene Verfahren zur Garbage Collection an, die alle auch über verschiedene Parameter weiter beeinflusst werden können. Das voreingestellte Verfahren wird zwar für viele Fälle funktionieren, um die Effizienz einer Applikation zu steigern, ist ein gezielter Einsatz der speziellen Verfahren aber ein gutes Mittel. 1 Das ist nicht ganz korrekt. Noch einfacher ist es, einfach überhaupt nicht aufzuräumen und die nicht mehr gebrauchten Objekte im Speicher zu belassen. Dies ist jedoch nur für sehr kleine Systeme, die nur kurze Einsatzzeiten haben, wirklich praktikabel. 2 Eine ausführliche Diskussion von optimierten Verfahren zur Garbage Collection findet sich zum Beispiel in der Dokumentation von Sun zur Garbage Collection der virtuellen Maschine ab Version 1.4. Die virtuelle Maschine von Java erlaubt aktuell die Auswahl aus vier unterschiedlichen Verfahren zur Garbage Collection. Der entsprechende Artikel findet sich unter http://java.sun.com/docs/hotspot/gc1.4.2/. 3 Existiert ein solcher Startpunkt nicht, können alle Objekte entfernt werden. Diese Situation tritt aber in praktischen Fällen nicht auf, da in der Regel ja zumindest mit der Applikation selbst (die in der Regel auch ein Objekt ist) weitergearbeitet werden soll. 4 Der englische Begriff sweep hat die wörtliche Übersetzung »ausfegen«, was schon ziemlich gut das Vorgehen des Algorithmus trifft. Wir sprechen trotzdem in der deutschen Übersetzung von der Löschphase des Algorithmus.
|
|
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Copyright © Galileo Press 2006
Für Ihren privaten Gebrauch dürfen Sie die Online-Version natürlich ausdrucken. Ansonsten unterliegt das <openbook> denselben Bestimmungen, wie die gebundene Ausgabe: Das Werk einschließlich aller seiner Teile ist urheberrechtlich geschützt. Alle Rechte vorbehalten einschließlich der Vervielfältigung, Übersetzung, Mikroverfilmung sowie Einspeicherung und Verarbeitung in elektronischen Systemen.
