Programmazione II - Lezione 9groups.di.unipi.it/~daniele/teaching/pr2-10/pr2-09.pdf ·...

Programmazione IILezione 9

Daniele Sgandurra

[email protected]

16/11/2010

1/31 Programmazione II Lezione 9 16/11/2010

Sommario

1 Gestione della MemoriaGestione Dinamica Mediante HeapImplementazione delle Regole di Scope StaticoImplementazione delle Regole di Scope Dinamico


Gestione della Memoria

Parte I

Gestione della Memoria


Gestione della MemoriaGestione Dinamica Mediante HeapImplementazione delle Regole di Scope StaticoImplementazione delle Regole di Scope Dinamico

Gestione Dinamica Mediante Heap

Per linguaggi con allocazione esplicita della memoria:

C, C++, Pascal, etc.

Non e possibile usare una politica LIFO.

Serve un’altra zona di memoria diversa dallo stack:

una zona di memoria dove i blocchi possono essere allocati edeallocati:

gestito con blocchi di dimensione fissa;gestito con blocchi di dimensione variabile.



Esempio

1 i n t ∗p , ∗q ;2 p = ( i n t ∗) malloc ( s i z e o f ( i n t ) ) ;3 q = ( i n t ∗) malloc ( s i z e o f ( i n t ) ) ;4 ∗p = 0 ;5 ∗q = 1 ;6 free ( p ) ;7 free ( q ) ;

Nell’esempio, l’ordine di allocazione/deallocazione e effettuato nellostesso ordine: non e possibile gestire la memoria tramite strategie LIFO.

Per gestire allocazioni esplicite di memoria e in momenti arbitrari: zonaparticolare di memoria, lo heap.



Blocchi con Dimensione Fissa

Heap suddiviso in blocchi di dimensioni fisse (e limitate) collegati in unastruttura di lista detta lista libera.

Allocazione:

il primo elemento della lista libera viene rimosso;il puntatore a tale elemento viene restituito;si aggiorna il puntatore al primo elemento della lista liberaall’elemento successivo.

Deallocazione:

il blocco liberato viene collegato in testa alla lista libera;si aggiorna il puntatore all’elemento successivo a quello aggiunto.



Lista Libera per Heap con Blocchi di Dimensione Fissa



Blocchi con Dimensione Variabile

Dimensione fissa: inadeguatezza per strutture grandi:

es., array di dimensioni variabili (memoria sequenziale).

Richiesta una gestione dello heap con blocchi di dimensione variabile.

Gestione tesa a ottimizzare (con un compromesso):

1 l’occupazione della memoria; es. frammentazione:

interna: porzione di blocco allocato inutilizzato;esterna: memoria libera sufficiente nel complesso, ma non inun unico blocco (necessita di ricompattamento).

2 l’efficienza dell’esecuzione:

basso numero di operazioni aggiuntive richieste (overhead).



Frammentazione Esterna



Blocchi con Dimensione Variabile: Unica Lista Libera

Inizialmente una lista pari a tutta la memoria disponibile (heap):

allocazione: soddisfatta usando le prime n parole allocabili:

si avanza il puntatore inizio heap.

la memoria deallocata fa parte di una lista libera utilizzabile quando nonc’e piu altro spazio sull’heap;

utilizzo diretto della lista libera:

si mantiene una lista di blocchi liberi di dimensione variabile;allocazione: si cerca un blocco sufficientemente grande nella lista:

la porzione di blocco non usata resta nella lista memoria libera;politiche first-fit (migliore efficienza) e best fit (miglioreoccupazione).

deallocazione: si ricompatta il blocco con i blocchi liberi adiacenti.

compattazione della memoria libera:

in condizione di fine spazio direttamente allocabile:

spostamento dei blocchi attivi (solo se rilocabili);compattamento dei blocchi liberi in un’estremita dellamemoria.



Blocchi con Dimensione Variabile: Liste Libere Multiple

Molte liste di blocchi di dimensioni diverse.

Per un fabbisogno pari a n:

selezione della lista con blocchi di dimensioni maggiori o uguali a n;allocazione (frammentazione interna se le dimensioni sono statiche).

Buddy system: le dimensioni dei blocchi sono potenze di 2:

allocazione: sia k tale che blocco di dimensione 2k > n

se libero viene allocato;altrimenti passa a uno della lista 2(k+1) e lo si divide in 2: unaallocata, l’altra diventa libero tra i blocchi 2k .

deallocazione: ricerca del compagno (buddy):

se libero, fusione in un blocco di dimensione 2(k+1).

Heap di Fibonacci: come il precedente, ma usando numeri di Fibonacci

invece di potenze di 2:

la successione di Fibonacci cresce piu lentamente (minorframmentazione interna).



Implementazione delle Regole di Scope: Catena Statica

Ordine di ricerca di riferimenti non locali non coincidente con quello deiblocchi nella pila.

RdA del blocco B collegato mediante puntatore di catena statica al

blocco immediatamente esterno a esso:

se B attivo anche i blocchi esterni che lo contengono devono essereattivi (RdA sulla pila);vengono mantenute 2 catene;gestione tramite codice della sequenza di chiamata, prologo edepilogo.



Esempio

1 A :{ i n t y = 0 ;2 B :{ i n t x = 0 ;3 vo i d pippo ( i n t n ){4 x = n − 1 ;5 y = n + 2 ;6 }7 C :{ i n t x = 1 ;8 pippo (2 ) ;9 write ( x ) ;

10 }11 }12 write ( y )13 }



Pila RdA con Catena Statica



Implementazione delle Regole di Scope: Puntatore CatenaStatica

