Riassunto del libro di Sistemi Operativi - Capitolo 10: La memoria virtuale

 :: Capitolo 10: La memoria virtuale ::

Torna alla pagina di Sistemi Operativi

10.1 Ambiente

I programmi per essere eseguiti devono risiedere in memoria centrale, essi quindi dipendono dalla dimensione della memoria, in quanto non possono essere più grandi di quest'ultima. Non tutte le procedure di un programma caricato in memoria sarà utile, di conseguenza potremmo anche non caricarlo per intero, questo porta a dei vantaggi:

• Il programma non è vincolato dalla dimensione della memoria;
• Più programmi potrebbero risiedere in memoria contemporaneamente;
• Meno chiamate I/O necessarie per scambiare programmi.

La memoria virtuale comporta una separazione fra la memoria vista dall'utente e quella fisica, questo permette di scrivere programmi che sono più grandi della memoria disponibile. Ha come vantaggio anche quello di non sapere come allocare la memoria.
La memoria virtuale fa riferimento allo spazio di indirizzi logici. Dal punto di vista dell'utente quindi l'informazione potrebbe essere contigua, anche se con l'effettiva traduzione da logico a fisico potrebbe non dimostrarsi vero.
La memoria virtuale permette anche di condividere la memoria logica, quindi condivisione di librerie fra processi, oppure permette ai processi di condividere una zona della memoria, sempre logica. La memoria virtuale permette inoltre di condividere la pagine durante la creazione di processi, accelerando la creazione stessa.

10.2 Richiesta di paginazione

La memoria virtuale è implementata mediante la richiesta di paginazione. La si potrebbe anche implementare mediante la segmentazione, ma le tecniche di sostituzione del segmento sono più complesse. La situazione è simile a quella dei processi, solo che in questo contesto non si cambiano interi processi, scaricandoli nell' area di swap, ma piuttosto si sostituiscono le pagine. Questo avviene con un scambiatore pigro, che non cambia le pagine se non è necessario.

10.2.1 Concetti fondamentali

Inizialmente si devono portare in memoria tutte quelle pagine che potrebbero servire per l'esecuzione del processo. Con un adeguato supporto hardware si possono distinguere quelle pagine che sono in memoria e che sono valide, con quelle che non sono in memoria. Si realizza ciò sempre con un bit. Se si valuta bene quali pagine serviranno allora non saremmo mai costretti a cercare una pagina nel disco. Quando avviene un page-foult di procede come segue:

• Si controlla che l'accesso fosse valido, se non lo era si termina il processo;
• Se era valido dobbiamo portare quella pagina in memoria;
• Si cerca un frame libero dove mappare la nuova pagina:
• Si schedula un'operazione su disco per leggere la pagina appena allocata;
• Quando la lettura è terminata si modifica la tabella delle pagine per indicare la presenza della pagina;
• Si riparte dall'istruzione che era stata interrotta al momento del page-foult.

Un'alternativa è la richiesta di pura paginazione: si portano in memoria quelle pagina che sono espressamente richieste, quindi non si carica nessuna pagina inizialmente. Si susseguiranno un certo numero di foult fino a che non saranno presenti tutte le pagine.
Fattore molto importante è che bisogna ripartire dall'istruzione interrotta una volta ritornato dalla routine di mancanza di pagina.

10.2.2 Prestazioni della richiesta di paginazione

La mancanza di pagina potrebbe incidere notevolmente sulle prestazioni, in quanto di deve effettuare una routine abbastanza sostenuta legata alla mancanza di pagina. Più basso è il tasso di mancanza di pagina più possiamo garantire un tempo di esecuzione ragionevole.

10.3 Copia durante la scrittura

Un nuovo processo viene generato con la chiamata fork() la quale crea una copia dello spazio di indirizzamento del processo padre per il processo figlio. Dato che la maggior parte dei figli immediatamente dopo effettua la chiamata exex() per caricare altro codice, la copia iniziale risulta uno spreco. La copia durante la scrittura permette al processo padre e a quello figlio di condividere la stessa pagine inizialmente. Se uno dei due effettua delle modifiche a tali pagine, che sono marchiate come modificabili, allora viene creata una copia della pagina. E' importante sapere anche dove queste copie saranno allocate, alcuni processi mettono a disposizione un insieme (pool) di pagine per questi scopi. Tali pagine vengono assegnate con la tecnica riempi con zero alla richiesto, così facendo il contenuto delle pagine sarà cancellato prima di essere allocato nuovamente.

10.4 Sostituzione della pagina

