ALGORITMI DI RIMPIAZZAMENTO DELLE PAGINE

Quando si genera un fault di pagina, il Sistema Operativo deve scegliere quale pagina scaricare dalla memoria.

È evidente che la scelta non può essere casuale perchè si rischierebbero rallentamente pesanti nella macchina.

I progettisti di computer hanno individuato un algortimo ottimale (che non può essere realizzato) per poi tentare di riprodurlo.

L’algoritmo ottimale dice che ogni pagina deve essere contrassegnata con il numero di istruzioni macchina che vengono eseguite prima che a quella pagina si faccia riferimento.

La pagina con il numero più alto viene scaricata.

Ovviamente questo algoritmo ha un implementazione impossibile perchè è impossibile determiare il numero di istruzioni che occorrono prima del riferimento alla pagina.

I progettisti hanno allora cercato degli algortimi che potessero aiutare veramente durante la progettazione di un computer:

Il primo algoritmo chiamato NRU ha bisogno, per essere utilizzato, di due bit: un bit R che viene messo a 1 quando si fa un riferimento alla pagina (lettura o scrittura) e un bit M che viene messo a 1 quando si fa una scrittura alla pagina.

Periodicamente, il bit R viene rimesso a 0 dal sistema operativo mentre l’M viene mantenuto ad 1 se la pagina è stata modificata.

Il sistema operativo, in questo modo, è in grado di classificare ogni pagina in 4 categorie:

Classe 0: non usata e non modificata (0,0)

Classe 1:non usata, modificata (0,1)

Classe 2: usata, non modificata (1,0)

Classe 3:usata,modificata(1,1)

Quando si genera un fault di pagina, il sistema operativo scarica dalla RAM una pagina casuale presa dalla classe più bassa non vuota.

Un altro algoritmo di rimpiazzamento è detto algoritmo FIFO.

É un algoritmo di facile implementazione, infatti, quando si genera un fault di pagina, viene scaricata dalla RAM la pagina che è presente da più tempo in memoria.

Il problema di questo algoritmo è evidente: anche se una pagina è vecchia, cioè da molto tempo in memoria, non vuol dire che sia inutile.

Una combinazione tra NRU e FIFO è l’algoritmo della seconda opportunità: quando si va in contro ad un fault di pagina, si va a cercare l’elemento più vecchio, cioè quello in coda alla lista.

Una volta che abbiamo trovato l’elemento più vecchio, si controlla il suo bit R. Se è a 0, vuol dire che la pagina è vecchia e non usata e allora la pagina viene scaricata su disco.

Se il bit R è a 1, viene messo a 0 e la pagina viene spostata in testa alla lista come se fosse stata appena caricata.

A questo punto si cotinua a cercare una pagina in fondo alla lista con bit R a 0.

L’algorimo dell’orologio consiste in questo: si mantiene una lista circolare di pagina con la lancetta che punta su una pagina. Se ad un fault di pagina la lancetta punta su una pagina con bit R a 0, la pagina viene scaricata, viene portata la lancetta avanti di uno e la pagina che deve entrare in memoria viene sostituita alla pagina appena scaricata.

Se il bit R e a 1, viene messo a 0 e la lancetta spostata in avanti fino a quando non si trova una pagina con bit 0.

Una buona approssimazione dell’algoritmo ottimale e quella offertaci dall’algoritmo LRU.

Questo algoritmo consiste nello scaricare dalla memoria la pagina non usata da più lungo tempo.

Un modo per implementare la LRU e quello di avere un contatore a 64 bit e che ogni pagina contenga abbastanza spazio per memorizzare il contenuto del contatore.

Dopo ogni riferimento in memoria, il valore del contatore viene memorizzato nella pagina a cui si è fatto riferimento.

Quando si va in contro ad un fault di pagina, viene scaricata dalla memoria la pagina con il valore del contatore più basso (la pagina corrispondente al contatore più basso e la pagina usata meno di recente).

Un altro metodo per implementare la LRU e quello di mantenere una tabella n*n (n numero delle pagine fisiche). Quando si fa un riferimento ad un pagina k , viene messa a 1 tutta la riga k e a 0 la colonna k.

Quando si genera un fault di pagina si controlla il valore binario di ogni riga: la riga con il valore binario più basso è quella usata meno di recente.

Queste implementazioni della LRU vengono eseguite via hardware. Il problema è che nessuna macchina possiede tale hardware.

Per questo si è cercato di simulare la LRU via software e si è riusciti con l’NFU.

Ad ogni pagina è associato un contatore e ad ogni interruzione di clock viene sommato il contatore al bit R della pagina.

Quando si verifica un fault di pagina, viene scelta la pagina con il contatore più basso.

Dopo varie simulazioni si è notato che anche questo algoritmo non è il massimo dell’efficienza, perchè non dimentica mai nulla e potrebbe essere che vengano scaricate su disco delle pagine che servano nell’immediato futuro.

Una modifica dell’NFU, chiamata algoritmo dell’invecchiamento, permette una resa ottimale e una buona approssimazione all’algoritmo ideale.

Come implementare tutto ciò?

Ogi pagina ha una serie di bit (8) che all’inizio vengono messi tutti a 0. Dopo ogni ciclo di clock, gli 8 bit vengono shiftati a destra di una posizione e viene messa nella posizione ora vuota il bit R.

Quando si genera un fault di pagina viene scaricata la pagina con la serie di bit più bassa.