Tecniche di Memoria Virtuale nella gestione delle Memorie nei Sistemi Operativi

La Tabella delle Pagine e il suo impatto sulla Memoria Virtuale

La Tabella delle Pagine è costituita da righe, ciascuna delle quali occupa un certo numero di bytes di informazioni. Questo comporta un notevole overhead di spazio per memorizzare questa struttura. Inoltre, se si riduce la dimensione delle Pagine, si avrà un notevole aumento delle righe all'interno della Tabella.

Il peso della Tabella delle Pagine per ogni Processo viene calcolato come il prodotto tra il numero di Pagine Logiche e i Bytes Informativi per ogni riga. Ad esempio, per una Memoria Virtuale di 4 GB con Pagine grandi 4 KB, si ottiene una Tabella delle Pagine grande circa 4 MB per ogni Processo, il che non è un costo trascurabile.

Si potrebbe provare a ridurre questo costo realizzando Pagine più grandi, ma ciò comporterebbe un aumento del problema della Frammentazione Interna.

Gli svantaggi principali della Memoria Virtuale con Paginazione riguardano quindi l'aumento dei costi in termini di Memoria occupata e di tempo necessario per accedere alla tabella.

Ma ci sono dei trucchi per risparmiare costi e tempo:

• È possibile ridurre l'overhead di tempo mediante hardware aggiuntivo: si utilizza un TLB (Translation Lookaside Buffer), che è una Memoria Associativa che contiene solo una parte della Tabella delle Pagine del Processo attualmente in esecuzione (essendo implementata in hardware non può che essere così, inoltre la velocità di ricerca sarà molto più elevata rispetto ad una soluzione software), la ricerca consiste nel confronto della chiave da ricercare con tutte le chiavi delle righe presenti nella TLB mediante comparatori paralleli. L'accesso non è per indirizzo ma per chiave-valore (il campo "chiave" è la Pagina Logica mentre il campo "valore" è la pagina Fisica). L'MMU effettua prima un tentativo di ricerca nel TLB, se si è fortunati si abbattono quasi completamente i tempi di traduzione, in caso di miss la MMU effettua

Una normale ricerca nella Tabella delle Pagine.

È possibile ridurre l’overhead di spazio utilizzando un indirizzamento a 2 livelli: invece di avere un’unica Tabella delle Pagine si utilizzano tante Tabelle più piccole indirizzate da un’unica Tabella degli Indici: i bits che codificano il numero di Pagine Logiche vengono suddivisi a metà, la prima parte identifica una riga all’interno della Tabella degli Indici, che contiene soltanto un puntatore ad una Mini-Tabella delle Pagine, la restante metà dei bits contiene il numero della Pagina Logica da indirizzare all’interno della Mini-Tabella. Anche se il doppio accesso causa un rallentamento nella ricerca, si ha un notevole vantaggio in termini di occupazione di Memoria in quanto invece di mantenere nella RAM un’unica Tabella con milioni di righe si mantengono soltanto poche piccole Tabelle richieste in quel momento.

Se ovviamente il Processo tende ad utilizzare tutte le sue Pagine

Logiche costantemente, tutte le piccole Tabelle dovranno essere portate in RAM e questa soluzione porterebbe solo svantaggi.
Altra soluzione per ridurre l'overhead di spazio consiste nell'utilizzare una Tabella delle Pagine molto più piccola di quella reale (in quanto un Processo non utilizza in genere tutte le sue Pagine Logiche, ma solo una parte). Per fare ciò è necessario trasformare l'indirizzo logico reale in un indirizzo logico ridotto (per indirizzare una riga nella tabella ridotta), ciò si può fare mediante un Algoritmo di Hashing come ad esempio la Divisione Resto Modulo. Il problema diventa la gestione degli alias (doppioni) in quanto ci sono più input che restituiscono lo stesso modulo resto, per cui ciò che si ottiene è una tabella di liste dove alla stessa Pagina Fisica possono essere associate più Pagine Logiche; diventa in tal caso necessario scorrere tutte queste liste per cercare la traduzione.corretta.Il SO invoca i meccanismi di Paginazione in 4 circostanze:
 Creazione di un Processo: viene creata la Tabella delle Pagine e vengono precaricate inMemoria Centrale alcune Pagine Logiche (per evitare troppi Page Foults iniziali);
 Esecuzione di un Processo: ogni qualvolta un Processo diventa Running e avviene unChange Context viene reimpostata la MMU per gestire il nuovo Processo, e quindi vieneaggiornata la Tabella delle Pagine ed il TLB;
 Page Fault: può capitare che il programma in esecuzione necessita l’accesso a dei daticustoditi su di una Pagina Logica che almomento non è presente nella RAM, si hacosì un Page Fault (Fallimento di Pagine). Intal caso occorre chiedere aiuto al SOmediante una Trap, in modo tale che essoeffettui un accesso al Disco e riporti (SwapIn) nella RAM l’intero blocco (PaginaLogica) che contiene il byte richiesto,provocando un rallentamento delleprestazioni del sistema in quanto lavelocità di accesso al

Disco è estremamente molto più elevata rispetto quella della RAM. A seguito di tale operazione è necessario aggiornare la Tabella delle Pagine ed il TLB;

Termina un Processo: viene rimossa la Tabella delle Pagine relativa al Processo dalla Memoria Centrale. Inoltre vengono rimosse le Pagine Logiche di quel Processo dalle pagine Fisiche della RAM;

