DGC

1

DGC

2

Motivation

x

new(x)

delete(x)

Speicher

DGC

3

Inhalt

Einführung GC / DGC

Der ideale DGC

Algorithmen

Zusammenfassung

DGC

4

Was ist Garbage Collection?

• übersetzt: „Müllsammlung“

• Automatisierte Verwaltung von dynamisch zugewiesenem Speicher

• Bestimmung des vom Programm nicht mehr genutzten Speichers

• Freigeben dieses Speichers

• Bestandteil einer Programmiersprache, der Hardware, des Betriebssystems

Was

• Manuelle Speicherverwaltung kostet Zeit und führt zu Fehlern

• Programme mit Speicherlecks

• mit wachsendem Internet von immer größerer Bedeutung

Wofür

DGC

5

Roots Roots

Einblick

lebendig

tot

Objekte

Roots Root-Set

Referenz

DGC

6

Reference Consistency Protocol

• Legt fest, wie Stubs und Scions erstellt werden

• Konsistenten Zustand bewahren

• Erreichbarkeit über Systemgrenzen sicher stellen

u v

stub scion

DGC

7

Allgemeine Probleme

• Statusabfrage mittels Nachrichten

• Kommunikation ist unzuverlässig

• Verteilte Systeme sind asynchron

• Systemausfälle

• Verteilte Zyklen

• Race Conditions

• Skalierbarkeit

DGC

DGC

8

Eigenschaften eines idealen DGC

• Vollständig

• Kooperierend

• Schnell

• Effizient

• Lokal

• Zweckmäßig

• Skalierbar

• Fault tolerant

• Sicher

DGC

9

Algorithmen

Counting-Algorithmen

• Zählen die Referenzen zu einem Objekt

• wenn keine Referenz existiert, wird Objekt entfernt

• z.B. Reference Counting

Tracing-Algorithmen

• Durchlaufen des Referenz-Graphen von der Root-Set aus bis zu den Kindern

• z.B. Mark-Sweep

Hybride-Algorithmen

• Komposition aus mehreren Algorithmen

• DGC Algorithmen sind modifizierte GC-Algorithmen

Grundarten

DGC

10

Reference Counting

• Einfachster Algorithmus (1960)

• An jedem Objekt wird ein Zähler angehängt

• Dieser wird erhöht bzw. erniedrigt bei einer Vervielfältigung bzw. Löschung einer Referenz

• Wenn der Zähler = 0 ist, wird das Objekt aus dem Speicher entfernt

1

Im Detail

u v

stub scion

@v

DGC

11

u

v

w

+1

Race Conditions

@v

12

u

v

w

-1+1

@v

10

ACK

DGC

12

• einfache zu implementieren

• inkrementell

• Speicher wird in Echtzeit freigegeben

• skalierbar

• Jedes Objekt muss Platz für Zähler lassen

• Overhead an Pointer-Update-Operationen

• Race Conditions oder

• Bestätigungsnachrichten (ACK) erzeugen extra Traffic

• Nicht fault-tolerant

• Speicherfragmentierung

• Zyklen werden nicht erkannt

Vorteile

Nachteile

Reference Counting

DGC

13

Distributed Garbage Cycle

Garbage

RA

RB RC

2

1

1

DGC

14

Weighted Reference Counting

• statt eines Counters werden Gewichte benutzt

• Jede entfernte Referenz hat zwei Gewichte

• Gesamt- und Teilgewicht (im scion)

• Ein stub beinhaltet nur das Teilgewicht

• Bei einer neuen entfernten Referenz:

• Hälfte des Gesamtgewichts an Referenz übergeben

• Bei Duplikation einer Referenz wird Teilgewicht halbiert

• entfernte Referenz erhält nur dekrement-Nachrichten, das sie vom Gesamtgewicht abzieht

• sind Gesamt- und Teilgewicht gleich, bestehen keine Referenzen mehr

DGC

15

x

