Tri-color marking

Beyaz, gri, siyah renkli işaretleme algoritmasını öğrenirsin.

Üç renkli işaretleme

Go GC'si nesneleri üç renge ayırır: beyaz (henüz görülmedi, toplanma adayı), gri (görüldü ama referansları taranmadı), siyah (görüldü ve tüm referansları tarandı). İşaretleme köklerden başlar:

1. Kökler gri olur
2. Gri nesneyi al → referanslarını gri yap → kendisini siyah yap
3. Gri kalmayınca dur
4. Beyaz kalan her şey çöptür → süpür

Sonuçta siyahlar yaşar, beyazlar silinir.

Değişmez kural

Program işaretleme sürerken de çalıştığı için bir kurala uyulmalıdır: siyah nesne asla beyaz nesneyi doğrudan göstermemelidir. Aksi halde GC siyahı tekrar taramadığı için beyaz nesne yaşıyor olduğu hâlde silinirdi. Bu kuralı yazma bariyeri (write barrier) korur.

Uygulama İşaretleme benzetimi

Bir grafı map[string][]string ile tanımla: "kok": {"a"}, "a": {"b"}, "c": {"b"}. Kökten başlayıp bir gri kuyruğuyla erişilebilir düğümleri işaretle ve siyah düğüm sayısını yazdır (c çöptür).

Örnek çözümü göster

package main

import "fmt"

func main() {
    graf := map[string][]string{"kok": {"a"}, "a": {"b"}, "c": {"b"}}
    siyah := map[string]bool{}
    gri := []string{"kok"}
    for len(gri) > 0 {
        n := gri[0]
        gri = gri[1:]
        if siyah[n] {
            continue
        }
        siyah[n] = true
        gri = append(gri, graf[n]...)
    }
    fmt.Println(len(siyah))
}

Kendini test et

İşaretleme bittiğinde gri nesne kalabilir mi?
- Hayır; işaretleme gri kalmayınca biter
- Evet, sonraki döngüye kalır
- Evet, gri nesneler silinir
- Yalnızca büyük nesneler
Cevabı göster

Hayır; işaretleme gri kalmayınca biter — Gri, "işi bitmemiş" demektir; bitiş koşulu tüm erişilebilir nesnelerin siyaha dönmesidir.

Taranmamış renk

const (
    white = iota
    ____
    black
)

Cevabı göster

const (
    white = iota
    grey
    black
)

Renk ve anlamı

Beyaz

Görülmedi, çöp adayı
Gri

Görüldü, taranacak
Siyah

Tarandı, yaşıyor
Süpürme

Beyazları serbest bırakır

Sıradaki ders: Concurrent GC

Deneyiminizi Geliştiriyoruz

Çerez Tercihleri

Kesinlikle Gerekli Çerezler

Analitik Çerezler