Linguaggi di Programmazione - Appunti in LaTeX

Capitolo 4. Gestione della memoria

pila (stack): oggetti allocati con politica LIFO (Last In First Out)

heap: oggetti allocati e de-allocati in qualsiasi momento

normalmente un programma usa tutti e tre i meccanismi.

4.2.1 Allocazione statica

Gli oggetti hanno un indirizzo assoluto, mantenuto per tutta la durata dell'esecuzione. Solitamente vengono allocati staticamente:

• variabili globali
• costanti determinabili a tempo di compilazione
• tabelle usate dal supporto a run-time (per type checking, garbage collection, etc.)

Allocazione statica completa

Alcuni linguaggi di programmazione (vecchie versioni di Fortran), usano l'allocazione statica per tutti i dati, in questo caso:

• ad ogni variabile (locale o globale) viene assegnato un indirizzo univoco per tutta l'esecuzione
• le variabili locali di una procedura mantengono il valore anche dopo la fine della procedura

Vantaggi dell'allocazione statica completa:

semplicità dell'implementazione• accesso ai dati più veloce, siccome ogni variabile sta sempre nella stessa posizione

Svantaggi dell'allocazione statica completa:• non si può fare la ricorsione, in quanto le varie chiamate ricorsive di una stessa procedura devono avere ciascuna uno spazio privato di memoria per: una copia delle variabili locali, ogni chiamata ricorsiva le può – modificare in modo diverso informazioni di controllo (indirizzo di ritorno)–ma l'allocazione statica non permette la creazione di molteplici spazi per una sola funzione. 74

CAPITOLO 4. GESTIONE DELLA MEMORIAforza ad usare più spazio del necessario, in quanto costringe ad allocare• spazio per tutte le variabili e per tutte le funzioni di tutto il codice. Comporta uno spreco perché magari due funzioni che richiedono molto spazio non vengono mai chiamate contemporaneamente

4.2.2 Allocazione dinamica: stack di attivazione In generale, a meno

Di allocazione statica completa, quando parte l'esecuzione del programma viene allocata la memoria che serve al programma principale e si esegue il codice finché c'è una chiamata ad una funzione. In questo caso deve essere allocato dello spazio nello stack di attivazione, che viene chiamato record di attivazione (RdA o frame). Nel momento in cui si esce dalla procedura questo spazio viene de-allocato.

Un record di attivazione di una procedura contiene:

• variabili locali
• parametri in ingresso e uscita
• indirizzo di ritorno (passaggio del controllo)
• link dinamico (al record di attivazione della procedura chiamante)
• link statico (al record di attivazione della procedura genitore, ovvero alla procedura a cui, in presenza di scoping statico, fa riferimento per le variabili non locali)
• risultati intermedi (uno spazio di memoria ausiliario che può essere necessario per valutare espressioni complesse)
• salvataggio dei

