Le chiamate ai metodi di una classe, all'interno di un Thread sono gestite seguendo una disciplina a Stack (pila). Uno Stack è un multiinsieme ordinato di elementi cui si accede mediante operazioni di inserimento ed estrazione con il vincolo che l'ultimo elemento inserito sia il primo ad essere estratto.
Questa struttura viene mantenuta in una zona di memoria che chiamiamo Stack Memory. Ad ogni chiamata di esecuzione di un metodo viene creato un record di attivazione messo in cima allo Stack.
Un record di attivazione rappresenta tutte le informazioni relative ad un specifica attivazione, in particolare:
- nome del metodo attivo e riferimento alla zona di memoria dove è memorizzato il corpo di istruzioni da eseguire;
- il riferimento all'istruzione cui tornare al termine dell'attivazione;
- parametri formali e loro legame con quelli attuali;
- variabili locali con riferimento alla memoria per esse allocata.
All'interno di applicazioni Java otteniamo l'eccezione della JVM java.lang.StackOverflowError, ogni qual volta la catena di attivazioni generata richiede una quantità di memoria che eccede la dimensione massima dello Stack. Una situazione tipica che può scatenare questa problematica è rappresentata dall'implementazione di un algoritmo di ricorsione.
Immaginiamo di voler realizzare un metodo per il calcolo del fattoriale e di voler utilizzare il naturale approccio induttivo alla realizzazione della funzione che lo rappresenta. Il calcolo del fattoriale di un numero può generare valori numerici estremamente grandi, ragion per cui optiamo per un'implementazione che faccia uso del tipo BigDecimal:
package it.html.java.stackoverflow;
import java.io.File;
import java.io.FileWriter;
import java.io.IOException;
import java.math.BigDecimal;
public class StackOverflowTest {
private final static BigDecimal zero = new BigDecimal(0);
private final static BigDecimal one = new BigDecimal(1);
public static void main(String[] args) throws IOException {
File file = new File("C:\\fattoriale\\fattoriale.txt");
file.createNewFile();
FileWriter writer = new FileWriter(file);
writer.write(fattoriale(new BigDecimal(2)).toString());
System.out.println("Fattoriale calcolato");
writer.close();
}
private static BigDecimal fattoriale(BigDecimal n) {
if (n.equals(zero))
return one;
else
return n.multiply(fattoriale(n.subtract(one)));
}
}Avendo definito preliminarmente una directory con il nome fattoriale all'interno del disco C:, mandiamo in esecuzione il programma ottenendo il calcolo del fattoriale di 2 senza alcun problema salvato all'interno del file fattoriale.txt. In questo particolare caso la sequenza di attivazioni,illustrata dall'immagine che segue, è molto contenuta:
Catena di attivazioni
In figura 1 sono mostrate le tre attivazioni di fattoriale(2), fattoriale(1) e fattoriale(0).
Essendo il predicato n=0 soddisfatto durante l'attivazione di fattoriale(0), la ricorsione termina e con essa la catena di attivazioni nello Stack. I record vengono quindi via via tolti dallo Stack restituendo i seguenti valori: l'attivazione di fattoriale(0) il valore 1, l'attivazione di fattoriale(1) il valore 1*1 (quindi 1) e l'attivazione di fattoriale(2) il valore 2*1 (quindi 2).
Vediamo ora cosa succede se proviamo a calcolare il fattoriale di un numero abbastanza grande, tentiamo ad esempio con il valore 50.000. Il risultato dovrebbe portare al blocco del programma con un eccezione del tipo:
Exception in thread "main" java.lang.StackOverflowError
at java.math.BigDecimal.valueOf(BigDecimal.java:1198)
at java.math.BigDecimal.add(BigDecimal.java:4429)
at java.math.BigDecimal.add(BigDecimal.java:4436)
at java.math.BigDecimal.subtract(BigDecimal.java:1436)
at it.html.java.stackoverflow.StackOverflowTest.fattoriale(StackOverflowTest.java:26)Il nostro programma non ha in se un bug in quanto la sua implementazione è corretta, il problema è nella complessità di spazio dell'algoritmo, tale da non consentire il calcolo del fattoriale di numeri di una determinata grandezza.
Quali soluzioni possiamo mettere in pratica per affrontare il problema? Un primo approccio potrebbe essere quello di sostituire l'algoritmo di implementazione ricorsivo con uno di complessità tale da poter gestire il calcolo del fattoriale per il range di numeri che è possibile avere in input.
Una versione iterativa del calcolo del fattoriale potrebbe essere una soluzione al problema. Se invece abbiamo a disposizione della memoria da poter utilizzare e non desideriamo abbandonare l'implementazione ricorsiva, possiamo incrementare la dimensione della memoria di Stack agendo sui parametri della JVM. Possiamo definire un limite massimo per lo Stack tale da consentire il calcolo del fattoriale per il massimo valore che è possibile avere in input senza saturare lo Stack stesso. Ad esempio nel nostro caso il valore massimo potrebbe essere rappresentato proprio dal valore 50.000.
Sappiamo che il valore di default per lo Stack della JVM è di 1024k per una architettura a 64bit, decidiamo di incrementarlo a circa il triplo del valore utilizzando l'argomento -Xss3m come input della JVM nell'esecuzione del nostro programma.
Ipotizzando di utilizzare Eclipse come IDE, settare questo valore per l'esecuzione dell'applicazione demo è molto semplice, è sufficiente infatti cliccare con il tasto destro del mouse sul nome del file StackOverflowTest.java, scegliere "Run/Debug Settings", selezionare "StackOverflowTest" e cliccare su "Edit".
Continuiamo agendo sulla tab "Arguments" ed inseriamo il valore -Xss3m all'interno dell'area di testo "VM arguments". Eseguendo nuovamente il programma l'esito dovrebbe essere
positivo con un'impostazione dello Stack della JVM che ci consente il calcolo del fattoriale fino ad un valore massimo di 50.000. L'inserimento di un controllo sul valore massimo dell'input rappresenta il tocco finale per il completamento del nostro programma.
