Che cos’è e come funziona il Garbage Collector (GC) in informatica

Il garbage collector (GC) è una funzionalità introdotta in diversi linguaggi di sviluppo allo scopo di sollevare il programmatore dal compito di allocare e deallocare la memoria delle variabili in modo esplicito.
Nei linguaggi che non possiedono questa funzionalità, come il C o il C++, è lo sviluppatore che ha il compito di allocare memoria quando crea delle variabili e deallocarla quando non sono più necessarie. Con questo processo manuale è facile incorrere in errori di programmazione a per cui delle porzioni di memoria, che di fatto possono essere riutilizzate, rimangono invece allocate. Questi errori sono chiamati memory leaks.

Il GC, quindi, ha il compito di individuare le locazioni di memoria appartenenti a variabili create, ma che non sono più necessarie, per deallocarle. Per effettuare questa operazione sono state sviluppate negli anni diverse tecniche utili all’individuazione delle variabili dette morte. Una variabile viene considerata morta quando non è più referenziata da qualche altra variabile.

Le tecniche di più famose sono:

1. mark and sweep: ogni oggetto in memoria ha un flag che rappresenta il suo stato (in uso o no). L’algoritmo partendo dalle variabili del root set comincia a marcare come in uso tutte le variabili raggiungibili tramite riferimenti da esso. Alla fine del primo step ripercorre tutta la memoria per eliminare quelle che risultano non più necessarie. Uno dei problemi di questa tecnica
   è rappresentato dal fatto che per portare a termine il processo è necessario percorrere l’intera memoria minimo due volte.
2. tri-color marking: è una variante del mark and sweep nella quale viene aggiunto uno stato oltre ai due già esistenti che rappresenta gli oggetti che non possiedono riferimenti ad altri oggetti. Viene chiamata tri-colour perchè si considerano come neri gli oggetti in uso, grigi quelli appartenenti al nuovo stato e bianchi quelli da eliminare. In questo modo è possibile, una volta settati tutti i flag, evitare di analizzare l’intera memoria partendo prima dagli oggetti di colore grigio e poi se necessario procedere con quelli neri che fanno riferimento ad essi.
3. reference counting: durante la creazione di oggetti e la loro distruzione si tiene traccia del numero di riferimenti a cui sono associati. Quando il numero raggiunge zero possono venire eliminati. Il vantaggio di questa tecnica è che riduce il tempo di analisi della memoria per`o, come contro, è necessaria un maggior quantitativo di memoria e istruzioni macchina per tenere aggiornato il contatore durante l’esecuzione.

Le implementazioni attuali dei GC utilizzano versioni modificate o ibride per migliorare le prestazioni della fase di individuazione delle locazioni di memoria da liberare.
Lo step successivo consiste nel rendere disponibili le celle di memoria non più utili e, nel caso sia previsto, riorganizzare la memoria per contenere le variabili vive. A questo scopo vengono utilizzate alcune metodologie differenti:

1. semi-spaces: vengono usati due spazi di memoria nella heap di uguali dimensioni. Le variabili vengono create in uno spazio; quando questo è pieno, dopo aver definito gli oggetti vivi, li copia nell’altra area di memoria. Una volta finito il processo vengono scambiati i ruoli dei due spazi della heap. Il tempo di esecuzione è proporzionale al numero degli oggetti vivi e quindi diventa molto pesante nel caso di molte variabili con vita lunga.
2. free-list: viene mantenuta una lista contenente le locazioni di memoria che sono state liberate perchè precedentemente occupate da oggetti morti. Con questa tecnica non avviene un compattamento della memoria in cui vengono salvati gli oggetti sopravvissuti con conseguente rischio di frammentazione.
3. generational: vengono create due aree di memoria di dimensioni differenti, una per l’immagazzinamento delle variabili dette young e l’altra per le variabili old. Quando un oggetto viene creato è allocato nell’area di memoria young e se sopravvive a una o più garbage collection viene spostato nell’area tenuered. Dopo di che verrà analizzata più frequentemente l’area young rispetto quella tenuered con conseguente risparmio di risorse; solo dopo che lo spazio per le variabili old sarà pieno verrà effettuata una garbage collection sull’intera heap. Questa tecnica si basa sull’ipotesi che normalmente nei programmi gli oggetti si dividono in due categorie: giovani che muoiono presto e vecchi che sopravvivono a lungo (alta mortalità infantile).

Quasi la totalità dei GC che sono stati implementati fino ad ora utilizzano una o più delle tecniche presentate, eventualmente modificate, per cercare di sfruttare i vantaggi di una riducendone gli svantaggi.