La gestione della memoria nei sistemi operativi e la memoria virtuale

Tecniche di allocazione della memoria centrale

Per i sistemi multiprogrammati esistono molte tecniche per l'allocazione del codice e dei dati dei processi in memoria centrale, e noi vedremo:

• allocazione contigua

a partizioni fisse (o statiche) a partizioni variabili (o dinamiche)

• allocazione non contigua

Paginazione (statica e dinamica) segmentazione segmentazione con paginazione (o segmentazione paginata)

Allocazione non contigua a paginazione statica

Entrambe le tecniche descritte in precedenza determinano problemi di frammentazione della memoria e la tecnica della compattazione, ovvero la fusione di tutti i blocchi liberi in uno solo, non sempre può essere applicata e in ogni caso è piuttosto onerosa in termini di computazione. Con l'allocazione non contigua si intende che la memoria centrale deve essere allocata in modo tale che un processo possa essere messo in aree separate e non consecutive di memoria fisica. La principale di queste tecniche è la paginazione e in questa Lezione cominceremo a vedere la modalità a pagine statiche, nota come paginazione pura, che utilizza l'allocazione statica cioè alloca la pagina una volta sola. La paginazione prevede che la memoria centrale sia suddivisa in blocchi aventi tutti la stessa dimensione e lo spazio degli indirizzi di un processo in memoria centrale sia suddiviso logicamente in parti uguali chiamate pagine. Non è necessario attuare operazioni di compattamento delle pagine sparse, come fatto con le partizioni, dato che le pagine possono essere caricate dove c'è spazio, ottimizzando l'uso dei blocchi sparsi rimasti liberi. Questo è uno dei vantaggi dell'allocazione non contigua.

Allocazione non contigua a paginazione statica: dimensione delle pagine

Essendo le pagine di dimensione fissa, le aree rimaste libere all'interno della pagina non possono essere recuperate. I blocchi hanno la stessa dimensione delle pagine (4 KB) e l'allocazione del programma avviene quando in memoria centrale esiste un numero di blocchi liberi pari o superiori al numero di pagine da allocare. Nella paginazione si fa una suddivisione del processo in pagine indipendentemente da quello che contengono, utilizzando un criterio fisico. Mentre le pagine sono logicamente contigue, i blocchi fisici di memoria centrale in cui verranno caricate possono non esserlo.

MEMORIA CENTRALE MODULI DEL SISTEMA OPERATIVO 1000 kB PROCESSO 1 BLK 0 1004 KB BLK 1 1008 KB BLK 2 1012 KB PROCESSO 1 BLK 3 1016 KB PROCESSO 1 BLK 4 1020 kB BLK 5 1024 KB PROCESSO 3 BLK 6 1028 KB PROCESSO 3 BLK 7 1032 KB PROCESSO 2 BLK 8 1036 KB BLK 9 1040 KB BLK 10 1044 KB PROCESSO 2 BLK 11 1048 KB BLK 12 1052 KB blocco libero blocco occupato dalle pagine di un processo

Allocazione non contigua a paginazione statica: gestione tabelle

Per esempio, se un processo è costituito da 4 pagine, al momento della sua allocazione il gestore della memoria dovrà trovare 4 blocchi (anche sparsi) liberi. Per poter fare questo il sistema operativo deve gestire delle tabelle di abbinamento fra pagine e blocchi: la tabella delle pagine e la tabella dei blocchi. La paginazione pura è evidentemente basata sulla rilocazione dinamica dato che l'operazione di traduzione viene effettuata in runtime in base ai blocchi di volta in volta liberi al momento dell'esecuzione. Inoltre, ricordiamo che essendo una tecnica a pagine statiche, l'allocazione è statica (viene fatta una volta sola), non è quindi previsto lo swapping.

MEMORIA CENTRALE MODULI DEL SISTEMA OPERATIVO 1000 kB PROCESSO 1 BLK 0 1004 KB BLK 1 1008 KB BLK 2 1012 KB PROCESSO 1 BLK 3 1016 KB PROCESSO 1 BLK 4 1020 kB BLK 5 1024 kB PROCESSO 3 BLK 6 1028 KB PROCESSO 3 BLK 7 1032 KB PROCESSO 2 BLK 8 1036 KB BLK 9 1040 KB BLK 10 1044 KB PROCESSO 2 BLK 11 1048 KB BLK 12 1052 KB blocco libero blocco occupato dalle pagine di un processo

La memoria virtuale

Con le tecniche viste finora (partizionamento statico e dinamico e paginazione pura) un programma è portato in memoria centrale e viene eseguito (diventando un processo) solo quando c'è a disposizione abbastanza memoria centrale libera da contenerlo tutto. I moderni sistemi operativi introducono quindi il concetto di memoria virtuale, realizzata con le tecniche di:

0 paginazione dinamica 0 segmentazione 0 tecniche ibride che uniscono i vantaggi di entrambe le soluzioni. Le tecniche di gestione con memoria virtuale hanno un altro fondamentale vantaggio: caricare in memoria solo le parti di programma che effettivamente sono utili per l'evoluzione del processo in quel dato istante e liberare le altre parti per poter caricare nuovi task.

La memoria virtuale: funzionamento

L'idea di base è quella di fare in modo che il SO mantenga in memoria principale solo le parti del programma in uso e trattenga il resto su disco. Ogni processo con questa tecnica può "credere" di avere tutta la memoria a sua disposizione, anche se praticamente gliene viene dato un "pezzo alla volta". La memoria totale che quindi il SO vede è la somma tra memoria RAM e memoria di swap.

