Questo articolo descrive gli algoritmi di base utilizzati dalla Java Virtual Machine per riciclare gli oggetti non più referenziati in Heap Memory ed è il primo di una serie dedicata al funzionamento del Garbage Collector. I concetti introdotti saranno utili, nel prosieguo della serie, a mostrare i meccanismi di funzionamento del Garbage Collector al fine di monitorarne e ottimizzarne le prestazioni.
In fase di implementazione di un programma, ogni sviluppatore deve porsi il problema di liberare le risorse e in particolare la memoria che viene allocata in fase di esecuzione. Alcuni linguaggi di programmazione lasciano questo compito interamente allo sviluppatore: in C++, ad esempio, è necessario implementare uno specifico distruttore per molte delle classi che si definiscono. Errori o dimenticanze nella scrittura nei distruttori portano a lasciare in memoria oggetti non più utili all’applicazione, fino potenzialmente a causare la saturazione delle risorse dell’ambiente di runtime. Altri sistemi, tra cui Java, mettono invece a disposizione un meccanismo automatico di gestione della memoria, che si occupa di riciclare le porzioni di memoria non più occupate da oggetti utili all’applicazione. Questo meccanismo prende il nome di Garbage Collector (GC), ossia, letteralmente, “spazzino”, e una sua prima versione fu introdotta già nel 1959 da John McCarthy per risolvere un problema di gestione di memoria del Lisp [1].
Vantaggi e metriche di valutazione del Garbage Collector
L’uso corretto di sistemi di Garbage Collection può portare ad alcuni importanti benefici. Il più evidente è sicuramente a vantaggio del programmatore, che non deve più occuparsi del riciclo degli oggetti allocati, ma può concentrarsi su aspetti più interessanti della progettazione di un’applicazione. Il Garbage Collector assicura che le risorse non più utilizzate vengano “riciclate” e rimesse a disposizione delle applicazioni: scompare, o quasi, la possibilità di avere i cosiddetti “memory leak”, incubo di ogni sviluppatore C/C++. Molti algoritmi di Garbage Collection hanno, inoltre, l’effetto di compattare la memoria evitandone la frammentazione, in modo da ripristinare la località della memoria, principio fondamentale per l’efficacia dei sistemi di caching.
L’uso di un Garbage Collector ha, naturalmente, anche un costo: parte delle risorse di sistema e del tempo di esecuzione di un programma devono essere dedicate alle attività di garbaging, che devono essere più efficienti possibile. È importante quindi definire una serie di parametri che indicano quanto un Garbage Collector è efficace. A questo scopo si definiscono diverse metriche, le più importanti delle quali sono:
- Throughput: la percentuale del tempo totale non speso in garbage collection, considerando lunghi periodi di tempo.
- Garbage collection overhead: l’inverso del throughput, ossia la percentuale del tempo totale speso in garbage collection.
- Pause time: il tempo durante il quale l’applicazione non è in esecuzione perche’ in attesa del garbaging della memoria.
- Frequency of collection: quanto spesso passa il GC.
- Footprint: la dimensione della memoria.
- Promptness: il tempo che intercorre tra la pulizia di una porzione di memoria e il momento in cui essa è nuovamente disponibile per essere allocata al programma.
Nella valuazione di un algoritmo di garbage collection si deve tener conto della sua efficacia rispetto alle metriche che interessa ottimizzare per una determinata tipologia di applicazione. In un’applicazione interattiva lato client, ad esempio, è importante minimizzare il pause time, per non pregiudicare la qualità dell'”esperienza utente”. Per applicazioni web, in cui l’interazione è comunque rallentata dai ritardi di rete, si deve fare più attenzione al throughput, mentre se l’applicazione gira su sistemi embedded sarà importante minimizzare il footprint, cioè lo spazio in memoria necessario all’algoritmo per essere efficiente.
Algoritmi di base
La Java Virtual Machine utilizza un Garbage Collector per la gestione dei dati residenti nella heap memory, la sezione di memoria dedicata all’allocazione degli oggetti instanziati dai programmi in esecuzione. Il Garbage Collector di Java utilizza diversi algoritmi di garbaging in porzioni diverse della JVM e mette a disposizioni dell’amministratore di sistema parecchie opzioni a riga di comando per scegliere i vari tipi di algoritmi e condizionarne il comportamento. Per poter procedere consapevolmente alla modifica di questi parametri è innanzitutto necessario conoscere gli algoritmi di base di garbage collection che possono essere utilizzati all’interno di una JVM.
Reference Counting
È l’algoritmo più semplice, il quale associa ad ogni oggetto il numero di riferimenti ad esso, incrementandolo e decrementandolo quando gli oggetti che lo referenziano vengono creati o distrutti. Un oggetto può essere eliminato quando il relativo contatore diventa zero. Quando, ad esempio, viene creato un nuovo oggetto A che referenzia un oggetto B, il reference count di A viene posto a uno e quello di B viene incrementato di uno. Quando B viene eliminato, il reference count di A viene decrementato e, se è diventato 0, anche A può essere distrutto. È evidente che lo svantaggio è dato dal maggior carico sul compilatore, che deve aggiungere le istruzioni relative alla gestione del counter per ogni oggetto istanziato, e a runtime, per i cicli di CPU utilizzati per il controllo e il decremento e incremento del counter ad ogni creazione e distruzione di un oggetto.
Tracing Collector
Sotto il nome di Tracing Collector ricade un’altra tipologia di algoritmi che evita di entrare nel merito della creazione e distruzione di ogni singolo oggetto, ma cerca di capire, a determinati intervalli di tempo, quali sono gli oggetti attivi in memoria e quali sono quelli non più utilizzati e quindi riciclabili. Un tracing collector ferma tutte le applicazioni in esecuzione (stop the world!) e inizia a tracciare gli oggetti a partire da un insieme di oggetti radice (roots) e, se alla fine di questo processo un oggetto non è stato raggiunto, viene riciclato. Esempi di oggetti radice sono i registri di programma, gli oggetti nello stack di ogni thread o le variabili statiche. Il problema più evidente dei tracing collectors è il fatto che durante l’esecuzione del GC tutti gli altri thread della JVM sono fermi, il che può causare notevoli problemi di performance soprattutto in presenza di heap memory molto grandi. A partire dalla versione 1.3.1 della JVM [3] sono state introdotte versioni parallelizzabili di questi tipi di algoritmi, in modo da diminuire i tempi di pausa dovuti al GC e da evitare problemi di scalabilità in sistemi multiprocessore. Le prossime sezioni descrivono alcuni dei più importanti tracing collectors, mettendo in evidenza i punti forza e gli svantaggi di ognuno di essi.
Mark-sweep collectors
I mark-sweep collectors eseguono il garbaging in due fasi. Nella prima fase, quella di mark, ogni oggetto viene visitato a partire da alcuni oggetti chiamati radici (roots). Tutti gli oggetti raggiunti durante questa fase vengono “marcati”, ponendo il valore del relativo bit di marking a 1. Nella seconda fase, quella di sweep, ogni oggetto in memoria viene analizzato e, se il suo bit di marking ha valore 0, l’oggetto può essere disallocato. Il problema fondamentale di questo tipo di algoritmi è che ogni oggetto in memoria è analizzato almeno una volta (due se è utilizzato) e durante queste scansioni le applicazioni non sono in esecuzione. Il pause time può diventare molto grande se siamo in presenza di applicazioni che utilizzano tanti oggetti anche piccoli e per brevi periodi di tempo.
Copying collectors
I copying collectors dividono la heap memory in due semispazi di uguale dimensione, uno attivo e l’altro inattivo. Quando lo spazio attivo si riempie, il GC visita gli oggetti attivi a partire dalle root e li copia nell’altro semispazio, che al termine di questo processo diventa attivo. Al termine di questo processo tutti gli oggetti utilizzati risulteranno allocati e compattati nel semispazio attivo. A differenza dei mark-sweep collectors, i copying collectors non scandiscono tutti gli oggetti in memoria, ma solo quelli effettivamente utilizzati, mentre quelli inutilizzati vengono implicitamente disallocati perche’ la sezione di memoria in cui risiedono diventa inattiva. I copying collectors hanno due evidenti svantaggi. Il primo è che, in ogni momento, metà dello spazio disponibile è completamente inutilizzato, e non sono quindi, indicati in ambiti in cui è importante la footprint. Il secondo è dato dal tempo necessario alla copia degli oggetti da un semispazio all’altro, soprattutto quando siamo in presenza di applicazioni che utilizzano oggetti per lunghi periodi di tempo. In questo caso, infatti, molti oggetti verranno continuamente copiati da un semispazio all’altro ad ogni passaggio del Garbage Collector.
Mark-compact collectors
I mark-compact collectors sono algoritmi in due fasi che cercano di combinare i vantaggi del mark-sweep e del copying. Durante la prima fase, gli oggetti visitati a partire dalle radici vengono marcati, come avviene nei mark-sweep collectors. Durante la fase di sweep gli oggetti marcati vengono copiati e compattati alla fine della heap memory. Al termine del garbaging, quindi, si avrà la porzione iniziale della memoria disponibile per l’allocazione di nuovi oggetti e la parte finale occupata dagli oggetti attivi. Un effetto importante di questo tipo di collector è che gli oggetti di “vita lunga”, che sopravvivono a diversi passaggi del Garbage Collector, tendono a essere compattati in fondo alla heap e per questo motivo non sarà necessario copiarli ad ogni passaggio, visto che si trovano già nella posizione desiderata. Se siamo in presenza, invece, di applicazioni che usano molti oggetti per brevi periodi di tempo, a ogni passaggio del GC ci saranno molti oggetti che devono essere spostati dalla loro locazione in fondo alla heap memory.
Conclusioni
In questo primo articolo della serie sono stati presentati i concetti fondamentali relativi alla garbage collection, di cui sono stati descritti i vantaggi e i costi da valutare. Sono stati introdotti anche i principali algoritmi di base utilizzati all’interno di una Java Virtual Machine per la gestione della heap memory. I concetti espressi finora saranno utili per mostrare nei prossimi articoli come il Garbage Collector della JVM utilizza gli algoritmi di base per la gestione dei dati allocati nella heap memory, quali sono gli strumenti per monitorarne il comportamento e i parametri su cui intervenire per effettuare il tuning delle performance.
Riferimenti
[1] John McCarthy, “Recursive Functions of Symbolic Expressions and Their Computation by Machine”, Massachusetts Institute of Technology, 1960
http://www-formal.standford.edu/jmc/recursive.html
[2] Brian Goetz, “A brief history of garbage collection”, Java theory and practise, 2003
http://www.ibm.com/developerworks/java/library/j-jtp10283/
[3] Tuning Garbage Collection with the 1.3.1 Java Virtual Machine
http://java.sun.com/docs/hotspot/gc/