Gestione Avanzata della Memoria Virtuale: Paginazione, Segmentazione e Algoritmi di Sostituzione

Strutture Hardware e di Controllo della Memoria

• Tutti i riferimenti alla memoria all'interno di un processo sono *indirizzi logici* che devono essere tradotti in indirizzi fisici durante l'esecuzione.
• Un processo può essere diviso in più parti (pagine o segmenti) e non è necessario che siano contigui durante l'esecuzione.
  • Ciò è reso possibile dalla combinazione di traduzione dinamica degli indirizzi e l'uso di tabelle di pagina o di segmento.

Esecuzione di un Programma e Meccanismo di Page Fault

• Il sistema operativo carica in memoria principale solo pochi frammenti del programma, incluso il frammento contenente l'inizio del programma.
• Il **set residente** del processo è la parte del processo che è effettivamente in memoria principale.
• Se il processore rileva un indirizzo che non è in memoria principale (un *page fault*), genera un interrupt.
• Il sistema operativo pone il processo interrotto nello stato di blocco.

• Il frammento del processo che ha causato l'errore viene portato in memoria principale, per cui il sistema operativo:
  • Emette una richiesta di lettura I/O su disco.
  • Rilascia un altro processo per l'esecuzione mentre l'operazione di I/O è in corso.
  • Una volta completata la transazione di I/O, viene inviato un interrupt e il sistema operativo modifica lo stato del processo interessato nello stato *Pronto*.

Vantaggi della Memoria Virtuale

• Più processi possono essere mantenuti nella memoria principale.
  • Vengono caricati in memoria principale solo pochi frammenti del processo.
  • Un uso più efficiente dei processori.

Almeno un processo, tra i molti che sono in memoria principale, sarà nello stato *Pronto*.

• È possibile che un processo sia più grande dell'intera memoria principale.
  • Con la paginazione o la segmentazione della memoria virtuale, il programmatore non deve preoccuparsi se il suo programma è troppo grande.

Tipi di Memoria in Esecuzione

• Memoria Reale
  • Memoria Principale
• Memoria Virtuale
  • Permette una multiprogrammazione efficace.
  • Rimuove i vincoli di dimensione della memoria per l'utente.

Thrashing (Eccessivo Scambio di Pagine)

• Se un frammento viene espulso poco prima dell'uso, è necessario riportarlo quasi subito.
• Troppi scambi portano al *thrashing*.
• Il processore impiega più tempo nello scambio di frammenti che nell'esecuzione delle istruzioni utili.

Principio di Località (Prossimità)

• I riferimenti ai dati e al programma all'interno di un processo tendono a raggrupparsi (*clustering*).
• Per brevi periodi di tempo, saranno necessari solo pochi frammenti del processo.
• Previsioni intelligenti su quali porzioni di un processo saranno necessarie nel prossimo futuro.

Supporto Necessario per la Memoria Virtuale

• L'hardware deve supportare paginazione e segmentazione.
• Il sistema operativo deve includere software per gestire i movimenti di pagine o segmenti tra memoria principale e secondaria.

Dettagli sulla Paginazione

• Ogni processo ha la sua tabella delle pagine.
• Ogni voce nella tabella delle pagine contiene il numero di *frame* (telaio) della pagina corrispondente in memoria principale.
• Un **bit** è necessario per indicare se la pagina è in memoria principale o meno (bit di presenza).
• Un altro **bit** (bit di modifica/dirty bit) viene utilizzato per indicare se il contenuto della pagina è stato modificato da quando è stata caricata in memoria principale. Se non ci sono state modifiche, non è necessario aggiornare la pagina quando viene sostituita.

Tabelle delle Pagine (Page Tables)

• C'è una tabella delle pagine per ogni processo.
• Alcune tabelle possono occupare grandi quantità di memoria principale.
• Le tabelle delle pagine vengono memorizzate in memoria virtuale.
• Quando un processo è in esecuzione, almeno una parte della tabella delle pagine deve essere in memoria principale.

