Gestione memoria (slide 36)

scrivi le def di regola di scope dinamico e statico in s02

Il display

Alternativa alla catena statica per implementare scope statico (e' piu veloce ma richiede mem in piu (per l'array))

Si puo ridurre il costo h ad una costante usando la tecnica del display

• la catena statica viene rappresentata mediante un array
  • i-esimo elem dell array = punt all'RdA del sottoprogramma di livello di annidamento i attivo per ultimo
• quindi: - Display[1]=RdA di una proc P di top level - Display[2]=RdA di una proc Q dichiarata in P - … - Display[2]=RdA della proc attiva in questo momento (dichiarata dentro quella che si trova in Display[i-1])

Se il sottoprogramma corrente è annidato a livello i, un oggetto che è in uno scope esterno di h livelli può essere trovato guardando il punt a RdA nel display alla posizione j = i - h

Esempio:

Se proc corrente annidata a livello i, lo scope esterno di h livelli si ottiene in Display[i - h] Con Display in memoria un oggetto è trovato con due accessi, uno per il display e uno per l’oggetto

Display o catena statica ? • Rari annidamenti di profondità > 3, quindi lunghezza max di catena statica = 3 • Tecniche di ottimizzazione possono migliorare gli accessi alle catene usate più frequentemente (tenendo nei registri i puntatori) • Il display è più costoso da mantenere della catena statica nella sequenza di chiamata … • Conclusione: display poco usato nelle implementazioni moderne…

Scope dinamico

Con scope dinamico l’associazione nomi-oggetti denotabili dipende – dal flusso del controllo a run-time – dall’ordine con cui i sottoprogrammi sono chiamati - La regola generale è semplice: l’associazione corrente per un nome è quella determinata per ultima nell’esecuzione (non ancora distrutta).

Implementazione ovvia:

• Memorizzare i nomi negli RdA
• Ricerca per nome risalendo la pila
• Esempio: chiamate A,B,C,D

Variante: A-list Le associazioni sono memorizzate in una struttura apposita (manipolata come una pila) Es: chiamate A B C D (in grigio le associazioni non attive) In pratica se ho x a livello A e x al livello B, quando parto da B o da sotto B risalendo trovo x(x deve essere attiva = visibile dal blocco corrente) quando mi sposto (es da A a C) devo rendere non visibili le var di altri blocchi (es. B non e' visibile da C o D)

Per ogni record che alloco sulla pila devo esplicitare le var visibili nei libri la regola di visibilita' viene prima della regola di scope (nella realta' dipende)

le associazioni non visibili lo sono per due casi:

1. sono state riscritte
2. sono invisibili secondo la regola di visibilita'

Costi delle A-list

• Molto semplice da implementare
• Occupazione mem (nomi presente esplicitamente)
• costo di gestione (ingresso uscita da blocco e inserzione rimozione blocchi dalla pila)
• tempo di accesso (lineare nella profondita della a list)

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

Tabella centrale dei riferimenti, CRT

evita le lunghe scansioni delle A list una tabella mantiene tutti i nomi distinti del programma

• se i nomi sono noti statitcamente si puo accedere all elemento della tabella in tempo costante
• altrimenti accesso hash

Ad ogni nome e' associata la lista delle associazioni di quel nome

• la piu recente e' la prima
• le altre (disattivate) seguono

Tempo di accesso costante

nell'ultima tabella v e'dichiarato non visibile (0)

Costi della CRT

Gestione più complessa di A-list Meno occupazione di memoria: – se nomi noti staticamente, i nomi non sono necessari – in ogni caso, ogni nome memorizzato una sola volta

Costo di gestione – ingresso/uscita da blocco (manipolazione di tutte le liste dei nomi presenti nel blocco) Tempo di accesso – costante (due accessi indiretti) Possiamo ridurre il tempo d’accesso medio, aumentando il tempo di ingresso/uscita da blocco…

Es. esrcizio

Si assuma che un generico linguaggio imperativo a blocchi. Il blocco A contenga una chiamata alla funzione f. Il numero dei record di attivazione (RdA) presenti run time sulla pila fra il RdA di A e quello della chiamata di f e' fissato staticamente o puo valere dinamicamente? Motivare la risoposta