Gestione della memoria - users.dimi.uniud.itpietro.digianantonio/linguaggi/lucidi...Uso della...

Gestione della memoria

Stack di attivazione, Heap

Stack di attivazione, Heap Gestione della memoria 1 / 1

La gestione della memoria

Come il compilatore-interprete, organizza i dati necessari all’esecuzionedel programma.Alcuni aspetti organizzativi già visti nel corso in assemblyCodici macchina

scritti a mano ogenerati da compilatori

strutturano la memoria in memoria in modo simile.


Uso della Memoria RAM

Nell’uso tipico, codice ARM prevede divisione della memoria neiseguenti intervalli consecutivi.

0 − 0xFFF: riservata al sistema operativo.0x1000 − xx : codice programma (.text), costanti (.data)yy - zz : heap per dati dinamici (liste, alberi)xx − yy : stack per chiamate di procedura, stack di attivazione.

Il registro r13, sp, (stack pointer) punta alla cima dello stackIl registro r11, fp, (frame pointer) punta al “frame” della procedura inesecuzione.


Stack di attivazione

Le procedure usano una struttura dati a pila:

ad ogni chiamata, allocato dello spaziospazio de-allocato all’uscita dalla procedura

Formato di un elemento dello stack:


Tipi di allocazione della memoria

Tre meccanismi di allocazione della memoria:

statica: memoria allocata a tempo di compilazionedinamica: memoria allocata a tempo d’esecuzione, divisa in:

pila (stack): oggetti allocati con politica LIFOheap: oggetti allocati e de-allocati in qualsiasi momento


Allocazione statica

Gli oggetti hanno un indirizzo assoluto, mantenuto per tutta ladurata dell’esecuzione.Solitamente sono allocati staticamente:

variabili globalicostanti determinabili a tempo di compilazionetabelle usate dal supporto a run-time (per type checking, garbagecollection, ecc.)

In casi particolari, può essere utilizzata per tutti i dati, in questocaso:


Allocazione statica di programma principale eprocedure.

Ad ogni variabile (locale o globale) assegnato un indirizzo univoco.Le variabili locali di una procedura mantengono il valore anchedopo la fine della procedura.


Svantaggi della allocazione statica completa.

Non permette ricorsione:

Le diverse chiamate ricorsive di una stessa procedura devonoavere ciascuna memoria peruna copia delle variabili locali, modificabili in ogni istanza,informazioni di controllo (indirizzo di ritorno)

Forza ad usare più spazio del necessario:

costringe ad allocare spazio per tutte le variabili di tutto il codice,di volta in volta, solo una piccola parte di queste sono attiva (quelleassociate alle procedure aperte).

Non permette strutture dati dinamiche.


Allocazione dinamica: stack di attivazione.

Per ogni istanza di un sottoprogramma a run-time abbiamo unrecord di attivazione (RdA o frame),spazio di memoria per contenere:

risultati intermedisalvataggio dei registri

variabili localiparametri in ingresso e in uscitaindirizzo di ritornolink dinamico (al frame della procedura chiamante)link statico (al frame della procedura genitore) (non semprepresente)

Analogamente, ogni blocco, con dichiarazione, può avere un suorecord di attivazione (più semplice, meno informazioni di controllo)

risultati intermedivariabili localilink dinamico (al frame della procedura chiamante)

Una Pila (LIFO) è la struttura dati naturale per gestire i RdA.Stack di attivazione, Heap Gestione della memoria 9 / 1

Esempio

{ int x=0;int y=x+1;

{ int z=(x+y)*(x-y);};

};

Push record con spazio per x, ySetta valori di x, y

Push record blocco internoSetta valore per zPop record per blocco interno

Pop record per blocco esterno

Nota

nel blocco interno l’accesso alle variabili non locali x e y non puòavvenire per (FP)+offset: si deve risalire la catena dinamica.


Accesso ai dati, gestione.

Per accedere ai variabili locali del blocco in esecuzione, uso il FramePointer,

Frame Pointer (FP):punta all´indirizzo base dell’ultimo frame (RdA)i dati dell’ultimo frame sono accessibili per offset rispetto allo FP:

indirizzo-dato = contenuto(FP)+offsetoffset determinabile staticamente

Per la gestione dello stack di attivazione uso anche:

Stack Pointer (SP)punta alla fine della pila, primo spazio di memoria disponibilein Assembly usavamo solo lo SP (usavamo frame di dimensionicostanti e ridotte)

L’accesso ai dati non locali alla procedura

Link dinamico (o control link) (Puntatore di Catena Dinamica)puntatore al precedente record sullo stack


Gestione della pila


Gestione dei blocchi in-line

Operazioni per la gestione (aggiornamento di FP, SP e link Dinamici)

Ingresso nel blocco: Pushallocazione dello spazio e scrittura dei link

link dinamico del nuovo RdA := FPFP = SPSP = SP + dimensione nuovo RdA

Uscita dal blocco: Pop, Elimina l’ultimo RdArecupera spazio e ripristina puntatori.

SP = FPFP := link dinamico del RdA tolto dallo stack


In realtà. . .

In molti linguaggi si preferisce evitare l’implementazione a pila per iblocchi anonimi:

tutte le dichiarazioni dei blocchi annidati sono raccolte dalcompilatoreallocazione di spazio per tutte.Potenziale spreco di memoria, ma. . .nessuna perdita di efficienza per la gestione della pila


Esempio di ricorsione, stack di attivazioneindispensabile.

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

}}

Nel RdA troviamo;

parametri ingressi: nparametri in uscita - risultato: fact(n). . . .

Tanti RdA quanto il valore iniziale di n


Allocazione dinamica con heap

Heap: zona di memoria le cui parti (blocchi) possono essereallocate (e de-allocate) a seconda della necessitàNecessario quando il linguaggio permette:

tipi di dato dinamicioggetti di dimensioni variabilioggetti che sopravvivono alla procedura che gli ha creati.

La gestione dello heap, problemi:

gestione efficiente dello spazio: frammentazionevelocità di ricerca spazi liberi


Heap suddiviso in blocchi di dimensione fissa

in origine: tutti i blocchi collegati nella lista liberaallocazione di uno o più blocchi contiguide-allocazione: restituzione alla lista liberail vincolo della dimensione fissa, rende il meccanismo troppo rigido.


Heap: blocchi di dimensione variabile

inizialmente unico blocco nello heapallocazione: determinare un blocco libero della dimensioneopportuna

che viene diviso in:

parte assegnataresto blocco libero

de-allocazione: restituzione alla lista libera

Problemi:

le operazioni devono essere efficientievitare lo spreco di memoria

frammentazione internaframmentazione esterna


Frammentazione - analogie

Problemi analoghi alla gestione memoria virtuale tramitesegmentazione, con analoghe soluzioni.

su uno spazio di memoria contiguovengono assegnati blocchi di dimensione variabileche, dopo un certo tempo, possono liberarti.


Frammentazione

Frammentazione interna: lo spazio richiesto è X,

viene allocato un blocco di dimensione Y > X,lo spazio Y-X è sprecato,meno problematica della:

Frammentazione esterna: ci sarebbe lo spazio necessario ma èinusabile perché suddiviso in “pezzi” troppo piccoli


Gestione della lista libera: unica lista

Ad ogni richiesta di allocazione: cerca blocco di dimensioneopportuna

first fit: primo blocco grande abbastanzabest fit: quello di dimensione più piccola, tra quelli sufficienti.

Se il blocco scelto è molto più grande di quello che serve vienediviso in due e la parte inutilizzata è aggiunta alla LLQuando un blocco è de-allocato, viene restituito alla LL (se unblocco adiacente è libero i due blocchi sono “fusi” in un unicoblocco).


Gestione lista libera: First fit o Best Fit ?

Solita situazione conflittuale:

First fit: più veloce, occupazione memoria peggioreBest fit: più lento, occupazione memoria migliore


Gestione della lista libera: più liste

Con unica LL costo allocazione lineare nel numero di blocchi liberi.Per migliorare liste libere multiple: ogni lista contiene blocchi liberidi dimensione simile.

Buddy system: n liste;

la lista k-esima ha blocchi di dimensione 2k

se si desidera un blocco di dimensione 2j , e la lista relativa è vuota:

blocco, nella lista successiva, di dimensione doppia, viene diviso in2,la procedura si ripete ricorsivamente.

quando un blocco di 2k e’ de-allocato, viene è riunito alla sua altrametà (Buddy), se disponibile

Fibonacci simile, ma i blocchi hanno dimensioni numeri di Fibonacci


Implementazione delle regole di scope.

Come recuperare dati non locali nello stack di attivazione?

Scope statico:

catena staticadisplay

Scope dinamico:

A-listTabella centrale dell’ambiente (CRT)


Scoping statico: come si determina il legame corretto?

Consideriamo il programma:

{int x=10;void incx () {

x++;}

void foo (){int x = 0;incx();}

foo();incx();}

incx viene chiamato due volte: indirettamente tramite foo,direttamente;incx accede sempre alla stessa variabile xx è memorizzato in un certo RdAproblema: determinare di quanti RdA scendere nella pila,

valore non univoco, dipende dalla chiamata a incx.


Scoping statico.

I legami validi sono quelli definiti:nella procedura correntenella procedura genitorenel genitore del genitore . . . .

In D, i legami validi sono quelli definiti in D, C, Ele altre dichiarazioni non hanno effetto


Link statico.

Soluzione al problema: costruisco una lista dei RdA con i legami validi,

attraverso un link statico:ogni RdA contiene un puntatore al RdA del genitore.

Nota: per ogni variabile x non locale ad una procedura D:

