Marco Lapegna » 13.La memoria virtuale

Sistemi operativi

La memoria virtuale

Background

La memoria e’ di solito gestita mediante tecniche di allocazione non contigua:

• Paginazione
• Segmentazione
• Tecniche ibride

Motivazione principale : Riduzione della frammentazione

Ci sono altri vantaggi ad usare tecniche di allocazione non contigua?

La memoria virtuale

Memoria virtuale

La memoria virtuale

La memoria virtuale e’ lo spazio di indirizzamento effettivamente utilizzabile dall’utente
Lo spazio logico degli indirizzi e’ più grande dello spazio fisico

Un maggior numero di processi puo’ concorrere all’uso della CPU

Esempi:

Esempi

Memoria gerarchica

Esempio: 16 QAM

Gestione del Page fault

Se la pagina referenziata non e’ in memoria viene mandata una interruzione al SO che consulta la tabella delle pagine per decidere se si tratta di…

• riferimento non valido ⇒ abort;
• pagina non in memoria.

Si accede alla pagina sul disco.

Si sposta la pagina in un frame libero

Si aggiorna la tabella (bit di validità = 1).

Viene riavviata l’istruzione che era stata interrotta.

Gestione del Page fault

Gestione del Page fault

Problema

Non sempre e’ presente in memoria un frame libero

Se esiste un frame libero, viene utilizzato.

Altrimenti viene utilizzato un algoritmo di sostituzione per selezionare un frame vittima.

La pagina vittima viene scritta sul disco e la pagina richiesta viene letta nel frame appena liberato;

Modifica delle tabelle delle pagine e dei frame.

Riavvio del processo utente.

Avvicendamento delle pagine

C.1 La pagina vittima viene scritta sul disco

C.2 il bit di validita’ della pagina vittima viene posto = 0

C.3 la pagina richiesta viene letta nel frame appena liberato

C.4 il bit di validita’ della pagina richiesta viene posto = 1

Avvicendamento delle pagine

Avvicendamento delle pagine

Paginazione su richiesta

porta una pagina in memoria solo quando è richiesta:

Vantaggi:

• in memoria ci sono tutte e sole le pagine necessarie
• maggior grado di multiprogrammazione

Svantaggi

• possibilita’ di notevole overhead

Esempio di paginazione su richiesta

Tempo di accesso alla memoria = 1 μ sec

Tempo di page fault = 10 msec = 10000 μ sec

p=0.5 (il 50% dei riferimenti produce un page fault)

EAT = 0.5 x 1 + 0.5 x 10000 ~ 5000 (in μ sec)

Esempio di paginazione su richiesta

Se un accesso su 1000 causa un p.f. (p=0.001),

EAT = 0.999 x 1 + 0.001 x 10000 ~ 11 μ sec ⇒ l’accesso in memoria viene rallentato di un fattore 11.

Se si desidera un rallentamento inferiore al 10%:

EAT = (1-p) x 1 + p x 10000 < 1.1 μ sec ⇒

9999p < 0.1 ⇒ p < 0.00001…

può essere permesso al piu’

un page fault ogni 100000 accessi in memoria.

Come migliorare le prestazioni ?

IDEA: Se una pagina selezionata come vittima non e’ stata modificata, si puo’ semplicemente riscriverci sopra, evitando lo swap-out e “dimezzando” l’I/O

L’informazione sull’eventuale modifica di una pagina e’ conservata in un bit associato alla pagina (dirty bit)

• dirty bit = 0 pagina non modificata
• dirty bit = 1 pagina modificata

Come migliorare le prestazioni ?

Al momento dell’avvicendamento della pagina, il S.O. esamina il dirty bit e decide se salvare la pagina vittima sul disco

Per aumentare la probabilita’ che il dirty bit = 0 al momento della sostituzione, il S.O. periodicamente

• Copia su disco le pagine con dirty bit=1
• Pone il d.b. =0

Un’alternativa: paginazione anticipata

Il S.O. cerca di prevedere quali pagine saranno richieste dal processo in esecuzione e le carica prima di quando vengono effettivamente richieste

Vantaggi

• Se il sistema e’ capace di effettuare la previsione si evita l’overhead della paginazione su richiesta

Svantaggi

• Deve essere progettato con attenzione per evitare di portare in memoria pagine inutili al posto di quelle che effettivamente serviranno

Possibile soluzione: approccio combinato

ESEMPIO: Linux

In caso di page fault, carica in memoria non solo la pagina mancante ma anche un piccolo gruppo di pagine adiacenti dello stesso processo

• 4 pagine (16 KB) se la memoria < 16 MB
• 8 pagine (32 KB) altrimenti

Idea alla base di tale scelta: se viene referenziata una pagina, probabilmente in un prossimo futuro serviranno anche quelle adiacenti (principio della localita’ spaziale)

Paginatore

Il modulo del S.O. Incaricato dell’avvicendamento delle pagine e’ chiamato PAGINATORE

Esistono molti algoritmi alla base dei paginatori con l’obiettivo comune di minimizzare la frequenza di page fault.

Paginatore

Obiettivo: Favorire i processi che esibiscono il principio di localita’

• Localita’ spaziale : processi che in ogni istante usano pagine vicine
• Localita’ temporale: processi che per un intervallo di tempo usano le stesse pagine

Prossima lezione

Gli algoritmi di avvicendamento delle pagine

• Algoritmi con numero di frame costanti
• Algoritmi con numero di frame variabili