RAM model - Algoritmi e strutture dati

Il Virtual Address Space ha una parentela relativa con la

memoria virtuale, infatti la memoria virtuale è una

tecnica per gestire lo spazio virtuale in determinati

sistemi operativi, lo spazio virtuale è lo spazio di

esecuzione del programma.

Proviamo a scrivere in un programma una variabile non

inizializzata di 100000 elementi, poi lo compiliamo e

guardiamo le dimensioni del programma, di solito sono

pochi byte, questo perché i 100000 elementi non sono

nel programma statico che invece contiene le istruzioni

perché lo spazio virtuale possa contenere 100000

elementi, quindi i veri 100000 elementi che abbiamo

chiesto verranno realmente creati nel momento in cui il

programma verrà messo in esecuzione, quindi dal loader

per i programmi compilati o da quello che è il vero

interprete delle istruzioni per i programmi interpretati

che invece vengono eseguiti in una macchina virtuale

che li isola dal resto del sistema.

Concentriamoci ora sullo spazio virtuale:

Esso è generalmente segmentato cioè contiene varie

regioni etichettate che hanno proprietà caratteristiche.

Notiamo che lo spazio virtuale della memoria, che in una

macchina a 32 bit potrebbe essere di 4 Gbyte, non è

necessariamente tutto allocato, solo i segmenti utilizzati

vengono realmente allocati, gli altri indirizzi esistono ma

non hanno una contropartita in memoria, non sono usati

e il fatto che non ci sia memoria fisica per quegli indirizzi

non dà fastidio a nessuno.

Nei linguaggi di programmazione più tradizionali i

segmenti che sicuramente troviamo sono:

Code segment che contiene le istruzioni tradotte del

1. programma

Data segment detto heap

2. Stack segment che è un segmento dati ma con un

3. utilizzo abbastanza particolare

Le organizzazioni delle strutture dati vanno a finire o

sulla heap o sullo stack

La heap a differenza dello stack non è ordinata, lo stack

è ordinato, in realtà la differenza è legata alla forma di

organizzazione.

In realtà l’unica parentela che c’è tra la struttura dati

heap e la struttura dati stack e l’heap o stack che

troviamo nello spazio virtuale è il nome e un certo modo

di gestire le cose, ma sono cose diverse.

L’heap contiene generalmente le variabili statiche, cioè

quelle che esistono per tutta la durata della vita del

programma, lo stack contiene le variabili automatiche,

ad esempio quelle che esistono per la durata della

funzione e poi spariscono, quindi che hanno un life time

più breve.

Come viene mappato la variabile del programma in

questi segmenti dipende dal linguaggio, cioè il

linguaggio stabilisce delle regole precise sulla visibilità

statica delle variabili e sula visibilità dinamica, quindi il

life time, delle variabili in memoria, è una cosa

importante da capire quando si apprende un nuovo

linguaggio.

Per valutare e confrontare gli algoritmi dobbiamo fare

riferimento a un modello di calcolo che sia condiviso

perchè sia dal punto di vista strettamente tecnologico

che dal punto di vista teorico è possibile definire diversi

modelli di calcolo, noi di solito parlando della tecnologia

facciamo riferimento alla macchina di Von Neumann,

essa è un macchina ideale in cui lo spazio di memoria

fisica è condiviso tra istruzioni e dati e il modello della

macchina di Von Neumann è quello che è riprodotto nel

disegno di sopra: la memoria della macchina contiene

sia i segmenti dati che i segmenti codice, quindi sia le

istruzioni che i dati su cui le istruzioni operano. Il

funzionamento della macchina di Von Neumann è: esiste

un ciclo infinito dammi una istruzione e lavoro su

quell’istruzione e così via, però sono possibili anche altri

modi di ragionare, esistono macchine per esempio in cui

lo spazio di memoria dati e quelle delle istruzioni sono

separate, il vantaggio è che i cicli di fetch, quindi di

caricamento delle istruzioni, possono avvenire in

parallelo ai cicli di fetch di dati mentre nella macchina di

Von Neumann il bus è unico quindi il fetch delle istruzioni

e quello dei dati devono necessariamente contendere

un’unica risorsa condivisa che è il bus dei dati.

Il modello a cui facciamo riferimento è detto RAM Model

dove RAM=random access machine, essa è una

versione un po' più concreta della macchina di tuning in

cui esiste un nastro infinito ed esiste un controllore che

può leggere un simbolo, scrivere un simbolo e muovere il

nastro, la RAM può fare un po' più cose, è più vicina alla

macchina di Von Neumann, in pratica consideriamo la

memoria come una schiera infinita di celle (la cui

dimensione spesso è indicata dal parallelismo della

macchina), in teoria viene considerata come infinita,

nella pratica va da zero fino a un massimo di memoria a

cui sottraggo 1 come indirizzo. Per valutare le prestazioni

degli algoritmi assumiamo che ogni ciclo di memoria

utilizzi esattamente un’unità di tempo, misureremo le

prestazioni degli algoritmi in unità di tempo e non

millisecondi o microsecondi perché queste sono

comunque unità di misura fisiche che dipendono dalla

velocità di esecuzione del processore; vedremo che

