20260224

Gestione della Memoria: Allocazione Dinamica e Pila (Stack)

Slide allocazione memoria lucido #7

Perché l'Allocazione Dinamica?

L'allocazione statica della memoria non è sufficiente nei linguaggi moderni, specialmente quando si usa la ricorsione. A tempo di esecuzione (run-time), possono esistere contemporaneamente più istanze della stessa variabile locale di una procedura. L'allocazione dinamica risolve questo problema.con la ricorsione l'allocazione statica non basta (a runtime possono esistere piu istanze della stessa variabile locale di una procedura)

Il Record di Attivazione (RdA)

Ogni volta che un sottoprogramma viene chiamato a run-time, gli viene assegnata una porzione di memoria chiamata Record di Attivazione (o Frame). L'RdA contiene tutte le informazioni relative a quella specifica istanza (variabili locali, indirizzo di ritorno, ecc.). Anche i blocchi di codice anonimi (come quelli nei cicli o negli if) hanno un loro RdA, seppur più semplice.

La struttura base di un RdA per blocchi anonimi include:

• Puntatore di Catena Dinamica: Punta all'RdA del blocco o sottoprogramma chiamante.
• Variabili Locali: Lo spazio per le variabili dichiarate in quel blocco.
• Risultati Intermedi: Spazio temporaneo per i calcoli.

La Pila (LIFO - Last In, First Out) è la struttura dati naturale per gestire i Record di Attivazione. Questo perché le chiamate di procedura e i blocchi di codice sono sempre annidati uno dentro l'altro, seguendo esattamente la logica LIFO.

Nota: La pila viene utilizzata per l'allocazione dinamica anche in linguaggi che non supportano la ricorsione. Record di attivazione per blocchi anonimi

Fasi di Gestione della Pila

La creazione e distruzione di un RdA è gestita attraverso blocchi di codice specifici:

• Sequenza di chiamata: Codice eseguito dal chiamante subito prima di invocare il sottoprogramma.
• Prologo: Codice eseguito all'inizio del blocco invocato (es. prepara l'RdA).
• Epilogo: Codice eseguito alla fine del blocco invocato (es. pulisce l'RdA).
• Sequenza di ritorno: Codice eseguito dal chiamante subito dopo che la chiamata è terminata.

Indirizzamento tramite Stack Pointer (SP)

Poiché l'indirizzo esatto di un RdA non è noto a tempo di compilazione (compile-time), si utilizza un registro chiamato Stack Pointer (SP) (o Puntatore all'RdA), che punta sempre all'RdA del blocco attualmente attivo.

• Le informazioni dentro l'RdA si leggono tramite un offset rispetto all'SP.
• Formula: Indirizzo del dato = contenuto(SP) + offset (guarda la foto dello stack)
• L'offset è determinabile staticamente dal compilatore.
• Il calcolo SP + offset viene eseguito in modo efficiente con una singola istruzione macchina (load o store).

Blocchi In-line e Catena Dinamica

Nei blocchi annidati (es. un blocco di codice dentro un altro), si utilizza il Link Dinamico (o control link), che è un puntatore al precedente record sullo stack.

• Ingresso nel blocco: Si fa un Push (il link dinamico del nuovo RdA diventa l'attuale SP, e poi l'SP viene aggiornato al nuovo RdA).
• Uscita dal blocco: Si fa un Pop (l'RdA viene eliminato e l'SP torna a puntare al valore salvato nel link dinamico).
• Problema: In prima approssimazione, in un blocco interno, per accedere alle variabili del blocco esterno (non locali), bisogna "risalire" la catena dinamica seguendo i puntatori, poiché non sono raggiungibili con un semplice SP + offset.

Nota: Anche se la teoria prevede un RdA per ogni blocco anonimo, nella pratica molti linguaggi non manipolano la pila per i blocchi anonimi.

• Il compilatore raccoglie in anticipo tutte le dichiarazioni dei blocchi annidati di una procedura.
• Alloca lo spazio per tutte queste variabili in un unico grande RdA all'inizio della procedura.
• Questo comporta un potenziale spreco di memoria (viene allocata memoria per variabili di blocchi che magari non verranno eseguiti), ma garantisce che non ci sia alcuna perdita di efficienza a run-time dovuta ai continui Push e Pop sulla gestione della pila.

Il Record di Attivazione (RdA) per le Procedure

