DseWiki: GarbageCollection

(engl. Abk: "GC") Fortgeschrittenes System zur Automatisierung der dynamischen SpeicherVerwaltung (Was man in C mittels malloc/free per Hand tun muss).

Eine auf deutsch verfasste Einführung: http://www.ssw.uni-linz.ac.at/Teaching/Lectures/Sem/2003/reports/Kusel/Kusel.pdf

Algorithmen zur GarbageCollection

Es gibt viele Algorithmen zur Implementierung von GarbageCollection, die alle ihre Vor- und Nachteile haben und die unterschiedlich komplex sind.

Tracing GC vs ReferenzZählung' Streng genommen gehört ReferenzZählung als Gegenstück zur "Tracing GC" (Verfolgenden GC) auch zur GarbageCollection, üblicherweise aber trennt man es strikt, und meint mit GC nur die "Tracing GC".

üblicherweise? Wo ist das üblich? Eine einfache Suche mit der Und-Verknüpfung von Garbage Collection und Reference Counting erzeugt über 12,000 Hits. In der einschlägigen Fachliteratur wird unter GarbageCollection immer auch die ReferenzZählung erwähnt. Hier nur ein Link mit der üblichen Definition: http://burks.brighton.ac.uk/burks/foldoc/89/45.htm :

garbage collection [...] The three main methods are mark-sweep garbage collection, reference counting and copying garbage collection. -- PeterFunk
In Programmiererkreisen, die mit GC arbeiten. D.h Lisp, Java, ML, Haskell, Smalltalk, u.a. --ReiniUrban

Konservative GC: Objekte müssen nur wissen wie groß sie sind, aber nicht ob sie Zeiger oder Daten beinhalten. Die Objekte werden nicht kopiert, also müssen keine Zeiger angepaßt werden. Der üblichste Algorithmus ist Mark and Sweep. Wenn das System keinerlei Unterstützung über den Datentyp in Objekten beinhaltet (Zeiger oder nicht), können einige Objekte uU. von der Freigabe ausgeschlossen sein, obwohl sie nicht mehr referenziert werden. "Black-listing" kann das umgehen. (

http://www.xanalys.com/software_tools/mm/glossary/b.html#blacklisting) Der Böhm GC ist der meistverwendete, vor allen mit primitiven Sprachen wie C++.

Kopierende GC: "Stop & Copy" verursacht die berühmten Pausen, ist aber relativ leicht zu implementieren und hält den Hauptspeicher kompakt. Kopierende GC sind "kompaktierend", dh. sie verursachen keine Löcher wie bei Mark-Sweep, malloc oder ReferenzZählung.

Verteilte GC: Wird in Systemen mit nicht durchgehenden Hauptspeicher Segmenten verwendet, zB. in verschiedenen Threads, privaten CPU-Heaps oder verschiedenen Maschinen. Auf WAN-System ist der Verwaltungsaufwand zur Synchronisation und Kommunikation sehr hoch, daher wird statt Tracing GC, üblicherweise "gewichtete ReferenzZählung" eingesetzt. (In DCOM nur ungewichtete ReferenzZählung). http://www.xanalys.com/software_tools/mm/glossary/w.html#weighted.reference.counting

Generationelle GC: Ein GC mit Trennung in verschiedene Altersklassen der Objekte, der sehr gut durch moderne CPU-Caches und moderne Sprachen unterstützt wird. Diese GC's sind üblicherweise die schnellsten. http://www.xanalys.com/software_tools/mm/glossary/g.html#generational.garbage.collection

Inkrementelle GC: Einfache GC's können in ihrer Ausführung nicht unterbrochen werden. Inkrementelle GC können durch Pausen unterbrochen werden, ohne inkonsistente Daten zu hinterlassen. Dadurch sind sie für Echtzeit- und hoch interaktive Anwendungen geeignet. http://www.xanalys.com/software_tools/mm/glossary/i.html#incremental.garbage.collection

Parallelle GC: Ein GC für Multiprozessorsysteme, der ähnlich aber schwieriger als ein inkrementeller GC ist, implementiert mit Hilfe von "Barriers" (Software oder Hardware Unterstützung bei LOAD und STORE ops). http://www.xanalys.com/software_tools/mm/glossary/p.html#parallel.garbage.collection

Viele Programmiersprachen habe GC als Feature: Lisp, Smalltalk, Java, ML, Prolog, manche Basic-Dialekte, ...
Hybrid (siehe ReferenzZählung): Perl, Python
Nicht: C, C++, PHP, ...

Vorteile:

Einfacher für den Programmierer
Eine Klasse möglicher Fehler fällt weg
Interface Probleme mit Bibliotheken fallen weg. Kein Zusatzaufwand an Speicher (doppelte Kopien), Zeit und Unlesbarkeit.
Dadurch bessere Lokalität, weniger aktive Variablen und weniger Paging.
...

Nachteile:

Performanceverluste (stimmt nicht --ru)
Probleme bei Real-Time-Anwendungen (Pausen, die durch die Speicherreorganisation entstehen können) (nur bei Stop-And-Copy GC --ru)
Fehler in der Speicherverwaltung, die man wegen "Vorteile - Eine Klasse möglicher Fehler fällt weg" nicht machen kann, wuerden evtl. von dem Programmierer der GC-Routinen gemacht und sind nun nicht mehr so einfach korrigierbar. (alte Mythen --ReiniUrban)

Deswegen programmiere ich auch grundsätzlich direkt in Maschinencode, da der Programmierer eines Compilers ja Fehler gemacht haben könnte, die ich dann nicht einfach korrigieren kann... ;-) -- IljaPreuß

