Sistemi operativi: funzioni del MMU, Algoritmi di page fault, Modello del Working set

Management Unit (MMU)

Management Unit (MMU) è un chip che mappa gli indirizzi virtuali sugli indirizzi della memoria fisica. La memoria fisica è divisa in blocchi di dimensione fissa (detti frame) e si suddivide la memoria logica in blocchi di pari dimensione (dette pagine). I trasferimenti fra la memoria ed il disco avvengono sempre per unità di pagina.

Quando si deve eseguire un processo, si caricano le sue pagine nei frame disponibili. Alcune pagine virtuali quindi non avranno corrispondenza in memoria fisica e negli attuali circuiti hardware un bit presente/assente è utilizzato per indicare se la pagina è mappata sulla memoria fisica oppure no.

Se una pagina non mappata in memoria fisica viene richiesta, la MMU genera un interrupt della CPU al SO chiamato PAGE FAULT, dopo il quale il SO sceglie un frame di pagina poco utilizzato e salva il suo contenuto su disco, quindi recupera la pagina referenziata e la alloca nel frame appena liberato (fetching della pagina), cambia la mappa e riparte con.

L'istruzione bloccata. Supponiamo che l'indirizzo virtuale sia di 16 bit e sia diviso in due parti. 4 bit rappresentano il numero di pagina, che serve come indice nella tabella delle pagine così da ottenere l'indirizzo fisico, mentre gli altri 12 rappresentano l'offset che deve essere sommato all'indirizzo di base per trovare l'indirizzo corretto in memoria fisica e che viene inviato all'unità di memoria.

• Se il bit presente/assente è 0 viene causata una eccezione
• Se il bit presente/assente è 1 il numero del frame trovato nella tabella delle pagine viene copiato nei 3 bit di ordine alto del registro di output con i 12 bit dell'offset (copiati senza modifiche dall'indirizzo virtuale)
• Il contenuto del registro di output viene messo sul bus di memoria come indirizzo di memoria fisica.

Il modello descritto è semplice, vi sono però dei problemi: la tabella delle pagine può essere molto grande,

Il mapping (da virtuale a fisico) deve essere veloce. Il modello più semplice consiste di una singola tabella delle pagine costituita da un array di registri hardware con un elemento per ogni pagina virtuale indicizzato dal numero di pagina virtuale. Quando viene iniziato un processo, il SO carica la sua tabella delle pagine nei registri. Vantaggi: il mapping è immediato, nessun riferimento in memoria. Svantaggi: il mapping è potenzialmente costoso (se la tabella delle pagine è grande) e il caricamento della tabella delle pagine nei registri ad ogni context switch può alterare le prestazioni (si noti che deve esistere una tabella diversa per ogni processo). All'estremo opposto la soluzione è mantenere la tabella delle pagine interamente in memoria. L'hardware necessario è un singolo registro che punta all'inizio della tabella delle pagine. Vantaggi: consente di modificare la mappa di memoria ad un context switch ricaricando un solo registro. Svantaggi:durante l'esecuzione di un'istruzione richiede uno o più riferimenti in memoria per leggere gli elementi della tabella delle pagine. 11. Algoritmi di rimpiazzamento delle pagine in memoria Per ogni page fault, il SO deve scegliere una pagina da rimuovere dalla memoria per creare spazio per la nuova pagina. Scegliere la pagina da rimpiazzare con un algoritmo per sostituire pagine poco utilizzate può portare a un miglioramento delle prestazioni. Se la pagina da rimuovere è stata modificata, la copia su disco deve essere aggiornata, se non c'è stata alcuna modifica, la nuova pagina sovrascrive quella da rimuovere. - Algoritmo ottimo: a ogni pagina viene assegnata un'etichetta corrispondente al numero di istruzioni che dovranno essere eseguite prima che quella pagina venga referenziata. L'algoritmo ottimo consiste nel rimuovere la pagina con etichetta maggiore, cioè la pagina che verrà referenziata tra più tempo. Non è

però realizzabile nella realtà, perché non è possibile conoscere a priori, al momento del page fault, quali pagine verranno referenziate.

Algoritmo FIFO: quando avviene un page fault, viene rimossa la pagina che si trova in memoria da più tempo. Questo algoritmo soffre dell'anomalia di Belady: aumentando il numero di frame e usando questo algoritmo, il numero di page fault può aumentare. L'algoritmo FIFO in questa forma viene utilizzato raramente: infatti, non è detto che la pagina più vecchia sia anche la meno utilizzata.