Buffer di Traduzione Avanzato (TLB)

• Ogni riferimento alla memoria può generare due accessi alla memoria:
  • Per l'accesso alla voce della tabella di pagina.
  • Per ottenere i dati desiderati.
  • Per risolvere questo problema, la maggior parte dei sistemi di memoria virtuale utilizza una cache speciale per le voci della tabella di pagina, chiamata **TLB** (*Translation Lookaside Buffer*).
• Contiene le voci della tabella delle pagine usate più di recente.
• Quando il processore riceve un indirizzo virtuale, esamina il TLB.
• Se la voce della tabella di pagina è presente (TLB hit), ottiene il numero di *frame* e può calcolare l'indirizzo fisico effettivo.
• Se non trovato, il processore utilizza il numero di pagina come un indice per cercare la tabella delle pagine del processo.
• Se viene trovato, il bit di presenza attivo indica che la pagina è in memoria principale e il processore può ottenere il numero di *frame* e, di conseguenza, l'indirizzo fisico.
• Il processore aggiorna il TLB.
• D'altra parte, se il bit di presenza non è attivo, significa che la pagina non è in memoria principale, causando un difetto di memoria chiamato *page fault*.

Dimensione della Pagina (Page Size)

• Più piccola è la dimensione della pagina, minore è la frammentazione interna.
• Più piccola è la pagina, maggiore è il numero di pagine necessarie per ogni processo.
• Più pagine significano tabelle delle pagine più grandi.
• Nelle tabelle delle pagine di grandi dimensioni, molte delle tabelle saranno in memoria virtuale.
• Le caratteristiche fisiche della maggior parte dei dispositivi di memorizzazione secondari sono adatte per dimensioni di pagina più grandi.
• Pagine di piccola dimensione: minor numero di pagine disponibili in memoria principale.
• Dopo un po', tutte le pagine in memoria contengono alcuni dei riferimenti recenti del processo. Pertanto, gli errori di pagina saranno minori.
• Quando la dimensione della pagina aumenta, essa può contenere posizioni di riferimento distanti da quelle recenti, aumentando il rischio di *page fault*.
• Diverse dimensioni di pagina forniscono una maggiore flessibilità nell'uso del TLB.
• Le pagine più grandi possono essere assegnate alle istruzioni del programma.
• Le pagine di piccole dimensioni possono essere assegnate allo *stack* di un *thread*.

Segmentazione

• La segmentazione consente allo sviluppatore di considerare la memoria come se fosse composta da spazi di indirizzi multipli.
• I segmenti possono essere di diverse dimensioni, anche in modo dinamico.
• Gli indirizzi di memoria sono costituiti dal numero del segmento e dallo *spostamento* (offset).
• Semplifica la gestione di strutture dati in crescita.
• Consente di modificare e ricompilare i segmenti del programma in modo indipendente.
• Consente la condivisione di dati tra processi.
• Permette la protezione.

Tabella dei Segmenti

• Ogni voce della tabella contiene l'indirizzo iniziale del segmento in memoria principale e la sua lunghezza.
• Contiene un **bit** che indica se il segmento è già nella memoria principale (bit di presenza).
• Contiene un **bit** che indica se il segmento è stato modificato da quando è stato caricato in memoria principale (bit di modifica).
• Contiene altri bit di controllo: protezione e condivisione.

Combinazione di Paginazione e Segmentazione

• Sfruttando i vantaggi di paginazione e segmentazione.
  • Ogni segmento può essere diviso in pagine di dimensione fissa.
  • Associata a ogni processo c'è una tabella dei segmenti e diverse tabelle delle pagine.

Protezione e Condivisione della Memoria

• Utilizzo di un sistema basato su *anelli* di protezione (Rings).
• Gli anelli interni hanno più privilegi.
• Un programma può accedere ai dati solo degli anelli con privilegi uguali o inferiori.
• Un programma può effettuare chiamate a servizi che si trovano sullo stesso anello o su anelli con privilegi superiori.