Chiamato all’esterno del chiamante:

perche il chiamato sia visibile, deve trovarsi in un blocco esterno cheincluda anche il chiamante;quindi l’RdA di questo blocco esterno e sulla pila;il numero di livelli di distanza determinabile dal compilatore:

k = livello(chiamato) - livello(chiamante);

si seguono k livelli di catena statica.

Chiamato all’interno del chiamante:

per la visibilita, il chiamato e dichiarato nel blocco della chiamata;il chiamante passa al chiamato, come puntatore di catena statica, ilpuntatore al proprio RdA.



Esempio: una Struttura a Blocchi



Esempio: Catena Statica per la Struttura Precedente

Sequenza di chiamate: A, B, C, D, E, C.



Implementazione delle Regole di Scope: Tabella dei Simboli

Il chiamato (prologo) memorizza il puntatore di catena statica ricevutonel suo RdA.

Il compilatore tiene traccia della catena statica usando la tabella dei

simboli:

associazione nomi usati / oggetti denotati;

identificati e numerati i vari scope in base al livello diannidamento;ad ogni nome e associato un numero che indica lo scope checontiene la dichiarazione;

tuttavia non puo risolvere tutti i riferimenti perche non e possibileconoscere staticamente il numero di RdA sulla pila.

Svantaggio:

per k livelli di distanza, si devono scorrere k livelli di catena statica.



Implementazione delle Regole di Scope: Tecnica delDisplay

Consente di ridurre a un numero costante gli accessi.

Display: vettore di dimensione pari a numero di livelli di annidamento:

display[k]: puntatore al RdA di livello k attivo.

Per ogni riferimento a un nome non locale:

dichiarato in blocco esterno a livello k,il puntatore all’RdA e nel display nella posizione k.

Gestione piu costosa rispetto ala catena statica:

chiamata/entrata sottoprogramma/blocco di livello k;il chiamato:

salva il valore di display[k], se presente (condivisione deldisplay in tutto o in parte col chiamante);aggiorna display[k] con il puntatore del RdA.



Esempio: Display per la Struttura Precedente

Sequenza di chiamate: A, B, C, D, E, C.



Implementazione delle Regole di Scope: Lista diAssociazioni

Vantaggio: piu semplice:

ambienti non locali considerati secondo l’ordine di chiamata.

Svantaggi:

necessita di memorizzare esplicitamente i nomi per la ricerca;puo essere inefficiente eseguire tutto a run-time.

Memorizzazione associazioni nome/oggetto:

nell’RdA, oppurein una lista di associazioni (A-list) gestita come una pila.

Entrata/uscita in/da un nuovo ambiente:

nuove associazioni locali sono inserite/eliminate nella/dalla lista.

Informazioni:

locazione memoria dell’oggetto;tipo;altre info necessarie a controlli semantici.



Esempio: una Struttura a Blocchi con Dichiarazioni Locali



Esempio: Memorizzazione Diretta nei RdA

Ambiente per il blocco D, sequenza di chiamate: A, B, C, D.



Esempio: Memorizzazione Tramite A-List




Implementazione delle Regole di Scope

Inconvenienti della memorizzazione diretta nei RdA o tramite A-List separata:

1 I nomi, diversamente all’implementazione dello scope statico, sono

memorizzati in strutture presenti a tempo di esecuzione:

nella A-List per definizione;nel caso di RdA: uno stesso nome, dichiarato in blocchi diversi, puoessere memorizzato in posizioni differenti nei diversi RdA:

con lo scope dinamico, non sappiamo qual e il blocco (quindi,l’RdA) e la posizione;quindi, dobbiamo memorizzare esplicitamente il nome e fareuna ricerca a run-time.

2 Inefficienza:

spesso occorre scandire tutta la lista (es., nomi globali).



Implementazione delle Regole di Scope: CRT

Tutti i blocchi in un’unica tabella (Tabella Centrale dell’Ambiente o CRT:

Central Referencing environment Table):

tutti i nomi, dove per ogni nome:

flag (associazione attiva sı/no);puntatore alle informazioni associate (locazione, tipo, ...).

Ovviano ai due inconvenienti suddetti.

Minor efficienza.

Se tutti i nomi sono noti a compile-time:

ricerca in tempo costante (indirizzo tabella+offset),altrimenti: ricerca hash.



Implementazione delle Regole di Scope: CRT

Operazioni entrata uscita da un blocco piu complicate:

quando da un blocco A si entra in un blocco B, la tabella centraledeve essere modificata per descrivere il nuovo ambiente B;le associazioni deattivate devono essere salvate.

Associazioni di un blocco non in posizioni contigue in CRT:

occorre considerare i singoli elementi della tabella: utilizzo di unapila per ogni entrata:

prima posizione: associazione valida; posizioni successive:associazioni disattivate per il nome.

alternativamente: unica pila nascosta, separata dalla CRT:

memorizza per tutti i nomi solo le associazioni deattivate;la tabella contiene nella seconda colonna un flag (attivo/no) eil riferimento all’oggetto (terza colonna);associazione deattivata: salvata nella pila e poi ripristinata.



Esempio: Memorizzazione Tramite CRT




Esempio: Memorizzazione Tramite CRT con Pila Nascosta




Riferimenti

[1] Linguaggi di programmazione: principi e paradigmi (Cap. 5).

Maurizio Gabbrielli, Simone Martini.


Programmazione II - Lezione 9groups.di.unipi.it/~daniele/teaching/pr2-10/pr2-09.pdf ·...

Documents

Transcript of Programmazione II - Lezione 9groups.di.unipi.it/~daniele/teaching/pr2-10/pr2-09.pdf ·...