E' rischioso allocare tutti i frame liberi per i processi, anche se si aumenta il grado della multiprogrammazione si potrebbe incorrere in una sovra-allocazione della memoria. I frame di fatti non sono usati solo per le pagine, ma anche i buffer di I/O consumano grandi quantità di memoria. Quindi è più vantaggioso far girare processi che non richiedano tutti i frame disponibili. Nel caso in cui si esaurisca la memoria disponibile il sistema non sarebbe più in grado di allocare memoria per un nuovo processo, potrebbe quindi abortire il processo. Un'alternativa sarebbe scaricare il processo in un'area di swap e liberare tutti i frame da lui occupati.

10.4.1 Sostituzione di base della pagina

Quando si verifica un page-foult si deve:

• Trovare la pagina che si vuole immettere nella memoria;
• Trovare un frame libero, quindi se ce ne è uno utilizzarlo, altrimenti sceglierne uno vittima e scaricarlo nella memoria ausiliaria e modificare la tabella delle pagine;
• Leggere la pagina desiderata,e modificare la tabella delle pagina;
• Riprendere il processo utente.

Se non ci sono delle pagine libere allora si devono effettuare due trasferimenti, uno verso la memoria ausiliaria, uno verso la memoria centrale, questo fa aumentare il tempo d'accesso. Si introduce allora un bit di modifica, il quale ci dice se una pagina dal momento in cui è stata caricata in memoria centrale è stata modificata o meno. Nel caso non fosse stata apportata alcuna modifica si potrebbe scegliere lei come pagina vittima, recuperando nel caso il suo contenuto dal disco. Il tempo per la mancanza di pagina si riduce notevolmente.
Per implementare la sostituzione della pagina bisogna implementare due algoritmi, uno di allocazione dei frame, uno di sostituzione della pagina.

10.4.2 Sostituzione FIFO della pagina

Una tecnica della sostituzione della pagina potrebbe essere quella FIFO. Ad ogni pagina si associa il tempo di caricamento. Quindi si va a sostituire la pagina con il tempo più vecchio. Questo metodo è semplice da implementare, ma non sempre è ottimo. La pagina sostituita potrebbe avere un modulo di inizializzazione molto vecchio, ma potrebbe contenere una variabile usata molto spesso. Questo potrebbe avere come conseguenza la sostituzione di una pagina attiva, in più si dovrebbe sprecare tempo per doverla recuperare immediatamente dopo proprio per il fatto che è una pagina attiva. La tecnica FIFO soffre dell'anomalia di Belady, ovvero che aumentando il numero di frame liberi aumenta il tasso di pagina.

10.4.3 Sostituzione ottimale della pagina

Per risolvere tale anomalia si è introdotto l'algoritmo ottimale di sostituzione della pagina. Tale algoritmo prevede la sostituzione della pagina che non sarà usata per il più periodo di tempo. Con tale algoritmo le mancanze di pagine diminuiscono drasticamente. L'unico problema è quello che è difficile da implementare in quanto si dovrebbe conoscere a priori le richieste che verranno effettuate.

10.4.4 Sostituzione LRU della pagina

Dato che l'algoritmo ottimale non è realizzabile allora si è cercata una sua approssimazione, la quale prevede un compromesso fra la tecnica FIFO e l'algoritmo ottimo. Quindi la sostituzione della pagina si basa sulla sulla pagina usata meno di recente (LRU). Il tasso del page foult è quindi una via di mezzo fra quello FIFO e quello dell'algoritmo ottimale. Una tale situazione dunque è accettabile. Per usare l'algoritmo LRU ho bisogno di un contatore per stabilire da quanto tempo è stata utilizzata una pagina e uno stack di modo tale che si possano mettere le pagine utilizzate più di recente in cima e quello meno di recente in fondo allo stack. Questa combinazione di hardware consente di eliminare facilmente la pagina.

10.4.5 Sostituzione della pagina con approssimazione dell'algoritmo LRU

Dato che pochi computer supportano l'hardware necessario per implementare l'algoritmo LRU allora si è cercata un'approssimazione anche di quest'ultimo.

10.4.5.1 Algoritmo dei bit di riferimento addizionali

Un modo per sapere quando è stata utilizzata la pagina, è quello di utilizzare un byte da 8 bit il quale dovrà essere memorizzato in memoria centrale. Ad intervalli regolari il controllo passa al sistema operativo il quale sposta il bit di riferimento nell'ordine più alto. Se il bit ha tutti 0 allora vuol dire che per otto unità di tempo non è stata utilizzata, dunque è la migliore per la sostituzione.

10.4.5.2 Algoritmo della seconda possibilità

L'algoritmo della seconda possibilità prevede di utilizzare solo il bit di riferimento delle pagina, se tale bit è settato a 0 si sostituisce tale pagina, nel caso fosse 1 si concede a tale pagina una seconda possibilità. A tale pagina verrà settato il bit di riferimento a 0 e non sarà sostituita fino a quando non saranno sostituite tutte le altre pagine.

