memoria gestita staticamente:
allocata dal compilatore prima dell’esecuzione in una zona
fissa della memoria (stabilita dal compilatore)
– variabili globali
– istruzioni del codice oggetto
– costanti
– tabelle del compilatore per il supporto a run-time del
linguaggio (gestione nomi, type checking, garbage collection)
– informazioni locali alle procedure (se non è supportata la
ricorsione): variabili locali, parametri indirizzo di ritorno
memoria gestita dinamicamente (pila a run-time);
blocchi in-line
A: {
int a = 1;
int b = 0;
B: { int c = 2;
int b = 3;
}
b = a+1;
}
push a; push b
push c; push b
pop
pop
record di attivazione (frame):
lo spazio di memoria allocato sulla pila e dedicato a un
blocco in-line (o a una procedura attivata);
per i blocchi in-line contiene:
– risultati intermedi (risultati senza nome esplicito)
– variabili locali (interne al blocco, dimensione nota)
– puntatore di catena dinamica (link dinamico o di controllo;
punta al precedente RdA sulla pila)
per le procedure contiene:
– risultati intermedi (risultati senza nome esplicito)
– variabili locali (interne al blocco e di dimensione nota
non array dinamici, per esempio)
– puntatore di catena dinamica (link dinamico o di controllo;
punta al precedente RdA sulla pila)
– puntatore di catena statica (informazioni per gestire lo scope
statico)
– indirizzo di ritorno, indirizzo del risultato;
– parametri;
i nomi sono memorizzati nel RdA ?
offset rispetto all’indirizzo del blocco in cui la variabile è memorizzata
gestione a run-time della pila di sistema
il compilatore inserisce frammenti di codice prima o dopo la
chiamata di procedura (o di un blocco)
– sequenza di chiamata: codice aggiunto al chiamante ed
eseguito prima della chiamata di procedura e dopo la
terminazione della procedura chiamata
– prologo: codice aggiunto al chiamato ed eseguito subito dopo
la chiamata
– epilogo: codice aggiunto al chiamato ed eseguito al termine
della procedura chiamata
come sono distribuite queste attività ?
sequenza di chiamata (chiamante) e prologo (chiamato)
– modifica del program counter (e salvataggio del vecchio
valore per mantenere l’indirizzo di ritorno)
– allocazione spazio sulla pila (e modifica del puntatore alla
memoria libera sulla pila)
– modifica del puntatore al (nuovo) RdA
– passaggio dei parametri (fatto dal chiamante)
– salvataggio dei registri (fra cui il vecchio puntatore al RdA)
– esecuzione codice di inizializzazione
epilogo (chiamato) e sequenza di chiamata (chiamante)
– ripristino del program counter
– restituzione dei valori (parametri o valore funzione)
– ripristino registri (fra cui il vecchio puntatore al RdA)
– esecuzione codice di finaizzazione
– deallocazione spazio sulla pila (il RdA della procedura
terminata è rimosso dalla pila)
di quali strutture dati ho bisogno per implementare questa gestione?
cosa succede se posso allocare e deallocare esplicitamente la
memoria?
memoria gestita dinamicamente (heap)
int *p, *q;
p = malloc(sizeof(int));
q = malloc(sizeof(int));
*p = 0;
*q = 1;
free(p);
free(q):
le operazioni di deallocazione della
memoria sono fatte nello stesso
ordine di quelle di allocazione;
no gestione LIFO
heap:
zona di memoria usata per gestire allocazioni esplicite di
memoria (con blocchi a dimensione fissa o variabile)
heap con blocchi di dimensione fissa (lista libera)
heap con blocchi di dimensione variabile
se il linguaggio permette l’allocazione a run-time di
memoria di dimensione variabile, la LL non è adeguata
due esigenze contrastanti:
– migliorare l’occupazione della memoria (frammentazione
interna ed esterna)
– velocizzare la gestione dello heap
tecniche di allocazione:
– unica lista libera
– liste libere multiple
unica lista libera
- un unico blocco di memoria contiene l’intero heap; se è richiesta
l’allocazione di n parole di memoria, il puntatore avanza di n (analogo
per le richieste successive)
- i blocchi deallocati sono collegati in una lista libera; quando lo heap
finisce si passa allo spazio deallocato, in due modi:
utilizzando direttamente la lista libera:
si cerca nella lista un blocco con dimensione adeguata, seguendo due
principi:
first fit (miglior tempo di gestione)
best fit (migliore occupazione di memoria)
compattando la memoria libera:
tutti i blocchi attivi spostati all’estremità dello heap (si può fare
sempre?)
liste libere multiple
- più liste libere, ognuna delle quali con blocchi di dimensioni diverse
se è richiesta l’allocazione di n parole di memoria, è selezionata la lista
che contiene blocchi di dimensione appropriata
- le dimensioni dei blocchi possono essere statiche o dinamiche
buddy system
le dimensioni dei blocchi sono potenze di 2; richiedo un blocco pari a n;
se k è tale che 2kn,
allora si cerca un blocco libero in lista 2k;
altrimenti, si prende un blocco in 2k+1,
si divide in due,
uno è occupato e l’altro entra nella lista 2k;
quando un blocco è liberato, si cerca il suo compagno e si riunificano
heap di Fibonacci
come sopra, ma con numeri di Fibonacci (che crescono di meno)
implementazione regole di scope
(come risolvere un riferimento non locale)
scope statico o scope annidato più vicino
l’ambiente in qualsiasi punto e in qualsiasi momento dipende
SOLO dalla struttura sintattica del programma (il RdA
collegato dal puntatore di catena dinamica NON è il record in
cui cercare per risolvere un riferimento non locale)
scope dinamico
l’associazione valida per un nome X, in un punto P di un
programma, è la più recente associazione creata (in senso
temporale) per X che sia ancora attiva quando il flusso di
esecuzione arriva a P
scope statico: la catena statica
A: {
int y = 0;
B: {
int x = 0;
void pippo(int n) {
x = n+1;
y = n+2;
}
C: { int x = 1;
pippo(2);
write(x);
}
}
write(x);
}
scope statico:
x (non locale in pippo) è quella
dichiarata nel blocco B, non in C
scope statico: la catena statica
scope statico: la catena statica
con la sequenza di chiamate A B C D E C, si ha
la gestione della catena statica è fatta nella sequenza di
chiamata, nel prologo e nell’epilogo;
il chiamante calcola il puntatore di catena statica del
chiamato e lo passa al chiamato; due casi:
– chiamato all’interno del chiamante: il chiamante passa al
chiamato il puntatore al proprio RdA
– chiamato all’esterno del chiamante: il chiamante calcola il
puntatore di catena statica deferenziando k+1 volte il proprio
puntatore di catena statica, con k = distanza di livello di
annidamento fra chiamato e chiamante (nota a compile-time)
il chiamato riceve il puntatore di catena statica e lo
memorizza nel proprio RdA
la tabella dei simboli contiene
- i livelli di annidamento di blocchi o procedure
- in generale, i nomi usati nel programma (il tipo e il
numero che indica lo scope che contiene la dichiarazione
per tale nome)
quindi, si può calcolare a compile-time la distanza fra lo
scope della chiamata e lo scope della dichiarazione
come risolvere riferimenti non locali senza fare ricerche
sulla pila?
basta risalire la catena statica di un numero di link pari
alla distanza dichiarazione-chiamata
si può risolvere un riferimento non locale completamente
a compile-time?
no, non sappiamo staticamente il numero di RdA sulla
pila
scope statico: la catena statica
A: {
int y = 0;
B: {
int x = 0;
void pippo(int n) {
x = n+1;
y = n+2;
}
C: { int x = 1;
pippo(2);
write(x);
}
}
write(x);
}
il compilatore sa che per usare y
deve risalire di due blocchi; basta
memorizzare a compile-time questo
numero e usarlo a run-time.
scope statico: il display
nome non locale,
dichiarato in un blocco esterno di k livelli
 k accessi alla memoria (a run-time) per scorrere la