Politiche del Sistema Operativo per la Memoria Virtuale

La progettazione della gestione della memoria in un sistema operativo dipende da tre aree:

• Se vengono utilizzate o meno tecniche di memoria virtuale.
• L'uso combinato di segmentazione e paginazione.
• Gli algoritmi per la gestione della memoria.

Le prime due voci dipendono dalla piattaforma hardware disponibile. Il terzo punto è di competenza del software del sistema operativo.

Algoritmi per la Gestione della Memoria

• Performance: l'obiettivo è minimizzare il *page fault* (errore di memoria).
  • Un difetto di memoria comporta un *overhead* del software.

Il sistema operativo deve:

• Sostituire le pagine.
• Pianificare un altro processo per l'esecuzione.

• La probabilità di riferirsi a una pagina mancante deve essere minima.

Politica di Caricamento (Fetch Policy)

• Riguarda la decisione su quando caricare una pagina in memoria principale.
  • **Demand Paging** (Paginazione a Richiesta)

La pagina viene portata in memoria solo quando si fa riferimento a una posizione al suo interno.

Quando un processo viene eseguito per la prima volta, ci saranno molti *page fault*.

• **Prepaging** (Caricamento Anticipato)

Vengono caricate pagine diverse da quelle richieste a causa di un *page fault*.

Se le pagine sono caricate in sequenza, è più efficiente portare in memoria un blocco di pagine contigue dalla memoria secondaria.

• Il *prepaging* non deve essere confuso con lo *swapping*. Quando un processo viene scaricato dalla memoria e passa allo stato sospeso, tutte le pagine residenti vengono rimosse.

Politica di Posizionamento (Placement Policy)

• Determina dove le parti del processo devono risiedere in memoria principale.
• Per la segmentazione pura: *best fit*, *first fit* e *next fit*.
• Nella combinazione di segmentazione con paginazione, la posizione è irrilevante.

Politica di Sostituzione (Replacement Policy)

• Selezione della pagina da sostituire durante il caricamento di una nuova pagina.
• Obiettivo: Sostituire la pagina che ha la minore probabilità di essere referenziata nel prossimo futuro.
• Si cerca di prevedere il futuro basandosi sul passato.

Blocco del Frame (Frame Locking)

• Restrizione alla politica di sostituzione.
  • Quando un *frame* è bloccato, la pagina caricata al suo interno non può essere sostituita.
• Il sistema operativo di base e le strutture di controllo fondamentali risiedono in *frame* bloccati.
• Un **bit** di blocco è associato a ogni *frame*.

Algoritmi di Sostituzione

• **Politica Ottimale (OPT)**
  • Seleziona per la sostituzione la pagina che dovrà attendere il maggior tempo prima di essere referenziata nuovamente.
  • Il sistema operativo richiede una precisa conoscenza di eventi futuri.
  • Viene utilizzato come standard per confrontare altri algoritmi.
• **Politica LRU** (*Least Recently Used*)
  • Sostituisce la pagina che non è stata referenziata per il maggior tempo.
  • Secondo il principio di località, è la pagina che avrà meno probabilità di essere referenziata nel prossimo futuro.
  • L'implementazione richiede di etichettare ogni pagina al momento del suo ultimo riferimento, il che comporta un *overhead*.
• **Politica FIFO** (*First-In, First-Out*)
  • Tratta i *frame* assegnati a un processo come un buffer circolare.
  • Le pagine vengono rimosse dalla memoria secondo la tecnica del sistema di rotazione.
  • Semplice da implementare.
  • Obiettivo: sostituire la pagina che è stata in memoria per il tempo più lungo.
  • Ampiamente usato per i dati che vengono caricati più volte ed espulsi.
