Tri-color marking
- Go kursu
- Uzman
- Ders 8/34
- 4 dk
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ürSonuç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).
Başlangıç kodu
package main
import "fmt"
func main() {
// buraya yaz
}Örnek çözüm
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))
}Beklenen çıktı
3
Soru ve cevaplar
Dersin sorularını cevaplarıyla birlikte inceleyebilirsin. Kendini denemek istersen dersi interaktif olarak çöz.
1 İşaretleme bittiğinde gri nesne kalabilir mi?
- Hayır; işaretleme gri kalmayınca biter Doğru cevap
- Evet, sonraki döngüye kalır
- Evet, gri nesneler silinir
- Yalnızca büyük nesneler
Açıklama: Gri, "işi bitmemiş" demektir; bitiş koşulu tüm erişilebilir nesnelerin siyaha dönmesidir.
2 Taranmamış renk
const (
white = iota
____
black
)const (
white = iota
grey
black
)Açıklama: Gri nesneler iş kuyruğundadır; taranınca siyaha döner.
3 Renk ve anlamı
| Kavram | Anlamı |
|---|---|
Beyaz |
Görülmedi, çöp adayı |
Gri |
Görüldü, taranacak |
Siyah |
Tarandı, yaşıyor |
Süpürme |
Beyazları serbest bırakır |