MarcoGT
05-12-2007, 19.39.38
Come ben sapete, tutti vogliamo (per usare FSX :-) ) una memoria infinita, veloce, non volatile ma soprattutto poco costosa --> impossibile!
La parte del SO che si gestisce la memoria si chiama Gestore della Memoria i cui compiti sono:
-- tenere traccia di quali parti di memoria sono in uso e di quali parti non lo sono;
-- allocare la memoria ai processi che ne hanno bisogno (e deallocarla quando il processo termina l'esecuzione dei proprio task);
-- gestire lo swapping tra la memoria principale (RAM) ed il disco quando la RAM non è sufficientemente grande per mantenere tutti i processi.
Riassumendo si può dire che il compito del gestore della memoria è quello di sfruttare al meglio la gerarchia di memoria.
Il problema più grande da affrontare è come gestire il passaggio da programma eseguibile (che si trova su disco) e processo in esecuzione (che si trova in RAM).
Bisogna quindi creare un'associazione tra istruzioni del programma e indirizzi di memoria; questa operazione si chiama address binding e può essere fatta in diversi momenti:
-- al momento della compilazione del programma (ossia, scrivete il vostro programma in C++ e compilate); quando l'address binding viene fatto in questo momento si parla di indirizzamento assoluto; il problema di questo tipo di address binding è che se in un certo momento l'indirizzo del programma deve cambiare, il programma deve essere ricompilato; questo tipo di address binding veniva usato per i programmi .com del DOS.
-- al momento del caricamento delle istruzioni in RAM: il codice generato dal compilatore viene chiamato in questo caso rilocabile; è il loader (e poi il linker) che fa le traduzioni opportune di istruzioni/indirizzi di memoria.
-- durante l'esecuzione: il programma può cambiare la sua posizione in memoria mentre è in esecuzione.
Prima ho parlato di swapping, ora spiego meglio;
nei sistemi odierni solitamente la memoria principale è insufficiente per tutti i processi attivi (non in esecuzione, ma attivi; un processo può occupare memoria senza essere attivo, si dice che si trova in stato di WAIT); è quindi necessario l'immagine dei processi da memoria a disco e viceversa; questa operazione si chiama swapping.
Un altro problema è: quanta memoria deve venire allocata ad un processo quando questo viene creato o viene portato in memoria tramite swapping?
Distinguiamo i processi in due macrogruppi:
-- processi a dimensione fissa;
-- processi che tendono a crescere durante la propria esecuzione.
Ai processi del secondo gruppo conviene ovviamente lasciare spazio a dispozione!
Quando un processo cerca di aumentare le proprie dimensioni, se il processo ha dello spazio libero adiacente, questo spazione può essere allocato; se invece il processo è adiacente ad un altro processo, il processo che sta crescendo di dimensioni può essere spostato in uno spazio di memoria libero e sufficientemente grande da contenerlo; oppure uno (o più) processi dovranno essere trasferiti su disco per creare uno spazio libero abbastanza grande da contenerlo.
Qui di seguito descrivo alcuni algoritmi per l'allocazione della memoria:
-- FIRST FIT: il gestore di memoria scandisce la lista dei segmenti (del disco) finché trova la prima zona libera abbastanza grande. La zona viene divisa in due parti, una per il processo e una per la memoria non utilizzata; è un algoritmo veloce perchè limita le operazioni di ricerca.
-- NEXT FIT: è come il precedente con la differenza che ad ogni ricerca inizia dal punto lasciato alla ricerca precedente; le prestazioni sono leggermente inferiori del first fit; il problema del next fit è che iniziando la scansione dal punto in cui si era fermato in precedenza, potrebbe saltare uno spazio di memoria grande abbastanza per questo processo, che però si era rivelato "piccolo" per il processo precedente;
-- BEST FIT: il gestore di memoria scandisce tutta la lista dei segmenti e scegli la più piccola zona libera sufficientemente grande da contenere il processo; è più lento di first fit poichè scandisce tutte i segmenti; spreca più memoria di first fit e next fit ed infine lascia zone di memoria troppo piccole per poter essere utilizzate;
-- WORST FIT: viene usato per risolvere il problema del best fit; worst fit infatti sceglie la più grande zona libera e non ha buone prestazioni.
In un calcolatore esistono due tipi di memoria:
-- memoria fisica (memoria effettivamente presente);
-- memoria virtuale (memoria che il processo in esecuzione, e tutto il SO, effettivamente vede).
Il principio base della memoria virtuale è che la dimensione totale di programma, dati e stack può superare la quantità di memoria fisica disponibile per il processo.
Il SO mantiene in memoria principale solo le parti del programma in uso e mantiene il resto su disco.
Il SO utilizza due approcci diversi per gestire la memoria virtuale:
-- paginazione;
-- segmentazione.
Nella paginazione, la memoria viene suddivisa in parti di dimensioni minori e l'allocazione avviene usando le pagine come blocco minimo di lavoro.
Nel paging l'accesso alla memoria è realizzato a livello hardware, seguendo uno scheba a tabella di pagine gestito dalla MMU (Memory Management Unit); come appena detto la memoria fisica è suddivisa in piccoli blocchi (solitamente di 4 kbytes ciascuno) ed ad ogni blocco è assegnato un numero di pagina. Il SO mantiene nella propria tabella interna una lista di queste pagine. Ogni volta che un programma (od un singolo processo) invia una richiesta di memoria, il sistema operativo alloca un numero sufficiente di pagine al programma e mantiene una lista delle pagine allocate.
Dato che il SO vede due memorie (fisica e virtuale) si parla quindi di pagine virtuali e pagine fisiche; viene creata una mappatura tra pagine virtuali e pagine fisiche; il problema principale è che alcune pagine virtuali possono non avere corrispondenza in memoria fisica; in questo caso di parla di Page Fault. Negli attuali circuiti hardware viene utilizzato un bit (assente/presente) per tenere traccia se la pagina mappata è sulla memoria fisica oppure no.
Se la pagina non esiste in RAM, la MMU causa un'eccezione, chiamata appunto page fault. Ma come funziona la MMU?
Supponiamo di avere un indirizzo virtuale di 16 bit (è un esempio); questo indirizzo viene diviso in:
-- numero di pagina di 4 bit;
-- offset di 12 bit.
Il numero di pagina viene usato come indice nella tabella delle pagine in modo da ottenere l'indirizzo fisico.
Se il bit presente/assente di cui abbiamo parlato prima è 0, ossia assente, viene sollevata un'eccezione.
Se invece il bit è 1, quindi la pagina è presente, 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 (so che questa ultima frase è difficile da capire...); il contenuto del registro di output viene messo sul bus di memoria come indirizzo di memoria fisica.
Come detto prima lo scopo della tabella delle pagine è quello di mappare le pagine virtuali sui frame; la tabella delle pagine però può essere molto grande ed inoltre il mapping da virtuale a fisico deve essere molto veloce.Il modello più semplice per la tabella delle pagine consiste in una singola tabella delle pagine formata da un array (ossia da una matrice) di registri hardware (quelli di cui parlava prima Filippo) con un elemento per ogni pagina virtuale indicizzato dal numero di pagina virtuale. Quando viene avviato un processo, il SO carica la sua tabella delle pagine nei registri; il vantaggio di questo approccio sono il mapping immediato e nessun riferimento in memoria; lo svantaggio è che il mapping è *potenzialmente* costoso se la tabella è di grandi dimensioni ed il caricamento della tabella delle pagine nei registri ad ogni context switch (ossia quando la CPU viene assegnata ad un processo) può variare le prestazioni; un altro svantaggio è che deve esistere una tabella per ogni processo.
L'altra soluzione, all'opposto di quella appena presentata, è quella di mantenere la tabella delle pagine interamente in memoria. Si ha bisogno di un solo registro hardware che contiene il puntatore all'inizio della tabelal delle pagine; il vantaggio di questo approccio è che consente di modificare la mappa ad ogni context switch ricaricando un solo registro anzichè un'intera tabella; lo svantaggio è che durante l'esecuzione di un'istruzione richiede uno (o più) riferimenti in memoria per leggere gli elementi della tabella della pagine.
Si possono implementare delle tabelle a più livelli la cui struttura è la seguente:
-- un campo che rappresenta il numero del frame di pagina (è il campo più importante);
-- bit presente/assente che consente di verificare se la pagina virtuale corrispondente all'elemento è in memoria oppure no;
-- bit di protezione che contengono le informazioni su quali tipi di accesso sono consentiti (lettura, scrittura ed esecuzione);
-- bit di pagina modificata e referenziata che tengono traccia dell'utilizzo della pagina;
-- bit di caching che serve per le pagine che mappano su registri di periferiche invece che in memoria.
Le tabelle delle pagine vengono tenute in memoria per le loro grandi dimensioni, ma questo può penalizzare fortemente le prestazioni in quanto una singola istruzione può fare riferimento a più indirizzi.
I programmi tendono a fare la maggior parte dei riferimenti a un piccolo numero di pagine, quindi solo una piccola parte degli elementi nella tabella delle pagine vengono letti frequentemente; si parla di locazione temporale, ossia una pagina se viene richiesta nell'istante x, è molto probabile che venga richiesta anche negli istanti immediatamente successivi.
Una soluzione alle dimensioni della tabella delle pagine è la tabella delle pagine inversa; in questo caso la tabella contiene un elemento solo per ogni pagina effettivamente in memoria, ogni elemento allora contiene la coppia [processo, pagina virtuale]; in questo caso il problema è la traduzione degli indirizzi virtuali, bisogna infatti consultare l'intera tabella, non solo un singolo elemento.
Un approccio che si affianca alla paginazione è la segmentazione; con la paginazione la memoria virtuale è unidimensionale, ossia gli indirizzi vanno da 0 all'indirizzo massimo; in questo caso però ci possono essere tabelle con molto spazio libero. La soluzione è la segmentazione; ogni segmento è una sequenza di indirizzi da 0 ad un massimo; la lunghezza di ogni segmento può variare da 0 ad un massimo consentito e può variare durante l'esecuzione.
Per specificare un indirizzo in una memoria segmentata (detta anche bidimensionale), il programma deve fornire un indirizzo costituito da due parti:
1) numero di segmento;
2) indirizzo all'interno del segmento.
La segmentazione presenta diversi vantaggi; semplifica la gestione di strutture dati che aumentano/diminuiscono di dimensione; facilita la condivisione di procedure o dati tra processi diversi.
Quale scegliere tra segmentazione e paginazione?
Hanno un differenza fondamentale: le pagine hanno dimensione fissa, mentre i segmenti hanno dimensione variabile.
Se i segmenti vengono continuamente caricati e sostituiti in memoria, dopo un certo tempo si formeranno in memoria delle zone non utilizzate: questo fenomeno è la frammentazione, ciò che si può fare è la famosissima deframmentazione
Vi è un terzo approccio, segmentazione con paginazione; è stata sviluppata per sfruttare i vantaggi di entrambe le soluzioni; un indirizzo virtuale è costituito da tre parti:
-- indice di segmento
-- numero di pagina
-- offset interno alla pagina.
I passi che vengono svolti per un accesso alla memoria gestita con segmentazione con paginazione sono i seguenti:
1) l'indice di segmento viene usato per trovare il descrittore di segmento;
2) si effettua un controllo per verificare se la tabella delle pagine del segmento è in memoria, se è presente viene localizzata, altrimenti si ha un page fault.
3) Si esamina l'elemento nella tabella delle pagine
corrispondente, se la pagina è in memoria si ottiene
l'indirizzo, altrimenti si ha un page fault
4) L'offset viene aggiunto all'origine della pagina per ottenere
l'indirizzo di memoria
5) Si ha infine l'operazione di lettura o scrittura
Ecco qui qualche accenno alla gestione della memoria; purtroppo è uno degli argomenti più difficili da spiegare ma soprattutto da capire...!
La parte del SO che si gestisce la memoria si chiama Gestore della Memoria i cui compiti sono:
-- tenere traccia di quali parti di memoria sono in uso e di quali parti non lo sono;
-- allocare la memoria ai processi che ne hanno bisogno (e deallocarla quando il processo termina l'esecuzione dei proprio task);
-- gestire lo swapping tra la memoria principale (RAM) ed il disco quando la RAM non è sufficientemente grande per mantenere tutti i processi.
Riassumendo si può dire che il compito del gestore della memoria è quello di sfruttare al meglio la gerarchia di memoria.
Il problema più grande da affrontare è come gestire il passaggio da programma eseguibile (che si trova su disco) e processo in esecuzione (che si trova in RAM).
Bisogna quindi creare un'associazione tra istruzioni del programma e indirizzi di memoria; questa operazione si chiama address binding e può essere fatta in diversi momenti:
-- al momento della compilazione del programma (ossia, scrivete il vostro programma in C++ e compilate); quando l'address binding viene fatto in questo momento si parla di indirizzamento assoluto; il problema di questo tipo di address binding è che se in un certo momento l'indirizzo del programma deve cambiare, il programma deve essere ricompilato; questo tipo di address binding veniva usato per i programmi .com del DOS.
-- al momento del caricamento delle istruzioni in RAM: il codice generato dal compilatore viene chiamato in questo caso rilocabile; è il loader (e poi il linker) che fa le traduzioni opportune di istruzioni/indirizzi di memoria.
-- durante l'esecuzione: il programma può cambiare la sua posizione in memoria mentre è in esecuzione.
Prima ho parlato di swapping, ora spiego meglio;
nei sistemi odierni solitamente la memoria principale è insufficiente per tutti i processi attivi (non in esecuzione, ma attivi; un processo può occupare memoria senza essere attivo, si dice che si trova in stato di WAIT); è quindi necessario l'immagine dei processi da memoria a disco e viceversa; questa operazione si chiama swapping.
Un altro problema è: quanta memoria deve venire allocata ad un processo quando questo viene creato o viene portato in memoria tramite swapping?
Distinguiamo i processi in due macrogruppi:
-- processi a dimensione fissa;
-- processi che tendono a crescere durante la propria esecuzione.
Ai processi del secondo gruppo conviene ovviamente lasciare spazio a dispozione!
Quando un processo cerca di aumentare le proprie dimensioni, se il processo ha dello spazio libero adiacente, questo spazione può essere allocato; se invece il processo è adiacente ad un altro processo, il processo che sta crescendo di dimensioni può essere spostato in uno spazio di memoria libero e sufficientemente grande da contenerlo; oppure uno (o più) processi dovranno essere trasferiti su disco per creare uno spazio libero abbastanza grande da contenerlo.
Qui di seguito descrivo alcuni algoritmi per l'allocazione della memoria:
-- FIRST FIT: il gestore di memoria scandisce la lista dei segmenti (del disco) finché trova la prima zona libera abbastanza grande. La zona viene divisa in due parti, una per il processo e una per la memoria non utilizzata; è un algoritmo veloce perchè limita le operazioni di ricerca.
-- NEXT FIT: è come il precedente con la differenza che ad ogni ricerca inizia dal punto lasciato alla ricerca precedente; le prestazioni sono leggermente inferiori del first fit; il problema del next fit è che iniziando la scansione dal punto in cui si era fermato in precedenza, potrebbe saltare uno spazio di memoria grande abbastanza per questo processo, che però si era rivelato "piccolo" per il processo precedente;
-- BEST FIT: il gestore di memoria scandisce tutta la lista dei segmenti e scegli la più piccola zona libera sufficientemente grande da contenere il processo; è più lento di first fit poichè scandisce tutte i segmenti; spreca più memoria di first fit e next fit ed infine lascia zone di memoria troppo piccole per poter essere utilizzate;
-- WORST FIT: viene usato per risolvere il problema del best fit; worst fit infatti sceglie la più grande zona libera e non ha buone prestazioni.
In un calcolatore esistono due tipi di memoria:
-- memoria fisica (memoria effettivamente presente);
-- memoria virtuale (memoria che il processo in esecuzione, e tutto il SO, effettivamente vede).
Il principio base della memoria virtuale è che la dimensione totale di programma, dati e stack può superare la quantità di memoria fisica disponibile per il processo.
Il SO mantiene in memoria principale solo le parti del programma in uso e mantiene il resto su disco.
Il SO utilizza due approcci diversi per gestire la memoria virtuale:
-- paginazione;
-- segmentazione.
Nella paginazione, la memoria viene suddivisa in parti di dimensioni minori e l'allocazione avviene usando le pagine come blocco minimo di lavoro.
Nel paging l'accesso alla memoria è realizzato a livello hardware, seguendo uno scheba a tabella di pagine gestito dalla MMU (Memory Management Unit); come appena detto la memoria fisica è suddivisa in piccoli blocchi (solitamente di 4 kbytes ciascuno) ed ad ogni blocco è assegnato un numero di pagina. Il SO mantiene nella propria tabella interna una lista di queste pagine. Ogni volta che un programma (od un singolo processo) invia una richiesta di memoria, il sistema operativo alloca un numero sufficiente di pagine al programma e mantiene una lista delle pagine allocate.
Dato che il SO vede due memorie (fisica e virtuale) si parla quindi di pagine virtuali e pagine fisiche; viene creata una mappatura tra pagine virtuali e pagine fisiche; il problema principale è che alcune pagine virtuali possono non avere corrispondenza in memoria fisica; in questo caso di parla di Page Fault. Negli attuali circuiti hardware viene utilizzato un bit (assente/presente) per tenere traccia se la pagina mappata è sulla memoria fisica oppure no.
Se la pagina non esiste in RAM, la MMU causa un'eccezione, chiamata appunto page fault. Ma come funziona la MMU?
Supponiamo di avere un indirizzo virtuale di 16 bit (è un esempio); questo indirizzo viene diviso in:
-- numero di pagina di 4 bit;
-- offset di 12 bit.
Il numero di pagina viene usato come indice nella tabella delle pagine in modo da ottenere l'indirizzo fisico.
Se il bit presente/assente di cui abbiamo parlato prima è 0, ossia assente, viene sollevata un'eccezione.
Se invece il bit è 1, quindi la pagina è presente, 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 (so che questa ultima frase è difficile da capire...); il contenuto del registro di output viene messo sul bus di memoria come indirizzo di memoria fisica.
Come detto prima lo scopo della tabella delle pagine è quello di mappare le pagine virtuali sui frame; la tabella delle pagine però può essere molto grande ed inoltre il mapping da virtuale a fisico deve essere molto veloce.Il modello più semplice per la tabella delle pagine consiste in una singola tabella delle pagine formata da un array (ossia da una matrice) di registri hardware (quelli di cui parlava prima Filippo) con un elemento per ogni pagina virtuale indicizzato dal numero di pagina virtuale. Quando viene avviato un processo, il SO carica la sua tabella delle pagine nei registri; il vantaggio di questo approccio sono il mapping immediato e nessun riferimento in memoria; lo svantaggio è che il mapping è *potenzialmente* costoso se la tabella è di grandi dimensioni ed il caricamento della tabella delle pagine nei registri ad ogni context switch (ossia quando la CPU viene assegnata ad un processo) può variare le prestazioni; un altro svantaggio è che deve esistere una tabella per ogni processo.
L'altra soluzione, all'opposto di quella appena presentata, è quella di mantenere la tabella delle pagine interamente in memoria. Si ha bisogno di un solo registro hardware che contiene il puntatore all'inizio della tabelal delle pagine; il vantaggio di questo approccio è che consente di modificare la mappa ad ogni context switch ricaricando un solo registro anzichè un'intera tabella; lo svantaggio è che durante l'esecuzione di un'istruzione richiede uno (o più) riferimenti in memoria per leggere gli elementi della tabella della pagine.
Si possono implementare delle tabelle a più livelli la cui struttura è la seguente:
-- un campo che rappresenta il numero del frame di pagina (è il campo più importante);
-- bit presente/assente che consente di verificare se la pagina virtuale corrispondente all'elemento è in memoria oppure no;
-- bit di protezione che contengono le informazioni su quali tipi di accesso sono consentiti (lettura, scrittura ed esecuzione);
-- bit di pagina modificata e referenziata che tengono traccia dell'utilizzo della pagina;
-- bit di caching che serve per le pagine che mappano su registri di periferiche invece che in memoria.
Le tabelle delle pagine vengono tenute in memoria per le loro grandi dimensioni, ma questo può penalizzare fortemente le prestazioni in quanto una singola istruzione può fare riferimento a più indirizzi.
I programmi tendono a fare la maggior parte dei riferimenti a un piccolo numero di pagine, quindi solo una piccola parte degli elementi nella tabella delle pagine vengono letti frequentemente; si parla di locazione temporale, ossia una pagina se viene richiesta nell'istante x, è molto probabile che venga richiesta anche negli istanti immediatamente successivi.
Una soluzione alle dimensioni della tabella delle pagine è la tabella delle pagine inversa; in questo caso la tabella contiene un elemento solo per ogni pagina effettivamente in memoria, ogni elemento allora contiene la coppia [processo, pagina virtuale]; in questo caso il problema è la traduzione degli indirizzi virtuali, bisogna infatti consultare l'intera tabella, non solo un singolo elemento.
Un approccio che si affianca alla paginazione è la segmentazione; con la paginazione la memoria virtuale è unidimensionale, ossia gli indirizzi vanno da 0 all'indirizzo massimo; in questo caso però ci possono essere tabelle con molto spazio libero. La soluzione è la segmentazione; ogni segmento è una sequenza di indirizzi da 0 ad un massimo; la lunghezza di ogni segmento può variare da 0 ad un massimo consentito e può variare durante l'esecuzione.
Per specificare un indirizzo in una memoria segmentata (detta anche bidimensionale), il programma deve fornire un indirizzo costituito da due parti:
1) numero di segmento;
2) indirizzo all'interno del segmento.
La segmentazione presenta diversi vantaggi; semplifica la gestione di strutture dati che aumentano/diminuiscono di dimensione; facilita la condivisione di procedure o dati tra processi diversi.
Quale scegliere tra segmentazione e paginazione?
Hanno un differenza fondamentale: le pagine hanno dimensione fissa, mentre i segmenti hanno dimensione variabile.
Se i segmenti vengono continuamente caricati e sostituiti in memoria, dopo un certo tempo si formeranno in memoria delle zone non utilizzate: questo fenomeno è la frammentazione, ciò che si può fare è la famosissima deframmentazione
Vi è un terzo approccio, segmentazione con paginazione; è stata sviluppata per sfruttare i vantaggi di entrambe le soluzioni; un indirizzo virtuale è costituito da tre parti:
-- indice di segmento
-- numero di pagina
-- offset interno alla pagina.
I passi che vengono svolti per un accesso alla memoria gestita con segmentazione con paginazione sono i seguenti:
1) l'indice di segmento viene usato per trovare il descrittore di segmento;
2) si effettua un controllo per verificare se la tabella delle pagine del segmento è in memoria, se è presente viene localizzata, altrimenti si ha un page fault.
3) Si esamina l'elemento nella tabella delle pagine
corrispondente, se la pagina è in memoria si ottiene
l'indirizzo, altrimenti si ha un page fault
4) L'offset viene aggiunto all'origine della pagina per ottenere
l'indirizzo di memoria
5) Si ha infine l'operazione di lettura o scrittura
Ecco qui qualche accenno alla gestione della memoria; purtroppo è uno degli argomenti più difficili da spiegare ma soprattutto da capire...!