Pila di Attivazione

(1)

G. Mecca – Università della Basilicata – mecca@unibas.it

Programmazione Procedurale in Linguaggio C++

Sottoprogrammi Concetti Avanzati Pila di Attivazione

versione 2.5

Questo lavoro è concesso in uso secondo i termini di una licenza Creative Commons (vedi ultima pagina)

Sommario

m

Pila di Attivazione

ðRecord di Attivazione

m

Funzionamento del Compilatore

m

La Ricorsione

Sottoprogrammi: Concetti Avanzati >> Sommario

(2)

G. Mecca - Programmazione Procedurale in Linguaggio C++ 3

Pila di Attivazione

m

In questa parte

ðapprofondimenti sul funzionamento e sulla gestione della memoria nelle applicazioni

m

Argomento particolarmente importante

ðchiarisce il concetto di stato di un programma ðchiarisce il funzionamento del compilatore ðconsente di affrontare l’utilizzo del

“debugger” (o correttore)

4

Pila di Attivazione

m

Compiti del compilatore e del collegatore

ðgenerare il codice eseguibile a partire dal

codice sorgente

m

Codice eseguibile

ðdeve eseguire le istruzioni dell’applicazione ðeffettuare le chiamate dei sottoprogrammi ðgestire l’allocazione di memoria per i moduli ðgestire le regole di visibilità

Sottoprogrammi: Concetti Avanzati >> Pila di Attivazione

(3)

Pila di Attivazione

m

Come viene gestito questo processo ?

ðutilizzando un algoritmo standard

ðbasato su una precisa strategia di gestione della memoria

m

Memoria per un’applicazione

ðdivisa in due zone

ðmemoria per il codice macchina ðmemoria per i dati

ðesiste una terza zona (“heap”) >>

Pila di Attivazione

m

Memoria per il codice

ðcodice oggetto compilato (linguaggio macchina) a partire dal codice sorgente ðogni istruzione sorgente corrisponde ad un

blocco di istruzioni di codice macchina

ðil codice oggetto opportunamente collegato, viene caricato in memoria all’esecuzione ðogni istruzione in linguaggio macchina

occupa un registro della memoria

(4)

Esempio:

Equazioni di II Grado

istruzioni del codice sorgente (discriminante)

istruzioni corrispondenti in codice macchina

indirizzi della memoria

8

Pila di Attivazione

m

Esecuzione delle istruzioni

ðviene effettuata attraverso opportuni registri del processore

ð“program counter”: registro che contiene l’indirizzo di memoria della prossima istruz.

ð“registro istruzione”: registro che contiene il codice binario dell’istruzione da eseguire ðregistri dati: registri utilizzati per gli operandi

(5)

Pila di Attivazione

m

Memoria per i dati

ðvista informalmente negli esempi

ðpiù precisamente, corrisponde alla “pila di attivazione”

m

Pila di attivazione (“Program Stack”)

ðspazio della memoria dedicato all’esecuzione di un programma

ðcontiene tutte le informazioni necessarie al processore per gestire l’esecuzione del prog.

Pila di Attivazione

m

Perché pila ?

ðla memoria viene gestita come una pila di piatti (rovesciata)

ðper ogni nuovo modulo eseguito, la memoria viene disposta come un nuovo piatto sulla pila (in fondo alla pila)

ðgli spazi vengono rilasciati nell’ordine in cui compaiono nella pila

ðla struttura di dati è una pila di record

(6)

Pila di Attivazione

m

Inizialmente

ðviene riservato un primo blocco di memoria per gli eventuali dati globali (dati dichiarati a livello di file)

ðsuccessivamente viene eseguito il main, e riservato lo spazio di memoria corrispondente ðpoi vengono eseguite le eventuali chiamate

successive, secondo la semantica descritta

12

Esempio: Istruzioni di II Grado

memoria per il main memoria per leggiDatiEquazione

(a1, b1, c1) memoria per leggiDatiEquazione

(a2, b2, c2) memoria per stampaDatiEquazione

(a1, b1, c1) memoria per stampaDatiEquazione

(a2, b2, c2) memoria per discriminante (a1, b1, c1) memoria per discriminante (a2, b2, c2) memoria per discriminante (a1, b1, c1) memoria per discriminante (a2, b2, c2) memoria per primaRadiceReale

(a1, b1, c1) memoria per primaRadiceReale

(a2, b2, c2) memoria per discriminante (a1, b1, c1) memoria per discriminante (a2, b2, c2) memoria per secondaRadiceReale

(a1, b1, c1) memoria per secondaRadiceReale

(a2, b2, c2)

Memoria RAM memoria per i

dati globali (vuota in questo caso)

analogo ad una pila di 4 piatti

(7)

Pila di Attivazione

m

Blocchi di memoria per ogni chiamata

