Questo articolo descrive gli algoritmi generazionali di Garbage Collection e prende come base il GC di default della Java Virtual Machine 1.4.1 per descrivere i vari algoritmi di garbaging messi a disposizione dalle moderne JVM. Si conclude con l‘analisi delle principali novità introdotte dalle JVM 1.5 e 1.6 per quanto riguarda la determinazione automatica degli algoritimi di garbaging da utilizzare.
Il precedente articolo di questa serie dedicata al Garbage Collector ha introdotto gli algoritmi di base usati per riciclare gli oggetti istanziati in heap memory e ne ha descritto i vantaggi e le controindicazioni.
L’osservazione del ciclo di vita degli oggetti creati da qualsiasi applicazione Java dimostra che nessuno degli algoritmi descritti è abbastanza flessibile da adattarsi in maniera ottimale a tutte le casistiche. Per questo motivo le JVM più recenti utilizzano più algoritmi di base in diverse sezioni della heap memory per ottimizzare il riciclo degli oggetti soprattutto in termini di throughput e low pause. Questo articolo illustra le motivazioni che giustificano la divisione della memoria in sezioni, introducendo i cosiddetti Garbage Collector “generazionali” di cui fanno uso le moderne JVM. La descrizione di questo tipo di collector permette di entrare nei dettagli dei vari algoritmi messi a disposizione dal Garbage Gollector per poi mostrare le principali novità introdotte nelle versioni più recenti della JVM.
Considerazioni preliminari: mortalità infantile e oggetti permanenti
L’organizzazione della heap memory nella Java Virtual Machine prende forma a partire da due importanti considerazioni sul ciclo di vita degli oggetti istanziati. Studi empirici condotti sui linguaggi di programmazione a oggetti hanno dimostrato che la maggior parte degli oggetti istanziati vengono rilasciati dopo brevissimo tempo. Tale caratteristica prende il nome di “mortalità infantile” e coinvolge circa il 98% degli oggetti istanziati in quasi tutte le tipologie di applicazione. Si pensi ad esempio a tutti quegli oggetti istanziati all’interno di un metodo e che possono essere riciclati dal GC al termine del metodo stesso. Situazioni in cui si presenta un alto tasso di mortalità infantile influenzano fortemente la scelta dell’algoritmo di garbaging. In questi casi, come si è visto nel precedente articolo, i copying collectors performano particolamente bene, perche‘ analizzano soltanto gli oggetti ancora referenziati che sono la stragrande minoranza del totale.
Un’altra importante caratteristica è che gli oggetti non colpiti da mortalità infantile tendono ad avere una vita lunga e, in alcuni casi, a sopravvivere per tutta la durata dell’applicazione. Ne sono un esempio gli oggetti in sessione o gli entity bean in applicazioni Java EE. Gli oggetti inizializzati all’avvio dell’applicazione e utilizzati per tutta la sua durata prendono il nome di oggetti permententi. Si pensi ad esempio a un JDBC Connection Pool all’interno di un web application server. In questi casi gli algoritmi di mark-sweep sono particolarmente indicati perche‘ hanno l’effetto di compattare gli oggetti alla fine della heap memory e tendono a lasciare intatti gli oggetti che sopravvivono a più cicli di garbaging.
Algoritmi generazionali
La JVM utilizza un Garbage Collector generazionale che divide la heap memory in due sezioni: la young generation, che contiene gli oggetti “giovani” o appena creati, e la old generation, in cui vengono spostati gli oggetti “sopravvissuti” nella young generation a più cicli di garbaging. Il più evidente vantaggio offerto da questo tipo di GC è la possibilità di utilizzare diverse strategie di garbaging in ognuna delle sezioni in cui è divisa la heap memory. Un Garbage Collector generazionale, inoltre, non costringe a effettuare il riciclo degli oggetti in tutte le sezioni ad ogni passaggio, ma permette di eseguire il garbaging indipendentemente in ogni sezione, diminuendo il tempo di pausa. In caso di allocation failure, ovvero quando non si è in grado di soddisfare una richiesta di allocazione di memoria, un collector generazionale può eseguire prima il riciclo degli oggetti nella young generation, effettuando una cosiddetta minor collection. Poiche‘ nella young generation, per le considerazioni fatte in precedenza, ci saranno molti oggetti non più utilizzati, una minor collection libererà una notevole quantità di spazio in heap memory. Inoltre l’uso di algoritimi di copying collection, che visitano solo la minoranza degli oggetti ancora utili, assicura tempi di garbaging molto bassi. Se lo spazio liberato al termine di una minor collection è sufficiente, non c’è la necessità di analizzare le altre sezioni di memoria e l’applicazione può tornare ad essere eseguita. Solo in caso contrario è necessario effettuare una major collection, che sposta gli oggetti dalla young generation alla old generation ed esegue il riciclo degli oggetti più vecchi e non più utilizzati.
Oltre ai vantaggi analizzati finora, un Garbage Collector generazionale pone un problema: il tracing delle referenze intergenerazionali. Tutti i tracing collector, come il copying, il mark-sweep e mark-compact, partono da un insieme di oggetti root per individuare gli oggetti ancora utili. I collector generazionali fermano il tracing degli oggetti in caso di referenze che portano ad oggetti in generazioni più vecchie. Nasce però un problema importante: che cosa succede in caso di oggetti in generazioni più vecchie che hanno riferimenti a oggetti in generazioni più giovani? In questa situazione c’è il rischio che una minor collection non li raggiunga e li ricicli anche se sono ancora in uso. Questo tipo di riferimenti, chiamate referenze “old-to-young”, possono essere creati solo quando un oggetto che referenzia oggetti giovani viene promosso in generazioni più vecchie o quando un puntatore all’interno di un oggetto più vecchio viene modificato per puntare a un oggetto in una generazione più giovane. Nel primo caso il Garbage Collector può in autonomia mantenere una lista di reference old-to-young aggiornandola ogni volta che promuove un oggetto alla old generation. Nel secondo caso il GC deve lavorare in collaborazione con il componente che esegue la modifica del puntatore.
La JVM utilizza a questo scopo un algoritmo detto di card marking, con il quale divide logicamente la old generation in piccole sezioni, chiamate card, e mantiene una tabella in cui è associato un bit ad ogni card. Quando un campo puntatore di un oggetto contenuto in una card viene modificato, il corrispondente bit nella tabella viene posto a 1. Prima della sua esecuzione il Garbage Collector analizza gli oggetti contenuti nelle sole card con relativo bit a 1 e aggiorna l’elenco delle referenze old-to-young.
L’algoritmo di default della JVM e le sue varianti
La Java Virtual Machine utilizza un Garbage Collector generazionale implementato tenendo conto delle considerazioni fino a qui introdotte. Se non specificato diversamente, in questa sezione dell’articolo si fa riferimento all’algoritmo utilizzato di default dalla JVM versione 1.4.1, anche se i comportamenti più basilari del Garbage Collector sono rimasti invariati a partire dalla versione 1.2, che utilizzava per la prima volta un GC generazionale. La JVM divide, come è già detto, la heap memory in due sezioni: la young generation e la old generation. La young generation è a sua volta suddivisa in una parte in cui vengono allocati gli oggetti appena creati, detta Eden, e due semispazi in cui agisce un copying collector. La old generation è a sua volta suddivisa in una zona, detta Tunered, contenente gli oggetti sopravvissuti ad un certo numero di copie tra i semispazi della young generation, e una zona, detta Perm, che contiene gli oggetti permanenti. Il GC utilizza per la old generation un algortimo di tipo mark-compact. L’esecuzione di una minor collection provoca il passaggio di oggetti in Eden verso uno dei due semispazi, la copia degli oggetti da un semispazio all’altro e lo spostamento di alcuni oggetti del semispazio attivo nella old generation. Una major collection implica, invece, il garbaging degli oggetti anche della old generation. L’unico modo a disposizione dello sviluppatore per forzare il riciclo degli oggetti è la chiamata alla funzione System.gc() che avvia una major collection, mentre non c’è modo di indurre solamente una minor collection.
La JVM mette a disposizione diverse varianti dell’algoritmo sino a qui descritto che fanno uso di collector paralleli, con lo scopo di eseguire parte delle funzioni di garbaging in concorrenza con le applicazioni o utilizzando più thread. È evidente che i collector paralleli apportano significativi benefici solo se utilizzati in macchine multiprocessore, mentre l’overhead dovuto alla concorrenza li rende sconsigliabili in ambienti monoprocessore. La versione 1.4.1 della JVM mette a disposizione tre tipi di GC aggiuntivi rispetto a quello seriale di default:
- Il Throughput Collector. Utilizza una versione parallela del copying collector nella young generation, i cui oggetti vengono riciclati utilizzando più thread sia per la fase di mark che per la fase di copy. L’effetto è quello di avere minor collection più veloci. Questo collector si attiva con l’opzione -XX:+UseParallelGC ed è utile per ottimizzare il throughput di applicazioni che possono tollerare pause lunghe, anche se infrequenti.
- Il Concurrent Low Pause Collector. Utilizza un collector parallelo anche per le major collection. Un solo thread del GC esegue una prima fase di mark, che identifica l’insieme iniziale dei soli oggetti attivi raggiungibili direttamente dal codice applicativo. La seconda fase di mark usa un solo thread, in concorrenza con quelli applicativi, per identificare gli oggetti raggiungibili dall’insieme iniziale prodotto dalla fase precedente. La terza fase, detta di remark, ferma l’applicazione e con più thread paralleli traccia le referenze a partire dagli oggetti eventualmente modificati dall’applicazione durante la seconda fase. La successiva fase di sweep può riciclare gli oggetti con un unico thread in concorrenza con l’applicativo. Il concurrent low pause collector si attiva con l’opzione -XX:+UseConcMarkSweepGC e minimizza i tempi di pausa effettuando parte del lavoro di garbaging in concorrenza con la normale attività e utilizzando thread paralleli.
- L’Incremental Low Pause Collector. Ricicla, durante le minor collection, anche parte degli oggetti che si trovano nella old generation, con lo scopo di distribuire le lunghe pause di una major collection su più minor collection. Pur minimizzando i tempi di pausa, può dar luogo a un throughput più basso su tempi lunghi. Si attiva con il flag -Xincgc.
Novità delle JVM 1.5 e 1.6: gli ergonomics
Le versioni 1.5 e 1.6 organizzano la heap memory in generazioni con le stesse modalità della 1.4.1, mettendo a disposizione gli stessi collector e introducendone uno aggiuntivo, il Parallel Compacting Collector (-XX:+UseParallelOldGC), che rispetto al throughput collector utilizza anche per la old generation un collector parallelo. Le novità introdotte dalle ultime JVM riguardano la scelta automatica del tipo di GC. Fino alla versione 1.4, infatti, veniva utilzzato di default il collector seriale anche su macchine multiprocessore e l’attivazione di algoritmi paralleli era lasciata all’iniziativa e alla responsabilità dell’amministratore di sistema. La JVM 1.5 introduce il concetto di “ergonomics”, ossia la selezione automatica del collector e della dimensioni iniziali e massime della heap memory. Per farlo viene individuata una server-class all’interno della quale ricadono le macchine con 2 o più processori fisici e con due o più GigaByte di memoria fisica. Per questo tipo di macchine viene posta la heap memory iniziale ad 1/64 della memoria fisica, la dimensione massima a 1/4 della memoria fisica, fino a 1 GB e viene utilizzato il throughput collector. Per gli altri tipi di macchine vengono impostati 4 MB e 64MB come limiti iniziali e massimi della heap e viene usato il GC seriale. Le impostazioni per macchine client-class o server-class possono comunque essere forzate con gli switch -client e -server.
Un’altra importante novità introdotta dalla versione 1.5 è la possibilità di indicare degli obiettivi di ottimizzazione al garbage collector. Si possono in particolare usare i parametri
- -XX:MaxGCPauseMillis=n. Il GC imposta i suoi parametri di ottimizzazione cercando di evitare pause più lunghe di n millisecondi.
- -XX:GCTimeRatio=n. Il GC deve avere come obiettivo la massimizzazione del throughput. In particolare deve fare in modo che il rapporto tra il tempo speso in garbaging e il tempo totale sia percentualmente minore di 1/(1+n). Il valore di default è n=99, ovvero il rapporto tra tempo di garbaging e il tempo totale deve essere minore dell’1%.
L’introduzione della scelta automatica del tipo e degli obiettivi del GC non impedisce comunque all’amministratore di sistema di cercare di ottimizzare i tempi di garbaging mediante i numerosi parametri a riga di comando messi a disposizione dalla JVM, che saranno argomento del prossimo articolo di questa serie.
Conclusioni
Questo articolo ha descritto gli algoritmi generazionali che utilizzano i vari algoritmi di base, visti nel primo articolo della serie, per rendere efficiente il riciclo degli oggetti in tutte le sezioni in cui è organizzata la heap memory. Il Garbage Collector della JVM può utilizzare diverse varianti dell’algoritmo generazionale di default per massimizzare il throughput e minimizzare il low pause derivanti dal riciclo degli oggetti. La comprensione dell’organizzazione della heap memory e dei vari tipi di garbaging utilizzabili permette di ottimizzare consapevolmente il GC di una JVM. Il prossimo, e ultimo articolo della serie, introdurrà le principali opzioni di ottimizzazione del GC e gli strumenti di monitoraggio della heap memory, che consentono di valutare i miglioramenti apportati dalle ottimizzazioni effettuate.
Riferimenti
[1] Brian Goetz, “Garbage Collection in the HotSpot JVM”, Java theory and practise, 2003
http://www.ibm.com/developerworks/java/library/j-jtp11253/
[2] Tuning Garbage Collection with the 1.4.2 Java™ Virtual Machine
http://java.sun.com/docs/hotspot/gc1.4.2/
[3] Tuning Garbage Collection with the 5.0 Java™ Virtual Machine
http://java.sun.com/docs/hotspot/gc5.0/gc_tuning_5.html
[4] Java SE 6 HotSpot™ Virtual Machine Garbage Collection Tuning
http://java.sun.com/javase/technologies/hotspot/gc/gc_tuning_6.html
[5] Memory Management in the Java HotSpot™ Virtual Machine
http://java.sun.com/j2se/reference/whitepapers/memorymanagement_whitepaper.pdf
Luca Cinti ha conseguito la laurea in Informatica presso l’Università di Firenze con una tesi sul Grid Computing nell’ambito del progetto INFN Grid e in collaborazione con il centro di ricerca Deutsches Elektronen Synchrotron (DESY) di Amburgo. Lavora da qualche anno come amministratore di sistema presso una grossa finanziaria dove si occupa in particolare dell’implementazione e ottimizzazione di architetture Java EE.