Tecniche di Memoria Virtuale nella gestione delle Memorie nei Sistemi Operativi

appuntiDiIngegneria

Memoria Virtuale

Sommario

1.1. Gestione della Memoria ....................................................................................................................2

1.1.1. Monoprogrammazione ..................................................................................................................2

1.1.2. Multiprogrammazione a Partizioni Fisse ........................................................................................3

1.1.3. Swapping.......................................................................................................................................4

1.1.4. Memoria Virtuale ..........................................................................................................................6

1.1.4.1. Memoria Virtuale con Paginazione ............................................................................................6

1.1.4.2. Algoritmi di Sostituzione dei Blocchi ........................................................................................ 11

1.1.4.3. Memoria Virtuale con Segmentazione ..................................................................................... 17

1.1.4.4. Segmentazione con Paginazione .............................................................................................. 18

1

1.1. Gestione della Memoria

Il Gestore della Memoria (Memory Manager) è quella parte del SO che si occupa dell’allocazione

della Memoria ai Processi richiedenti e della deallocazione degli indirizzi di Memoria non più

utilizzati. A questi 2 compiti si aggiunge si aggiunge lo swap di Processi o di parte dell’immagine di

Processi dalla RAM al Disco e viceversa quando la RAM non è sufficientemente grande per ospitare

tutti i Processi in esecuzione. Idealmente una Memoria dovrebbe essere veloce, capiente, non

volatile, ed anche poco costosa; le tecnologie del momento non permettono di soddisfare

contemporaneamente tutti i requisiti e di conseguenza la maggior parte dei sistemi per

l’elaborazione adotta una Gerarchia di Memoria. La filosofia che è alla base di questa filosofia

consiste nel portare verso il vertice di tale gerarchia le informazioni più utilizzate dalla porzione di

programma in esecuzione cosicchè nella maggior parte dei casi il tempo di accesso coincide con

quello delle memorie più rapide. Utilizzando questo approccio i Processi avranno a disposizione

una quantità molto più ampia di Memoria, in quanto le informazioni che non saranno più utili,

almeno al momento, verranno spostate dalla Memoria Centrale verso il Disco lasciando quindi

libero dello spazio in quella porzione di Memoria. Esistono essenzialmente due modelli di

Gestione della Memoria e sono:

 Senza Rilocazione: modelli che non spostano i Processi, fra essi si distinguono la

Monoprogrammazione e la Multiprogrammazione a Partizioni Fisse;

 Con Rilocazione: modelli che spostano i Processi, fra essi si distinguono lo Swapping, la

Memoria Virtuale con Paginazione, con Segmentazione e con Paginazione con

Segmentazione.

1.1.1. Monoprogrammazione

Il modello più semplice è quello orientato alla monoprogrammazione (ormai in disuso a causa

dell’affermarsi della multiprogrammazione), il sistema esegue un solo programma alla volta e per

questo motivo l’area di memoria è condivisa dal Processo in esecuzione e dal Sistema Operativo.

Talvolta il SO può risiedere nella ROM in maniera tale da lasciare l’intera RAM all’esecuzione del

Processo utente (tale soluzione è ad esempio adottata nei sistemi embedded e nei palmari). Uno

scenario alternativo ai primi due appena visti consiste nel collocare nella ROM soltanto il BIOS

2

(contenente i Gestori dei Dispositivi di I/O) e di suddividere la RAM tra il SO ed il Processo in

esecuzione (questa soluzione è ad esempio impiegata da MS-DOS).

1.1.2. Multiprogrammazione a Partizioni Fisse

La Monoprogrammazione, fortunatamente, è diventata solo un ricordo del passato grazie alla

Multiprogrammazione. Con essa è possibile avere diversi Processi attivi contemporaneamente in

Memoria; quest’ultima viene suddivisa in partizioni fisse di diverse dimensioni, ognuna delle quali

può ospitare un solo Processo. Vuol dire che un nuovo Processo può partire se e solo se è presente

una partizione libera sufficientemente grande da accogliere l’intero spazio di indirizzamento del

Processo. Sono possibili due alternative o varianti, implementare un unica coda di attesa per ogni

partizione di Memoria oppure allestire un unica coda di attesa per tutte le partizioni.

La prima strategia penalizza i Processi in attesa su una coda quando in Memoria esistono altre

partizioni abbastanza grandi da accoglierli al momento vuote. Nel secondo caso, invece, i Processi

vengono messi in attesa tutti nella stessa coda: il Processo in testa alla coda è il primo ad essere

allocato, per esso si sceglierà la partizione di Memoria che più si avvicina alle dimensioni del

Processo; qualora non ci fosse spazio a sufficienza il Gestore della Memoria cerca di allocare le

partizioni di Memoria rimaste ai successivi Processi in coda. A seguito della terminazione di un

processo, il gestore della memoria potrebbe procedere cercando nella coda di attesa il processo

3

che meglio riempie il buco appena lasciato. Purtroppo nei sistemi senza Rilocazione la Memoria

