gc

Die Aufgabe der Garbage Collection ist es, den Speicher nicht mehr verwendeter Objekte freizugeben und Platz für andere Objekte zu schaffen. Diese einfache Beschreibung ist in der Implementierung jedoch alles andere als einfach. Die Geschichte der Garbage Collection reicht mehrere Jahrzehnte zurück. Schon in den 1960er Jahren verwendete Lisp erstmals einen Garbage-Collection-Mechanismus. Python und Objective-C nutzen hauptsächlich Referenzzählung als GC-Mechanismus, während Java und C# generationalen GC verwenden. Heute lassen sich Garbage-Collection-Algorithmen grob in folgende Kategorien einteilen:

• Referenzzählung: Jedes Objekt protokolliert, wie oft es referenziert wird. Bei einem Zähler von 0 wird es freigegeben
• Mark-and-Sweep: Aktive Objekte werden markiert, nicht markierte Objekte werden freigegeben
• Kopierender Algorithmus: Aktive Objekte werden in neuen Speicher kopiert, alle Objekte im alten Speicher werden freigegeben
• Mark-Compact: Eine Weiterentwicklung von Mark-and-Sweep, bei der aktive Objekte während der Freigabe an den Anfang des Heaps verschoben werden

Nach der Anwendungsmethode lassen sich folgende Kategorien unterscheiden:

• Globale Freigabe: Alle Garbage-Objekte werden auf einmal freigegeben
• Generationaler GC: Objekte werden nach ihrer Überlebensdauer in verschiedene Generationen unterteilt, für die unterschiedliche Algorithmen verwendet werden
• Inkrementeller GC: Bei jedem Durchlauf wird nur ein Teil des Garbage freigegeben

TIP

Besuchen Sie The Journey of Go's Garbage Collector, um mehr über die Geschichte von Go's Garbage Collection zu erfahren.

Bei der ersten Veröffentlichung war Go's Garbage-Collection-Mechanismus sehr einfach: nur ein einfacher Mark-and-Sweep-Algorithmus. Das durch GC verursachte STW (Stop The World - das Anhalten des gesamten Programms während der Garbage Collection) dauerte mehrere Sekunden oder länger. Das Go-Team erkannte dieses Problem und begann, den Garbage-Collection-Algorithmus zu verbessern. Zwischen Go 1.0 und Go 1.8 wurden verschiedene Ansätze ausprobiert:

1. Read-Barrier Concurrent Copying GC: Read-Barrier hat viele ungewisse Kosten, dieses Konzept wurde verworfen
2. Request-Oriented Collector (ROC): Erfordert permanent aktivierte Write-Barrier, was die Ausführungsgeschwindigkeit beeinträchtigt und die Kompilierzeit erhöht
3. Generationaler GC: In Go nicht sehr effizient, da Go's Compiler dazu neigt, neue Objekte auf dem Stack zuzuweisen und langlebige Objekte auf dem Heap, sodass die meisten kurzlebigen Objekte direkt vom Stack freigegeben werden
4. Card Marking ohne Write-Barrier: Ersetzt die Kosten der Write-Barrier durch Hashing-Kosten, erfordert Hardware-Unterstützung

Schließlich entschied sich das Go-Team für die Kombination aus dreifarbiger gleichzeitiger Markierung und Write-Barrier. Diese wurde in nachfolgenden Versionen kontinuierlich verbessert und optimiert und wird bis heute verwendet. Die folgende Abbildung zeigt die GC-Latenzentwicklung von Go 1.4 bis Go 1.9.

Zum Zeitpunkt dieses Artikels nähert sich Go bereits Version 1.23. Für das heutige Go ist die GC-Leistung längst kein Problem mehr. Die GC-Latenz liegt in den meisten Fällen unter 100 Mikrosekunden und erfüllt die Anforderungen der meisten Anwendungsszenarien.

Zusammenfassend lässt sich Go's Garbage Collection in folgende Phasen unterteilen:

• Scan-Phase: Sammeln von Wurzelobjekten aus Stack und globalen Variablen
• Markierungs-Phase: Einfärben der Objekte
• Markierungs-Abschluss-Phase: Aufräumarbeiten, Deaktivieren der Barrieren
• Freigabe-Phase: Freigeben und Recyceln des Speichers von Garbage-Objekten

