Garbage collection: differenze tra le versioni

Versione delle 23:10, 31 ago 2018

Versione delle 05:46, 29 ott 2018

Riga 4:

Nota: la voce non sembra essere stata ottenuta COMPLETAMENTE mediante traduzione automatica (vedi [[Teplate:Da correggere]])

-->

In [[informatica]] per '''garbage collection''' (termine a voltespesso abbreviato con '''GC''', letteralmente ''raccolta dei rifiuti'') si intende una modalità automatica di [[gestore della memoria|gestione della memoria]], mediante la quale un [[sistema operativo]], o un [[compilatore]] e un modulo di [[run-time]], liberano porzioni di [[memoria (informatica)|memoria]] non più utilizzate dalle [[applicazione (informatica)|applicazioni]]. In altre parole, il ''garbage collector'' annoterà le aree di memoria non più ''referenziate'', cioè allocate da un [[processo (informatica)|processo]] attivo, e le libererà automaticamente. La garbage collection è stata inventata nel 1959 da [[John McCarthy]] per il [[linguaggio di programmazione]] [[Lisp]]<ref>{{Cita web|url=http://portal.acm.org/citation.cfm?id=367177.367199 |titolo=Recursive functions of symbolic expressions and their computation by machine |editore=Portal.acm.org|lingua=en |data= |accesso=29 marzo 2009}}</ref><ref>{{Cita web|url=http://www-formal.stanford.edu/jmc/recursive.html|lingua=en|titolo=Recursive functions of symbolic expressions and their computation by machine, Part I|accesso=29 maggio 2009|urlmorto=sì|urlarchivio=https://web.archive.org/web/20131004215327/http://www-formal.stanford.edu/jmc/recursive.html|dataarchivio=4 ottobre 2013}}</ref>.

Questo meccanismo ha condotto ad un notevole cambio nello stile di [[Programmazione (informatica)|programmazione]] dei [[Linguaggio di programmazione|linguaggi]] che lo implementano. Infatti non è più necessario richiedere esplicitamente la liberazione della memoria utilizzata da un [[programmazione orientata agli oggetti|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''.

Riga 13:

# Recuperare le [[risorsa informatica|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 dati|elaborazione]]. Tale modalità automatica, migliora la stabilità dei programmi, in quanto consente di evitare quella classe di [[bug]] connessi alla necessità di manipolare direttamente, da parte del programmatore, i [[puntatore (programmazione)|puntatori]] alle varie aree di memoria che contenevano gli oggetti utilizzati durante l'[[esecuzione (informatica)|esecuzione]], ma già rilasciati per altri usi.<ref>Tecnicamente chiamato il problema dei '[[dangling pointer]]s'.</ref>

Alcuni [[linguaggio di programmazione|linguaggi di programmazione]], come [[Java (linguaggio di programmazione)|Java]], [[Python]] e [[C sharp|C#]] ([[.NET]]), hanno un sistema di ''garbage collection'' integrato direttamente nell'ambiente di esecuzione, mentre per altri linguaggi, come il [[C (linguaggio)|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 (linguaggio)|Ada]], [[Modula-3]] e [[Common Language Infrastructure|CLI]], consentono 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 dinamica della memoria|allocazione di memoria]].

=== Benefici ===

Riga 21:

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 bugs:

* ''[[Dangling pointer|'''Dangling pointers''']]'': persistenza nel programma di puntatori che si riferiscono ad aree di memoria che contenevano oggetti, ormai deallocate. Utilizzare tali aree di memoria deallocate 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]]s'':''' il programma perde traccia di alcune aree di memoria allocate<ref>Ad esempio nel caso in cui il puntatore ad esse viene modificato.</ref>, 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 ===

Riga 31:

La ''garbage collection'' presenta tuttavia anche alcuni svantaggi:

* '''Consumo di risorse di calcolo''' : il processo consuma risorse di calcolo, al fine sia diper tenere traccia dell'utilizzo delle varie aree di memoria, sia diper 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: questa incertezza può determinare improvvisi blocchi o ritardi nell'esecuzione. Problemi di questo genere sono inaccettabili in ambienti [[real-time]], nel rilevamento di [[driver|driver periferici]], e nell'[[transaction processing|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.<ref>{{cita pubblicazione |autore= Maebe Jonas |coautori= Ronsse Michiel, De Bosschere Koen|titolo=Precise detection of memory leaks|url=http://www.cs.virginia.edu/woda2004/papers/maebe.pdf|accesso=13 maggio 2010}}</ref> 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 "'''p"''' e "'''q"''' due oggetti, e sia q un oggetto raggiungibile. Diremo che p è raggiungibile in maniera ricorsiva, se e solo se esiste un riferimento ad esso tramite l'oggetto q (ovvero p è raggiungibile attraverso un oggetto q, 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:

Riga 73:

==== 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 clear''<ref name=":0">Trad.Ing.:"''Non in uso''"</ref>. Durante la prima fase, o '''fase di Mark''' del ciclo di Garbage Collection, viene scansionato l'intero set di [[Root (informatica)|root]], ponendo ogni oggetto in stato di ''flag set.''<ref name=":1">Trad.Ing.:"''In Uso''"</ref> Tutti gli oggetti accessibili dalla radice del set sono anch'essi contrassegnati come in stato di ''flag set''.<ref name=":1" /> Nella seconda fase, o '''fase di Sweep''', ogni oggetto in memoria viene ancora una volta esaminato;: quelli che hanno ancora il ''flag clear''<ref name=":0" /> non sono raggiungibili da nessun programma o dato, e la loro memoria viene quindi liberata.; Perper gli oggetti che sono marcati flag set, il flag viene posto in stato ''flag clear''<ref name=":0" />, preparandoli per il prossimo ciclo di Garbage Collection.

Questo metodo ha diversi svantaggi, per esempio, l'intero sistema viene sospeso durante la Garbage CollectioCollection 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 [[Latenza|latenze]] di risposta o in [[Real-time|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 virtuale|memoria paginata]].

==== Tri-colour marking ====

Riga 82:

# '''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.

Dal momento che tutti gli oggetti non immediatamente raggiungibili dalla radice sono tipicamente assegnati al set di bianco, e gli oggetti possono muoversi solo dal bianco al grigio e dal grigio al nero, l'algoritmo conserva un [[Invarianza|invariante]] importante - ''nessun oggetto nero punta direttamente ad un oggetto bianco''. Questo garantisce che gli oggetti bianchi possono essere distrutti in modo sicuro una volta che il set grigio è vuoto.

Dal momento che tutti gli oggetti non immediatamente raggiungibili dalla radice sono tipicamente assegnati al set di bianco, e gli oggetti possono muoversi solo dal bianco al grigio e dal grigio al nero, l'algoritmo conserva un [[Invarianza|invariante]] importante - ''nessun oggetto nero punta direttamente ad un oggetto bianco''. Questo garantisce che gli oggetti bianchi possono essere distrutti in modo sicuro una volta che il set grigio è vuoto.

L'algoritmo presenta un vantaggio importante: può essere eseguito '''''on-the-fly,''''' senza che sia arrestato il sistema per periodi di tempo significativo. Ciò si ottiene marcando gli oggetti nel momento in cui vengono allocati e durante le modifiche, mantenendo i tre insiemi. Monitorando la dimensione degli insiemi, il sistema può effettuare ''garbage collection'' periodicamente o quando necessario. Inoltre, viene eliminata la necessità di toccare l'intero insieme degli oggetti durante ciascun ciclo di Garbage Collected.

L'algoritmo presenta un vantaggio importante: può essere eseguito '''''on-the-fly,''''' senza che sia arrestato il sistema per periodi di tempo significativo. Ciò si ottiene marcando gli oggetti nel momento in cui vengono allocati e durante le modifiche, mantenendo i tre insiemi. Monitorando la dimensione degli insiemi, il sistema può effettuare ''garbage collection'' periodicamente o quando necessario. Inoltre, viene eliminata la necessità di toccare l'intero insieme degli oggetti durante ciascun ciclo di Garbage Collected.

=== Strategia di attuazione ===

Al fine di attuare l'algoritmo ''tri-colour marking'' si prendono importanti decisioni al momento della progettazione e ciò può incidere sensibilmente sulle caratteristiche delle prestazioni del garbage collector.

==== Movimento contro non movimento ====

Una volta che il set è stato classificato irraggiungibile, il Garbage Collector può semplicemente rilasciare gli oggetti irraggiungibili, oppure copiare alcuni o tutti gli oggetti raggiungibili in una nuova area di memoria, aggiornando tutti i riferimenti a tali oggetti come necessario. Questi sono chiamati rispettivamente collettor in '''''non movimento''''' ed '''''in movimento'''''.

A prima vista una strategia di Garbage Collector in movimento può sembrare inefficiente e costosa rispetto all'approccio di ''non movimento,'', dato che sembra essere richiesto molto più tempo di elaborazione per ogni ciclo. In realtà, la strategia in movimento porta a diversi vantaggi in termini di prestazioni, sia durante il ciclo di raccolta dei rifiuti, che durante l'esecuzione del programma vero e proprio:

* Non è necessario ulteriore tempo macchina per recuperare lo spazio liberato dagli oggetti irraggiungibili, l'intera regione viene così considerata libera. Viceversa un Garbage Collector in ''non movimento'' deve controllare ogni oggetto irraggiungibile e registrare che la memoria da essi occupata sia disponibile.