• **Politica Clock (Second Chance)**
  • Richiede un **bit** aggiuntivo associato a ciascun *frame*, chiamato **bit di utilizzo** (Use Bit).
  • Quando una pagina viene caricata per la prima volta in un *frame*, il bit di utilizzo viene azzerato (0).
  • Quando si fa riferimento alla pagina, il bit viene impostato a 1.
  • Quando è il momento di sostituire una pagina, il primo *frame* incontrato con il bit di utilizzo a 0 viene sostituito.
  • Durante la ricerca, ogni bit di utilizzo che è 1 viene modificato a 0.
• **Buffer delle Pagine**
  • Utilizza il criterio FIFO.
  • La pagina sostituita viene assegnata a una delle due liste:

• Pagine Libere (se non sono state modificate).
• Pagine Modificate (*Dirty Pages*).

La pagina non viene fisicamente spostata dalla memoria principale, ma viene eliminata solo la sua voce nella tabella delle pagine.

Gestione del Set Residente

Dimensione del Set Residente

• Il sistema operativo deve decidere la quantità di memoria principale da allocare a un certo processo.

Più basso è il numero di *frame* assegnati a un processo, maggiore è il numero di processi che possono risiedere in memoria principale.

Se c'è un piccolo numero di pagine, il tasso di *page fault* è maggiore.

L'allocazione di memoria aggiuntiva a un particolare processo non avrà effetti rilevanti sulla percentuale di errori di pagina (oltre un certo limite).

Allocazione Fissa

• Assegna al processo un determinato numero di *frame*.
• Se si verifica un *page fault*, è necessario sostituire una pagina del processo stesso.

Allocazione Variabile

• Permette che il numero di *frame* assegnati cambi dinamicamente.
• Nel caso in cui si verifichino molti *page fault*, verranno assegnati più *frame*.

Ambito della Sostituzione (Scope)

• L'ambito di una strategia di sostituzione può essere classificato in globale o locale.
  • **Globale**: Considera tutte le pagine in memoria come candidate alla sostituzione.
  • **Locale**: Considera solo le pagine del processo che ha causato il *page fault*.

Controllo del Carico (Load Control)

• Determina il numero di processi che possono risiedere in memoria principale (grado di multiprogrammazione).
• Se ci sono pochi processi in memoria, a volte possono essere tutti bloccati e si passa molto tempo nello *swapping*.
• D'altra parte, se ci sono troppi processi in memoria, aumentano le possibilità di *page fault*. Il risultato è il *thrashing*.

Sospensione del Processo (Process Suspension)

• Se si vuole ridurre il grado di multiprogrammazione, è necessario sospendere uno o più processi residenti in memoria principale.
  • Processi con priorità più bassa.
  • Processi con frequenti *page fault*.
  • Ultimo processo attivato.
  • Processo con il set residente più piccolo.
  • Il processo più vecchio.
  • Processo con il maggior tempo residuo (tempo rimanente).

Riepilogo dei Vantaggi della Memoria Virtuale

• Migliore utilizzo del processore.
• Rimuove la limitazione delle dimensioni nello sviluppo del software.
• Traduzione degli indirizzi logici in indirizzi fisici durante l'esecuzione.

Questo permette ai processi di essere in qualsiasi posizione di memoria principale e la posizione cambia nel tempo.

• Divisione di un processo in frammenti (pagine/segmenti).

Non è necessario che i frammenti siano contigui.

Non è necessario che tutti i frammenti siano in memoria principale.

• Gli approcci di base sono la paginazione e la segmentazione della memoria virtuale.
• Un sistema di gestione della memoria richiede il supporto hardware e software.
  • **Hardware**: Fornito dal processore.

Traduzione degli Indirizzi Virtuali

Generazione di un interrupt in caso di *page fault*.

• **Software**: Algoritmi per la gestione della memoria.
• Problemi di progettazione relativi ai sistemi operativi che forniscono supporto per la gestione della memoria:
  • Politica di Caricamento (Fetch Policy)
  • Politica di Posizionamento (Placement Policy)
  • Politica di Sostituzione (Replacement Policy)
  • Gestione del Set Residente
  • Politica di Scarico
  • Controllo del Carico (Load Control)