Konzepte

In der offiziellen Dokumentation und Artikeln können folgende Begriffe auftreten:

• Mutator: Ein technischer Begriff, der sich auf das Benutzerprogramm bezieht. In Go ist dies der Benutzercode
• Collector: Bezeichnet das für Garbage Collection verantwortliche Programm. In Go ist dies die Runtime
• Finalizer: Bezeichnet den Code, der nach Abschluss der Markierungs- und Scan-Arbeit für das Freigeben und Bereinigen des Objektspeichers verantwortlich ist
• Controller: Bezeichnet die globale Variable runtime.gcController vom Typ gcControllerState, die den Pacing-Algorithmus implementiert und bestimmt, wann Garbage Collection durchgeführt wird und wie viel Arbeit ausgeführt wird
• Limiter: Bezeichnet runtime.gcCPULimiter, der verhindert, dass Garbage Collection zu viel CPU beansprucht und das Benutzerprogramm beeinträchtigt

Auslösung

func gcStart(trigger gcTrigger)

Garbage Collection wird durch die Funktion runtime.gcStart gestartet. Sie empfängt nur eine Struktur runtime.gcTrigger, die den Grund für die GC-Auslösung, die aktuelle Zeit und die GC-Runde enthält.

type gcTrigger struct {
    kind gcTriggerKind
    now  int64  // gcTriggerTime: current time
    n    uint32 // gcTriggerCycle: cycle number to start
}

gcTriggerKind hat folgende mögliche Werte:

const (
  // gcTriggerHeap indicates that a cycle should be started when
  // the heap size reaches the trigger heap size computed by the
  // controller.
  gcTriggerHeap gcTriggerKind = iota

  // gcTriggerTime indicates that a cycle should be started when
  // it's been more than forcegcperiod nanoseconds since the
  // previous GC cycle.
  gcTriggerTime

  // gcTriggerCycle indicates that a cycle should be started if
  // we have not yet started cycle number gcTrigger.n (relative
  // to work.cycles).
  gcTriggerCycle
)

Insgesamt gibt es drei Auslösezeiten für Garbage Collection:

• Bei der Erstellung neuer Objekte: Wenn runtime.mallocgc Speicher zuweist und erkennt, dass der Heap-Speicher den Schwellenwert erreicht hat (normalerweise das Doppelte der letzten GC, dieser Wert wird auch vom Pacing-Algorithmus angepasst), wird Garbage Collection gestartet

  func mallocgc(size uintptr, typ *_type, needzero bool) unsafe.Pointer {
      ...
    if shouldhelpgc {
      if t := (gcTrigger{kind: gcTriggerHeap}); t.test() {
        gcStart(t)
      }
    }
      ...
  }

• Zeitgesteuerte Zwangsauslösung: Go startet zur Laufzeit eine eigene Goroutine, um die Funktion runtime.forcegchelper auszuführen. Wenn lange keine Garbage Collection durchgeführt wurde, wird GC zwangsweise gestartet. Dieser Zeitraum wird durch die Konstante runtime.forcegcperiod bestimmt, deren Wert 2 Minuten beträgt. Auch in der System-Monitoring-Goroutine wird regelmäßig geprüft, ob eine Zwangs-GC erforderlich ist

  func forcegchelper() {
    for {
          ...
      gcStart(gcTrigger{kind: gcTriggerTime, now: nanotime()})
          ...
    }
  }

  func sysmon() {
      ...
    for {
          ...
      // check if we need to force a GC
      if t := (gcTrigger{kind: gcTriggerTime, now: now}); t.test() && forcegc.idle.Load() {
        lock(&forcegc.lock)
        forcegc.idle.Store(false)
        var list gList
        list.push(forcegc.g)
        injectglist(&list)
        unlock(&forcegc.lock)
      }
    }
  }

• Manuelle Auslösung: Über die Funktion runtime.GC können Benutzer Garbage Collection manuell auslösen

  func GC() {
      ...
    n := work.cycles.Load()
    gcStart(gcTrigger{kind: gcTriggerCycle, n: n + 1})
      ...
  }

TIP

