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

Domenico Cotroneo » 18.Memoria Virtuale


Memoria virtuale

Sommario

  • Introduzione
  • Paginazione su richiesta
  • Sostituzione delle pagine
  • Attività di paginazione degenere (thrashing)
  • Modello del working set

Introduzione

La memoria virtuale rappresenta la separazione della memoria logica, vista dall’utente, dalla memoria fisica.

  • Solo parte del programma deve essere in memoria per l’esecuzione.
  • Lo spazio degli indirizzi logici può essere maggiore dello spazio degli indirizzi fisici.
  • Consente anche un miglioramento delle prestazioni durante la creazione dei processi.

La memoria virtuale generalmente si realizza nella forma di:

  • paginazione su richiesta (demand paging);
  • segmentazione su richiesta (demand segmentation).

Schema di memoria virtuale


Paginazione su richiesta

Non si carica mai nella memoria una pagina che non sia necessaria.

Minore tempo di swap.

Minore quantità di memoria fisica.

Risposta più veloce.

Più utenti.

Trasferimento di una memoria paginata nello spazio contiguo di un disco


Bit di validità

A ciascun elemento della tabella delle pagine è associato un bit di validità (1 => in memoria, 0 => non in memoria).

Inizialmente il bit di validità è impostato a 0.

Durante la traduzione degli indirizzi, se il bit di validità nella tabella delle pagine è 0 => pagina non valida.

Istantanea di una tabella delle pagine

Istantanea di una tabella delle pagine


Tabella delle pagine quando alcune paginenon si trovano nella memoria centrale


Page Fault

Se il processo tenta di accedere a una pagina che non era stata caricata nella memoria, si verifica un’eccezione di pagina mancante (page fault trap).

L’architettura di paginazione, traducendo l’indirizzo, nota che il bit non è valido e invia un segnale d’eccezione al sistema operativo.

Il sistema operativo deve decidere:

  • errore di indirizzo non valido => abort;
  • Caricamento della pagina in memoria.

Nell’ultimo caso:

  • si individua un blocco di memoria libero;
  • si trasferisce la pagina desiderata nel blocco di memoria libero;
  • si aggiornano le tabelle, bit di validità = 1;
  • si riavvia l’istruzione che era stata interrotta del segnale di eccezione.

Fasi di gestione di un Page FAULT


Schema di base

Si individua la locazione nel disco della pagina richiesta.

Si cerca un blocco di memoria libero:

  • se esiste, lo si usa;
  • altrimenti, si impiega un algoritmo di sostituzione delle pagine per scegliere un blocco di memoria “vittima”.

Si scrive la pagina richiesta nel blocco di memoria appena liberato; si modificano le tabelle delle pagine e dei blocchi di memoria.

Si riavvia il processo utente.

Prestazioni della paginazione su richiesta

Frequenza di assenza di pagina 0 ≤ p ≤ 1.0

  • Se p = 0 non si verifica assenza di pagina (page fault)
  • Se p = 1, ogni riferimento è un’assenza di pagina

Tempo d’accesso effettivo (EAT, effective access time)

EAT = (1 – p) × accesso alla memoria

+ p (page fault overhead
+ [swap page out ]
+ swap page in
+ restart overhead)

Sostituzione delle pagine

Previene la sovrassegnazione della memoria.

Utilizza un bit di modifica (dirty bit) per ridurre il sovraccarico: solo le pagine modificate vengono scritte su disco.

La sostituzione delle pagine completa la separazione tra memoria logica e memoria fisica.

Algoritmi di sostituzione delle pagine

Si desidera la minor frequenza di assenza di pagine.

Si valuta l’algoritmo su una particolare successione (stringa) di riferimenti (reference string) e si calcola il numero di assenze di pagine su quella successione.

In tutti i nostri esempi, la stringa di riferimento è:

1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5.

Algoritmo FIFO


Curva delle assenze di pagine per sostituzione FIFOsu una successione di riferimenti


Sostituzione delle pagine ottimale

Si sostituisce la pagina che non si userà per il periodo di tempo più lungo.

È possibile conoscere in anticipo la successione dei riferimenti?

Usato principalmente per studi comparativi, per valutare le prestazioni degli algoritmi.


Algoritmo LRU (Least Recently Used)

Successione dei riferimenti: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5

Contatori

A ogni elemento della tabella delle pagine si associa un campo del momento d’uso, e alla CPU si aggiunge un contatore che si incrementa a ogni riferimento alla memoria. Ogni volta che si fa un riferimento a una pagina, si copia il contenuto del registro contatore nel campo del momento d’uso nella tabella relativa a quella specifica pagina.

Quando occorre sostituire una pagina, si sostituisce quella con il valore associato più piccolo.


Algoritmo LRU

Pila: la miglior realizzazione si ottiene usando una lista doppiamente concatenata, con un puntatore all’elemento iniziale e uno a quello finale.

Ogni volta che si fa riferimento a una pagina:

  • la si estrae dalla pila e la si colloca in cima;
  • nel caso peggiore è necessario modificare sei puntatori.

Per una sostituzione non si deve compiere alcuna ricerca.

Sostituzione delle pagineper approssimazione a LRU

Bit di riferimento
A ciascuna pagina è associato un bit, inizialmente = 0.
Ogni volta che si fa riferimento a quella pagina, il bit è impostato a 1.
Si sostituisce quella che è a 0 (se esiste). Non è però possibile conoscere l’ordine d’uso.

Con seconda chance
Occorre il bit di riferimento.
Un puntatore (vittima) indica qual è la prima pagina da sostituire.
Se la pagina da sostituire (in ordine di clock) ha il bit di riferimento = 1, allora:

  • imposta il bit di riferimmento a 0;
  • lascia la pagina in memoria;
  • sostituisce la pagina successiva (in ordine di clock), soggetta alle stesse regole.