v

y

@v/16

32/64

32 1616

32/48

@v/32

control message:-16

Weighted Reference Counting

RA RB

RC

DGC

16

• Bei Gesamtgewicht von 2k nur k Duplizierungen sein

• nicht fault-tolerant

• keine Beseitigung von Zyklen

Vorteile

Nachteile

• Benutzt nur wenige Nachrichten wenig Traffic

• Keine Race-Conditions

Weighted Reference Counting

DGC

17

Reference Listing

• es gibt max. einen stub für einen scion

• scion gewöhnlich als doppelt verkettete Liste implementiert

• Operationen sind einfügen und löschen

• fault-tolerant

• Race Conditions bleiben bestehen (LösungtimeStamps)

RA

RB

RCx

y

v

DGC

18

Mark-Sweep

• Besteht aus 2 Phasen

• Phase 1 (Mark):

• Markieren der erreichbaren Objekte vom root-set aus

• Phase 2 (Sweep):

• Löschen aller unmarkierten Objekte

• in verteilten Systemen ist Mark-Phase global und Sweep-Phase lokal

Algorithmus

• Tracing-Collector

• beginnen im root-set und verfolgen Referenzen

• alle nicht erreichbaren Objekte werden entfernt

DGC

19

root

DGC

20

• automatisches beseitigen von zyklischen Datenstrukturen

• Kein Overhead bei Zeiger-Operationen

• fault-tolerant (bei Fehlern von vorn beginnen)

Vorteile

Nachteile

Mark-Sweep

• Fragmentierung

• Garbage wird erst entfernt, wenn Speicher erschöpft

• Unterbricht das Programm während des Vorgangs

• Kosten sind proportional zur Größe des Systems

• schlecht skalierbar

• Trashing

• Synchronisationsproblem

DGC

21

Synchronisationsproblem

A B

C

x

RA RB

z

@x

@x

x is garbage

Lösung

• Strenge Protokolle (globale Barriere)

• Am Ende jeder lokalen mark-Phase Barriere setzen

• Danach tritt globale sweep-Phase ein

DGC

22

Copying GC

• Erstmals in LISP verwendet (ca. 1965)

• Speicher wird in der Hälfte geteilt

• nur die lebendigen Objekte in den anderen Speicher bewegen

aktuell

veraltet

Speicher

aktuell

veraltet

DGC

23

• Keine Fragmentierung

• Einfache lineare Speicherzuordnung

• Keine Zyklen

• Kosten sind proportional zu den lebendigen Objekten

Vorteile

Nachteile

Copying GC

• Kopieren ist teuer

• doppelte Größe des benutzten Speichers wird benötigt

• Garbage wird erst entfernt, wenn Speicher erschöpft

• schlecht skalierbar

DGC

24

Hybride GCs

• Kombinieren zwei oder mehreren Algorithmen

• meist wird Reference Counting Technik mit Tracing Technik kombiniert

• so werden auch Zyklen entfernt

• Tracing wird dabei weniger häufig ausgeführt wie Reference Counting

• Algortihmen sind z.B.:

•Migration, Trial Deletion und Local Tracing

• heuristische Suche nach Zyklen

• sind meist ineffizient (Overheads beim Löschen einer Referenz)

DGC

25

Zusammenfassung

• es gibt keinen perfekten Algorithmus

• Anpassung an die Systemumgebung

• Tracing-Algorithmen:

• sollten nur in kleinen Verteilten Systemen angewendet werden (wegen Synchronisation+schlechten Skalierbarkeit)

• nicht für Interaktive und RealTime-Anwendungen geeignet

• wenn Response-Time unwichtig, dann schneller als Counting Algorithmen

• Counting-Algorithmen:

• Verwendung in Systemen, wo Zyklen selten oder nicht vorhanden sind

• bei großen verteilten Systemen:

• fault-tolerant Counting-Algorithmus (reference listing)

DGC

26

Fragen ???