Preparazione all'esame di Calcolatori elettronici

Per poter trovare questa tabella nella memoria principale esiste un registro hardware dove è

memorizzato il suo indirizzo.

Il bit di validità ha lo stesso funzionamento di quello nella cache: se vale 1 la pagina è presente, se

vale 0 la pagina non risiede nella memoria fisica e va cercata nella memoria di massa.

La tabella delle pagine, il PC e i registri costituiscono il cosiddetto stato di una macchina virtuale;

quando un’altra macchina virtuale deve utilizzare il processore, questo stato deve essere salvato

così da poter essere ripristinato in seguito quando la macchina virtuale che sta cedendo il

processore tornerà ad utilizzarlo.

Come abbiamo già ripetuto tante volte, quando il dato non è presente nella memoria fisica (e

quindi il bit di validità è a 0) si verifica una page fault e la pagina dovrà essere ricercata in

memoria, compito del sistema operativo. Quindi al verificarsi di questa page fault verrà sollevata

un’eccezione così da passare il compito al sistema operativo; il problema sta nel fatto che

l’indirizzo virtuale passato al sistema operativo non è sufficiente per risalire alla posizione nella

memoria del dato. In realtà il sistema operativo ha in memoria una struttura dati, chiamata spazio

di swap, dove sono salvati i corrispondenti indirizzi di memoria per ogni indirizzo virtuale del

programma in corso. Per capirci meglio: ogni volta che un programma entra in esecuzione, il

sistema operativo memorizza nel suo spazio di swap una tabella in cui è presente la

corrispondente tra ogni indirizzo virtuale (usato dal programma) e l’indirizzo del dato in memoria.

Questo significa che quando il dato verrà trovato e sostituirà un blocco nella memoria principale, il

blocco sostituito verrà memorizzato nello spazio di swap.

Ricapitoliamo con un disegno:

Il blocco che verrà sostituito sarà determinato dal metodo LRU. In realtà questo metodo è troppo

dispendioso da implementare e per questo motivo di solito ne viene utilizzata una versione più

semplice: il bit di utilizzo. Questo bit viene impostato a 1 ogni volta che la pagina è richiesta e,

ogni un tot di tempo, tutti i bit di utilizzo vengono portati a 0; si cerca di sostituire un blocco con

uno che contenga 0 come bit di utilizzo così significa che non è richiesto da molto tempo.

Ovviamente la tabella delle pagine richiede parecchio spazio, per questo motivo esistono

alcune tecniche per ridurre la quantità di memoria da lei richiesta:

• Memoria per la tabella di dimensione ridotta, la dimensione viene incrementata solo se

necessario (incremento man mano che aumentano le pagine).

• La maggior parte dei processori, tra cui il MIPS, necessita di due aree di memoria per la

memorizzazione dei dati; in questo caso la tabella delle pagine viene divisa in due e ogni

parte potrà crescere “rubando posto” all’altra parte.

• Creare una tabella delle pagine in cui vengono memorizzate solo le pagine fisiche, non le

pagine virtuali vuote.

• Tabella delle pagine suddivisa in pagine.

Cosa succede quando si vuole scrivere in memoria di massa un dato risiedente nella memoria

principale? Come abbiamo già detto qualche pagina fa, il metodo write-through non può essere

implementato in quanto richiederebbe veramente troppo tempo; viene quindi utilizzato il metodo

write-back in cui la scrittura in memoria avviene a blocchi di parole (già che richiederà tanto

tempo tanto vale trasferire grandi dati). Quando il dato viene copiato in memoria, un bit chiamato

dirty bit viene aggiunto alla tabella delle pagine.

Il TLB (Translation Lookaside Buffer)

All’inizio del nostro discorso sulle memorie abbiamo detto che esse sfruttano la località temporale

(dato richiesto dopo poco tempo) e spaziale (probabilmente richiesti anche i dati vicini). Il TLB,

buffer di traduzione consultato a parte, tiene in memoria gli indirizzi virtuali utilizzati più di

recente cosicché non debbano essere ritradotti dopo poco tempo, sfruttando così la località

temporale. E’ più facile capire tutto il funzionamento con uno schema:

L’unico dettaglio, come sempre, risulta capire quale indirizzo sostituire nel TLB; la maggior parte

dei processori sostituiscono un indirizzo a caso.

Anche se è ovvio, nessun dato può essere presente nella cache se non si trova anche nella

memoria virtuale e nella memoria virtuale se non si trova su disco!

Meccanismi di protezione basati sulla memoria virtuale

Abbiamo già detto nell’introduzione alle macchine virtuali che esse servono anche per proteggere

più utenti tra di loro, ora potremmo dire che la memoria virtuale deve essere in grado di far

condividere la stessa memoria principale a più processi proteggendoli tra di loro. Questo significa

che un processo non può scrivere nello spazio di indirizzamento di un altro processo oppure nello

spazio riservato al sistema operativo.

Perché un sistema operativo possa implementare questa protezione è necessario che l’hardware:

• sia in grado di supportare almeno due modalità di funzionamento: esecuzione di processi

utente e modalità kernel (o supervisore, esecuzione di processi del sistema operativo)

• mettere a disposizione dei processi in esecuzione lo stato del processore che, però, potrà