Algoritmo di rimpiazzamento second-chance

a) all’inizio dell’algoritmo

a) all'inizio dell'algoritmo

b) alla fine dell’algoritmo

b) alla fine dell'algoritmo


Rimpiazzamento periodico delle pagine

Molti sistemi prevedono di mantenere sempre disponibili un certo numero di pagine fisiche in modo da gestire più velocemente i page-fault
A tal fine, il sistema effettua una scansione periodica della memoria per rimpiazzare un certo numero di pagine, scegliendole ad esempio con criterio LRU

  • In realtà le pagine scelte vengono marcate come non valide, e quindi soggette a swap-out solo se modificate e quando la pagina fisica viene effettivamente rimpiazzata con una nuova pagina.
  • Qualora una delle pagine rimpiazzate fosse richiesta dal processo cui è stata tolta prima di essere usata per caricarvi una nuova pagina logica, il processo potrebbe riprenderla senza effettuare un trasferimento dal disco.

Come scegliere la frequenza di scansione?

La soluzione di Solaris 2

Mantiene una lista delle pagine libere da assegnare ai processi che ne abbiano bisogno.

Lotsfree: parametro associato alla lista delle pagine libere.

La paginazione è eseguita attraverso un processo noto come pageout.

Pageout scandisce le pagine usando un algoritmo con seconda chance modificato.

Scanrate è la frequenza di scansione delle pagine ed è compresa tra i valori slowscan e fastscan.

Pageout è eseguito più frequentemente a seconda del quantitativo di memoria libera disponibile.

Scansione delle pagine nel Solaris 2


Attività di paginazione degenere

Se un processo non dispone di un numero sufficiente di blocchi di memoria, si verificano parecchie assenze di pagine.

Ciò comporta:

  • basso utilizzo della CPU (ciò indurrà lo scheduler di lungo termine ad ammettere nuovi processi in memoria);
  • il processo continua a subire un numero sempre maggiore assenze di pagine, facendo sostituire pagine che saranno immediatamente riprese.

Thrashing ≡ degenerazione dell’attività di paginazione

Attività di paginazione degenere

L’atività di paginazione è degenerata in una situazione patologica che fa precipitare la produttività del sistema

L'atività di paginazione è degenerata in una situazione patologica che fa precipitare la produttività del sistema


Alcune considerazioni

Perché la paginazione funziona?

Modello di località

  • Un processo, durante la sua esecuzione, si sposta di località in località.
  • Le località si possono sovrapporre.

Perché si verifica attività di paginazione degenere?

Σ dimensione della località > dimensione totale della memoria.

Modello dell’insieme di lavoro

Δ ≡ finestra dell’insieme di lavoro ≡ numero fisso di riferimenti alle pagine.

Esempio: 10.000 istruzioni

WSSi (dimensione dell’insieme di lavoro del process Pi) =numero totale delle pagine cui il processo fa riferimento durante la sua esecuzione Δ (varia nel tempo).

  • Se Δ è troppo piccolo, non include l’intera località.
  • Se Δ è troppo grande, può sovrapporre più località.
  • Se Δ = ∞ → l’insieme di lavoro coincide con l’insieme di pagine cui il processo fa riferimento durante la sua esecuzione.

D = Σ WSSi ≡richiesta totale dei blocchi di memoria.
Se D > m (blocchi liberi) → l’attività di paginazione degenera (thrashing), in questo caso il sistema operativo individua un processo da sospendere.

Modello dell’insieme di lavoro


Tecnica delle frequenza delle assenze di pagine

Stabilisce un tasso “accettabile” di assenza delle pagine.

Se la frequenza delle assenze di pagine è molto bassa, il processo potrebbe disporre di troppi blocchi di memoria.

Se la frequenza delle assenze di pagine è eccessiva, significa che il processo necessita di più blocchi di memoria.


Altre considerazioni

  • Portata del TLB
  • Struttura del programma
  • Vincoli di I/O

Altre considerazioni

Portata del TLB (TLB reach): quantità di memoria accessibile dal TLB.

Portata del TLB = (numero di elementi) X (dimensione delle pagine).

Idealmente, il TLB dovrebbe contenere l’insieme di lavoro di un processo; altrimenti vi sarà un elevato grado di assenza delle pagine.

Aumentare la portata del TLB

Aumentare la dimensione delle pagine

Potrebbe portare a una maggiore frammentazione della memoria relativamente alle applicazioni che non richiedono pagine così grandi.

Impiegare diverse dimensioni delle pagine

Ciò consente alle applicazioni che richiedono dimensioni di pagina maggiori di utilizzarle senza che si verifichi un aumento della frammentazione.

Altre considerazioni

Struttura del programma
int A[][] = new int[1024][1024];
Ciascuna riga è memorizzata in una pagina

Programma 1

for (j = 0; j < A.length; j++)

for (i = 0; i < A.length; i++)

A[i,j] = 0;

1024 x 1024 assenze di pagine

Programma 2

for (i = 0; i < A.length; i++)

for (j = 0; j < A.length; j++)

A[i,j] = 0;

1024 assenze di pagine

Altre considerazioni

Vincolo di I/O

Talvolta occorre permettere che alcune pagine si possano vincolare alla memoria.

Prendiamo in considerazione l’I/O.

Le pagine utilizzate per la copia di un file da un dispositivo non possono essere selezionate per la sostituzione. Completato l’I/O, si rimuove il vincolo.

I materiali di supporto della lezione

P. Ancilotti, M. Boari, A. Ciampolini, G. Lipari, “Sistemi Operativi”, Mc-Graw-Hill (Cap. 4, par. 4.3.3)

  • 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