Sommario
La memoria virtuale rappresenta la separazione della memoria logica, vista dall’utente, dalla memoria fisica.
La memoria virtuale generalmente si realizza nella forma di:
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.
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.
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:
Nell’ultimo caso:
Si individua la locazione nel disco della pagina richiesta.
Si cerca un blocco di memoria libero:
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.
Frequenza di assenza di pagina 0 ≤ p ≤ 1.0
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)
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.
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.
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.
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.
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:
Per una sostituzione non si deve compiere alcuna ricerca.
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:
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
Come scegliere la frequenza di scansione?
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.
Se un processo non dispone di un numero sufficiente di blocchi di memoria, si verificano parecchie assenze di pagine.
Ciò comporta:
Thrashing ≡ degenerazione dell’attività di paginazione
L'atività di paginazione è degenerata in una situazione patologica che fa precipitare la produttività del sistema
Perché la paginazione funziona?
Modello di località
Perché si verifica attività di paginazione degenere?
Σ dimensione della località > dimensione totale della memoria.
Δ ≡ 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).
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.
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.
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 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.
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
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.
1. Introduzione ai Sistemi Operativi
5. Scheduling nei sistemi mono-processore
6. Threads, SMP
8. Scheduling Multiprocessore e Real-Time
9. Gestione dei processi nei sistemi operativi Unix/Linux e Window...
10. Introduzione alla Programmazione Concorrente
11. Sincronizzazione nel modello ad ambiente globale
12. Problemi di cooperazione nel modello ad ambiente globale
14. Sincronizzazione nel modello ad ambiente locale
15. Deadlock
16. Programmazione Multithread
18. Memoria Virtuale
20. Il File System
21. Primitive di sincronizzazione nel kernel Linux
22. Esercitazione: System call per la gestione dei processi
23. Esercitazione: Inteprocess Communication e Shared Memory
24. Esercitazione: System Call per la gestione dei semafori in Linu...
25. Esercitazione: Problema dei Produttori e dei Consumatori
26. Posix Threads
P. Ancilotti, M. Boari, A. Ciampolini, G. Lipari, “Sistemi Operativi”, Mc-Graw-Hill (Cap. 4, par. 4.3.3)