A differenza dei semplici blocchi anonimi, il Record di Attivazione per una procedura (o funzione) è più complesso e strutturato, in quanto deve gestire il passaggio di parametri e il ritorno di valori. I campi tipici (dall'alto verso il basso della pila) sono:

• Puntatore di Catena Dinamica: Punta all'RdA del chiamante (chi ha invocato la procedura).
• Puntatore di Catena Statica: Usato per l'accesso alle variabili non locali in linguaggi con scoping statico annidato.
• Indirizzo di Ritorno: L'istruzione esatta a cui il programma deve tornare una volta terminata la procedura.
• Indirizzo del Risultato: Puntatore alla locazione di memoria (nell'RdA del chiamante) dove verrà salvato il valore calcolato dalla funzione.
• Parametri: I valori passati alla procedura al momento della chiamata.
• Variabili Locali: Spazio per le variabili dichiarate all'interno della procedura.
• Risultati Intermedi: Spazio di lavoro temporaneo (es. per salvare il risultato di una sotto-espressione o di una chiamata ricorsiva prima di completare un calcolo).

Gestione della pila:

Struttura della Pila e Puntatori

La gestione fisica della memoria sulla pila utilizza dei puntatori chiave per orientarsi:

• Puntatore RdA (Frame Pointer / Base Pointer): Punta alla base dell'RdA attualmente in esecuzione. È il punto di riferimento (tramite offset) per trovare variabili locali e parametri.
• Puntatore al Top della Pila (Stack Pointer - SP): Punta all'ultima locazione di memoria occupata sulla pila. Segna il confine con la zona di memoria ancora libera.
• Inizio della pila: L'indirizzo fisso da cui la pila inizia a crescere.

Fasi Dettagliate: Ingresso e Uscita da un Blocco/Procedura

Il ciclo di vita di un RdA si divide in fasi ben precise gestite dal chiamante e dal chiamato. A. Ingresso nel blocco (Sequenza di chiamata e Prologo):

1. Modifica del Contatore di Programma (salvataggio dell'indirizzo di ritorno).
2. Allocazione del nuovo RdA sulla pila (si aggiorna il Puntatore al Top, in quanto la pila cresce).
3. Aggiornamento del Puntatore all'RdA (che ora punterà al nuovo blocco).
4. Passaggio dei parametri.
5. Salvataggio dello stato dei registri della CPU (per poterli ripristinare dopo).
6. Eventuali inizializzazioni.
7. Trasferimento effettivo del controllo al codice della procedura.

B. Uscita dal blocco (Sequenza di uscita ed Epilogo):

1. Restituzione dei valori/risultati dal chiamato al chiamante.
2. Ripristino dei registri della CPU salvati in precedenza.
3. Ripristino del vecchio Puntatore all'RdA (si segue la catena dinamica per tornare all'RdA precedente).
4. Eventuale finalizzazione.
5. Deallocazione dello spazio sulla pila (si arretra il Puntatore al Top).
6. Ripristino del Contatore di Programma all'indirizzo di ritorno salvato.

Esempio di Ricorsione: Il Fattoriale

Prendiamo come esempio la funzione fattoriale: fact(n) { if (n<=1) return 1; else return n * fact(n-1); }

• Quando chiamiamo fact(3), viene creato un RdA.
• Poiché la funzione deve calcolare 3 * fact(2), la moltiplicazione rimane "in sospeso". Viene salvato lo stato e generato un nuovo RdA per fact(2), impilato sopra il precedente.
• Questo processo si ripete fino al caso base fact(1).
• Nota sulla memoria: I nomi delle variabili ("n", "fact(n-1)") non esistono fisicamente in memoria a run-time, ma usiamo gli offset. La complessità spaziale di questa ricorsione standard è lineare $O(n)$, poiché avremo $n$ Record di Attivazione contemporaneamente sulla pila prima di iniziare le moltiplicazioni a ritroso. (Altre funzioni come Fibonacci standard hanno complessità spaziale e temporale peggiore).

C'è un caso speciale molto importante in cui possiamo risparmiare tantissima memoria.

• Se la chiamata ricorsiva è l'ultimissima operazione eseguita dalla funzione prima di ritornare (es. return fact_tail(n-1, accumulatore) senza moltiplicare nulla dopo), si parla di ricorsione in coda.
• In questo caso, non c'è alcun calcolo lasciato "in sospeso" nell'RdA corrente.
• L'ottimizzazione: Invece di allocare un nuovo RdA per la chiamata successiva, il compilatore può riutilizzare lo stesso identico Record di Attivazione, sovrascrivendo i vecchi parametri con i nuovi. Questo abbatte la complessità spaziale da lineare a costante $O(1)$.
• Spesso, per trasformare una ricorsione normale in una ricorsione in coda, il programmatore deve aggiungere un parametro aggiuntivo (un "accumulatore") per portarsi dietro il risultato parziale durante le chiamate.

Allocazione Dinamica con Heap

L'Heap è una regione di memoria in cui i blocchi possono essere allocati e deallocati in momenti arbitrari. È fondamentale per la gestione di dati dinamici.

• Quando è necessario:
  • Quando il linguaggio permette l'allocazione esplicita a run-time (es. tramite puntatori per strutture dati dinamiche come alberi e liste).
  • Per oggetti di dimensione variabile (es. stringhe, insiemi).
  • Per oggetti la cui "vita" non segue una logica LIFO (Last In, First Out) come avviene invece per la Pila (Stack).
• Sfide principali: La gestione non è banale; richiede di bilanciare la velocità di accesso con l'efficienza dello spazio (per evitare la frammentazione).

Gestione dei Blocchi e Frammentazione

L'Heap può essere gestito con blocchi di dimensione fissa o variabile, e utilizza una Lista Libera (LL) per tenere traccia dello spazio disponibile.

• Blocchi a dimensione fissa: L'Heap è diviso in blocchi di ugual misura. L'allocazione fornisce uno o più blocchi contigui; la deallocazione li restituisce alla LL.
• Blocchi a dimensione variabile: All'inizio l'Heap è un unico grande blocco. Durante l'allocazione si cerca un blocco libero della dimensione adatta.

Il problema della Frammentazione:

• Frammentazione Interna: Si verifica quando lo spazio richiesto ($x$) è minore della dimensione del blocco allocato ($y$). Poiché $y > x$, lo spazio in eccesso all'interno del blocco viene sprecato.
• Frammentazione Esterna: C'è abbastanza memoria libera totale per soddisfare una richiesta, ma è inutilizzabile perché divisa in "frammenti" troppo piccoli e non contigui. (Ricorda: la memoria allocata deve essere contigua, ad esempio per accedere a un array tramite offset).
• Soluzione teorica ma inefficace: Spostare tutti gli indirizzi e ricompattare la memoria. È un'operazione computazionalmente troppo costosa.

Gestione della Lista Libera (LL)

Per combattere la frammentazione e ottimizzare le ricerche, si usano diverse strategie per gestire la Lista Libera.

A. Unica Lista Libera: All'inizio contiene un solo blocco grande quanto tutto l'Heap. Ad ogni richiesta, si cerca un blocco grande abbastanza.

• Metodi di ricerca:
  • First Fit: Sceglie il primo blocco grande abbastanza. (Vantaggio: molto veloce).
  • Best Fit: Sceglie il blocco di dimensione più piccola tra quelli grandi abbastanza. (Vantaggio: ottimizza lo spazio).

Nota: Se il blocco scelto è troppo grande, viene diviso in due: la parte usata viene allocata, quella in eccesso resta nella LL. Quando un blocco viene deallocato, se confina con un altro blocco libero, i due vengono "fusi" in un unico blocco più grande.

B. Liste Libere Multiple: Si usano liste separate per blocchi di dimensioni diverse.

• Buddy System (Sistema dei Gemelli): Si usano $k$ liste. La lista $k$ contiene blocchi di dimensione $2^k$. Se serve un blocco $2^k$ e non c'è, si prende un blocco dalla lista $2^{k+1}$ e lo si divide in due metà (i "buddy"). Quando un blocco viene deallocato, se anche il suo buddy è libero, si fondono tornando un blocco di dimensione $2^{k+1}$.
• Fibonacci System: Simile al Buddy System, ma le dimensioni seguono la sequenza di Fibonacci anziché le potenze di 2 (crescono più lentamente, riducendo lo spreco interno).

---

Implementazione delle Regole di Scope (Visibilità)

Come fa il programma a sapere a quale variabile ci stiamo riferendo se ci sono più variabili con lo stesso nome?

• Scope Statico (Risolto a compile-time):
  • Si implementa tramite Catena Statica (puntatori che risalgono ai blocchi annidati nel codice sorgente) o tramite Display (un array di puntatori per velocizzare l'accesso).
• Scope Dinamico (Risolto a run-time):
  • Si implementa tramite A-list (Association List) o Tabella Centrale dell'Ambiente (CRT).

Esempio Pratico: Legame Corretto (Scope Statico)

Consideriamo il seguente pseudo-codice:

{ int x = 10;          // x globale
  void foo() { x++; }  // foo incrementa la x globale
  void fie() {
    int x = 0;         // x locale a fie
    foo();
  }
  // Esecuzione (Main)
  fie();
  foo();
}

Come si comporta in memoria? Il codice della funzione foo deve accedere sempre alla stessa variabile x (quella dichiarata globalmente a valore 10, memorizzata nel Record di Attivazione - RdA - del main).

• Anche se chiamiamo foo dall'interno di fie (dove esiste una x locale a 0), lo scope statico impone che foo "veda" solo l'ambiente in cui è stata definita (il main).
• Il meccanismo: A run-time, in cima alla pila c'è l'RdA di foo (il Puntatore SP guarda lì). Per trovare la x giusta, il sistema non la cerca semplicemente "indietro" nella pila dinamica, ma usa i puntatori di scope per determinare prima qual è l'RdA corretto a cui appartiene quella variabile (in questo caso l'RdA del main). Una volta trovato l'RdA giusto, accede a x tramite l'offset calcolato rispetto a quell'RdA, ignorando totalmente la x locale di fie.

x tramite offset relativo a tale RdA (e non relativo a SP)

Link Dinamico vs Link Statico

Nel Record di Attivazione (RdA), quando si usa lo scope statico, sono presenti due puntatori fondamentali che servono a scopi diversi:

• Link Dinamico: Punta all'RdA della procedura chiamante (quella precedente sulla pila). Dipende esclusivamente dalla sequenza di esecuzione del programma a run-time.
• Link Statico: Punta all'RdA del blocco che contiene testualmente la procedura in esecuzione (il blocco "padre" nel codice sorgente). Dipende esclusivamente dall'annidamento statico del codice scritto dal programmatore.

Esempio

Sequenza di chiamate a run time A, B, C, D, E, C  Risoluzione delle Variabili (Come trovare la 'x' giusta) Se un sottoprogramma (es. $E$) è annidato a livello $k$, la sua catena statica è lunga $k$. Quando il programma deve accedere a una variabile _non locale $x$:

1. Cosa fa il Compilatore: Determina a livello statico a quale blocco appartiene la variabile (es. "la $x$ si trova 2 livelli più in alto"). Associa al nome della variabile un indice $h$:
   • $h=0$: Variabile locale (trovata nell'RdA corrente).
   • $h>0$: Variabile non locale definita $h$ blocchi sopra. Il compilatore dice al programma quanti passi fare, ma non conosce l'indirizzo esatto in memoria.
2. Cosa succede a Run-time: Il programma usa il Link Statico per "risalire" di $h$ RdA. Una volta raggiunto l'RdA corretto (es. risalendo dal blocco $E$ al blocco $C$, e poi al blocco $A$), utilizza un offset per accedere fisicamente alla variabile.

Nota: Se un sottoprogramma è annidato a livello k, allora la catena è lunga k

Esempio Pratico: Se la funzione $A$ è definita nel main, il suo link statico punterà sempre all'RdA del main. Se $A$ modifica $x$, modificherà sempre la $x$ del main, indipendentemente da chi ha chiamato $A$ a run-time.

{int x;
void A(){
    x=x+1;}
void B(){
    int x;
    void C (int y){
        int x;
        x=y+2; A();
    }
    x=0; A(); C(3);
}
x=10;
B();
}

(non si capisce molto)

• la x che viene modificata e' sempre quella del main visto che viene modificata da A e il puntatore di catena statica di A punta al main. Le altre x non vengono modificate da A.
• C modifica la propria x (visto che la dichiara ed e'quindi locale)

Quando una procedura $Ch$ (chiamante) invoca una procedura $P$ (chiamato), è il chiamante che deve determinare e passare il Link Statico al chiamato. Affinché $Ch$ possa chiamare $P$, $P$ deve essere nel suo scope visibile. Ci sono due casi, basati sulla distanza di annidamento ($k$) tra $Ch$ e $P$:

• Caso 1 ($k=0$): $P$ è definito immediatamente dentro $Ch$.
  • Soluzione: $Ch$ passa a $P$ semplicemente il proprio Stack Pointer (SP). L'RdA di $Ch$ diventa il Link Statico di $P$.
• Caso 2 ($k>0$): $P$ è definito in un blocco $k$ passi "fuori" da $Ch$ (cioè $Ch$ e $P$ condividono un blocco padre o nonno comune).
  • Soluzione: $Ch$ risale la propria catena statica di $k$ passi per trovare l'RdA del blocco in cui è definito $P$, e passa quel puntatore come Link Statico a $P$.

Nota di Visibilità: Un blocco non può chiamare un altro blocco "fratello" se non lo "vede" (es. se $B$ e $C$ sono definiti dentro $A$, e $D$ è definito dentro $C$, il blocco $B$ non può chiamare $D$ direttamente).

Ripartizione dei Compiti e Costi Computazionali

L'implementazione dello scope statico divide il lavoro e introduce dei costi a run-time:

• Compilatore: * Associa la distanza di chiamata ($k$) ad ogni invocazione di funzione.
  • Associa la distanza di annidamento ($h$) ad ogni accesso a variabile.
• Sequenza di chiamata / Prologo (Run-time):
  • Risale materialmente la catena statica e inizializza il puntatore per il nuovo RdA.
• Costi a Run-time:
  • Costo di chiamata: Per ogni chiamata a funzione, bisogna fare $k$ "salti" sui puntatori della catena statica.
  • Costo di accesso a variabile non locale: Per ogni lettura/scrittura, bisogna fare $h$ "salti" nella catena statica (più costoso rispetto all'accesso di una variabile locale, che richiede 0 salti).Compilatore: