Corso di Programmazione e Metodi Numerici Ingegneria Aerospaziale – BAER Unità...

Corso di Programmazione e Metodi NumericiIngegneria Aerospaziale – BAER

Unità 5

Gestione della memoria

Unità 5

Domenico Daniele Bloisi

Docenti

Metodi Numericiprof. Vittoria Bruni

[email protected]

Programmazioneprof. Domenico Daniele Bloisi

[email protected]@dis.uniroma1.it

Sito del corso http://www.dis.uniroma1.it/~pmnNota: %7E corrisponde alla tilde ~

Pagina 22011/2012Gestione della memoriaUnità 5

Orario delle Lezioni

Lunedì 10.15 – 11.45Martedì 08.30 – 10.00Martedì 08.30 – 10.00Giovedì 10.15 – 11.45Venerdì 10.15 – 11.45

Aula 15, Via Scarpa 14Aula 15, Via Scarpa 14


Informazioni Generali

Ing. Domenico Daniele Bloisi, PhD

Dipartimento di Ingegneria Informatica Dipartimento di Ingegneria Informatica Automatica e GestionaleVia Ariosto 25(adiacente Piazza Dante,

A fermate Manzoni, Vittorio Emanuele,Tram 3 fermata via Labicana)

mailto:[email protected]

http://www.dis.uniroma1.it/~bloisiPagina 42011/2012Gestione della memoria

Unità 5

Ricevimento

Martedì 15.00 – 17.00DIS via Ariosto 25DIS via Ariosto 25

Aula docenti adiacente aula A4

Si consiglia di inviare una email per conferma edi controllare preventivamente la bacheca degli avvisiavvisi


Sommario – Unità 5

• Definizione di funzioni• Passaggio dei parametri• Esecuzione di una funzione• Esecuzione di una funzione• Variabili dichiarate in una funzione: campo diazione

• Overloading di funzioni• Organizzazione di un programma• Domini definiti induttivamente• Domini definiti induttivamente• Ricorsione e funzioni ricorsive• Gestione della memoria a run -time• Ricorsione multipla


Gestione della memoria a run -time

A tempo di esecuzione, il sistema operativo deve ges tire diverse zone di memoria:

• zona che contiene il codice eseguibile del programm a• zona che contiene il codice eseguibile del programm a– determinata a tempo di esecuzione al momento del

caricamento del codice– dimensione fissata per ogni funzione a tempo di

compilazione

• heap: zona di memoria che contiene le variabili allocate dinamicamente

Pagina 72011/2012

dinamicamente– cresce e decresce dinamicamente durante l’esecuzion e– ogni variabile viene allocata e deallocata indipen dentemente

dalle altre

Gestione della memoriaUnità 5

Gestione della memoria a run -time

• stack o pila dei record di attivazione: zona di memoria per i dati locali alle funzioni (variabili e paramet ri)per i dati locali alle funzioni (variabili e paramet ri)

– cresce e descresce dinamicamente durante l’esecuzione

– viene gestita con un meccanismo a pila


Pila dei record di attivazioneUna pila (o stack) è una struttura dati con accesso LIFO

Last In First Out = l’ultimo entrato è il primo a u scireLast In First Out = l’ultimo entrato è il primo a u scire(Esempio: pila di piatti).

A run-time il sistema operativo gestisce la pila de i record di attivazione (RDA) :

• per ogni attivazione di funzione viene creato un nuo vo RDA in cima alla pila;

Pagina 92011/2012

RDA in cima alla pila;

• al termine dell’attivazione della funzione il RDA vi ene rimosso dalla pila.


Record di attivazione

Un RDA tiene traccia

• delle locazioni di memoria per i parametri formali (se

PF v1VL v2VR v3IR v4

• delle locazioni di memoria per i parametri formali (se presenti);

• delle locazioni di memoria per le variabili locali (se presenti);

• del valore di ritorno dell’invocazione della funzion e (se la funzione ha tipo di ritorno diverso da void );

Pagina 102011/2012

la funzione ha tipo di ritorno diverso da void );

• della locazione di memoria per l’indirizzo di ritorno , ovvero l’indirizzo della prossima istruzione da esegui re nella funzione chiamante.