esistono algoritmi la cui complessità si misura in milioni

di miliardi di unità di tempo e in questi casi il fatto di

avere un microsecondo o millisecondo non cambia

drasticamente la situazione a livello pratico, per cui si

preferisce analizzare le prestazioni degli algoritmi in

unità di tempo generiche cercando algoritmi che usano

meno unità di tempo in assoluto e non in microsecondi.

Facciamo certe assunzioni:

Ogni accesso alla memoria per una singola cella

4. richiede esattamente un’unità di tempo

indipendentemente dall’indirizzo, quindi il tempo di

accesso è uniforme. Notiamo che questo, ad

esempio non è vero per i dischi magnetici o

meccanici in cui l’accesso alla memoria cambia in

base a dove vogliamo andare e alla posizione della

testina del disco

Nelle operazioni aritmetiche le decisioni semplici,

5. cioè se una variabile è vera o falsa e le chiamate di

funzione sono tutte considerate operazioni

atomiche, quindi una unità di tempo

I cicli e le funzioni complesse, come seno, coseno

6. etc… non sono operazioni semplici, è necessario

indicare il costo nel calcolo di queste operazioni

Osserviamo le seguenti colonne:

Quello che esiste davvero e che compriamo in negozio è

la colonna a destra, quindi la memoria corrisponde a una

schiera di celle che contiene dei valori. La colonna subito

accanto è l’indirizzo in memoria, che non è scritto in

memoria ma c’è una decodifica che permette di

indirizzare una cella, e la colonna ancora a sinistra

contiene il nome della variabile, è il nome che scriviamo

noi nel programma, quindi ogni variabile che scriviamo

in un nostro programma è da considerarsi come il nome

di una o più celle di memoria all’interno di questo array,

tale nome verrà tradotto dal compilatore in due modi

diversi a seconda delle circostanze, verrà tradotto come

l-value, cioè come indirizzo di memoria, o come r-value,

cioè valore corrispondente a quell’indirizzo.

Consideriamo l’operazione z=x+y, il segno di uguale è

un uguale di assegnazione. L’istruzione significa prendi il

valore di x, prendi il valore di y, sommali e metti il

risultato all’indirizzo della variabile z, queste tre variabili

vengono in questo caso tradotte in due modi diversi dal

compilatore, infatti x e y significano valore della variabile

x e valore della variabile y, invece z significa indirizzo

della variabile z, notiamo inoltre che x e y stanno a

destra mentre la z a sinistra, di x e y uso l’r-value (right

value) mentre della z uso l-value (left value). Ogni

variabile del programma ha un r-value e un l-value,

compito del compilatore è calcolare gli indirizzi in modo

tale che si sappia dov’è la variabile in memoria perché la

CPU deve caricare un indirizzo di memoria e non un

nome, a quell’indirizzo c’è un r-value, quello che c’è nella

memoria è l’r-value.

Indirizzamenti

Ora ci chiediamo come facciamo a leggere e scrivere

dati in memoria, per rispondere possiamo dire che le

macchine hanno a disposizione una suite abbastanza

ricca di modi di indirizzamento, cioè modi di andare a

indirizzare i contenuti della memoria, indirizzare significa

individuare il contenuto sia per leggerlo che per

scriverlo, questi modi sono:

Immediare mode:

7. es: z=x+3

in molte architettura l’operazione aritmetica con

costanti, in questo caso 3, non richiedono molti cicli

di memoria perché spesso la costante sta

nell’istruzione stessa, quindi il valore 3 fa parte

dell’istruzione somma stessa, l’unico valore che

devo andare a leggere dalla memoria è il valore di

x, quindi questa operazione z=x+3 si traduce in un

ciclo per fare l’operazione di soma, un’unità per

scrivere il valore di z e uno per leggere il valore di x

Quindi questo indirizzamento si risolve in 3 cicli:

1 per op (‘+’)

· 2 per accesso alla memoria: leggere x e

· scrivere z

Direct mode

8. Es: z=x+y

X e y sono valori che devo leggere dalla memoria, z

è un indirizzo a cui devo scrivere

Questo indirizzamento richiederà 4 cicli:

1 per op (‘+’)

· 3 per accesso alla memoria, cioè per leggere la

· x, per leggere la y e scrivere in z

Notiamo che usare una variabile al posto che usare

una costante mi aumenta di 1 i cicli che sto

eseguendo, rispetto a prima è il 30% in più

Indirect mode

9. Es: z=x+(*y)

*y significa che voglio il valore (cioè in questo caso

56) che sta all’indirizzo il cui valore è memorizzato

nella variabile y

Cioè prende il valore che è nella y cioè 42 e prendi il

valore presente nella cella numero 42

In questa operazione sto facendo z=67+56

Questo indirizzamento è indirect addressing per chi

usa assembler oppure “dereferencing a pointer

variable” per i linguaggi ad alto livello, è quasi la

stessa cosa.

Questa operazione richiede 5 cicli:

1 per op(‘+’)

· 4 per accesso alla memoria: x, y, *y, z

· Indexed mode (constant as index)

10.

Esempio: z=W[2] (la parentesi quadra indica spesso

l’indicizzazion