solo essere letto e non modificato, ma con il compito di conoscere sempre come sta

lavorando in quel momento

• fornire dei meccanismi per il passaggio dalle due modalità: da utente a SO (system call) o

viceversa.

Occorre anche evitare, non solo che non venga scritto negli indirizzi di un altro processo, ma anche

che non vengano letti i dati di altri processi; la memoria principale mette a disposizione la

possibilità di proteggerli inserendo le tabelle (in cui sono memorizzate le corrispondenze dei dati)

nella sua parte riservata al sistema operativo.

La gestione delle miss del TLB

Ripetiamo per l’ennesima volta che quando il dato non è presente, in questo caso nel TLB, dovrà

essere cercato in una memoria sottostante e questa ricerca viene fatta via software dal sistema

operativo interpellato tramite una eccezione, una volta gestita l’eccezione e reperito i dati si

riprenderà il normale funzionamento. L’importante, però, è che l’eccezione venga “inviata” subito

prima del termine del ciclo di clock di accesso alla memoria cosicché il ciclo successivo il sistema

operativo sia già all’opera per risolverla e non stia eseguendo le istruzioni seguenti (in pratica la

pipeline viene “azzerata” per essere sostituita da istruzioni di ricerca nella memoria).

Vediamo come risolve l’eccezione il sistema operativo:

• con l’indirizzo virtuale cerca nella tabella il corrispondente indirizzo fisico

• sceglie quale pagina della memoria principale verrà sostituita e quindi, per la tecnica write-

back, copia questa pagina da sostituire nella memoria impostando il suo dirty bit a 1

• legge dal disco e copia il dato nella pagina della memoria principale.

Una volta che il dato è stato trasferito correttamente il sistema operativo rimanda in esecuzione

l’istruzione che aveva generato una page fault e che ora non la genererà più.

Forse non ci siamo accorti che abbiamo gestito l’eccezione mediante il passaggio ai due

funzionamenti: utente kernel utente.

à à

Le eccezioni nel MIPS

Applichiamo il discorso generale al nostro processore MIPS:

• si verifica una miss salvataggio della pagina richiesta in un registro speciale chiamato

à

badVAddr (bad Virtual Address) e richiesta del SO

• trasferimento nell’indirizzo che gestisce le eccezioni (8000 0000 ) e caricamento dei dati

esa

per il calcolo dell’indirizzo in cui si trova il dato in un registro speciale chiamato Context

• gestione eccezione viene copiato Context in $k1 e poi, sempre in $k1 viene caricato

à

l’indirizzo corretto trovato.

Il MIPS ha inoltre un’istruzioni apposita per trattare il TLB: tlbwr (TLB Write Random) permette la

sostituzione di un blocco random del TLB. Una miss del TLB viene gestita in circa dieci cicli di clock;

ovviamente se il dato non è presente nemmeno nella memoria principale (page fault) saranno

necessari più cicli e più elaborazione.

Ricordiamo che, sì, esistono istruzioni apposite per la gestione delle eccezioni ma la vera

gestione viene fatta da codice C!

Riepilogo generale: rispondiamo alle domande

Dove può essere posizionato un blocco?

Ci sono tre opzioni: mappatura diretta (in una sola possibile locazione), mappatura set-associativa

(più locazioni possibili) oppure mappatura completamente associativa (ogni locazione è buona per

contenere il dato). Più l’associatività è alta meno miss verranno generate.

Come si trova un blocco?

Dipende dal grado di associatività ma, in generale, l’indirizzo è diviso in: tag, indice e blocco.

Inoltre nei sistemi a memoria virtuale è presente una tabella che mette in relazione l’indirizzo

virtuale con l’indirizzo fisico di dove risiede il dato in memoria.

Quale blocco sostituire in caso di miss?

Anche in questo caso dipende dal tipo di mappatura: se si tratta di mappatura diretta abbiamo

solo una possibilità mentre se si tratta di mappatura completamente associativa ogni blocco è un

potenziale candidato e verrà scelto quello non utilizzato da più tempo (LRU… abbiamo visto

solitamente approssimata).

Cosa succede in caso di scrittura?

Abbiamo due possibili opzioni: write-through (scrittura contemporanea) oppure write-back

(scrittura quando dato richiesto di nuovo). Le memorie virtuali utilizzano sempre la modalità write-

back perché la write-through sarebbe troppo dispendiosa in termini di tempo.

Quali sono le possibili cause di una miss?

Di solito vengono riassunte come modello delle tre C:

• Compulsory miss (miss obbligate): accadono per forza all’inizio di un programma quando la

cache è vuota e quindi nessun dato richiesto è presente

• Capacity miss (miss di capacità): la cache non è in grado di contenere tutti i dati e quindi si

verifica una miss di capacità quando un dato scartato per far posto ad un altro viene

richiesto dopo poco tempo

• Conflict miss (miss di conflitto): si verificano nella mappatura diretta o nella set-associativa

quando più dati competono per la stessa locazione nella cache. Queste miss si risolvono

utilizzando una cache completamente associativa.

Il controllo semplificato della cache

La cache è dotata di un controllore che può assumere quattro possibili stati:

• Idle (i