10.4.5.3 Algoritmo della seconda possibilità migliorato

Una variante dell'algoritmo della seconda possibilità e quello di considerare sia il bit di riferimento sia il bit di modifica:

• (0,0) non usata e non modificata, la migliore da sostituire;

(0,1) non usata ma modificata, dovrà essere prima scaricata nel disco e poi utiilizzata; (1,0) usata di recente ma pulita, probabile venga usata a breve; (1,1) recentemente usata e modificata, sarà usata a breve.

10.4.6 Sostituzione della pagina basata su conteggio

Altri algoritmi possono essere usati per la sostituzione della pagina, alcuni sono basati sul conteggio:

• Sostituzione della pagina usata meno frequentemente: prevede che sia sostituita quella pagina che è usata meno di frequente. Le pagine attive dovrebbero avere un grande conteggio di riferimento. Il problema nasce quando alcune pagine sono usate pesantemente all'inizio e poi non sono più usate. Hanno il loro conteggio molto alto ma sarebbero ottime per la sostituzione dato che non sono più usate;
• Sostituzione della pagina usate più di frequente: assume che la pagina che ha il conteggio più basso sia stata da poco portata in memoria centrale e dovrà essere ancora usata.

10.4.7 Algoritmi per l'uso del buffer delle pagine

Bisogna considerare il fatto che il sistema riserva un certo numero di frame liberi. Quando capita una mancanza di pagina, la pagina vittima viene salvata su disco. Conservare un pool di pagine libere permette al processo di incominciare la sua esecuzione ancor prima che la vittima sia salvata. Un'idea furba sarebbe di mantenere un elenco della pagine modificate, di modo tale che mentre il dispositivo di paginazione è a riposo si possano salvare queste pagine su disco e metterle nel pool di pagine libere.

10.4.8 Le applicazioni e la sostituzione della pagina

Alcuni sistemi operativi mettono a disposizione dei dischi grezzi, che possono essere delle partizioni utilizzate come una grande successione sequenziale di blocchi logici. In tali partizioni non vi sono file-system. Per tali dischi vi sono operazioni I/O grezze, le quali escludono tutti i servizi del file-system. Sebbene alcune applicazioni siano più efficienti con un disco grezzo, molte altre si comportano meglio con la presenza di un file-system.

10.5 Allocazione dei frame

Vi sono molte tecniche per allocare i frame. Uno di questi è la iniziare con la paginazione pura, si ha una condizione iniziale dove non è presente nemmeno una pagina nella memoria centrale. Man mano che si presentano le richieste delle pagine, a meno che non siano presenti a causa di precedenti richieste, si avrà un page-foult. Una volta terminato il caricamento di tutte la pagine desiderate si provvederà a sostituire le pagine qualora non vi sia più spazio. Nel caso le pagine riservato al sistema operativo non siano utilizzate si può chiedere al sistema stessa di poterle utilizzare.

10.5.1 Numero minimo di frame

Bisogna assicurare un numero minimo di frame, che è definito dall'architettura del computer. Questa garanzia è necessaria per le prestazioni dell'elaboratore, in quanto al decrescere del numero di frame liberi aumenta il tasso di mancanza di pagina per ogni processo, è questo è inaccettabile. Il caso peggiore si ha quando ci sono sistemi operativi che permettono livelli multipli di indirezione, ovvero istruzioni che fanno riferimento ad un indirizzo, il quale fa riferimento ad un altro indirizzo, e così via. In questo caso la memoria virtuale deve essere interamente nella memoria centrale, in quanto vengono toccate tutte le pagine nella memoria virtuale. Si è stabilito quindi un numero massimo di livelli di indirezioni.

10.5.2 Algoritmi di allocazione

Ci si chiede ora come dovranno essere allocati m frame per n processi. Un metodo immediato è quello di fare proporzione dello spazio in base ai processi presenti: m/n. Tale allocazione è detta “allocazione omogenea”. Non sempre però un processo userà tutto lo spazio che gli viene assegnato mediante questo metodo, dunque è stata introdotta “l'allocazione proporzionale”. Essa prevede di assegnare ad ogni processo viene assegnata una quantità di memoria proporzionale alla sua dimensione. In tutte e due le allocazioni lo spazio concesso ad ogni processo potrebbe cambiare a seconda del livello di multiprogrammazione.

10.5.3 Confronto tra le allocazioni con sostituzioni locale e globale

Per quanto riguarda la sostituzione della pagina ci sono due punti di vista:

• sostituzione globale;
• sostituzione locale;