non viene ceduta facilmente dai Processi, e di conseguenza si vanno ad intaccare le performance

dell'intero sistema. Per questo motivo nei moderni SO si tende ad utilizzare sempre di più modelli

di Gestione della Memoria con Rilocazione, poiché più efficienti.

Swapping

1.1.3.

Lo Swapping è un primo approccio alla Gestione della Memoria con Rilocazione: è sicuramente un

metodo ancora influenzato dai sistemi senza Rilocazione e che comunque non è decisamente

efficace. Nello swapping un Processo è interamente caricato in Memoria (non ci sono partizioni

fisse); quindi viene eseguito per un certo intervallo di tempo ed infine è scaricato dalla Memoria

principale al Disco fisso. Anche i Processi creati successivamente al primo vengono allocati

interamente in Memoria, tuttavia se lo spazio rimasto (contiguo) è insufficiente il Processo non

può essere caricato in Memoria e per questo motivo viene ucciso. Viene mostrato un esempio:

Con lo Swapping nascono diversi problemi, il primo è quello della Frammentazione Esterna:

quando un Processo in Memoria principale termina, lo spazio di Memoria ad esso allocato ritorna

ad essere disponibile per le successive allocazioni. Ciò genera diversi buchi in Memoria che è

possibile compattare in unico buco mediante un’operazione di compattazione, anche nota come

deframmentazione. Si tratta di un’operazione periodica (molto lenta) che effettua degli

spostamenti fra le Immagini dei Processi attualmente in Memoria al fine di recuperare spazio

raggruppando tutti i buchi. Altro problema dello Swapping è il Calcolo dello Spazio da allocare per

ogni Processo: nell’Immagine di un Processo soltanto l’Area Testo e l’Area Dati hanno una

dimensione fissa, non è così per l’Area Stack e l’Area Heap per i quali il SO non può prevedere

quanto spazio riservare, può solo fare una “stima” lasciando un’area vuota (polmone di crescita)

fra esse per consentire alle 2 Aree di espandersi (limitatamente). Se durante l’esecuzione del

Processo lo spazio di memoria che intercorre fra l’Area Heap e l’Area Stack si esaurisce, il Processo

deve essere rilocato in un buco di Memoria sufficientemente grande da contenerlo; se tale buco

non esiste il Processo viene scaricato dalla Memoria principale al Disco fisso, in attesa che lo spazio

necessario si renda disponibile, in alternativa il Processo può anche essere ucciso. Altro problema

è quello della rilocazione dinamica: lo stesso Processo in momenti diversi della sua esecuzione

può stare in blocchi di Memoria differenti (sempre consecutivi però), ciò viene gestito in maniera

abbastanza semplice dalla Memory Management Unit MMU sommando a run time l’indirizzo del

processo con un valore di offset contenuto all’interno del Registro Base. Ed ancora, altro problema

4

dello Swapping è la Gestione degli spazi liberi di Memoria: occorre utilizzare apposite strutture

dati per mantenere traccia dinamicamente dei blocchi liberi e blocchi occupati della Memoria. La

struttura dati più semplice che si potrebbe utilizzare è la Bitmap (Mappa di Bit), che vede la

Memoria come una grande matrice dove ogni cella rappresenta una singola unità di allocazione,

quindi essa richiede tanti bit quanto sono i blocchi in cui è divisa la Memoria, le celle

contrassegnate da un 1 indicano che il blocco corrispondente è occupato, spetta al SO il compito di

tenere questa mappa continuamente aggiornata. Siccome i Processi devono essere allocati in un

insieme di blocchi liberi contigui, l’allocazione in Memoria di un nuovo Processo mediante una

Bitmap si traduce nella ricerca di un certo numero di elementi 0 consecutivi. Struttura alternativa

è la Lista Concatenata (Linked List), dove ogni elemento della lista può fare riferimento ad un

processo (P) oppure ad un buco (H), esso indicherà inoltre l’indirizzo di partenza del

Processo/Buco in Memoria e la lunghezza impiegata. L’allocazione in Memoria di un nuovo

Processo mediante una lista concatenata si traduce nello scorrimento di tutta la lista fino a trovare

il giusto buco in Memoria.

In entrambi i casi, quindi, deve essere analizzata tutta la struttura dati prima di ricavarne lo spazio

libero, per questo motivo può risultare utile organizzare la lista concatenata in diverso modo, ad

esempio tenendo separate le liste dedicate ai Processi e quelle dedicate ai Buchi (magari anche

ordinandoli per dimensione). Esistono diversi algoritmi per l’allocazione della Memoria ad un

Processo creato oppure ricaricato dal Disco:

 First Fit: il Gestore della Memoria scorre la lista (o cerca una sequenza di 0) fino a quando

non trova un buco abbastanza grande per poterci mettere un Processo. Esso prende

dunque il primo buco libero che trova sufficientemente grande, p il più veloce;

 Best Fit: il Gestore della Memoria sceglie il buco libero più piccolo fra tutti quelli

sufficientemente grandi da accogliere il Processo, in modo da ottimizzare l’occupazi