In informatica per garbage collection (GC, ) si intende una modalità automatica di gestione della memoria, mediante la quale un sistema operativo, o un compilatore e un modulo di run-time liberano porzioni di memoria non più utilizzate dalle applicazioni. In altre parole, il garbage collector annoterà le aree di memoria non più referenziate, cioè allocate da un processo attivo, e le libererà automaticamente. La garbage collection è stata inventata nel 1959 da John McCarthy per il linguaggio di programmazione Lisp.
Questo meccanismo ha provocato un notevole cambio nello stile di programmazione dei linguaggi che lo implementano. Infatti non è più necessario richiedere esplicitamente la liberazione della memoria utilizzata da un oggetto, ovvero terminare tale oggetto in modo deterministico, ma si lascia che il sistema esegua questa operazione automaticamente, nel momento in cui lo riterrà più opportuno al fine di migliorare le prestazioni complessive. Tale azione viene definita nell'ambito delle finalizzazioni non deterministiche.
Descrizione Per la gestione della memoria si tiene conto di due principi fondamentali: Trovare gli oggetti precedentemente creati da un programma ai quali non sarà più necessario accedere; Recuperare le risorse utilizzate da questi oggetti.
Attuando il processo di garbage collection, l'ambiente nel quale viene eseguito il programma gestisce la memoria automaticamente, liberando il programmatore dalla necessità di prevedere quando rilasciare le risorse utilizzate da un oggetto non più necessario all'elaborazione. Tale modalità automatica migliora la stabilità dei programmi in quanto consente di evitare quella classe di bug connessi all'utilizzo di puntatori alle varie aree di memoria già liberate in passato.Tecnicamente chiamato il problema dei 'dangling pointers'.
Alcuni linguaggi di programmazione, come Java, Python e C# (.NET), hanno un sistema di garbage collection integrato direttamente nell'ambiente di esecuzione, mentre per altri linguaggi, come il C e il C++, la sua eventuale implementazione è a carico del programmatore. Tuttavia molti linguaggi di programmazione utilizzano una combinazione dei due approcci, come Ada, Modula-3 e CLI, consentendo all'utente di eliminare manualmente gli oggetti o, volendo velocizzare il processo, addirittura disattivare la gestione automatica del sistema GC. La garbage collection è quasi sempre strettamente integrata con l'allocazione di memoria.
Benefici La garbage collection esonera il programmatore dall'eseguire manualmente l'allocazione (richiesta) e la deallocazione (rilascio) di aree di memoria, riducendo o eliminando del tutto alcune categorie di bug:
Dangling pointers: persistenza nel programma di puntatori che si riferiscono ad aree di memoria che contenevano oggetti ormai deallocate. Utilizzare tali aree di memoria delocate può, nel migliore dei casi, provocare un errore fatale dell'applicazione, ma si possono manifestare altri problemi anche a distanza di tempo dalla effettiva deallocazione. La risoluzione di questi problemi può essere molto difficoltosa. Doppia deallocazione: il programma tenta di liberare nuovamente una zona di memoria già rilasciata. Alcuni tipi di memory leak: il programma perde traccia di alcune aree di memoria allocateAd esempio nel caso in cui il puntatore ad esse viene modificato., perdendo la possibilità di deallocarle nel momento in cui non servono più. Questo tipo di problema può accumularsi nel corso dell'esecuzione del programma, portando, nel corso del tempo, all'esaurimento della memoria disponibile.
La maggior parte degli errori di programmazione nei linguaggi che non prevedono la garbage collection, o quando la stessa venga volontariamente disattivata, rientrano nei casi sopra descritti.
Svantaggi La garbage collection presenta tuttavia anche alcuni svantaggi: Consumo di risorse di calcolo: il processo consuma risorse di calcolo, al fine sia di tenere traccia dell'utilizzo delle varie aree di memoria, sia di poter decidere il momento e la quantità di memoria da liberare; Incertezza del momento in cui viene effettuata la Garbage Collection: il momento in cui viene effettuata tale operazione non è prevedibile e questa incertezza può determinare improvvisi blocchi o ritardi nell'esecuzione. Problemi di questo genere sono inaccettabili in ambienti real-time, nel rilevamento di driver periferici e nell'elaborazione di transazioni; Rilascio della memoria non deterministico: analogamente, sia il momento in cui una data area di memoria viene rilasciata, sia l'ordine di rilascio delle varie aree non più utilizzate, dipendono dal particolare algoritmo implementato dal garbage collector. Si può dire che il rilascio di memoria avviene in modo non deterministico. Presenza di memory leak: i memory leak, perdita o fuoriuscita di memoria, possono comunque verificarsi, nonostante la presenza di un garbage collector. Ciò può accadere se il programma mantiene un riferimento ad oggetti che hanno esaurito il loro ciclo logico di vita nell'applicazione. La presenza di riferimenti attivi comporta l'impossibilità da parte del collector di rilevare l'area di memoria come non utilizzata. Questo può verificarsi, ad esempio, con collezioni di oggetti. Il monitoraggio del ciclo di vita degli oggetti è una responsabilità primaria dello sviluppatore in ambienti garbage-collected.
Tracing garbage collection Il metodo più comune per attuare la garbage collection è il metodo del tracciamento, in inglese: Tracing. Tale metodo consiste nel determinare in primo luogo quali oggetti sono raggiungibili (o potenzialmente tali), per poi successivamente scartare tutti quelli che non lo sono.
Raggiungibilità di un oggetto Siano e due oggetti, e sia un oggetto raggiungibile. Diremo che è raggiungibile in maniera ricorsiva se e solo se esiste un riferimento ad esso tramite l'oggetto (ovvero è raggiungibile attraverso un oggetto , a sua volta raggiungibile). Un oggetto può essere raggiungibile solo in due casi: Quando viene creato all'avvio del programma (oggetto globale) o di una sua sotto-procedura (oggetti di scope, creati sullo stack); l'oggetto in questione viene detto in tal caso radice; Quando un altro oggetto, raggiungibile, trattiene un riferimento ad esso; in modo più formale, la raggiungibilità è una chiusura transitiva.
L'identificazione delle aree di memoria spazzatura con quelle non raggiungibili non è ottimale, in quanto potrebbe accadere che un programma utilizzi per l'ultima volta una certa area molto prima che questa diventi irraggiungibile. A volte si distingue perciò fra spazzatura sintattica, quando l'oggetto non può essere raggiunto dal programma, e semantica, quando il programma non vuole più utilizzare l'oggetto. Ad esempio:
Object x = new Foo(); Object y = new Bar(); x = new Quux(); /* Da questo punto l'oggetto Foo, originariamente * assegnato ad x, non può più essere referenziato: * Foo è un oggetto spazzatura sintattico */
if(x.check_something()) { x.do_something(y); } System.exit(0); /* Nel blocco condizionale, y potrebbe essere spazzatura semantica, ma non * possiamo dirlo finché x.check_something() non termini restituendo un * valore; ciò sempre ammesso che effettivamente termini in un tempo finito */
Il problema di individuare precisamente la spazzatura semantica è purtroppo solo parzialmente decidibile: dall'esempio mostrato sopra, infatti, è chiaro che l'identificazione positiva di un oggetto come spazzatura semantica dipende dal fatto che le elaborazioni precedenti terminino correttamente in un tempo finito. Ciò comporta che un collector che volesse identificare la spazzatura semantica dovrebbe poter decidere, sempre in un tempo finito, se una certa procedura termini (problema della fermata). Pertanto, essenzialmente tutti i collector implementati si concentrano sulla spazzatura sintattica.
Algoritmo di base I tracing collector sono algoritmi dedicati, in quanto in grado di tracciare il set di lavoro della memoria, effettuando ciclicamente la raccolta degli oggetti non più necessari. Un ciclo viene avviato quando il garbage collector stabilisce di avere la necessità di recuperare memoria; ciò accade più frequentemente quando il sistema è in memoria bassa. Il metodo originale prevede un mark-and-sweepTrad.Ing.:"Marca e butta via" in cui il set di memoria viene più volte analizzato.
Naïve mark-and-sweep Nel mark-and-sweep ogni oggetto in memoria possiede un flag, in genere è sufficiente un bit, riservato esclusivamente per l'utilizzo del garbage collector. Quando l'oggetto viene creato, il flag viene posto in stato flag clearTrad.Ing.:"Non in uso".
Durante la prima fase, o fase di Mark, del ciclo di garbage collection, viene scansionato l'intero set di root, ponendo ogni oggetto in stato di flag set.Trad.Ing.:"In Uso" Tutti gli oggetti accessibili dalla radice del set sono anch'essi contrassegnati come in stato di flag set.
Nella seconda fase, o fase di sweep, ogni oggetto in memoria viene ancora una volta esaminato; quelli che hanno ancora il flag clear non sono raggiungibili da nessun programma o dato, e la loro memoria viene quindi liberata. Per gli oggetti che sono marcati flag set, il flag viene posto in stato flag clear, preparandoli per il prossimo ciclo di Garbage Collection.
Questo metodo ha diversi svantaggi, per esempio l'intero sistema viene sospeso durante la Garbage Collection in modo non sempre prevedibile e per periodi di tempo non determinabili a priori; questo tipo di comportamento può creare notevoli problemi in ambienti che necessitano di basse latenze di risposta o in sistemi real-time o mission critical, con possibili malfunzionamenti, deadlock e arresti che possono compromettere l'intero sistema. Inoltre, tutta la memoria di lavoro deve essere esaminata minimo due volte, causando potenzialmente problemi nei sistemi a memoria paginata.
Tri-colour marking A causa di questi svantaggi, gli algoritmi più moderni di garbage collection attuano delle varianti rispetto a semplici meccanismi, quali il mark-and-sweep, applicando algoritmi del tipo tri-colour marking. L'algoritmo effettua marcature su tre diversi livelli secondo le seguenti fasi:
Crea set di livelli di bianco, grigio e nero utilizzati per segnare i vari progressi effettuati durante il ciclo. Il set bianco è l'insieme di oggetti candidati al riciclo. Il set nero è l'insieme di oggetti privi di riferimenti in uscita a oggetti del set bianco, raggiungibili dalla radice. Gli oggetti del set nero non sono candidati per essere riciclati; in molte implementazioni, il set nero inizia come vuoto. Il set grigio contiene tutti gli oggetti raggiungibili dalla radice, ma che ancora devono essere sottoposti a scansione per controllare se hanno riferimenti in uscita agli oggetti "bianchi". Dal momento che sono noti per essere raggiungibile dalla radice, non possono essere riciclati e finiranno nel set nero dopo essere stati sottoposti a scansione. Il set grigio è inizializzato con gli oggetti direttamente riferiti dalla radice; in genere tutti gli altri oggetti sono inizialmente posizionati nel set bianco. Gli oggetti possono passare soltanto dal bianco al grigio e dal grigio al nero ma non in senso opposto. Raccoglie gli oggetti dal set di grigio e sposta questi nel set di nero (Blacken) se questi non possono essere garbage collected. Ripete i vari passaggi fino a quando il set di grigio diventa vuoto. Quando non vi sono più oggetti nel set di grigio, per tutti i rimanenti oggetti nel set bianco è stato dimostrato che non sono raggiungibili per cui lo spazio di memoria da essi occupato viene recuperato.