catena statica e trovare il RdA in cui è dichiarato
display (riduce a 2 il numero di accessi):
– vettore di tanti elementi quanti sono i livelli di annidamento
dei blocchi
– l’elemento k-esimo del display contiene il puntatore al RdA
di livello di annidamento k attualmente attivo
– se cerco un oggetto non locale dichiarato in un blocco di
livello k, accedo alla posizione k del vettore e seguo il
puntatore
entrando in (o uscendo da) una procedura di livello k,
occorre:
– aggiornare il display in posizione k con il valore del
puntatore al RdA del chiamato
– salvare il vecchio valore (nel RdA del chiamato)
due casi:
– chiamato all’interno del chiamante: se il chiamante è a
livello n, entrambi condividono il display, a cui si aggiunge un
nuovo valore in posizione n+1;
– chiamato esterno al chiamante: se il chiamante è a livello n
e il chiamato a livello m (m<n), essi condividono il display
fino alla posizione m-1; l’elemento m è aggiornato con il
puntatore al RdA del chiamato, ma il vecchio valore deve
essere salvato, e servirà quando il chiamato termina;
scope dinamico
per risolvere un riferimento a un nome x si risale la pila
fino a trovare il blocco che contiene x;
le associazioni nome-oggetto sono memorizzate nel RdA
scope dinamico: lista di associazioni
le associazioni nome-oggetto possono essere
memorizzate in una A(ssociation)-list, gestita come una
pila
due inconvenienti:
– occorre memorizzare i nomi in strutture presenti a tempo di
esecuzione (al contrario dello scope statico);
•
•
è ovvio per la A-list
anche per il caso RdA, perche’ uno stesso nome può
essere memorizzato in posti diversi in diversi RdA
– inefficienza della ricerca a run-time
tabella centrale dell’ambiente (limita i due inconvenenti):
tutti i blocchi del programma fanno riferimento a una sola
tabella (CRT), che contiene:
– tutti nomi usati nel programma, e per ogni nome
– un flag che indica se l’’associazione per il nome è attiva
– un puntatore alle informazioni sull’oggetto
– i nomi hanno posizioni fisse in tabella (perché tutti gli
identificatori usati nel programma sono noti), quindi l’accesso
a run-time è costante
– se dal blocco A si entra in B, la CRT è modificata per
descrivere il nuovo ambiente di B; le associazioni deattivate
devono essere salvate (per quando esco da B)
– a ogni nome della CRT è associata una pila che contiene
nella prima posizione l’associazione valida e (nelle
successive) quelle disattivate
– oppure si usa una sola pila nascosta per memorizzare tutte
le associazioni deattivate per ogni nome
usando la CRT (con pila nascosta o no) per conoscere
una associazione dell’ambiente occorre:
– accedere alla tabella (diretto)
– accedere alla memoria con il puntatore trovato nella tabella
– non serve nessuna ricerca a run-time