ðrecord di attivazione della chiamata

ðtutte le informazioni necessarie al processore per eseguire la chiamata

m

Record di attivazione (“Stack Frame”)

ðcontiene tutte lo spazio per i dati del modulo ðcontiene i riferimenti al codice del modulo ðcontiene i riferimenti per gestire le regole di

visibilità (vediamo una versione semplificata)

Record di Attivazione

m

Struttura

ðidentificatore del modulo (ad ogni modulo viene assegnato un codice numerico)

ðriferimento al codice (indirizzo di memoria del registro a cui comincia il codice del corpo) ðpunto di ritorno (indirizzo di memoria

dell’istruzione successiva da eseguire al termine della chiamata)

(8)

Record di Attivazione

m

Struttura (continua)

ðspazio per i parametri (registri destinati ai parametri del modulo)

ðspazio per costanti e variabili locali (registri destinati ai dati locali del modulo)

ð“puntatore di catena statica” (indirizzo del blocco di memoria contenente i dati globali)

16

Record di Attivazione

m

Esecuzione di una chiamata

ðcreazione del record di attivazione per la chiamata e passaggio dei parametri

ðassegnazione al “program counter” del riferimento al codice

ðesecuzione del codice del sottoprogramma ðal termine: assegnazione al “program

counter” del punto di ritorno ðrilascio del record di attivazione

(9)

Record di Attivazione

m

Regole di visibilità

ðogni volta che viene richiesto l’accesso ad un dato in un modulo, il processore cerca il dato tra i dati locali

ðse trova un dato con il nome richiesto, lo utilizza

ðaltrimenti segue il puntatore di catena statica per cercare un eventuale dato globale con lo stesso nome, ed usa quello

Record di Attivazione

m

Nel seguito

ðun esempio basato sull’applicazione della Morra Cinese

ðutilizza varie semplificazioni

ðper i riferimenti al codice utilizzeremo il codice sorgente invece che il codice macchina

ðinoltre, trascureremo i record di attivazione dei sottoprogrammi predefiniti

(10)

G. Mecca - Programmazione Procedurale in Linguaggio C++... ... 19 }

#118

return;

#117 }

#106

cout << " Benvenuto, " << nome << "\n";

#116

getline(cin, nome);

#115

cout << "Immetti il tuo nome ";

#114

