Vai alla Home Page About me Courseware Federica Living Library Federica Virtual Campus 3D Le Miniguide all'orientamento Gli eBook di Federica
 
 
Il Corso Le lezioni del Corso La Cattedra
 
Materiali di approfondimento Risorse Web Il Podcast di questa lezione

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?

Esempio:

  • Memoria 32 MB
  • S.O. 8 MB
  • 3 processi di 8 MB
  • Pagine di 2 MB

Altri processi non possono utilizzare la memoria Soluzione: Tenere in memoria centrale solo la pagine correntemente in esecuzione di ogni processo, mentre le altre possono risiedere in memoria di massa

Esempio

Esempio


La memoria virtuale

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

Esempi


Memoria gerarchica

Esempio: 16 QAM

Esempio: 16 QAM


Page fault

Un bit di validità viene associato a ciascun elemento della tabella delle pagine

(1 ⇒ in memoria, 0 ⇒ non in memoria).

Page fault

Page fault


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

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

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

Prestazioni della paginazione su richiesta

Page Fault Rate: 0 ≤ p ≤ 1.0 e’ la percentuale dei page fault sul numero totale dei riferimenti

se p = 0 non si hanno page fault;

se p = 1, ciascun riferimento è un fault.

Tempo medio di accesso (EAT):

Tempo medio di accesso

Tempo medio di accesso


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

Il principio di localita’

Esempio di riferimenti in memoria di un programma in esecuzione

Localita’ spaziale (pagine vicine allo stesso istante)
Localita’ temporale (stesse pagine per un intervallo di tempo)

Il principio di località

Il principio di località


Prossima lezione

Gli algoritmi di avvicendamento delle pagine

  • Algoritmi con numero di frame costanti
  • Algoritmi con numero di frame variabili
  • Contenuti protetti da Creative Commons
  • Feed RSS
  • Condividi su FriendFeed
  • Condividi su Facebook
  • Segnala su Twitter
  • Condividi su LinkedIn
Progetto "Campus Virtuale" dell'Università degli Studi di Napoli Federico II, realizzato con il cofinanziamento dell'Unione europea. Asse V - Società dell'informazione - Obiettivo Operativo 5.1 e-Government ed e-Inclusion