Gestione della memoria (da slide 7)

Allocazione dinamica (pila)

con la ricorsione l'allocazione statica non basta (a runtime possono esistere piu istanze della stessa variabile locale di una procedura) ogni istanza di un sottoprogramma a run time ha una porzione di memoria detta record di attivazione (o frame) contenente le informazioni relative alla specifica istanza (indirizzo di ritorno) Analogalmente ogni blocco ha un suo record di attivazione (piu semplice) La pila (lifo) e' la struttura e' la struttura dati naturale per gestire i recordd did attivazione perche le chiamate di procedura ed i blocchi sono annidati uno dentro laltro

La pila puo essere usata anche in un linguaggio senza ricorsione

Record di attivazione per blocchi anonimi

Allocazione dinamica con pila

La gestione della pila e' compiuta mediante:

• sequenza di chiamata (codice eseguito dal chiamante immediatamente prima della chiamata)
• prologo (codice eseguito all'inizio del blocco)
• epilogo (codice eseguito alla fine del blocco)
• sequenza di ritorno (codice eseguito dal chiamante immediatamente dopo la chiamata)

Indirizzo di un RdA non e' noto a compile-time Il puntatore RdA o SP punta al RdA del blocco attiva Le info contenute in un RdA sono accessibili per offset rispetto allo SP (indirizzo-info = contenuto(SP)+offset) offset determinabile staticamente dal compilatore Somma SP+offset eseguita con unica istruzione macchina load o store

Record di attivazione per blocchi in-line Link dinamico (o control link) puntatore al precedente record sullo stack ingresso nel blocco: push (link dinamico del nuovo Rda := SP – SP aggiornato a nuovo RdA) Uscita dal blocco: Pop – Elimina RdA puntato da SP – SP := link dinamico del Rda tolto dallo stack

In realtà… • In molti linguaggi non c’è manipolazione della pila per i blocchi anonimi ! • Tutte le dichiarazioni dei blocchi annidati sono raccolte dal compilatore • Allocazione di spazio per tutte • Potenziale spreco di memoria, ma… • Nessuna perdita di efficienza per la gestione della pila

Record di attivazione per procedure

Gestione della pila:

Esempio

non e' possibile determinare prima il numero massimo di record di attivazione Se la chiamata ricorsiva e' lultima cosa che viene fatta es. else return fact(n-1) non devo generare un nuovo record di attivazione. Si chiama ricorsione in coda. Posso usare un solo record did attivazione per la ricorsione in coda. e'possibilie trasformare una chiamata ricorsiva in una ricorsiva con ricorsione in coda (spesso aggiungendo un paramentro accumulatore che salvi il risultato) La complessita in termini di spazio e' lineare con n (fib e' esponenziale)

Gestione pila: ingresso in blocco

• modifica contatore programma
• allocazione RdA sulla pila (modifica puntatore a top (visto che e' una pila il top e' lultimo elemento))
• modifica del putatore al TdA
• passaggio dei parametri
• salvataggio dei registri
• eventuali inizializzazioni
• trasferimento del controllo

Gestione della pila: uscita da blocco • Sequenza di uscita ed epilogo si dividono i seguenti compiti: – Restituzione dei valori dal chiamato al chiamante, oppure il valore calcolato dalla funzione – Ripristino dei registri • In particolare deve essere ripristinato il vecchio valore del puntatore al RdA. – Eventuale finalizzazione – Deallocazione dello spazio sulla pila – Ripristino del valore del contatore programma

Allocazione dinamica con heap

Heap: regione di memoria i cui sotto blocchi possono essere allocati e deallocati in momenti arbitrari Necessario quando il linguaggio permette allocazione esplicita di memoria a run time (puntatotri e strutture dati dinamiche tipo alberi e liste) Oggetti di dimensione variabili (stringhe, insiemi) Oggetti la cui vita non ha un regime definito a priori (cioe' con vita non lifo) La gestione dell heap non e'banale (gestione efficiente dello spazio: frammentazione e Velocita' di accesso)

Heap: blocchi di dimensione fissa Heap suddiviso in blocchi di dimensione fissa (e abbastanza limitata: qualche parola) In origine: tutti i blocchi collegati nella lista libera

Heap: blocchi di dimensione fissa • Allocazione di uno o più blocchi contigui • Deallocazione: restituzione alla lista liber

Problema: frammentazione della memoria

Heap: blocchi di dimensione variabile Inizialmente unico blocco nello heap Allocazione: determinazione di un blocco libero della dimensione opportuna Deallocazione: restituzione alla lista libera

Problemi:

• le operazioni devono essere efficienti
• evitare lo spreco di memoria (frammentazione interma e esterna)

Frammentazione Interna: lo spazio richiesto e' x: - viene allocato un blocco di dimensione y dove y>x - spreco dello spazio Esterna:

• ci sarebbe lo spazio necessario ma e' inusabile perche diviso in pezzi troppo piccoli La memoria deve essere contigua (per accedere in modo efficiente ad un array lo si fa tramite offset)

Cosa posso fare? Spostare tutti gli indirizzi e ricompattare il tutto? molto costoso

Gestione della lista libera: unica lista Inizialmente contiene un solo blocco, della dimensione dello heap Ad ogni richiesta di allocazione:cerca blocco di dimensione opportuna, due modi di ricerca

• first fit: primo blocco grande abbastanza (molto veloce)
• best fit: quello di dimensione più piccola, grande abbastanza (molto efficiente)

Se il blocco scelto è molto più grande di quello che serve, viene diviso in due e la parte inutilizzata è aggiunta alla LL • Quando un blocco è de-allocato, viene restitutito alla LL (se un blocco adiacente è libero, i due blocchi sono ``fusi’’ in un unico blocco).

Liste libere multiple Per blocchi di dimensione diversa (la ripartizione dei blocchi fra le varie liste puo essere statica o dinamica (buddy system o fibonacci system)) Buddy system: k liste; la lista k ha blocchi di dimensione $2^k$

• se richiesta allocazione per blocco di $2^k$ è tale dimensione non è disponibile, blocco di 2k+1 diviso in 2
• se un blocco di 2k e’ de-allocato è riunito alla sua altra metà (buddy), se disponibile

Fibonacci simile, ma si usano numeri di Fibonacci invece di potenze di 2 (crescono più lentamente)

Implementazione delle regole di scope • Scope statico – catena statica – display • Scope dinamico – A-list – Tabella centrale dell’ambiente (CRT)

Come si determina il legame corretto?

{int x=10;
void foo () {
x++;
}
void fie (){
int x=0;
foo();
}
fie();
foo();
}

Il codice di foo deve accedere sempre alla stessa variabile x • Tale x è memorizzato in un certo RdA (in questo caso in quello del main) • In cima alla pila abbiamo il RdA di foo (perché foo è in esecuzione)

• Determina prima il corretto RdA dove trovare x •Accedi a 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)