Laß mich raten --- dem Umsetzer Mnemonik -> Maschinencode hast du auch selbst geschrieben, da die Assembler-Programmierer auch Fehler gemacht haben könnten ;-) --rae

Ich hatte schon mit voller Absicht Maschinencode und nicht Assembler geschrieben... Was mir noch echte Kopfzerbrechen bereitet: Ich bin noch nicht dazu gekommen, den Microcode für meinen eigenen Prozessor zu schreiben - seit Intel weiß man ja, inwieweit man sich da auf andere verlassen darf... %-) -- ip

Beachte, das automatische SpeicherVerwaltung auch ReferenzZählung sein kann. Bekannte Beispiele sind Perl und COM. Siehe auch

http://www.xanalys.com/software_tools/mm/faq.html Moderne GC (incremental generational oder RealTime? GC's) sind ungleich besser als manuelle SpeicherVerwaltung. --ReiniUrban

Vergleich ReferenzZählung - GarbageCollection:

refcounts sind trivial zu implementieren, langsam, brauchen Speicher pro node und können keine rekursiven datenstrukturen.
gc sind höchst kompliziert zu implementieren, schnell, brauchen keinen Speicher pro node und können alles.

Der Vergleich zu malloc schaut ähnlich aus. Allokierung geht mit GC ungleich schneller als mit malloc, free ist etwa schneller als GC, aber Generationelle GC's gleichen das aus.

Außerdem, wer verwendet schon den C alloca? In guten Lisp's, ML's oder scheme passiert das automatisch, da der Compiler mehr weiß und Funktionsaufrufe besser optimieren kann. (-> automatische SpeicherVerwaltung)

Links:

Verschiedene GC-Systeme für C und C++,

http://www.lisp.org/table/memory.htm
http://www.xanalys.com/software_tools/mm/faq.html
http://www.xanalys.com/software_tools/products/myths&legends.html
http://www.enme.ucalgary.ca/~nascheme/python/gc.html --GarbageCollection in SprachePython
http://sit.gmd.de/Lava/LavaDoc/html/PointersRefCounts.htm GarbageCollection mit ReferenzZählung in SpracheLava
PhD? thesis: Escape Analysis (spezielle Optimierungen), http://www.di.ens.fr/~blanchet/escape-eng.html

Siehe auch:

GarbageCollectionBuch
Richard Jones, Linksammlung, http://www.cs.kent.ac.uk/people/staff/rej/gc.html

GC in Java

IBM-Java, siehe Artikelserie Teil 1, Teil 2

GC in Smalltalk

Die oben genannten Techniken werden kombiniert. Der GC von VisualWorks besteht z. B. aus einem sog. Generation Scavenger, einem Incrementellen GC und einem Kompaktifizierer. Außerdem kann auch die Objektbasis für den Suchalgorithmus bereinigt werden (globaler GC für den Permanentspeicher), was ein Standardschritt beim Deployment ist. Will man C-Routinen ansprechen, sind wieder andere Mechanismen wie z. B. explizite Heap-Kopie oder Schutz vor dem GC erforderlich.

Vor Speicherzugriffsfehlern der VM braucht man kaum Angst zu haben. Problematischer wird's bei der Parametriesierung des GC. Anwendungen mit speziellen Anforderungen an den GC müssen adäquate Werte setzen oder eine Unterklasse der Standard-Memory-Policy schreiben.

Auf den Seiten von Cincom gibt es hochinteressante aber mitunter leider schwer zu findende Dokumente über das Memory-Management von VisualWorks. Einen ersten Überblick gibt

http://www.cincomsmalltalk.com/CincomSmalltalkWiki/DOWNLOAD/DOCS/memory-VW3.x.pdf

KategorieProgrammierSprachenKonzepte KategorieResourcen KategorieJargon