Algoritmo NRU: a ogni pagina vengono associati due bit: un bit R che indica che la pagina è stata referenziata e un bit M che indica che la pagina è stata modificata. Inizialmente i bit R e M vengono inizializzati a 0 dal SO. Periodicamente (ad esempio a ogni interrupt del clock) il bit R viene azzerato per distinguere le pagine non referenziate recentemente dalle altre. Quando avviene un page fault,

Il SO controlla i valori dei due bit e divide le pagine in quattro classi:

• classe 0: non referenziate, non modificate
• classe 1: non referenziate, modificate
• classe 2: referenziate, non modificate
• classe 3: referenziate, modificate

L'algoritmo NRU rimuove una pagina qualsiasi (a caso) dalla classe di numero inferiore non vuota.

Algoritmo second chance: viene controllato il bit R della pagina più vecchia: se vale 0 la pagina è sia vecchia che non utilizzata e quindi viene rimpiazzata, se vale 1, il bit viene azzerato e la pagina viene messa in coda alla lista come se fosse appena stata caricata in memoria.

L'algoritmo si basa sulla ricerca di una pagina che non sia stata referenziata nel precedente intervallo di clock. Se tutte le pagine sono state referenziate, degenera nell'algoritmo FIFO puro.

Algoritmo clock: come l'algoritmo second chance, ma le pagine sono tenute in una lista circolare a forma di orologio con una lancetta.

che punta alla pagina più vecchia. Quando avviene un page fault, se il bit R della pagina vale 0, allora la pagina puntata dalla lancetta viene rimossa e la lancetta viene spostata in avanti di una posizione; se il bit R vale 1, viene azzerato e la lancetta viene spostata in avanti di una posizione. Questo processo viene ripetuto finché non viene trovata una pagina con R=0. Differisce dall'algoritmo second chance solo per l'implementazione.

Algoritmo LRU (Least Recently Used): quando avviene un page fault viene rimpiazzata la pagina che da più tempo non viene usata.

Algoritmo NFU (Not Frequently Used): è una approssimazione dell'LRU. A ogni pagina viene associato un contatore inizialmente posto a 0. A ogni clock viene sommato al contatore il bit R. Al momento di un page fault, viene rimpiazzata la pagina con contatore minimo (ciò vuol dire che è una pagina usata poco rispetto alle altre che stiamo considerando). Il problema è che

L'NFU non dimentica nulla, ossia: se una pagina è stata molto utilizzata, non verrà più rimossa anche se non più utile. Quindi è stata proposta una variante di questa versione modificata con invecchiamento (aging): a ogni clock il contatore scorre a destra introducendo R come bit più significativo.

12. Descrivere il modello del Working Set

Nel modello più semplice di paginazione, le pagine vengono caricate in memoria solo al momento del page fault e si parla infatti di paginazione su richiesta (on demand). L'insieme di pagine che un processo sta correntemente usando viene detto working set. Il modello del working set fa invece parte di quella strategia di fetch chiamata pre-paging e utilizza un parametro delta per definire la finestra del working set.

L'idea consiste nello stabilire che i più recenti delta riferimenti di un processo, fanno parte del suo working set. Se una pagina viene utilizzata, allora rimane nel working set.

altrimenti viene eliminata delta unità di tempo dopo il suo ultimo riferimento. Quindi il working set è l'insieme di pagine a cui il processo sta facendo riferimento e a cui, probabilmente, farà riferimenti futuri. Più è alto il numero di pagine in memoria, più è probabile che l'intero working set sia in memoria e quindi che non avvengano page fault: 1 <= W < min(delta, N) La tecnica del pre-paging prevede di caricare il working set di un processo in memoria prima che esso venga eseguito, ma per fare questo è necessario che il working set di ogni processo venga mantenuto aggiornato (da qui nasce il WSCLOCK). Un programma che causa page fault per ogni piccolo insieme di istruzioni viene detto in thrashing (spesso causato da un numero eccessivo di processi in memoria). Il WS con parametro d (delta) al tempo t, W(d,t) è l'insieme delle pagine a cui ci si è riferiti nelle ultime d unità di tempo.

località si indica che il prossimo accesso di memoria sarà nelle vicinanze di quello corrente - località spaziale: il prossimo indirizzo differirà di poco - località temporale: la stessa cella (o pagina) sarà molto probabilmente utilizzata nel futuro prossimo

Strategia di fetch: stabilisce quando una pagina deve essere trasferita in memoria. La paginazione su richiesta porta una pagina in memoria solo quando si ha un riferimento a quella. Si hanno molti page fault quando un processo parte. Il prepaging porta in memoria più pagine del necessario. È più efficiente se le pagine su disco sono contigue.

Prepaging: per risolvere il problema del thrashing molti sistemi a paginazione utilizzano il prepaging prima