Distinguishing pointers and data on the heap is the first problem any garbage collector needs to solve. The GC needs to follow pointers in order to discover live objects.
In generale, ci sono due approcci per identificare riferimenti e non riferimenti:
-
Metadati che ti dice se una variabile è una variabile di riferimento o altrimenti. Questi metadati ti diranno anche dove si trova la variabile, sia in un registro per una certa durata, sia in una posizione di memoria. Tali metadati vengono generati durante la generazione del codice. In generale, il codice generato verrà reso consapevole della necessità di questi metadati, e questo può avere alcuni effetti minori sul registro e sulle scelte di posizione della memoria, in modo che i metadati non siano eccessivamente complessi. Tuttavia, tutte le informazioni che l'identificatore delle radici degli oggetti ha bisogno di sapere è se ogni posizione di memoria è un puntatore o meno, ovunque sia sospeso un metodo (ad es. Nei siti di chiamata, sospensione nello stack).
-
Indovinare, che si ottiene osservando i valori per vedere se potrebbero trovarsi nell'intervallo dell'heap garbage collocato. Un tale approccio, per essere corretto, deve essere prudente, quindi assumere determinati valori come indicatori, anche se potrebbero non esserlo. Un tale approccio potrebbe essere trovato negli approcci alla garbage collection per C / C ++ (sì, esistono!) Dove il compilatore non è noto per aiutare, e dobbiamo preoccuparci dei numeri interi che contengono puntatori. Questo probabilmente non verrebbe utilizzato per altri linguaggi che sono più progettati per supportare l'approccio dei metadati. (Si noti inoltre che l'ipotesi impedisce la compattazione poiché non possiamo rischiare di modificare interi che assomigliano a dei puntatori.)
As long as we can identify what class an object comes from, we can find all of its pointers.
Nei runtime raccolti da garbage, spesso scopriremo che il modello di oggetto prescrive che il primo slot dell'oggetto sia un puntatore vtable o un altro riferimento di classe. Tale riferimento è fondamentalmente nascosto all'utente, anche se utilizzato per eseguire cast, chiamate di metodi virtuali, trovare interfacce e individuare riferimenti all'interno dell'oggetto.
The garbage collector works in two phases: the mark phase, and the sweep phase. In the mark phase, the garbage collector starts walks object references in order to find objects that are still reachable. The garbage collector starts at a few basic places where the object references are stored and given names (the stack, and global storage, and static storage), and then traverses references in the objects.
Alcuni riferimenti sono visti come radici dal vivo, quindi tutto ciò che queste radici raggiungono (o potrebbero raggiungere) è vivo e dovrebbe essere considerato dal vivo e quindi non essere raccolto. Le radici costituiscono tutti i thread (vale a dire i loro stack, le attivazioni aka, ovvero i frame stack) e anche tutte le variabili statiche / globali. I metadati che stiamo analizzando in precedenza descrivono i frame dello stack e le variabili statiche / globali.
I don't see how you can traverse objects, and know that it is ready to be garbage collected or not. Any tips on understanding that part would be of help
Non lo facciamo: qualsiasi oggetto attraversato è necessariamente considerato dal vivo. Il trucco è quindi identificare gli oggetti che non sono attraversati dall'ultimo traversal che inizia da queste radici. Pertanto, gli oggetti sono etichettati come vivi o sconosciuti / morti. (Durante l'attraversamento abbiamo live vs. non visitato, e post traversal abbiamo live vs dead.) A volte il bit per questo tag viene rubato dal puntatore vtable o class nel primo slot, poiché ci sono bit (generalmente parlando) che dovrebbe sempre essere zero al LSB di tali puntatori (i puntatori devono quindi essere usati con maggiore attenzione). Durante la traccia, gli oggetti che sono noti per essere raggiungibili sono contrassegnati come tali, mentre gli oggetti che non sono rimasti non modificati.
Potresti pensare che tutti gli oggetti dovrebbero prima essere contrassegnati come irraggiungibili, al fine di identificare quelli che non sono raggiunti, e tuttavia la maggior parte degli algoritmi GC non richiama questa inizializzazione, anche se questo è dovuto al fatto che c'è un trucco che può essere usato per invertire il senso di questo bit live / sconosciuto su ogni attraversamento della raccolta GC: quindi i nodi visitati sono contrassegnati con "1" su una raccolta GC (e quelli contrassegnati con "0" vengono raccolti come garbage) mentre su alla prossima raccolta, usiamo "0" per segnare quelli raggiungibili, e quelli non raggiungibili tengono ancora "1" dalla raccolta precedente.
Da questo si può vedere che è necessario essere in grado di trovare gli oggetti non controllati rimanenti, operazione che può essere eseguita attraversando l'heap in ordine di memoria, dato che in genere i modelli oggetto prescrivono che ogni oggetto ha un riferimento vtable o un puntatore di classe nel primo slot, così puoi facilmente dire quanto è grande l'oggetto e quindi dove si trova l'oggetto successivo sequenzialmente nell'heap gc.
Anche nel caso in cui i metadati identificano le radici, usate come inizio di oggetti vivi (attraversamento), queste radici potrebbero essere conservative nel senso che alcune radici potrebbero non essere effettivamente utilizzate in seguito. Quindi, mentre in un approccio orientato ai metadati sappiamo con certezza se una variabile è un riferimento o meno, non sappiamo in realtà se la variabile verrà o meno utilizzata successivamente nell'algoritmo del codice (cioè i thread). In questo senso c'è un certo conservatorismo in questo approccio. Alcuni approcci di compilatore / ottimizzazione (ad esempio incorporati nei metadati) possono ridurre la finestra della vivacità potenziale, in modo tale che anche se alcune variabili possono ancora contenere un riferimento è noto che non devono essere utilizzate, ad esempio, dopo l'ultimo utilizzo della variabile anche se il suo spazio di archiviazione contiene ancora un riferimento.