Interessierte können Go Gc Pacer Re-Design lesen, um mehr über das Design und die Verbesserungen des Pacing-Algorithmus zur GC-Auslösung zu erfahren. Da der Inhalt komplex ist und viele mathematische Formeln enthält, wird er im Haupttext nicht näher erläutert.

Markierung

Heute ist Go's GC-Algorithmus immer noch ein Mark-and-Sweep-Verfahren, aber die Implementierung ist nicht mehr so einfach wie früher.

Mark-and-Sweep

Beginnen wir mit dem einfachsten Mark-and-Sweep-Algorithmus. Im Speicher bilden die Referenzbeziehungen zwischen Objekten einen Graphen. Die Garbage Collection arbeitet auf diesem Graphen in zwei Phasen:

• Markierungs-Phase: Beginnend von den Wurzelknoten (normalerweise Variablen auf dem Stack, globale Variablen und andere aktive Objekte) wird jeder erreichbare Knoten durchlaufen und als aktives Objekt markiert, bis alle erreichbaren Knoten durchlaufen wurden
• Freigabe-Phase: Alle Objekte im Heap werden durchlaufen, nicht markierte Objekte werden freigegeben und ihr Speicherplatz wird freigegeben oder wiederverwendet

Während der Freigabe darf sich die Struktur des Objektgraphen nicht ändern, daher muss das gesamte Programm angehalten werden (STW). Erst nach Abschluss der Freigabe kann es weiterlaufen. Der Nachteil dieses Algorithmus ist die lange Dauer, die die Ausführungseffizienz des Programms beeinträchtigt. Dies war der Markierungsalgorithmus der frühen Go-Versionen mit offensichtlichen Nachteilen:

