Garbage collection: differenze tra le versioni
Contenuto cancellato Contenuto aggiunto
fix /migliorata leggibilità wikitesto |
fix wikilink errato |
||
| (Una versione intermedia di un altro utente non mostrate) | |||
Riga 1:
[[File:Garbage collection.gif|thumb|upright=1.4|Esecuzione della Garbage Collection]]
In [[informatica]] per '''''garbage collection''''' ('''GC''', {{Lett|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ù
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]], 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 dinamica della memoria|allocazione di memoria]].
=== Benefici ===
Riga 18:
* ''[[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 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.
*
*
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 28:
* 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 [[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
== 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 radice;
* 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();
Line 59 ⟶ 60:
</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 ''collector'' implementati si concentrano sulla spazzatura sintattica.
=== Algoritmo di base ===
I ''
==== 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
Durante la prima fase, o fase di Mark, del ciclo di
Nella seconda fase, o fase di
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 [[Latenza|latenze]] di risposta o in [[Sistema 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]].
Line 81 ⟶ 82:
#* 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 invariante importante
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
=== 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 ''
* 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 collector possono tracciare gli oggetti secondo tre set (bianco, grigio e nero) e mantenerli durante il ciclo di raccolta. L'approccio più semplice è stato inventato nel 1969 e prende il nome di ''semi-space collector''. In questo schema di
Un ''mark-and-sweep'' ''garbage collection'', mantiene uno o due bit per ogni oggetto da registrare. L'albero di riferimento viene attraversato nel corso di un ciclo di raccolta (fase di ''mark'') e gli oggetti vengono manipolati dal collettor per riflettere lo stato attuale e la fase di sweep libera la memoria. Il ''mark-and-sweep'' ha il vantaggio che, una volta determinato il set irraggiungibile, non può essere attuata né una strategia di movimento, né una strategia di non movimento.
Un ''mark-and-don't-sweep'' garbage collection come il precedente, mantiene un bit per ogni oggetto da registrare, vi sono però due differenze fondamentali: innanzitutto il set di bianco e nero hanno significato diverso da quello del ''mark-and-sweep'', poiché in quest'ultimo sistema tutti gli oggetti raggiungibili sono sempre di colore nero. Un oggetto contrassegnato come nero rimarrà tale anche se diventa irraggiungibile. Un oggetto bianco è attribuito come inutilizzabile. In secondo luogo l'interpretazione di nero/bianco può variare (0=bianco, 1= nero) e viceversa.
==== 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 ''stop-the-world'' opera semplicemente interrompendo l'esecuzione del ciclo di raccolta in modo da garantire che i nuovi oggetti non siano assegnati e non diventino improvvisamente irraggiungibili mentre il collector è in esecuzione. Svantaggio evidente è che il programma non può svolgere alcun lavoro utile mentre è in esecuzione il ciclo di raccolta (detta
==== 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 141 ⟶ 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 ==
Line 156 ⟶ 157:
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
== 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) ===
<syntaxhighlight lang="java" line="1" copy=1>
class A {
final int finalValue;
Line 188 ⟶ 189:
== 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 ==
| |||