void schermoIniziale(string& nome) { // id=2

#113 }

#112

return;

#111

schermoIniziale(nome);

#110

srand(seme); //***

#109

int seme = time(NULL); //***

#108

void inizioGioco(string& nome) { // id=1

#107

schermoFinale(nome);

#105

gioca(nome);

#104

inizioGioco(nome);

#103

string nome;

#102

void main() { // id blocc=0

#101

const int MANI=3;

#100

...

#1000 p. cat. statica

#1016

#1004 nome

#1015

#111 punto rit.

#1014

#114 rif. codice

#1013

2 id blocco

#1012

#1011

xxx seme

#1010

#1004 nome

#1009

#104 punto. rit.

#1008

#108 rif. codice

#1007

1 id blocco

#1006

#1005

xxx nome

#1004

- punto rit.

#1003

#102 rif. codice

#1002

0 id blocco

#1001

3 MANI

#1000

Esempio: Equazioni di II Grado

20

Record di Attivazione

m

In concreto

ðla pila è fatta di registri di memoria ðpiù un indicatore di riempimento (“stack

pointer”)

ðpush: aumento dell’indicatore di riempimento e inizializzazione dei registri der record di att.

ðpop: diminuzione dell’indicatore di riempimento

(11)

Record di Attivazione

m

Attenzione

ðla memoria riservata alla pila di attivazione è tipicamente fissata dal compilatore

ðvalori tipici: da 64KB a 1MB ðpuò essere configurata

m

“Stack Overflow”

ðcondizione di errore irreversibile dovuta al tentativo di allocare memoria nello stack oltre il limite fissato

Funzionamento del Compilatore

m

Codice eseguibile di un’applicazione

ðcodice oggetto dell’applicazione (variabile da applicazione ad applicazione)

ðcodice oggetto per la gestione della pila (uguale in tutte le applicazioni)

ðquest’ultimo si incarica di creare e rilasciare i record di attivazione

ðe di gestire opportunamente l’esecuzione delle chiamate

Sottoprogrammi: Concetti Avanzati >> Funzionamento del Compilatore

(12)

Funzionamento del Compilatore

m

Cosa sono il compilatore e il collegatore?

ðapplicazioni software

ðimplementano un algoritmo relativamente complesso ma comprensibile

m

Passo 1: analisi lessicale

ðraggruppamento dei caratteri del codice sorgente in gruppi detti “token”

ðparole chiave, identificatori, punteggiatura

24

Funzionamento del Compilatore

m

Passo 2: analisi sintattica

ðverifica che la sequenza dei token del programma rispetti le regole della grammatica

ðse non è così: errore sintattico

m

Passo 3: traduzione in codice oggetto

ðtraduzione di ciascuna istruzione nelle

corrispondenti istruzioni del linguaggio macchina

(13)

Funzionamento del Compilatore

m

Passo 4: collegamento

m

Passo 5: aggiunta del codice per l’esecuzione

ðaggiunta del codice oggetto per il caricamento e l’avvio del programma

ðaggiunta del codice oggetto per la gestione delle operazioni sulla pila di attivazione

Una Domanda

m

Perché tutta questa complessità ?

ðnon sarebbe più semplice assegnare

staticamente la memoria a ciascun

sottoprogramma all’inizio dell’esecuzione ?

m

In questo caso si avrebbe una notevole semplificazione

ði moduli avrebbero blocchi di memoria fissati ðtutti i record di attivazione del modulo

sarebbero conservati nello stesso blocco

(14)

La Ricorsione

m

La risposta: la “ricorsione”

ðquesta è la ragione alla base della pila di att.

m

Ricorsione

ðtecnica per cui un sottoprogramma può (direttamente o indirettamente) chiamare sé stesso

ðdi conseguenza, possono essere

contemporaneamente attive varie attivazioni dello stesso sottoprogramma

28

La Ricorsione

m

Perché la ricorsione è importante ?

ðmolti problemi matematici sono basati su

definizioni “ricorsive”

ðdefinizioni in cui il problema è definito in termini di (varianti di) sé stesso

m

In questi casi

ðla strategia di programmazione basata sull’uso della ricorsione nel programma è la più naturale

Sottoprogrammi: Concetti Avanzati >> La Ricorsione

(15)

Un Esempio: Il Calcolo del Fattoriale

m

E’ possibile darne due definizioni

m

Definizione aperta (“iterativa”) – già vista

ð0! = 1, 1! = 1

ðn! = n x (n-1) x (n-2) x...x 2 x 1

m

Definizione ricorsiva

ð0! = 1 (caso base della def.)

ðn! = n x (n-1)! (caso ricorsivo della def.)

Soluzione Ricorsiva

const int massimo=13;

int fattoriale (int n) { int fatt;

if (n<0 || n>massimo) { return -1;

}

if (n==0) { fatt = 1;

} else {

fatt = n * fattoriale(n-1);

}

return fatt;

}

Codice per il caso base Codice per il caso ricorsivo

(16)

Un Esempio: Il Calcolo del Fattoriale

m

Esempio:

ðmain chiama fattoriale(3)

ðfattoriale(3) chiama fattoriale(2) ðfattoriale(2) chiama fattoriale(1) ðfattoriale(1) chiama fattoriale(0) ðfattoriale(0) restituisce 1

ðfattoriale(1) restituisce 1*1=1 ðfattoriale(2) restituisce 2*1=2 ðfattoriale(3) restituisce 3*2=6

32

Soluzione Ricorsiva

Memoria RAM memoria per i

dati globali memoria per il main

memoria per fattoriale(3) memoria per

fattoriale(2) memoria per

fattoriale(1) memoria per

fattoriale(0)

(17)

La Ricorsione

m

In realtà

ðla ricorsione è una tecnica di programmazione complessa

ðper ogni soluzione ricorsiva di un problema, ne esiste sempre una iterativa; esempio: il fattoriale

ðinoltre la ricorsione peggiora le prestazioni (altissima dinamica nella pila)

ðquindi, la ricorsione è spesso inutile

La Ricorsione

m

Però

ðci sono problemi che hanno una definizione ricorsiva più naturale di quella iterativa

ðesempio: algoritmi su alcune strutture di dati (liste, alberi e grafi)

ðin questi casi la programmazione ricorsiva è spesso più naturale di quella iterativa

ðsolo in questi casi è opportuno utilizzare la ricorsione

(18)

Riassumendo

m

Pila di Attivazione

ðRecord di Attivazione

m

Funzionamento del Compilatore

m

La Ricorsione

36

Termini della Licenza

m This work is licensed under the Creative Commons Attribution- ShareAlike License. To view a copy of this license, visit

http://creativecommons.org/licenses/by-sa/1.0/ or send a letter to Creative Commons, 559 Nathan Abbott Way, Stanford, California 94305, USA.

Termini della Licenza

m Questo lavoro viene concesso in uso secondo i termini della licenza “Attribution-ShareAlike” di Creative Commons. Per ottenere una copia della licenza, è possibile visitare

http://creativecommons.org/licenses/by-sa/1.0/ oppure inviare una lettera all’indirizzo Creative Commons, 559 Nathan Abbott Way, Stanford, California 94305, USA.