In caso di Page Fault occorre effettuare uno Swap In per caricare una pagina logica dal Disco alla RAM, ma molto spesso capita che non ci sono più Pagine Fisiche al momento libere, per occorre effettuare un'operazione di Swap Out: il SO deve scegliere una Pagina Logica al momento non utilizzata e la deve rimuovere in modo tale da fare spazio alla nuova Pagina Logica, quale Pagina sostituire viene deciso da un Algoritmo di Sostituzione dei Blocchi.

Algoritmi di Sostituzione dei Blocchi:

In caso di Page Fault il SO si occupa di sostituire una delle Pagine Logiche in Memoria con la Pagina Logica che necessita

(conservata sul Disco), e per farlo sfrutta degli Algoritmi di Sostituzione. Gli obiettivi di questi algoritmi sono essenzialmente 3:

• Cercare di non spostare Pagine Logiche che sono modificate (bit Modified uguale ad 1), in quanto prima di portarle su Disco bisogna salvarle sul Disco per recuperare la consistenza, mentre le Pagine non modificate possono essere semplicemente sovrascritte. Un riga della Tabella delle Pagine assume quindi questo aspetto:
• Minimizzare il numero di Page Fault, ovvero non togliere Pagine Logiche che possono tornare utili nel breve periodo (e che quindi possono generare altri Page Fault);
• Nel sistema può essere presente anche un DMA che sovrappone le attività di elaborazione della CPU con delle attività di I/O che il Processore gli ha delegato. Può capitare che mentre il DMA sta effettuando delle scritture in RAM si verifica un Page Fault ed il SO decide di rimpiazzare proprio la Pagina Logica sulla quale il DMA stava scrivendo.

“danneggiando” laPagina appena letta. La soluzione consiste nel Pinning: viene introdotto un bit nella righedella Tabella delle Pagine che il DMA setta ad 1 se le corrispondenti Pagine Logiche NONSONO SOSTITUIBILI al momento.

Si analizzano adesso alcuni degli algoritmi di sostituzione più famosi in letteratura:

Algoritmo di Sostituzione Ottimo

Si tratta di un algoritmo non fisicamente realizzabile in quanto consiste nel sostituire la pagina chesarà utilizzata nell’istante di tempo più lontano, quindi si basa su una previsione futura. Se unaPagina ad esempio non sarà usata per 8 milioni di istruzioni e un'altra Pagina non sarà usata per 6milioni di istruzioni, rimuovere la prima Pagina posticipa il Page Fault. Questo criterio tuttaviadiventa utile se confrontato con altri criteri di rimpiazzamento, esso infatti è usato per misurare leperformance di un algoritmo in quanto essendo ideale raccoglie risultati ottimali.

utilizza ad esempio tale algoritmo per misurare le performance dell'algoritmo di sostituzione FIFO, che è il criterio più banale a disposizione in quanto non fa altro che spostare la Pagina presente in Memoria da più tempo (la prima ad entrare sarà la prima ad uscire). Si suppone ad esempio di avere una RAM composta da 4 pagine Fisiche, e si suppone che l'ordine delle pagine richieste sia il seguente: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5: Algoritmo Ottimo: essendo la RAM inizialmente vuota, ci saranno 4 Page Faults iniziali per caricare le prime pagine in Memoria; poi sono richieste le pagine 1 e 2 che sono disponibili, ma in seguito viene richiesta la pagine 5 che non è presente (Page Fault), essa andrà a rimpiazzare la pagina che sarà usata più tempo, cioè la 4. Poi saranno richieste le pagine 1, 2, e 3 che sono disponibili, ma poi alla fine è richiesta la pagina 4 (Page Fault). Algoritmo FIFO: essendo la RAMinizialmente vuota, ci saranno 4 Page Faults iniziali per caricare le prime pagine in Memoria. Quando ad un certo punto viene richiesta la Pagina 5 si ha un Page Fault e viene rimpiazzata la pagina 1 (la prima ad entrare). La Pagina 1 viene subito dopo richiesta, ma essendo stata sostituita anche essa verrà generato un Page Fault e FIFO rimuoverà la pagina che da più tempo è stata in Memoria, ovvero la 2. Algoritmo di Sostituzione Not Recently Used (NRU) Si tratta di un algoritmo che utilizza 2 bit per riconoscere le Pagine che non sono state utilizzate recentemente: il bit M (Modified) vale 1 se la Pagina è stata modificata in scrittura, invece il bit R (Referred) vale 1 se la Pagina è stata utilizzata di recente in lettura o in scrittura nell'ultimo intervallo di tempo (ogni tot tempo avviene un'interruzione hardware che pone a zero il bit R ma lascia invariato il bit M). Dalle 4 combinazioni di valori che questi 2 bits possono assumere le Pagine possono

essere suddivise in 4 classi: 12

Questo algoritmo, nel momento in cui si presenta un Page Fault, cerca la Pagina da sostituire in base alla classe: inizialmente cercherà una Pagina di classe 0, se non dovessero esserci Pagine di classe 0 passerà a quelle di classe 1 e così via. Nel momento in cui ci sono più Pagine della stessa classe viene rimossa una Pagina a caso. Questa casualità rende questo algoritmo poco affidabile, poiché più volte potrebbe rimpiazzare Pagine potenzialmente utili. La classe 3 è quella assolutamente più da evitare perché la Pagina è stata modificata, e dunque necessita di uno SwapOut per aggiornare la versione del Disco, ed inoltre la Pagina è stata riferita di recente, quindi per il Principio di Località Temporale è molto probabile che essa verrà riferita di nuovo prossimamente generando un Page Fault.

Algoritmo di Sostituzione Least Recently Used (LRU)

Si tratta di

un algoritmo che rimpia

un algoritmo che rimpia