Con la prima un processo può selezionare un frame da sostituire a partire da tutti i frame disponibili, quindi anche da frame che fanno riferimento ad altri processi. La seconda sostituzione permette di sostituire solo frame che fanno riferimento solo ai frame allocati per quel processo. Un fattore importante è che con la sostituzione globale un processo può vedere crescere il suo numero di frame allocati, mentre con la sostituzione locale un processo non avrà mai più di quei frame che gli sono stati concessi. A causa di tutto ciò se si usa la tecnica globale un processo non potrà controllare il tasso di mancanza di pagina in quanto altri processi gli possono “rubare” i frame, quindi non dipende da lui.

10.6 Trashing

In caso il numero minimo di frame che devono essere allocati per un processo decresce ulteriormente si deve sospendere quel processo e liberare i frame da lui occupati. Questo perché il tasso di mancanza di pagina continuerà a salire con il scendere dei frame allocati. Questo processo dunque sostituirà pagine attive e immediatamente dopo provvederà a riportarle in memoria, quest'azione si ripeterà fino a quando non si allocheranno altri frame per tale processo. Inizierà dunque a fare delle sostituzioni inutili e sprecherà tempo a scapito dell'esecuzione della computazione. Si dice dunque che entrerà in trashing.

10.6.1 Cause del trashing

Se si è nell'ottica della sostituzione globale introducendo un ulteriore grado di multiprogrammazione si diminuirà il numero di frame disponibili per ogni processo. Dunque questi inizieranno a rubarsi le pagine fra di loro, cosicché ognuno inizierà a segnalare la mancanza di pagina al paginatore. Quindi tutti i processi aspetteranno delle pagine che sono utilizzate da altri processi, facendo crescere la coda delle richieste del paginatore. La situazione degenera quando questi processi attendono che il paginatore inizi a soddisfare le richieste, l'utilizzo della CPU cala e lo schedulatore aumenta ancora il grado di multiprogrammazione.
Si possono limitare gli effetti del trashing utilizzando la sostituzione locale, di modo tale che un processo non può rubare frame ad altri processi, tuttavia il problema resta, in quanto i processi che sono in coda per la richiesta attenderanno facendo ritardare l'esecuzione del processo stesso. L'efficienza ancora lontana. Il problema si risolve del tutto se allochiamo ad ogni processo il numero di frame che sono a lui necessari, ma come si fa a saperlo a priori?Si definisce a questo scopo il modello di località, il quale prevede che il processo mentre è in esecuzione si muove da una località ad un'altra. Per località si intendono un insieme di pagine che sono attive contemporaneamente. Tali località possono anche sovrapporsi.

10.6.2 Il modello working-set

Un altro metodo è quello del working-set, basato sulle località. Il working-set è praticamente una finestra dove sono contenute le pagine che sono state usate più recentemente. All'interno di questa finestra saranno quindi presenti tutte la pagine che sono attive, mentre quelle non più attive non vi rientrano. Essendo un'approssimazione della località del programma si possono individuare quelle pagine che servono al processo, non sostituendo queste ultime, ma bensì quelle inattive.

10.6.3 Frequenza delle mancanze di pagina

l metodo del working-set è considerato un metodo rozzo per controllare il trashing, anche se molto carino. Dunque si potrebbe utilizzare una strategia che considera la frequenza della mancanza di pagina. Con tale tecnica si può controllare se un processo ha un alto tasso di mancanza di pagina, allora vuol dire che ha bisogno di più frame, in caso tale tasso fosse basso allora vuol dire che a quel processo sono stati allocati più frame di quelli a lui necessari.

10.7 File mappati in memoria

Ogni qual volta che si accede ad un file su disco bisogna effettuare delle chiamate di sistema (a seconda delle operazioni che vi si vogliono effettuare: lettura, scrittura e apertura). In alternativa è possibile mappare un file nella memoria, tale tecnica associa logicamente un file ad una parte dello spazio degli indirizzi virtuali. Tale risultato si ottiene mappando una pagina o più pagine in memoria centrale. Con tale metodo si alleggerisce il carico delle chiamate di sistema per poter manipolare un file.

10.8.1 Prepaginazione

Per far fronte alle innumerevoli mancanze di pagina al momento dell'avvio di un processo, nel casi si utilizzi la richiesta di pura paginazione si potrebbe utilizzare la prepaginazione. Tale tecnica prevede di diminuire il tasso di mancanza di pagina caricando in memoria tutte quella pagine che serviranno al processo. Il problema principale della prepaginazione è che potrebbe costare più dell'assistenza della mancanza di pagina. Questo potrebbe accadere in quanto alcune pagine portate in memoria nella prepaginazione potrebbero non essere utilizzate dal processo, questo provocherebbe uno spreco di tempo che poteva essere impiegato per la computazione, quindi la richiesta della mancanza di pagina poteva risultare più efficiente.