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.

4. 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)

Record di attivazione per scoping statico Link dinamico: – puntatore all’RdA precedente sulla pila (RdA del chiamante) • Link statico: – puntatore all’RdA del blocco che contiene immediatamente il testo del blocco in esecuzione • Osserva: – link dinamico dipende dalla sequenza di esecuzione del programma – link statico dipende dall’annidamento statico (nel testo) delle dichiarazioni delle procedure

Catena Statica: esempio Sequenza di chiamate a run time A, B, C, D, E, C le linee tratteggiate sono link statici

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

se sono in e e sto cercando una var x non locale allora vado in c e poi vado in a questo grazie ai link statici (questi puntatori sono determinati a runtime) Esempio

{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();
}

Struttura main con dentro a e b e b con dentro c

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)

il compilatore dice di risalire di 1 il record di attivazione. A lo fa e trova a x del main (con un offset)

se in C avessi la variabile pippo chee e' definita nel main il compilatore mi direbbe che pippo e' definito in main (2 livelli sopra) e quindi quando devo manipolarla o chiamarla salgo due livelli e ne uso il valore

Il compilatore sa dove sono dichiarate le variabili ma non sa la loro posizione a runtime (quindi ci dice solo quanto andare in su ma il dove va deciso a runtime grazie alla catena statica)

Dal punto di vista del supporto a run time Come viene determinato il link statico del chiamato?

es sopra sono nel main, chiamo B devo inizializzre il puntatore di catena statica di B, so che B e' inizializzato dentro al main quindi inizializzo il suo puntatore al main (me) Ora B chiama A, come posso inizializzare il suo puntatore? B sa che A e' allo stesso livello di annidamento di A e quindi gli basta risalire di (0) livelli e passare il puntatore a A. In generale o X e' inizializzato dentro a A (e quindi il suo indirizzo e' A) oppure Si calcola livello di annidamento di A - X e si risalgono i A-X livelli e si assegna l'indirizzo a X

e'il chiamante a determinare il link statico del chiamato Info a disposizione del chiamante:

• annidamento statico dei blocchi (determinata dal compilatore)
• proprio RdA

Come determinare il puntatore di Catena statica (CS) il chiamante Ch conosce l'annidamento dei blocchi:

• quando Ch chiama P sa se la definizione di P e':
  • immediatamente inclusain Ch (k=0)
  • in un blocco k passi fuori da Ch

– nessun altro caso possibile: • perché P deve essere in scope! – nel caso a destra: • chiamate: A, B, C, D, E, C – con i dati di catena statica: • A; (B,0); (C,1); (D,0); (E,1); (C,2)

Se k=0: – Ch passa a P il proprio SP •Se k>0: – Ch risale la propria catena statica di k passi e passa il puntatore così determinato

Nota: Se B chiamasse D non potrebbe farlo perche' non lo puo' vedere.

Ripartizione dei compiti Compilatore:

• associa l'informazione k ad ogni chiamata
• associa ad ogni nome un indice h:
  • h=0: nome locale
  • h diverso da 0: nome non locale definito h blocchi sopra
• sequenza chiamata/prologo
  • risale la catena statica
  • inizializza il puntatore di catena statica
• Costi:
  • per ogni chiamata: k passi di catena statica
  • ad ogni accesso ad una variabile non locale:(h passi di catena statica in piu rispetto all'accesso ad un locale)