• Erzeugt Speicherfragmente (aufgrund von Go's TCMalloc-ähnlicher Speicherverwaltung ist die Auswirkung von Fragmenten nicht gravierend)
• Scannt in der Markierungs-Phase alle Objekte im Heap
• Verursacht STW, das das gesamte Programm anhält, für eine nicht unerhebliche Zeit

Dreifarbige Markierung

Um die Effizienz zu verbessern, verwendete Go den klassischen dreifarbigen Markierungsalgorithmus. Die drei Farben sind Schwarz, Grau und Weiß:

• Schwarz: Das Objekt wurde während der Markierung besucht und alle direkt referenzierten Objekte wurden ebenfalls besucht, stellt ein aktives Objekt dar
• Grau: Das Objekt wurde während der Markierung besucht, aber nicht alle direkt referenzierten Objekte wurden besucht. Wenn alle besucht wurden, wechselt es zu Schwarz, stellt ein aktives Objekt dar
• Weiß: Das Objekt wurde während der Markierung nie besucht. Nach dem Besuch wechselt es zu Grau, stellt ein möglicherweise zu entsorgendes Objekt dar

Zu Beginn der dreifarbigen Markierung gibt es nur graue und weiße Objekte. Alle Wurzelobjekte sind grau, alle anderen Objekte sind weiß:

Zu Beginn jeder Markierungsrunde wird zuerst das graue Objekt markiert, es wird schwarz markiert als aktives Objekt. Dann werden alle direkt referenzierten Objekte des schwarzen Objekts grau markiert. Übrig bleiben weiße Objekte. Jetzt gibt es alle drei Farben:

Dieser Vorgang wird wiederholt, bis nur noch schwarze und weiße Objekte übrig sind. Wenn die Menge der grauen Objekte leer ist, ist die Markierung beendet:

Nach Abschluss der Markierung wird in der Freigabe-Phase einfach der Speicher der Objekte in der weißen Menge freigegeben.

Invariante

Die dreifarbige Markierung selbst kann nicht nebenläufig markieren (d.h. das Programm läuft während der Markierung). Wenn sich die Struktur des Objektgraphen während der Markierung ändert, können zwei Situationen auftreten:

• Übermarkierung: Nachdem ein Objekt schwarz markiert wurde, löscht das Benutzerprogramm alle Referenzen auf dieses Objekt. Es sollte also weiß sein und freigegeben werden
• Untermarkierung: Nachdem ein Objekt weiß markiert wurde, referenziert ein anderes Objekt im Benutzerprogramm dieses Objekt. Es sollte also schwarz sein und nicht freigegeben werden

Der erste Fall ist akzeptabel, da nicht bereinigte Objekte in der nächsten Runde verarbeitet werden können. Der zweite Fall ist jedoch inakzeptabel: Der Speicher eines noch verwendeten Objekts wird fälschlicherweise freigegeben, was zu schwerwiegenden Programmfehlern führt. Dies muss unbedingt vermieden werden.

Das Konzept der dreifarbigen Invariante stammt aus der 1998 von Pekka P. Pirinen veröffentlichten Arbeit Barrier techniques for incremental tracing. Es bezeichnet zwei Invarianten der Objektfarben bei nebenläufiger Markierung:

• Starke dreifarbige Invariante: Ein schwarzes Objekt kann nicht direkt ein weißes Objekt referenzieren
• Schwache dreifarbige Invariante: Wenn ein schwarzes Objekt direkt ein weißes Objekt referenziert, muss ein anderes graues Objekt dieses weiße Objekt direkt oder indirekt erreichen können (man sagt, es steht unter dem Schutz des grauen Objekts)

Für die starke dreifarbige Invariante: Angenommen, das schwarze Objekt 3 ist bereits besucht und alle seine Unterobjekte sind ebenfalls besucht und grau markiert. Wenn das Benutzerprogramm nun nebenläufig dem schwarzen Objekt 3 eine neue Referenz auf das weiße Objekt 7 hinzufügt, sollte das weiße Objekt 7 eigentlich grau markiert werden. Da das schwarze Objekt 3 aber bereits besucht wurde, wird Objekt 7 nicht besucht und bleibt immer weiß, um schließlich fälschlicherweise bereinigt zu werden.

Für die schwache dreifarbige Invariante gilt im Prinzip dasselbe wie für die starke. Da ein graues Objekt das weiße Objekt direkt oder indirekt erreichen kann, wird es schließlich während des Markierungsprozesses grau markiert und vermeidet so die fälschliche Bereinigung.

Durch die Invariante wird sichergestellt, dass während der Markierung kein Objekt fälschlicherweise bereinigt wird, was die Korrektheit der Markierungsarbeit unter Nebenläufigkeitsbedingungen garantiert. So kann die dreifarbige Markierung nebenläufig arbeiten, was die Markierungseffizienz im Vergleich zum Mark-and-Sweep-Algorithmus erheblich verbessert. Der Schlüssel zur Gewährleistung der dreifarbigen Invariante unter Nebenläufigkeit liegt in der Barriere-Technik.

Markierungsarbeit

In der GC-Scan-Phase gibt es eine globale Variable runtime.gcphase zur Darstellung des GC-Status mit folgenden möglichen Werten:

• _GCoff: Markierungsarbeit noch nicht begonnen
• _GCmark: Markierungsarbeit hat begonnen
• _GCmarktermination: Markierungsarbeit wird beendet

Wenn die Markierungsarbeit beginnt, ist der Status von runtime.gcphase _GCmark. Die Markierungsarbeit wird von der Funktion runtime.gcDrain ausgeführt, wobei der Parameter runtime.gcWork ein Puffer-Pool ist, der zu verfolgende Objektzeiger enthält.

func gcDrain(gcw *gcWork, flags gcDrainFlags)

Bei der Arbeit versucht sie, verfolgbare Zeiger aus dem Puffer-Pool zu holen. Wenn welche vorhanden sind, wird die Funktion runtime.scanobject aufgerufen, um die Scanning-Aufgabe fortzusetzen. Ihre Aufgabe ist es, Objekte im Puffer kontinuierlich zu scannen und sie schwarz zu färben.

if work.full == 0 {
    gcw.balance()
}

b := gcw.tryGetFast()
if b == 0 {
    b = gcw.tryGet()
    if b == 0 {
        // Flush the write barrier
        // buffer; this may create
        // more work.
        wbBufFlush()
        b = gcw.tryGet()
    }
}
if b == 0 {
    // Unable to get work.
    break
}
scanobject(b, gcw)

Die Scanning-Arbeit stoppt nur, wenn P präemptiert wird oder ein STW eintritt:

for !(gp.preempt && (preemptible || sched.gcwaiting.Load() || pp.runSafePointFn != 0)) {
  ...
  scanobject(b, gcw)
  ...
}

runtime.gcwork ist eine Warteschlange nach dem Producer/Consumer-Modell. Diese Warteschlange speichert zu scannende graue Objekte. Jeder Prozessor P hat lokal eine solche Warteschlange, entsprechend dem Feld runtime.p.gcw.

func scanobject(b uintptr, gcw *gcWork) {
  ...
  for {
    var addr uintptr
    if hbits, addr = hbits.nextFast(); addr == 0 {
            if hbits, addr = hbits.next(); addr == 0 {
                break
            }
        }
    scanSize = addr - b + goarch.PtrSize
    obj := *(*uintptr)(unsafe.Pointer(addr))
    if obj != 0 && obj-b >= n {
      if obj, span, objIndex := findObject(obj, b, addr-b); obj != 0 {
        greyobject(obj, b, addr-b, span, gcw, objIndex)
      }
    }
  }
  gcw.bytesMarked += uint64(n)
  gcw.heapScanWork += int64(scanSize)
}

Die Funktion runtime.scanobject markiert während des Scannens kontinuierlich erreichbare weiße Objekte als grau und fügt sie durch gcw.put in die lokale Warteschlange ein. Gleichzeitig versucht die Funktion gcDrain kontinuierlich über gcw.tryget, graue Objekte zu holen, um weiter zu scannen. Der Markierungs-Scan-Prozess ist inkrementell und muss nicht alle Markierungsarbeiten auf einmal erledigen. Wenn die Markierungsaufgabe aus bestimmten Gründen unterbrochen wird, kann sie nach der Wiederaufnahme anhand der verbleibenden grauen Objekte in der Warteschlange fortgesetzt werden.

Hintergrundmarkierung

Die Markierungsarbeit wird nicht sofort beim GC-Start ausgeführt. Beim Auslösen von GC erstellt Go Markierungsaufgaben in derselben Anzahl wie die aktuellen Prozessoren P. Sie werden zur globalen Aufgabenwarteschlange hinzugefügt und schlafen dann, bis sie in der Markierungsphase geweckt werden. Zur Laufzeit wird die Aufgabenzuweisung von runtime.gcBgMarkStartWorkers durchgeführt. Die Markierungsaufgabe ist eigentlich die Funktion runtime.gcBgMarkWorker, wobei die globalen Laufzeitvariablen gcBgMarkWorkerCount und gomaxprocs jeweils die aktuelle Anzahl der Worker und die Anzahl der Prozessoren P darstellen.

func gcBgMarkStartWorkers() {
  // Background marking is performed by per-P G's. Ensure that each P has
  // a background GC G.
  for gcBgMarkWorkerCount < gomaxprocs {
    go gcBgMarkWorker()

    notetsleepg(&work.bgMarkReady, -1)
    noteclear(&work.bgMarkReady)

    gcBgMarkWorkerCount++
  }
}

Nach dem Start des Workers erstellt er eine Struktur runtime.gcBgMarkWorkerNode, fügt sie zum globalen Worker-Pool runtime.gcBgMarkWorkerPool hinzu und ruft dann runtime.gopark auf, um die Goroutine schlafen zu legen:

func gcBgMarkWorker() {
    ...
  node := new(gcBgMarkWorkerNode)
  node.gp.set(gp)
  notewakeup(&work.bgMarkReady)

  for {
    gopark(func(g *g, nodep unsafe.Pointer) bool {
      node := (*gcBgMarkWorkerNode)(nodep)
      gcBgMarkWorkerPool.push(&node.node)
      return true
    }, unsafe.Pointer(node), waitReasonGCWorkerIdle, traceBlockSystemGoroutine, 0)
    }
    ...
}

Es gibt zwei Situationen, in denen ein Worker geweckt werden kann:

• In der Markierungsphase weckt der Scheduling-Loop über runtime.gcController.findRunnableGCWorker schlafende Worker
• In der Markierungsphase, wenn der Prozessor P gerade im Leerlauf ist, versucht der Scheduling-Loop, direkt aus dem globalen Worker-Pool gcBgMarkWorkerPool verfügbare Worker zu holen

Der Prozessor P hat ein Feld gcMarkWorkerMode im Struktur, das den Ausführungsmodus der Markierungsaufgabe angibt:

• gcMarkWorkerNotWorker: Der aktuelle Prozessor P führt keine Markierungsaufgabe aus
• gcMarkWorkerDedicatedMode: Der aktuelle Prozessor P ist ausschließlich für Markierungsaufgaben zuständig und wird während dieser Zeit nicht präemptiert
• gcMarkWorkerFractionalMode: Der aktuelle Prozessor führt Markierungsaufgaben aus, weil die GC-Auslastung nicht den Standard (25%) erreicht hat, und kann während der Ausführung präemptiert werden
• gcMarkWorkerIdleMode: Der aktuelle Prozessor führt Markierungsaufgaben aus, weil er im Leerlauf ist, und kann während der Ausführung präemptiert werden

Markierungshilfe

Die Goroutine G hat zur Laufzeit ein Feld gcAssistBytes, hier als GC-Hilfspunkte bezeichnet. Im GC-Markierungsstatus, wenn eine Goroutine versucht, Speicher einer bestimmten Größe anzufordern, werden ihr Punkte in Höhe der angeforderten Speichergröße abgezogen. Wenn die Punkte zu diesem Zeitpunkt negativ sind, muss die Goroutine eine bestimmte Menge an GC-Scanning-Aufgaben als Hilfe ausführen, um die Punkte zurückzuzahlen. Wenn die Punkte positiv sind, muss die Goroutine keine Hilfsmarkierungsaufgaben mehr ausführen.

Die Funktion zum Abziehen von Punkten ist runtime.deductAssistCredit, die vor der Speicherzuweisung in runtime.mallocgc aufgerufen wird.

func deductAssistCredit(size uintptr) *g {
    var assistG *g
    if gcBlackenEnabled != 0 {
       assistG = getg()
       if assistG.m.curg != nil {
          assistG = assistG.m.curg
       }
       assistG.gcAssistBytes -= int64(size)

       if assistG.gcAssistBytes < 0 {
          gcAssistAlloc(assistG)
       }
    }
    return assistG
}

Wenn die Goroutine eine bestimmte Menge an Hilfsscanning-Arbeit abgeschlossen hat, werden der aktuellen Goroutine Punkte zurückerstattet. Die tatsächlich für die Hilfsmarkierung verantwortliche Funktion ist runtime.gcDrainN.

func gcAssistAlloc1(gp *g, scanWork int64) {
    ...
  gcw := &getg().m.p.ptr().gcw
  workDone := gcDrainN(gcw, scanWork)
  ...
  assistBytesPerWork := gcController.assistBytesPerWork.Load()
  gp.gcAssistBytes += 1 + int64(assistBytesPerWork*float64(workDone))
    ...
}

Da das Scanning nebenläufig ist, gehört nur ein Teil der aufgezeichneten Arbeit zur aktuellen Goroutine. Die verbleibende Arbeit wird nacheinander an andere Goroutinen in der Hilfswarteschlange zurückerstattet. Wenn noch etwas übrig ist, wird es zu den globalen Punkten gcController.assistBytesPerWork hinzugefügt.

Markierungsabschluss

Wenn alle erreichbaren grauen Objekte schwarz gefärbt wurden, wechselt der Status von _GCmark zu _GCmarktermination. Dieser Prozess wird von der Funktion runtime.gcMarkDone durchgeführt. Zunächst prüft sie, ob noch Aufgaben auszuführen sind:

top:
  if !(gcphase == _GCmark && work.nwait == work.nproc && !gcMarkWorkAvailable(nil)) {
    return
  }

  gcMarkDoneFlushed = 0
  forEachP(waitReasonGCMarkTermination, func(pp *p) {
    wbBufFlush1(pp)
    pp.gcw.dispose()
    if pp.gcw.flushedWork {
      atomic.Xadd(&gcMarkDoneFlushed, 1)
      pp.gcw.flushedWork = false
    }
  })

  if gcMarkDoneFlushed != 0 {
    goto top
  }

Wenn keine globalen und lokalen Aufgaben mehr auszuführen sind, wird runtime.stopTheWorldWithSema für STW aufgerufen und Abschlussarbeiten durchgeführt:

atomic.Store(&gcBlackenEnabled, 0)
gcCPULimiter.startGCTransition(false, now)
gcWakeAllAssists()
schedEnableUser(true)
gcController.endCycle(now, int(gomaxprocs), work.userForced)
gcMarkTermination(stw)

Zuerst wird runtime.BlackenEnabled auf 0 gesetzt, was anzeigt, dass die Markierungsarbeit beendet ist. Dann wird der Limiter benachrichtigt, dass die Markierungshilfe beendet ist, die Speicherbarrieren werden deaktiviert, alle wegen Hilfsmarkierung schlafenden Goroutinen werden geweckt, alle Benutzer-Goroutinen werden wieder geweckt, und es werden verschiedene Daten dieser Scanning-Runde gesammelt, um den Pacing-Algorithmus für die nächste Runde anzupassen. Nach Abschluss der Abschlussarbeiten wird runtime.gcSweep aufgerufen, um Garbage-Objekte zu bereinigen, und schließlich wird runtime.startTheWorldWithSema aufgerufen, um das Programm wieder laufen zu lassen.

Barrieren

Die Funktion von Speicherbarrieren kann als Hook für die Zuweisung von Objekten verstanden werden. Vor der Zuweisung werden bestimmte Operationen ausgeführt. Dieser Hook-Code wird normalerweise während der Kompilierung vom Compiler in den Code eingefügt. Wie oben erwähnt, kann die dreifarbige Markierung unter Nebenläufigkeit beim Hinzufügen und Löschen von Objektreferenzen Probleme verursachen. Da beide Schreiboperationen sind (Löschen ist die Zuweisung eines Nullwerts), werden die Barrieren, die sie abfangen, zusammenfassend als Write-Barrier bezeichnet. Der Barrier-Mechanismus ist jedoch nicht kostenlos. Das Abfangen von Speicherschreiboperationen verursacht zusätzlichen Overhead, daher funktioniert der Barrier-Mechanismus nur auf dem Heap. Angesichts der Implementierungskomplexität und der Leistungseinbußen wird er nicht auf Stack und Register angewendet.

TIP

Um mehr über die Details der Barrier-Technik in Go zu erfahren, besuchen Sie Eliminate STW stack rescan.

Insert-Write-Barrier

Die Insert-Write-Barrier wurde von Dijkstra vorgeschlagen und erfüllt die starke dreifarbige Invariante. Wenn einem schwarzen Objekt eine neue Referenz auf ein weißes Objekt hinzugefügt wird, fängt die Insert-Write-Barrier diese Operation ab und markiert das weiße Objekt als grau. Dies vermeidet, dass ein schwarzes Objekt direkt ein weißes Objekt referenziert, und gewährleistet die starke dreifarbige Invariante.

Wie erwähnt, wird die Write-Barrier nicht auf dem Stack angewendet. Wenn sich während der nebenläufigen Markierung die Referenzbeziehungen von Stack-Objekten ändern, z.B. ein schwarzes Objekt im Stack ein weißes Objekt im Heap referenziert, muss zur Gewährleistung der Korrektheit der Stack-Objekte nach Abschluss der Markierung erneut eine Markierung durchgeführt werden. In der zweiten Markierung muss STW durchgeführt werden. Wenn Hunderte von Goroutine-Stacks gleichzeitig existieren, ist die Dauer dieses Scanning-Prozesses nicht zu vernachlässigen. Nach offiziellen Statistiken dauert das erneute Scannen etwa 10-100 Millisekunden.

Vorteile: Kein STW während des Scannens Nachteile: Zweimaliges Scannen des Stack-Bereichs zur Gewährleistung der Korrektheit, STW erforderlich

Delete-Write-Barrier

Die Delete-Write-Barrier wurde von Yuasa vorgeschlagen, auch bekannt als Snapshot-at-the-Beginning-Barrier. Diese Methode erfordert zu Beginn STW, um eine Momentaufnahme der Wurzelobjekte zu erstellen, und markiert alle Wurzelobjekte schwarz und alle direkten Unterobjekte grau. Somit stehen alle übrigen weißen Unterobjekte unter dem Schutz der grauen Objekte. Das Go-Team hat die Delete-Write-Barrier nicht direkt angewendet, sondern sich dafür entschieden, sie mit der Insert-Write-Barrier zu kombinieren.

Vorteile: Da alle Stack-Objekte schwarz sind, muss der Stack-Bereich nicht zweimal gescannt werden Nachteile: Zu Beginn des Scannens ist STW erforderlich, um eine Momentaufnahme der Wurzelobjekte im Stack-Bereich zu erstellen

Hybrid-Write-Barrier

In Go 1.8 wurde ein neuer Barrier-Mechanismus eingeführt: die Hybrid-Write-Barrier, eine Kombination aus Insert-Write-Barrier und Delete-Write-Barrier, die die Vorteile beider vereint:

• Insert-Write-Barrier erfordert zu Beginn kein STW für die Momentaufnahme
• Delete-Write-Barrier erfordert kein STW für das zweimalige Scannen des Stack-Bereichs

Hier ist der offizielle Pseudocode:

writePointer(slot, ptr):
    shade(*slot)
    if current stack is grey:
        shade(ptr)
    *slot = ptr

Offiziell zusammengefasst: Wenn die Hybrid-Write-Barrier eine Schreiboperation abfängt, wird das ursprüngliche Objekt grau markiert. Wenn der aktuelle Goroutine-Stack noch nicht gescannt wurde, wird auch das neue Objekt grau markiert.

Wenn die Markierungsarbeit beginnt, muss der Stack-Bereich gescannt werden, um Wurzelobjekte zu sammeln. Dabei werden sie direkt alle schwarz markiert. Während dieser Zeit werden auch alle neu erstellten Objekte schwarz markiert, um sicherzustellen, dass alle Objekte im Stack schwarz sind. Wenn der Goroutine-Stack vollständig schwarz ist, ist die starke dreifarbige Invariante erfüllt. Nach Abschluss des Scannens muss der Stack-Bereich nicht erneut gescannt werden, was STW-Zeit spart.

Seit Go 1.8 hat Go den grundlegenden Rahmen für Garbage Collection festgelegt. Nachfolgende Verbesserungen basieren auf der Hybrid-Write-Barrier. Da der Großteil des STW eliminiert wurde, liegt die durchschnittliche GC-Latenz jetzt im Mikrosekundenbereich.

Freigabe

In der Garbage Collection ist der wichtigste Teil das Finden von Garbage-Objekten, also das Scannen und Markieren. Nach Abschluss der Markierung ist die Freigabe relativ einfach: Sie muss nur nicht markierte Objekte freigeben. Go's Freigabe-Algorithmus ist in zwei Arten unterteilt:

Objektfreigabe

Die Objektfreigabe erfolgt in der Markierungs-Abschluss-Phase durch runtime.sweepone. Der Prozess ist asynchron. Bei der Bereinigung versucht sie, nicht markierte Objekte in Speichereinheiten zu finden und freizugeben. Wenn eine gesamte Speichereinheit nicht markiert ist, wird die gesamte Einheit freigegeben.

Einheitenfreigabe

Die Einheitenfreigabe erfolgt vor der Speicherzuweisung durch die Methode runtime.mheap.reclaim. Sie sucht im Heap nach Speichereinheiten, in denen alle Objekte nicht markiert sind, und gibt die gesamte Einheit frei.

Für Speichereinheiten gibt es ein Feld sweepgen, das den Freigabestatus angibt:

• mspan.sweepgen == mheap.sweepgen - 2: Diese Speichereinheit muss freigegeben werden
• mspan.sweepgen == mheap.sweepgen - 1: Diese Speichereinheit wird gerade freigegeben
• mspan.sweepgen == mheap.sweepgen: Diese Speichereinheit wurde bereits freigegeben und kann normal verwendet werden
• mspan.sweepgen == mheap.sweepgen + 1: Speichereinheit ist im Cache und muss freigegeben werden
• mspan.sweepgen == mheap.sweepgen + 3: Speichereinheit wurde bereits freigegeben, ist aber noch im Cache

mheap.sweepgen erhöht sich mit jeder GC-Runde, und jedes Mal um +2.