registri (i registri della CPU contengono dati temporanei, quando il controllo passa ad un'altra procedura quei dati devono essere salvati in memoria)

Analogamente, ogni blocco che non è una procedura deve avere un suo record di attivazione anche se con meno informazioni di controllo:

• variabili locali
• risultati intermedi
• link dinamico (al record di attivazione della procedura chiamante)

Normalmente, nello stack di attivazione vengono occupati prima gli indirizzi alti e poi quelli più bassi. Ricordiamo inoltre che:

• il (FP) punta all'indirizzo base dell'ultimo record e i dati frame pointer dell'ultimo frame sono accessibili per offset (determinabile staticamente a tempo di compilazione) rispetto al frame pointer;
• indirizzo_dato = FP + offset 75

CAPITOLO 4. GESTIONE DELLA MEMORIA per dati non locali è necessario determinare l'indirizzo base del record del dato, si usa il che è il puntatore al precedente

recordlink dinamicosullo stack. Serve per risalire la catena dei link;

• per la gestione dello stack di attivazione si usa anche lo stack pointer(SP) che punta alla fine della pila, più precisamente al primo spazio dimemoria disponibile.

Inizio della pila RdARdA Puntatori di catenadinamica...

Frame pointer RdAStack pointer Zona di memorialibera per la pila

Figura 4.1: Stack di attivazione e i vari puntatori

Esempio: come funziona il meccanismo dei record di attivazione

{1 int x = 0;
2 int y = x + 1;
3 {
4 int z = (x + y) * (x - y);
5 }
6 }
7 76

CAPITOLO 4. GESTIONE DELLA MEMORIA... ... ...

FP ... ... ...
RdA ... ...
... ... ...SP

FP LD
x = 0 x = 0
y = x + 1 y = 1
SP

FP LD
z = -1
risultati
intermedi
SP

... ... ...
FP FP
... ... ...
... ... ...
FP SP SP
LD LD
x = 0 x = 0
y = x + 1 y = x + 1
SP LD LD
z = -1 z = -1
risultati risultati
intermedi intermedi

Figura 4.2: Evoluzione dello stack di attivazione

Passaggi eseguiti nello stack di attivazione per il precedente codice:

1. push del record con

spazio per ex y(a) scrittura del link dinamico nello spazio di memoria apposito(b) link dinamico del nuovo RdA: LD = FP(c) FP = SP(d) SP = SP + dimensione_nuovo_RdA

assegnazione dei valori di ex y

push del record del blocco interno con spazio per e per il risultatozintermedio x + y(a) scrittura del link dinamico nello spazio di memoria apposito(b) link dinamico del nuovo RdA: LD = FP(c) FP = SP(d) SP = SP + dimensione_nuovo_RdA

assegnazione del valore di z

pop del record del blocco interno, elimina l'ultimo RdA, recupera spazioe ripristina i puntatori 77CAPITOLO 4. GESTIONE DELLA MEMORIA(a) SP = FP(b) dell'RdA tolto dallo stackFP = link_dinamico

pop del record del blocco esterno(a) SP = FP(b) dell'RdA tolto dallo stackFP = link_dinamico

Nella pratica, in molti linguaggi si preferisce evitare l'implementazione apila per i blocchi anonimi perché magari per blocchi che devono essere eseguitimolte volte all'interno di altre procedure risulta

dispendioso creare nuovi record nello stack di attivazione. Quello che si fa invece è, quando si crea il record per una procedura, si alloca anche lo spazio necessario per contenere i dati di tutti i blocchi anonimi che stanno all'interno della procedura. Questa tecnica potrebbe risultare più costosa in termini di memoria utilizzata, perché alcuni dei blocchi allocati potrebbero non essere usati o non essere usati contemporaneamente, ma sicuramente si ottiene un vantaggio in termini di velocità.

Esempio di ricorsione:

int fact(int n){
    if(n <= 1) return 1;
    else return n * fact(n - 1);
}

Nell'RdA troviamo:

• parametri di input: n
• parametri di output: fact(n)
• link statici, dinamici e indirizzo di ritorno, back up registri del processore ci saranno tanti RdA quanto il valore iniziale di n.

Nella seguente figura viene illustrato come lo stack si modifica durante l'esecuzione della ricorsione del codice esempio chiamata con n

èfact(3).il parametro, r sta per return, ra sta per return address, LD sta per linkdinamico, pp sta per programma principale. 78CAPITOLO 4. GESTIONE DELLA MEMORIAFP 1 2 3 4FP... ... ... ...SP LD LD LDn = 3 n = 3 n = 3r r rra = pp ra = pp ra = ppSP FP LD LDn = 2 n = 2r rra = fact ra = factSP FP LDn = 1r = 1ra = factSP5 6 FP 7... ... ...FP SPLD LDn = 3 n = 3r r = 6ra = pp ra = ppFP SPLDn = 2r = 2ra = factSP

Figura 4.3: Utilizzo dello stack di attivazione durante la ricorsione chiamatacon fact(3)

I passi che vengono compiuti sono:

Chiamata della procedura

1. allocazione dello spazio del RdA
2. inserire nel RdA appena creato i valori dei parametri passati
3. inizializzare le variabili locali
4. impostare link statici e dinamici
5. salvare i registri

Uscita dalla procedura

1. passare il risultato, tipicamente inserendolo in una locazione di memoriadove chi lo riceve sa dove trovarlo
2. cambiare FP e SP
3. ripristinare i registri
4. deallocare il RdA

79CAPITOLO 4. GESTIONE DELLA MEMORIAAlcune di

queste operazioni possono essere indifferentemente svolte dal chiamante o dal chiamato. Un'osservazione da fare è che inserire il codice nella procedura chiamata porta a generare meno codice, perché, nel caso una procedura venisse chiamata più volte, il codice non deve essere ripetuto per ogni chiamata.

4.2.3 Allocazione dinamica: heap

Come anticipato, la heap è una parte di memoria dove i blocchi possono essere allocati e deallocati a seconda delle necessità.

Necessaria quando il linguaggio permette:

• tipi di dato dinamici
• oggetti di dimensioni variabili (per esempio un vettore con dimensione variabile)
• oggetti che sopravvivono alla procedura che li ha creati

In questi casi non è possibile usare lo stack perché la quantità di spazio allocato nello stack non è variabile e una volta conclusa la funzione lo spazio viene deallocato.

I problemi della heap sono:

• gestione poco efficiente dello spazio: allocare spazio

Gestione della heap: suddivisione in blocchi di dimensione fissa

In questo tipo di heap i blocchi sono collegati tra loro come una lista libera, ovvero c’è un puntatore al primo blocco della lista e in ogni blocco c’è un puntatore al successivo. Quando c’è bisogno di memoria si possono dunque aggiungere blocchi alla lista e quando non ce n’è più bisogno si possono togliere. In questo modo la gestione della memoria è relativamente efficiente, ma il vincolo della dimensione fissa rende il tutto troppo rigido: non fornisce blocchi di elevata dimensione per strutture dati contigue di dimensione elevata. Dividere una struttura dati in più blocchi non è una strada praticabile perché rende la gestione troppo complessa in quanto richiedono una porzione sequenziale di memoria. Neanche l’opzione