Memoria principale Area di swap Swap out P Spazio utente Swap in P, SO

Allocazione non contigua a paginazione dinamica

La gestione della memoria virtuale a paginazione dinamica utilizza le stesse tecniche della paginazione pura suddividendo il programma in pagine e la memoria centrale in blocchi della stessa dimensione delle pagine, solo che in ogni istante non tutte le pagine hanno associato un reale blocco fisico in memoria, cioè non tutte le pagine sono fisicamente caricate in memoria centrale. I moduli di gestione del sistema operativo scelgono quali pagine caricare in memoria fin dall'inizio. Se durante l'esecuzione l'istruzione da eseguire si trova in una pagina non presente in memoria centrale, viene generata una "interruzione per mancanza di pagina" (page fault) e viene richiesto al sistema operativo di provvedere al suo caricamento dalla memoria secondaria.

Pagine Frame 0x80600000 0x80500000 0x80400000 0x80300000 0x80200000 0x80100000 0x80000000

Allocazione non contigua a paginazione dinamica: tabelle

Per tenere sotto controllo l'occupazione della memoria il sistema operativo dovrà gestire ora tre tabelle:

• la tabella delle pagine;
• O la tabella dei blocchi;
• la tabella di mappa.

La tabella delle pagine ha il campo STATO perché ora serve sapere per ogni pagina di un processo se ha trovato posto in un blocco della memoria centrale o se è ancora in memoria secondaria; Viene introdotta la tabella di mappa perché ora serve sapere in quale blocco sono state caricate solo le pagine che hanno trovato posto in memoria centrale.

Esempio di paginazione Page 0 0 0 4 Page 1 1 Page 0 2 Page 2 +3 2 4 Page 3 3 Page 2 5 4 Page 1 Programma 6 A7 5 6 Tabella delle pagine 7 Page 3 Memoria RAM

Page replacement

Quindi quando una pagina viene caricata in memoria:

• se sono presenti in memoria frame liberi, la pagina viene caricata immediatamente;
• se tutte le pagine fisiche sono occupate, è necessario "fare spazio", cioè si sceglie un frame di pagina scegliendo la più adatta, si salva il suo contenuto su disco e solo in quel momento è possibile caricare la pagina nel frame appena liberato (procedura di page replacement).

In entrambi i casi, naturalmente, si deve cambiare la mappa delle pagine e solo allora il SO riparte con l'istruzione bloccata.

12 9

Page replacement algorithm (algoritmi di sostituzione)

Questi algoritmi effettuano la scelta delle pagine "vittime" che andranno sovrascritte in memoria dalle nuove pagine da caricare con l'obiettivo di minimizzare il nº page fault. La finalità di ogni algoritmo di sostituzione delle pagine è sostituire quelle pagine la cui probabilità di essere accedute a breve termine è bassa. Vedremo:

1. FIFO Page Replacement Algorithm: con questa politica viene sostituita la pagina che occupa da più tempo la memoria;
2. Least Recently Used (LRU): viene sostituita la pagina che è stata usata meno recentemente, cioè che "da più tempo risulta inutilizzata";
3. Not Recently Used (NRU), con questa politica le pagine utilizzate di frequente hanno alta probabilità di rimanere in memoria principale: si ricerca la pagina vittima solo tra quelle che, nella tabella utilizzata per tenere traccia dell'età delle pagine, hanno un particolare bit chiamato R con valore 0. R viene azzerato periodicamente, e messo a uno ogni volta che la pagina viene acceduta.

12 9

Vantaggi e svantaggi della paginazione

Il vantaggio della paginazione è che si elimina completamente il problema della frammentazione esterna della memoria in quanto le dimensioni di pagine e frame coincidono e, inoltre, possono essere assegnate anche in modo non contiguo. Come svantaggio si ha, invece, che si viene a creare una separazione tra vista utente e vista fisica della memoria.

Memoria virtuale: segmentazione

Nella paginazione il programma viene suddiviso in pagine a prescindere dal suo contenuto, cioè, per esempio, senza distinguere l'area del codice da quella dei dati: questo impedisce di fatto che si possa condividere il codice su due istanze dello stesso programma, obbligando a caricare in memoria più volte lo stesso codice. Per ovviare a questo problema si utilizza la segmentazione: l'idea di base è quella di suddividere la memoria centrale nello stesso modo in cui sono divisi logicamente i programmi.

1 1 4 2 segmenti 3 2 4 3 Spazio indirizzi logici Spazio fisico

Memoria virtuale: segmentazione e controllo dell'occupazione

Nella segmentazione la memoria centrale fisica è divisa in segmenti fisici (frame) di dimensioni diverse, mentre lo spazio di indirizzamento del processo è diviso in segmenti logici (segmenti). Per tenere sotto controllo l'occupazione della memoria il SO mantiene una o più tabelle dei segmenti dove il numero di segmento funge da indice. Quando è richiesta l'esecuzione di un programma, inizialmente viene caricato in memoria centrale solo il segmento che contiene il programma principale (MAIN). Ogni volta che durante l'esecuzione viene fatto riferimento a un sottoprogramma o a una struttura dati contenuti in un altro segmento, questo viene caricato dalla memoria secondaria alla memoria centrale (swap- in). Se un processo fa riferimento a un segmento che non è presente in memoria centrale viene generata una "interruzione per mancanza di segmento" (segment fault) e il sistema operativo deve provvedere al suo caricamento dalla memoria secondaria.

1 1 4 2 segmenti 3 2 4 3 Spazio indirizzi logici Spazio fisico