Garbage collection: differenze tra le versioni
Contenuto cancellato Contenuto aggiunto
No2 (discussione | contributi) →Raggiungibilità di un oggetto: Pila (informatica) |
fix wikilink errato |
||
(21 versioni intermedie di 9 utenti non mostrate) | |||
Riga 1:
[[File:Garbage collection.gif|thumb|upright=1.4|Esecuzione della Garbage Collection]]
In [[informatica]] per '''Garbage Collection''' (termine a volte abbreviato con '''GC''', letteralmente ''raccolta di 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=https://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>.▼
▲In [[informatica]] per '''
Questo meccanismo ha provocato 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''.▼
▲Questo meccanismo ha provocato 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
== Descrizione ==
Per la gestione della memoria si tiene conto di due principi fondamentali:
# Trovare gli oggetti precedentemente creati da un [[programma (informatica)|programma]] ai quali non sarà più necessario accedere;
# 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 all'utilizzo di puntatori alle varie aree di memoria già liberate in passato.<ref group="N">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]],
=== Benefici ===
La ''garbage collection'' esonera il programmatore dall'eseguire manualmente l'allocazione (richiesta) e la
* ''[[Dangling pointer|
▲La ''garbage collection'' esonera il programmatore dall'eseguire manualmente l'allocazione (richiesta) e la delocazione (rilascio) di aree di memoria, riducendo o eliminando del tutto alcune categorie di bugs:
*
*
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.▼
▲* ''[[Dangling pointer|'''Dangling pointers''']]'': persistenza nel programma di puntatori che si riferiscono ad aree di memoria che contenevano oggetti, ormai delocate. 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 delocazione. 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 ===
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: questa incertezza può determinare improvvisi blocchi o ritardi nell'esecuzione. Problemi di questo genere sono inaccettabili in ambienti [[sistema real-time|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=https://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''
=== Raggiungibilità di un oggetto ===
Siano
* Quando viene creato all'avvio del programma (oggetto globale) o di una sua sotto-procedura (oggetti di [[scope]], creati sullo [[Pila (informatica)|stack]]); l'oggetto in questione viene detto in tal caso
* Quando un altro oggetto, raggiungibile, trattiene un riferimento ad esso; in modo più formale, la raggiungibilità è una
L'identificazione delle aree di memoria
<syntaxhighlight lang="java" line="1" copy=1>
Object x = new Foo();
Object y = new Bar();
Riga 58:
* valore; ciò sempre ammesso che effettivamente termini in un tempo finito
*/
</syntaxhighlight>
Il problema di individuare precisamente la spazzatura semantica è purtroppo solo parzialmente [[decidibilità|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
=== Algoritmo di base ===
I ''
▲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-sweep'''<ref>Trad.Ing.:"''Marca e butta via''"</ref> 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 clear''<ref name=":0" group="N">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" group="N">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" group="N" />
Questo metodo ha diversi svantaggi, per esempio
==== 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
#
#* Il
#* Il
#* Il
#* Gli oggetti possono passare soltanto dal bianco al grigio e dal grigio al nero ma non in senso opposto.
#
#
#
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
L'algoritmo presenta un vantaggio importante: può essere eseguito
=== 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
A prima vista una strategia di
* Non è necessario ulteriore tempo macchina per recuperare lo spazio liberato dagli oggetti irraggiungibili, l'intera regione viene così considerata libera. Viceversa un
* Dal momento che grandi regioni contigue della memoria sono generalmente messe a disposizione dalla strategia di ''
▲* 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.
▲* Dal momento che grandi regioni contigue della memoria sono generalmente messe a disposizione dalla strategia di ''Garbage Collector in movimento'', i nuovi oggetti possono essere attribuiti semplicemente incrementando una locazione di memoria. Una strategia di non movimento invece può, dopo qualche tempo, portare ad una struttura dei dati ([[Heap (struttura dati)|heap]]) fortemente frammentata, struttura che richiede una consultazione più frequente dei piccoli blocchi di memoria disponibili, al fine di allocare questi nuovi oggetti.
* Oggetti che fanno riferimento l'uno all'altro spesso possono essere spostati in locazioni di memoria adiacenti, aumentando la probabilità che questi si trovino sulla stessa linea della [[cache]] o della pagina di [[RAM|memoria virtuale]]. Questo accelererà notevolmente l'accesso ai nuovi oggetti attraverso i riferimenti.
Uno svantaggio del ''
|url = https://msdn.microsoft.com/en-us/library/23acw07k.aspx
|titolo = Copying and Pinning
Line 109 ⟶ 110:
==== La copia mark-and-sweep contro la copia mark-and-don't-sweep ====
Come abbiamo già visto, per raffinare ulteriormente la distinzione, i
Un
Un
==== Generational Garbage Collector (Ephemeral Garbage Collector) ====
È stato osservato che in molti programmi gli oggetti più recenti, sono anche quelli con più probabilità di diventare rapidamente irraggiungibili<ref group="N">Effetto noto come Ephemeral o Generational Garbage Collection.</ref>. L'ipotesi generazionale divide gli oggetti in generazioni. Inoltre il sistema di [[Run-time|runtime]] mantiene la conoscenza di tutti i riferimenti tenendo traccia dalla loro creazione, alla sovrascrittura dei riferimenti. Quando il Garbage Collector va in esecuzione, può essere in grado di utilizzare tale conoscenza per dimostrare che alcuni oggetti inizialmente nel set iniziale bianco non sono raggiungibili senza dover attraversare l'intera struttura di riferimento. Al fine di attuare questo concetto, molti Garbage Collector generazionali utilizzano aree di memoria separate per i diversi livelli degli oggetti. Quando una regione è piena, i pochi oggetti referenziati nella vecchia memoria sono promossi (copiati) nella regione immediatamente successiva per cui l'intera regione può essere sovrascritta con nuovi oggetti. Questa tecnica permette di incrementare la velocità, in quanto la raccolta dei rifiuti di una sola regione avviene nello stesso momento.
''Generational
==== Stop-the-world contro incremental contro concurrent ====
Il meccanismo
==== Precise contro conservative and internal
Alcuni collezionisti in esecuzioni in particolari ambienti possono identificare correttamente tutti i puntatori (riferimenti) di un oggetto che sono perciò detti "precisi", contrariamente ai collezionisti conservatori. Questi ultimi suppongono che una qualsiasi sequenza di bit in memoria potrebbe essere un puntatore che punta un qualsiasi oggetto allocato. Un esempio in cui il
Una problematica correlata è quella degli ''internal
=== Implicazioni ===
Line 132 ⟶ 133:
'''Allocazione heap manuale''':
* Ricerca di blocchi di dimensioni sufficienti secondo il [[Gestore della memoria|best/first-fit]].
* Manutenzione delle [[Lista Libera|free list]].
'''Allocazione Garbage collection'''
* Individuare gli oggetti raggiungibili
* Copiare gli oggetti che sono stati spostati
Line 143 ⟶ 142:
* Ricerca di [[Gestore della memoria|best/ first-block]]
È difficile stabilire quale dei due casi sia migliore, in quanto il loro comportamento dipende dalla situazione. Alcuni progressi nel
=== Determinismo ===
Il Tracing garbage collection non è deterministico. Un oggetto che diventa ammissibile per il
Questo può portare diversi problemi:
* La maggior parte degli ambienti con l'analisi
* L'impatto sulle prestazioni causate dal
== Reference counting ==
{{vedi anche|Reference counting}}
Il Reference counting, o conteggio dei riferimenti, è una forma di gestione automatica della memoria, dove ogni oggetto ha un conteggio del numero di riferimenti ad esso. Il contatore è incrementato quando viene creato un riferimento all'oggetto e diminuisce quando un riferimento viene distrutto. La memoria dell'oggetto viene recuperata quando il conteggio si azzera.
Ci sono due principali svantaggi per il conteggio dei riferimenti:
* Se due o più oggetti rimandano l'uno all'altro, possono creare un ciclo in cui non vengono mai rilasciati ed il loro riferimento viene valutato zero. Alcuni sistemi di
* Nelle implementazioni più semplici, ogni assegnazione di riferimento, ed ogni riferimento perso, richiedono spesso modifiche di uno o più contatori di riferimento. Quando viene utilizzato in un ambiente [[multithreading]] tali modifiche, di incremento/decremento, possono essere intrecciate, ma tale operazione risulta costosa per processi senza operazioni atomiche, come Compare-and-swap. Un importante vantaggio del contatore dei riferimenti è che esso fornisce un
▲* Se due o più oggetti rimandano l'uno all'altro, possono creare un ciclo in cui non vengono mai rilasciati ed il loro riferimento viene valutato zero. Alcuni sistemi di Garbage Collector, come quello in CPython, utilizzano uno specifico conteggio dei riferimenti per affrontare questo problema.<ref>{{Cita web|url=https://www.python.org/doc/2.5.2/ext/refcounts.html|accesso=13 novembre 2008|data=21 febbraio 2008|titolo=Reference Counts|sito=Extending and Embedding the Python Interpreter|citazione=While Python uses the traditional reference counting implementation, it also offers a cycle detector that works to detect reference cycles.|urlmorto=sì|urlarchivio=https://web.archive.org/web/20081023133624/http://www.python.org/doc/2.5.2/ext/refcounts.html|dataarchivio=23 ottobre 2008}}</ref>
▲* Nelle implementazioni più semplici, ogni assegnazione di riferimento, ed ogni riferimento perso, richiedono spesso modifiche di uno o più contatori di riferimento. Quando viene utilizzato in un ambiente [[multithreading]] tali modifiche, di incremento/decremento, possono essere intrecciate, ma tale operazione risulta costosa per processi senza operazioni atomiche, come Compare-and-swap. Un importante vantaggio del contatore dei riferimenti è che esso fornisce un Garbage Collector deterministico.
== Escape Analysis ==
La ''Escape Analysis'' può essere utilizzata per spostare le locazioni di memoria dallo heap allo stack o ai registri della CPU, riducendo così la quantità di lavoro che deve essere svolta dal ''garbage collector''. Lo spostamento è lecito quando il riferimento all'oggetto non sopravvive alla [[subroutine]] in cui è stato dichiarato, cioè quando il riferimento è a tutti gli effetti una variabile locale, che non viene passata ad ulteriori subroutine o ritornata a monte.
=== Esempio (Java) ===
<
class A {
final int finalValue;
Line 183 ⟶ 184:
}
}
</syntaxhighlight>
In questo esempio il costruttore della classe A passa la nuova istanza di A a <code>B.doSomething</code>, quindi il compilatore non può garantire che il puntatore non sopravviva al costruttore: il puntatore "escapes", fugge.
== Disponibilità ==
In generale, [[linguaggio di programmazione ad alto livello|linguaggi di programmazione ad alto livello]] dispongono solitamente del
Altri linguaggi dinamici come [[Ruby (linguaggio di programmazione)|Ruby]] tendono ad usare il Garbage Collector. I [[Object oriented|linguaggi di programmazione orientati agli oggetti]], come [[Smalltalk]], [[Java (linguaggio di programmazione)|Java]] e [[ECMAScript]], solitamente prevedono il
== Ambienti limitati ==
Il
== Note ==
;Annotazioni
<references group="N"/>
;Fonti
<references/>
Line 202 ⟶ 206:
* [[Memory leak]]
* [[Automatic Reference Counting]]
== Altri progetti ==
{{Interprogetto|preposizione=sulla}}
== Collegamenti esterni ==
* {{Collegamenti esterni}}
* {{FOLDOC}}
{{Controllo di autorità}}
|