il numero di link statici da seguire per trovare il RdA contenente xresta costante, in ogni ricerca.la posizione di x nel RdA così trovato è fissa:non serve memorizzare il nome delle variabili negli RdA,

Riassumendo:

link dinamico (procedura chiamante) dipende dalla sequenza diesecuzione del programmalink statico (procedura genitore) dipende dalla struttura delledichiarazioni di procedure


Esempio: programma con struttura a blocchi

Sequenza di chiamate A, B, C, D, E, C, genera la pila:


Esempio esecuzione.

{int x = 10;void A(){

x=x+1;}void B(){

int x = 5;void C (){

x=x+2; A();}A(); C();

}B();

}


Come si determina il link statico?

La procedura chiamante Ch determinare il link statico della procedurachiamata P.Il chiamante Ch “conosce” l’annidamento dei blocchi:

quando Ch chiama P sa se la definizione di P è:

nelle dichiarazioni di Ch (k=0);nelle dichiarazioni di un n-esimo avo di Ch, k = nin altre posizione P non sarebbe visibile


Esempio di valutazione di k

Nel caso di un programma con struttura

La procedura C, può chiamare tutte la altre con valore di K(A,2) (B,1); (D,0); (E,0)


Come si determina il link statico?

Se k=0:

Ch passa a P, come link statico, il Frame Pointer attuale.

Se k>0:

Ch scende la propria catena statica di k passi, passa il puntatorecosì determinato


Tentativo di ridurre i costi: il display

L’accesso a variabili non locali, comporta la scansione della catena dilink statici,

costo proporzionale alla profondità.si può ridurre questo costo ad un singolo accesso usando ildisplay:

La sequenza di link della Catena Statica vengono raggruppati in unsingolo un array (detto display):

i-esimo elemento dell’array: puntatore al RdA sottoprogramma

di livello di annidamento statico i,ultima istanza attivata (se, per ricorsione, ci sono più istanza)

se il sottoprogramma corrente è annidato a livello i,

un oggetto in uno scope esterno di h livelli, viene letto usandol´elemento nel display in posizione i - h


Come si aggiorna il display

Quando Ch chiama P:salva nel RDA il Display corrente,aggiorna il Display aggiungendovi, in coda, il proprio Frame Pointer,

La procedura chiamata P:in base alla sua profondità statica, decide la porzione di Display dautilizzare

Terminato P, Ch ripristina il Display originario.Stack di attivazione, Heap Gestione della memoria 34 / 1

Nella pratica

Nella statistica del codice rare lunghezze catena statica > 3, displaypoco usato nelle implementazioni moderne.


Scope dinamico

Con scope dinamico l’associazione nome-oggetto denotabili dipende

dal flusso del controllo a run-timedall’ordine con cui i sottoprogrammi sono chiamati.

La regola generale è semplice:

il legame valido per il nome nè determinato dall’ultima dichiarazione del nome n eseguita.


Implementazione ovvia

memorizzare i nomi negli RdA

con scoping statico, non è necessario memorizzare i nomi.

ricerca per nome scendendo nello stack di attivazione.


Esempio - Programma con chiamate A,B,C,D


Variante: Association List: A-list

Le associazioni sono raggruppate in una struttura apposita,una lista di legami validiaggiornata con lo SdA


Costi delle A-list

Molto semplice da implementareOccupazione memoria:

nomi presenti esplicitamente

Costo di gestione

ingresso/uscita da blocco

inserzione/rimozione di blocchi sulla pila

Tempo di accesso

sempre lineare nella profondità della A-list

Possiamo ridurre il tempo d’accesso medio, aumentando il tempo diingresso/uscita da blocco. . .


Tabella centrale dei riferimenti, CRT

Evita le lunghe scansioni della A-listUna tabella mantiene tutti i nomi distinti del programma

se nomi noti staticamente accesso in tempo costantealtrimenti, accesso hash

Ad ogni nome è associata la lista delle associazioni di quel nome:

la più recente è la primale altre, disattivate e per uso futuro, seguono

Tempo di accesso costante


Esempio (con chiamate A,B,C,D )


Costi della CRT

Gestione più complessa di A-list

Costo di gestione

ingresso/uscita da bloccomanipolazione delle liste dei nomi dichiarati nel blocco

Tempo di accesso

costante (due accessi indiretti)

Confronto con A-List

si riduce il tempo d’accesso medio,si aumenta il tempo di ingresso/uscita dal blocco

Ottimizzazione:

posso inserire in CRT solo i nomi locali usati esternamente allaprocedura,ai nomi locali, si accede direttamente tramite RdA.


Gestione della memoria - users.dimi.uniud.itpietro.digianantonio/linguaggi/lucidi...Uso della...

Documents

Transcript of Gestione della memoria - users.dimi.uniud.itpietro.digianantonio/linguaggi/lucidi...Uso della...