Sistemi Operativi - 10: Memoria Virtuale

Memoria Virtuale

• La memoria virtuale (MV) è un insieme di tecniche che permettono l'esecuzione di processi, dove codice e/o dati non sono caricati completamente in memoria primaria.
• I metodi di gestione della memoria principale (MP) tentano di tenere in RAM il maggior numero di processi possibile per aumentare la multiprogrammazione.
• Per una certa quantità di RAM disponibile in un sistema, il numero di processi che possono stare in MP dipende dalla loro dimensione.
• La MV funziona perché i programmi non hanno bisogno di essere caricati interamente in MP per essere eseguiti.
• Esempi di casi in cui ciò si verifica includono codice per trattare condizioni di errore, array, liste, tabelle dichiarate con dimensioni maggiori di quanto effettivamente usate e librerie dinamiche caricate solo quando usate.
• L'idea di fondo della MV è caricare in MP solo le parti di programma/dati che devono essere effettivamente eseguite in un certo momento dell'esecuzione.

Paginazione su Richiesta (Demand Paging)

• Idea di base: portare una pagina in MP solo nel momento in cui è richiesto l'accesso ad una locazione di memoria appartenente a quella pagina (un dato o un'istruzione).
• Quando la CPU esegue un'istruzione che indirizza una locazione di RAM in una pagina diversa da quella in esecuzione e la pagina non è in MP, si dice che il processo ha generato un "page fault".
• Il sistema operativo (SO) deve sospendere il processo, caricare la pagina mancante in memoria e ripartire il processo dal punto in cui era stato sospeso.
• Un modulo del SO, detto "pager", si occupa del caricamento della pagina mancante dalla memoria secondaria (MS) in un frame libero della memoria principale (MP).
• In attesa di completare il caricamento, la CPU viene assegnata ad un altro processo.
• Quando la pagina è in MP, il processo corrispondente viene rimesso nella coda di ready e riprenderà l'esecuzione dall'istruzione che aveva causato il problema quando sarà scelto dallo scheduler.

Prestazioni della Paginazione su Richiesta

• Supponiamo di dover leggere un dato in MP. Se il dato è presente, il tempo di accesso è di circa 100-200 nanosecondi (ma). Se c'è un page fault, il tempo di gestione del page fault si aggiunge al tempo di accesso alla pagina, che è piuttosto lungo (circa 8 millisecondi).
• eat (effective access time) = [(1-p) x ma] + [p x tempo di gestione del page fault], dove p è la probabilità di un page fault.
• La gestione di un page fault richiede la gestione del page fault (circa 1-100 μsec), il recupero della pagina mancante dalla memoria secondaria (circa 8 millisecondi) e il riavvio del processo (circa 1-100 μsec)
• Il tempo di esecuzione rallenta a causa della gestione del page fault (p).
• Per minimizzare il degrado, la probabilità di page fault (p) deve essere molto bassa (es. <2.5 x 10^-6, ovvero meno di un page fault ogni 400.000 accessi in memoria).

L'area di Swap

• La memoria virtuale ha bisogno di una porzione dell'hard disk (HD) detta area di Swap.
• All'installazione, sull'HD viene riservata una porzione del disco ad uso esclusivo del SO.
• L'area di swap è gestita con meccanismi più semplici ed efficienti rispetto al file system per quanto riguarda il posizionamento di pagine dei processi.

Sostituzione delle Pagine

• Il SO, in caso di page fault e mancanza di frame liberi in RAM, sceglie una "pagina vittima" da rimuovere dalla RAM, salva la pagina vittima nella swap area (se necessario) e carica la pagina mancante nel frame liberato.
• Le pagine di codice non devono essere salvate in swap perché c'è una copia nel file system.
• Le pagine di dati modificate devono essere salvate in swap prima di essere rimosse, per mantenere le modifiche.
• Un dirty bit fa capire se una pagina è stata modificata o meno; il SO salva nella swap solo le pagine con il dirty bit a 1.

Algoritmi di Sostituzione delle Pagine

• Un buon algoritmo di sostituzione minimizza il numero di page fault.
• Vari metodi di valutazione possono essere utilizzati per testare la bontà di differenti algoritmi di sostituzione, come sequenze di riferimenti casuali o generate da programmi reali.

Allocazione dei Frame

• In un sistema multiprogrammato, come distribuiamo i frame disponibili fra i processi?
• Possibili strategie includono un numero uguale di frame per ogni processo, proporzionale alle dimensioni dei processi o alle loro priorità.

Allocazione Globale e Locale

• Allocazione globale: la pagina vittima viene scelta tra tutte le pagine in memoria principale (escluso il SO).
• Allocazione locale: la pagina vittima viene scelta tra le pagine del processo che ha generato il page fault.
• Le allocazioni globali sono generalmente preferite per sistemi time sharing perché forniscono un throughput più elevato.

Thrashing

• Il thrashing è un fenomeno di elevata attività di paginazione che peggiora le prestazioni del sistema se i frame sono pochi.
• Thrashing avviene quando i processi sono costantemente impegnati a caricare e scaricare pagine da/nella memoria principale, causando molti page fault.
• Il thrashing può essere ridotto diminuendo il numero di processi attivi contemporaneamente.

Altri considerazioni: dimensione delle pagine

• Le pagine tendono ad essere delle potenze di 2 (es. 4k, 8k) e le dimensioni ottimali delle pagine dipendono da vari fattori, tra cui la grandezza della tabella delle pagine (PT), la frammentazione interna e la latenza del disco.
• Le pagine piccole (i.e., "più piccole" delle dimensioni tipiche) generano più page fault, mentre le pagine grandi (i.e., "più grandi" delle dimensioni tipiche) possono portare a frammentazione interna e a più operazioni di lettura/scrittura sul disco.

Struttura dei Programmi

• La struttura dei programmi influenza il numero di page fault.
• Gli array bidimensionali allocati per riga tendono a generare meno page fault rispetto agli array allocati per colonna in casi in cui si accede agli elementi dei dati secondo le colonne.
• Le hash table possono generare molti page fault a causa del loro pattern di accesso non sequenziale.

Windows 10

• Windows 10 utilizza una tecnica di clustering nella demand paging, caricando anche pagine adiacenti a quella richiesta.
• Imposta un insieme di lavoro minimo e massimo per quantificare le pagine in RAM per processo.
• Adotta un algoritmo di sostituzione che utilizza la seconda chance per decidere quali pagine rimuovere quando la RAM è a capacità piena.

Solaris

• Solaris impiegano una paginazione su richiesta standard, ma gestisce i frame liberi.
• C'è un parametro lostfree, equivalente a circa 1/64 dei frame totali, che segnala la potenziale mancanza di frame liberi.
• Il processo pageout viene attivato se la quantità di frame liberi scende al di sotto del valore lostfree.
• Il processo pageout opera in due fasi: la scansione di tutte le pagine in memoria principale per azzerare il bit di riferimento e una seconda scansione delle pagine (in cui quelle senza bit di riferimento vengono riutilizzate e, se modificate, salvate in memoria secondaria prima di essere riutilizzate)