Esempio di evoluzione della pila dei record di attivazioneint B(int pb) {/* b0 */ cout

Esempio di evoluzione della pila dei record di attivazioneint main() {/* m0 */ cout

Output prodotto dal programma

In main.Chiamata di A(22).Chiamata di A(22).In A. Parametro pa = 22Chiamata di B(44).In B. Parametro pb = 44Di nuovo in A. va = 45Di nuovo in main. vm = 67

Pagina 132011/2012

Di nuovo in main. vm = 67


Program counter

Per comprendere cosa avviene durante l’esecuzione del codice, è necessario fare riferimento, oltre che alla pila dei RDA, al riferimento, oltre che alla pila dei RDA, al program counter (PC), il cui valore è l’indirizzodella prossima istruzione da eseguire.

Si assuma chem0abbia indirizzo 100


m0abbia indirizzo 100a0 abbia indirizzo 200b0 abbia indirizzo 300

Evoluzione della pila dei RDA

Figura 5.1


Figura 5.1

Prima dell’attivazione di A(vm) , la pila dei RDA è come mostrato in 1 nella Fig. 5.1:

1. vengono valutati i parametri attuali: in questo caso il

Evoluzione della pila dei RDA:individuazione e chiamata di A

1. vengono valutati i parametri attuali: in questo caso il parametro attuale è l’espressione vm che ha come valore l’intero 22;

2. viene individuata la funzione da eseguire in base al numero e tipo dei parametri attuali, cercando la definizione di una funzione la cui segnatura sia conforme alla invocazione: nel nostro caso la funzion e

Pagina 162011/2012

conforme alla invocazione: nel nostro caso la funzion e da eseguire deve avere la segnatura A(int) ;

3. viene sospesa l’esecuzione della funzione chiamant e: nel nostro caso la funzione main ;


4. viene creato il RDA relativo all’attivazione corr ente della funzione chiamata: nel nostro caso viene creato il R DA relativo all’attivazione corrente di A; il RDA contiene:

• le locazioni di memoria per i parametri formali:

Evoluzione della pila dei RDA:creazione del record di A

• le locazioni di memoria per i parametri formali:nel nostro caso, il parametro pa di tipo int ;

• le locazioni di memoria per le variabili locali:nel nostro caso, la variabile va di tipo int ;

• una locazione di memoria per il valore di ritorno:nel nostro caso indicata con VR;

• una locazione di memoria per l’indirizzo di ritorno:

Pagina 172011/2012

• una locazione di memoria per l’indirizzo di ritorno:nel nostro caso indicata con IR;

5. viene assegnato il valore dei parametri attuali ai parametri formali: nel nostro caso, il parametro formale pa viene inizializzato con il valore 22;


Evoluzione della pila dei RDA:modifica valore del PC6. l’indirizzo di ritorno nel RDA viene impostato

all’indirizzo della prossima istruzione che deve esser e eseguita nella funzione chiamante al termine eseguita nella funzione chiamante al termine dell’invocazione: nel nostro caso, l’indirizzo di rito rno nel RDA relativo all’attivazione di A viene impostato al valore 104, che è l’indirizzo dell’istruzione di maincorrispondente all’istruzione m4, da eseguire quando l’attivazione di A sarà terminata; a questo punto, la pila dei RDA è come mostrato in 2 nella Fig. 5.1;

Pagina 182011/2012

7. al program counter viene assegnato l’indirizzo del la prima istruzione della funzione invocata: nel nostro caso, al program counter viene assegnato l’indirizzo 200, che è l’indirizzo della prima istruzione di A;


8. si passa ad eseguire la prossima istruzione indic ata dal program counter, che sarà la prima istruzione della funzione invocata: nel nostro caso l’istruzione di

Evoluzione della pila dei RDA:esecuzione di A

funzione invocata: nel nostro caso l’istruzione di indirizzo 200, ovvero la prima istruzione di A.

Dopo questi passi, le istruzioni della funzione chiam ata, nel nostro caso di A, vengono eseguite in sequenza. In particolare, avverrà l’attivazione, l’esecuzione e la terminazione di eventuali funzioni a loro volta invoc ate nella funzione chiamata. Nel nostro caso, avverrà

Pagina 192011/2012

nella funzione chiamata. Nel nostro caso, avverrà l’attivazione, l’esecuzione e la terminazione della funzione B, con un meccanismo analogo a quello adottato per A; la pila dei RDA passerà attraverso gli stati 3 e 4.


Evoluzione della pila dei RDA:terminazione di A

Analizziamo ora in dettaglio cosa avviene al momento della terminazione dell’attivazione di A, cioè quando viene eseguita l’istruzione return va+pa;eseguita l’istruzione return va+pa;

Prima dell’esecuzione, la pila dei RDA è come mostra to in 4 nella Fig. 5.1 (in realtà, la zona di memoria pred isposta a contenere il valore di ritorno, indicata con VR n ella figura, viene inizializzata contestualmente all’esecuzi one dell’istruzione return , e non prima).


Evoluzione della pila dei RDA:valore di ritorno

1. al program counter viene assegnato il valore memorizzato nella locazione di memoria riservata all’indirizzo di ritorno nel RDA corrente: nel nostro all’indirizzo di ritorno nel RDA corrente: nel nostro caso, tale valore è pari a 104, che è proprio l’ind irizzo, memorizzato in IR, della prossima istruzione di mainche dovrà essere eseguita;

2. nel caso la funzione invocata preveda la restit uzione di un valore di ritorno, tale valore viene memorizzato i n un’apposita locazione di memoria del RDA corrente:

Pagina 212011/2012

un’apposita locazione di memoria del RDA corrente: nel nostro caso, il valore 67, risultato della valu tazione dell’espressione va+pa viene assegnato alla locazione di memoria indicata con VR, predisposta per contene re il valore di ritorno;


Evoluzione della pila dei RDA:eliminazione del record

3. viene eliminato dalla pila dei RDA il RDA relati vo all’attivazione corrente, e il RDA corrente diviene quello immediatamente precedente nella pila; quello immediatamente precedente nella pila; contestualmente all’eliminazione del RDA dalla pila dei RDA, un eventuale valore di ritorno viene copiato i n una locazione di memoria del RDA del chiamante: nel nostro caso, viene eliminato il RDA relativo all’attivazione di A e il RDA corrente diviene quell o relativo all’attivazione di main ; inoltre, il valore 67, memorizzato nella locazione di memoria VR viene

Pagina 222011/2012

memorizzato nella locazione di memoria VR viene assegnato alla variabile vm nel RDA di main ; la pila dei RDA è come mostrato in 5 nella Fig. 5.1;


4. si passa ad eseguire la prossima istruzione indicata dal program counter, cioè quella appena impostata al passo 1: nel nostro caso,

Evoluzione della pila dei RDA:prossima istruzione nel PC

appena impostata al passo 1: nel nostro caso, si passa ad eseguire l’istruzione di indirizzo 104, che fa riprendere l’esecuzione di main .


Evoluzione della pila dei RDA nel caso di funzioni ricorsive

Nel caso di funzioni ricorsive, i meccanismi con cui evolvono la pila dei RDA ed il program cui evolvono la pila dei RDA ed il program counter sono identici al caso di funzioni non ricorsive.

Importante: un RDA è associato ad un’attivazione di una funzione e non ad una funzione.


Esempiovoid ricorsivo(int i) {/* r0 */ cout

Esempioint main() {/* m0 */ int j;/* m1 */ cout j;/* m3 */ cout

Output con input 2

In main - Attivazione di ricorsivo(2)In ricorsivo(2) - Attivazione di ricorsivo(1)In ricorsivo(2) - Attivazione di ricorsivo(1)In ricorsivo(1) - Attivazione di ricorsivo(0)In ricorsivo(0) - FinitoDi nuovo in ricorsivo(1) - FinitoDi nuovo in ricorsivo(2) - FinitoDi nuovo in main - Finito


Evoluzione della pila dei RDA

Si assuma chem0abbia indirizzo 100r0 abbia indirizzo 200r0 abbia indirizzo 200

i 2 i 2

i 1IR 206

i 2

i 1IR 206

i 0IR 206

i 2

i 1IR 206

i 2


j 2 j 2

i 2IR 105

j 2

i 2IR 105

j 2

i 2IR 105

j 2

i 2IR 105

j 2

i 2IR 105

j 2

Evoluzione della pila dei RDA:tipo di ritorno void105 è l’indirizzo dell’istruzione che segue l’attivazio ne di ricorsivo(j) in main , mentre 206 è l’indirizzo dell’istruzione che segue l’attivazione di ricorsivo(i - 1)dell’istruzione che segue l’attivazione di ricorsivo(i - 1)in ricorsivo .

Dal momento che le funzioni invocate non prevedono l a restituzione di un valore di ritorno (il tipo di rit orno è void ), i RDA non contengono una locazione di memoriaper tale valore. Inoltre, non abbiamo indicato la f unzione alla quale si riferisce ciascun RDA, in quanto il R DA in


alla quale si riferisce ciascun RDA, in quanto il R DA in fondo alla pila è relativo a main , e tutti gli altri sono relativi ad attivazioni successive di ricorsivo .

Evoluzione della pila dei RDA:IR per attivazioni ricorsivePer le diverse attivazioni ricorsive vengono creati diversi RDA sulla pila, con valori via via decrescenti del parametro i , fino all’ultima attivazione ricorsiva, per la parametro i , fino all’ultima attivazione ricorsiva, per la quale il parametro i assume valore 0.A questo punto non avviene più un’attivazione ricors iva, viene stampato " - Finito" , e l’attivazione termina.In cascata, avviene l’uscita dalle attivazioni prece denti, ogni volta preceduta dalla stampa di"Di nuovo in ricorsivo( i ) - Finito".


L’indirizzo di ritorno memorizzato nei RDA per le diver se attivazioni ricorsive è sempre lo stesso, tranne che per la prima attivazione.

Ricorsione multiplaSi ha ricorsione multipla quando un’attivazione di u na funzione può causare più di una attivazione ricorsiva della stessa funzione.della stessa funzione.

Esempio: funzione ricorsiva per il calcolo dell’n-es imo numero di Fibonacci.


F(0), F(1), F(2), . . . è detta sequenza dei numeri diFibonacci: 0, 1, 1, 2, 3, 5, 8, 13, 21, . . .

Fibonacci: cenni storici

La sequenza prende il nome dal matematico pisano del XIII secolo Leonardo Fibonacci e i termini di questa successione sono chiamati numeri di questa successione sono chiamati numeri di Fibonacci .

L'intento di Fibonacci era quello di trovare una legge che descrivesse la crescita di una popolazione di conigli.


conigli.

Dettagli: http://it.wikipedia.org/wiki/Successione_di_Fibonac ci

Fibonacci

int fibonacci(int n) {if (n < 0)

return - 1;return - 1;// F(n) non e’ definito per n negativo!if (n == 0)

return 0;else if (n == 1)

return 1;else

return fibonacci(n-1) + fibonacci(n-2);}

Pagina 332011/2012

}


Esempio: Torri di Hanoi

Il problema delle Torri di Hanoi ha origine da una leggenda secondo la quale in un tempio vietnamita alcuni monaci sono costantemente vietnamita alcuni monaci sono costantemente impegnati a spostare su tre colonne di diamante 64 dischi d'oro secondo delle precise regole .

La leggenda narra che quando i monaci completeranno il lavoro, il mondo finirà.

Pagina 342011/2012

completeranno il lavoro, il mondo finirà.


http://it.wikipedia.org/wiki/Torre_di_Hanoi

Regole: Torri di HanoiLo spostamento della torre di dischi avviene second o le seguenti regole:• inizialmente, la torre di dischi di dimensione • inizialmente, la torre di dischi di dimensione decrescente è posizionata su un perno 1;

• l’obiettivo è quello di spostarla su un perno 2, u sando un perno 3 di appoggio;

• le condizioni per effettuare gli spostamenti sono:– tutti i dischi, tranne quello spostato, devono sta re

su una delle torri– è possibile spostare un solo disco alla volta,

Pagina 352011/2012

– è possibile spostare un solo disco alla volta, dalla cima di una torre alla cima di un’altra torre ;

– un disco non può mai stare su un disco più piccolo.



6 dischi

statostatoiniziale

stato intermedio


statofinale

Formulazione ricorsiva

Per spostare n > 1 dischi da 1 a 2, usando 3 come appoggio:

1. sposta n − 1 dischi da 1 a 3

2. sposta l’n -esimo disco da 1 a 2


Pagina 372011/2012



Implementazione tramite ricorsione multipla

void muoviUnDisco(int sorg, int dest) {cout

Implementazione tramite ricorsione multipla

int main () {cout n;cout

Esecuzione


Numero di attivazioni nel caso di ricorsione multiplaQuando si usa la ricorsione multipla, bisogna tenere presente che il numero di attivazioni ricorsive potrebbe essere esponenziale nella ricorsive potrebbe essere esponenziale nella profondità delle chiamate ricorsive (cioè nell’altezza massima della pila dei RDA).




Nota: nel caso del problema delle Torri di Hanoi il numero esponenziale di attivazioni è una caratteristica intr inseca del problema, nel senso che non esiste una soluzione mig liore.

EserciziEsercizio 5.5

Modificare l’implementazione ricorsiva della funzione fibonacci in modo che, invocata sull’intero n, fibonacci in modo che, invocata sull’intero n, restituisca, oltre al valore dell’n-esimo numero diFibonacci, anche il numero complessivo di attivazion i ricorsive di fibonacci effettuate per il calcolo.

Esercizio 5.6

Verificare se esiste la possibilità di una chiamata

Pagina 432011/2012

Verificare se esiste la possibilità di una chiamata ricorsiva alla funzione main . In caso affermativo, scrivere un programma che chiami n > 1 volte la funzione mainstampando di volta in volta il numero dell’attivazio ne corrente.


EserciziEsercizio 5.7

Scrivere una funzione che calcoli log(x+1)+sqrt(x+2)-1 .Scrivere una funzione che trovi lo zero di tale funzione Scrivere una funzione che trovi lo zero di tale funzione applicando il metodo delle bisezioni.La funzione per il calcolo delle bisezioni deve avere tre argomenti:a, b, che denotano l'intervallo di ricerca (o intervallo di separazione)ed e che denota l'errore massimo accettabile.

Pagina 442011/2012

ed e che denota l'errore massimo accettabile.Scrivere un programma di prova (cioè, una funzione main) che trovi uno zero della funzione log(x+1)+sqrt(x+2)-1nell'intervallo [-0.5,0] con errore minore di 10-3.


Soluzione Esercizio 5.7



double f(double x) {return log(x+1)+sqrt(x+2) - 1;return log(x+1)+sqrt(x+2) - 1;

}


Soluzione Esercizio 5.7double bisezioni(double a, double b, double e) {

double x;double f_x = e;while(fabs(f_x) >= e) {

x = (a+b)/2;x = (a+b)/2;f_x = f(x);cout

Soluzione Esercizio 5.7int main() {

double a = -0.5;double b = 0;double e = 1e - 3;double e = 1e - 3;double result = bisezioni(a, b, e);cout

Output Soluzione Esercizio 5.7

-0.5 0 -0.25 0.0351936-0.5 -0.25 -0.375 -0.195249-0.375 -0.25 -0.3125 -0.0756553-0.375 -0.25 -0.3125 -0.0756553-0.3125 -0.25 -0.28125 -0.0192306-0.28125 -0.25 -0.265625 0.00822124-0.28125 -0.265625 -0.273438 -0.00544352-0.273438 -0.265625 -0.269531 0.001404-0.273438 -0.269531 -0.271484 -0.00201596-0.271484 -0.269531 -0.270508 -0.000305032


-0.271484 -0.269531 -0.270508 -0.000305032result = -0.270508

Corso di Programmazione e Metodi Numerici Ingegneria Aerospaziale – BAER Unità...

Documents

Transcript of Corso di Programmazione e Metodi Numerici Ingegneria Aerospaziale – BAER Unità...