Gestione della memoria virtuale

SOVRALLOCAZIONE E SOSTITUZIONE DELLE PAGINE

Durante l’esecuzione di un processo utente si può verificare un’assenza di pagina.

Il SO determina la localizzazione della pagina all’interno del disco. A questo punto può succedere

che la lista dei frame liberi sia vuota, ossia la memoria è completamente occupata.

Per risolvere questo problema, denominato sovrallocazione, è necessario scegliere una pagina da

sostituire.

Per eseguire la sostituzione si possono applicare vari algoritmi, la scelta si basa sulla frequenza

delle assenze di pagina. Viene scelto l’algoritmo che presenta una frequenza bassa.

Ogni algoritmo si basa sulla successione dei riferimenti e sul calcolo del numero di assenze di

pagina.

A FIFO

LGORITMO DI SOSTITUZIONE

È l’algoritmo più semplice e associa ad ogni pagina l’istante di tempo in cui quella pagina è stata

portata in memoria, per cui, durante la sostituzione, si sceglie sempre la pagina che è presente in

memoria da più tempo.

L’algoritmo FIFO si basa sull’utilizzo di una coda; si sostituisce sempre la pagina che si trova

come primo elemento della coda.

È un algoritmo semplice e facile da programmare, ma non ha buone prestazioni.

Infatti, la prima pagina caricata che poi verrà sostituita se necessario, potrebbe contenere variabili

utilizzate spesso o ancora in uso, e quindi necessarie all’esecuzione del processo. Non appena si

sostituisce la pagina si ha un’eccezione per pagina mancante.

A lungo andare aumenta la frequenza delle assenze di pagina, rallentando l’esecuzione del processo.

Si definisce anomalia di Belady il fatto che all’aumentare dei frame assegnati aumenta anche la

frequenza delle assenze di pagina.

A LGORITMO OTTIMALE DI SOSTITUZIONE

È stato pensato per risolvere l’anomalia di Belady e presenta la minore frequenza delle assenze di

pagina. Con questo algoritmo si sostituisce la pagina che non si userà per il periodo di tempo più

lungo, ma è difficilmente realizzabile in quanto è necessario conoscere la futura successione dei

riferimenti.

ALGORITMO DI SOSTITUZIONE LRU

È un’approssimazione dell’algoritmo ottimale, quindi non è affetta dall’anomalia di Belady.

Si sostituisce la pagina che non è stata usata per il periodo più lungo.

L’algoritmo LRU è abbastanza valido ma il problema riguarda la realizzazione della sostituzione

stessa, la quale può richiedere una notevole assistenza dall’architettura del sistema di calcolo.

Il problema consiste nel determinare un ordine per i frame che si basa sull’ultimo utilizzo di ogni

pagina. Si può risolvere mediante l’utilizzo di:

contatori. Si associa ad ogni elemento della pagina un campo del momento d’uso e si

• aggiunge alla CPU un contatore che si incrementa ad ogni riferimento di memoria, al

momento della sostituzione viene scelta la pagina con il valore di momento d’uso minimo;

pila dei numeri delle pagine. Ogni volta che si fa un riferimento a una pagina, la si estrae

• dalla pila e la si colloca in cima a quest’ultima. Nella cima sarà presente l’ultima pagina

utilizzata, mentre nella coda sarà presente quella utilizzata meno recentemente.

ALLOCAZIONE DEI FRAME

Occorre stabilire una tecnica per allocare la memoria libera tra i processi.

Le tecniche di allocazione sono soggette a molti vincoli. Non si possono assegnare più frame di

quanti non ne siano disponibili, a meno che non vi sia condivisione delle pagine, ed è necessario

assegnare almeno un numero minimo di frame, il quale è definito dall’hardware del calcolatore.

Ovviamente, al decrescere del numero dei frame allocati a ciascun processo aumenta la frequenza di

mancanza di pagina, con conseguente ritardo dell’esecuzione dei processi.

Di conseguenza, i frame disponibili devono essere in numero sufficiente per contenere tutte le

pagine cui ogni singola istruzione può far riferimento.

Il numero massimo di frame è definito dalla quantità di memoria disponibile.

Il modo più semplice per suddividere m frame tra n processi è quello per cui a ciascun processo si

dà una parte uguale, quindi m/n frame. Questo metodo è detto allocazione uniforme.

Un altro metodo, chiamato allocazione proporzionale, si basa sull’assegnare i frame in base alla

dimensione del processo.

Sia nell’allocazione uniforme sia in quella proporzionale, l’allocazione a ogni processo può variare

rispetto al livello di multiprogrammazione:

se aumenta, ciascun processo perde un po’ di frame per fornire la memoria necessaria al

• nuovo processo;

se diminuisce, i frame allocati al processo terminato vengono distribuiti tra quelli restanti.

•

Un altro importante fattore che riguarda il modo in cui si assegnano i frame ai vari processi è la

sostituzione delle pagine. Nei casi in cui vi siano più processi in competizione per i frame, gli

algoritmi di sostituzione delle pagine si possono classificare in due categorie generali:

sostituzione globale, permette che per un processo si scelga un frame per la sostituzione

• dall’insieme di tutti i frame, anche se quel frame è correntemente allocato a un altro

processo;

sostituzione locale, richiede invece che per ogni processo si scelga un frame solo dal

• proprio insieme di frame.

Con la sostituzione locale, il numero di blocchi di memoria assegnati a un processo non cambia,

mentre con quella globale può accadere che per un certo processo si selezionino solo frame allocati

ad altri processi.

L’algoritmo di sostituzione globale risente di un problema, che non occorre in quello di sostituzione

locale: un processo non può controllare la propria frequenza di assenze di pagine, in quanto dipende

anche dalla paginazione di altri processi.

TRASHING (PAGINAZIONE DEGENERE)

Si consideri un qualsiasi processo che non disponga di un numero di frame sufficiente.

Anche se si può ridurre il numero di frame allocati, esiste una serie di pagine che sono attive e

quindi in uso. Se non si dispone del numero di frame necessario, si verifica subito un’assenza di

pagina, e si cerca una pagina da sostituire. In quanto tutte le pagine sono attive, si andrà a sostituire

una pagina che sarà immediatamente necessaria, e il processo subirà continue assenze di pagina.

Il trashing si verifica quando si spende più tempo per la paginazione che per l’esecuzione.