Memoria virtuale

In informatica, la memoria virtuale è una architettura di sistema capace di simulare uno spazio di memoria centrale maggiore di quello fisicamente presente; questo risultato si raggiunge utilizzando spazio di memoria secondaria su altri dispositivi, di solito le unità a disco. La memoria centrale fisicamente presente diventa quindi la parte effettivamente utilizzata di quella virtuale, più grande: questo stratagemma è utile in virtù del principio di località dell'esecuzione dei programmi. La memoria secondaria utilizzata a questo scopo è comunemente chiamata, in ambiente Posix, swap o spazio di swap (verbo inglese che significa "scambiare"), mentre, in ambiente Windows, è chiamata file di paging. Le operazioni di spostamento delle pagine dallo spazio di swap alla memoria fisica sono chiamate swapping.

In un sistema dotato di memoria virtuale, il processore e i programmi si riferiscono alla memoria centrale con indirizzi logici, virtuali, che vengono tradotti in indirizzi fisici reali da una unità apposita, la MMU o memory management unit che in genere è incorporata nei processori.

La MMU svolge i seguenti compiti:

Traduce l'indirizzo logico in indirizzo fisico;
Controlla che l'indirizzo fisico corrisponda a una zona di memoria fisicamente presente nella memoria centrale;
Se invece la zona in questione è nello spazio di swap, la MMU solleva una eccezione di page fault e il processore si occupa di caricarla in memoria centrale, scartando una pagina già presente.

Questo meccanismo ha un prezzo in termini di prestazioni: la MMU impiega del tempo per tradurre l'indirizzo logico in indirizzo fisico, e ce ne vuole molto di più per caricare una zona di memoria dallo spazio di swap: in ultima analisi quindi, implementare una memoria virtuale significa sacrificare potenza di calcolo per poter eseguire un maggior numero di processi contemporanei.

Detto T_a il normale tempo di accesso alla memoria fisica, T_t il tempo di traduzione di indirizzi della MMU e T_load il tempo necessario a caricare una zona di memoria dallo swap, il tempo (medio) di accesso in caso di memoria virtuale è:

T_av = T_t + T_a + T_load * P_fault

dove P_fault è la probabilità di page fault, cioè di incappare in una pagina che non è presente in memoria centrale e di doverla quindi caricare dallo swap.

Meccanismi di memoria virtuale

Esistono principalmente due modi di implementare un sistema di memoria virtuale: dividere la memoria in tante pagine identiche, gestite dall'hardware, oppure lasciare che sia il programmatore e/o il compilatore che usa a "segmentare" il proprio programma in più segmenti (sperabilmente) indipendenti.
Entrambi i metodi presentano vantaggi e svantaggi: in questi ultimi tempi tuttavia il sistema di gran lunga più usato è la memoria paginata, per via della maggiore omogeneità e indipendenza dal software.

Memoria paginata

Con questo schema la memoria viene divisa in pagine tutte della stessa grandezza (4 o 8 kilobyte): i programmi non hanno bisogno di sapere nulla su come è organizzata la memoria e non devono avere nessuna struttura interna particolare; la esatta ubicazione e disposizione fisica della memoria che occupano non li riguarda e tutto il sistema di memoria virtuale è completamente gestito dalla MMU attraverso un complesso sistema di registri associativi. Proprio questo sistema di registri è il punto debole di questo tipo di meccanismo: se il numero delle pagine è molto grande (pagine di piccole dimensioni, oppure grandi quantità di memoria virtuale da emulare) il meccanismo associativo può diventare troppo complesso, rallentando sensibilmente l'accesso alla memoria (e quindi tutto il sistema).

Un possibile rimedio è quello di aumentare la dimensione della pagine di memoria, al prezzo di un maggior spreco di memoria stessa (frammentazione interna: più grandi sono le pagine, più aumenta il numero di pagine parzialmente vuote e più spazio viene sprecato).

Più dettagliatamente il meccanismo di gestione della memoria virtuale con paginazione è il seguente. L'immagine di un processo è suddivisa in pagine di dimensione fissa. La memoria principale è suddivisa anch'essa in "pezzi", della stessa dimensione delle pagine, detti frame. Ad ogni processo è associata una tabella, mantenuta in memoria principale o secondaria a seconda delle dimensioni, detta tabella delle pagine. Ogni entrata (riga) della tabella delle pagine contiene:

Il numero di pagina per quella riga, Il bit present , Il bit modified, Il numero di frame corrispondente

Gli indirizzi logici sono rappresentati dalla coppia (nr. di pagina, offset). La traduzione avviene in questo modo: si trova la riga corrispondente al numero di pagina dell'indirizzo logico, se il bit Present è 0, la pagina non è presente in memoria principale, si genera quindi un Page Fault e si attende che la pagina sia caricata in memoria, infine si genera l'indirizzo fisico (nr. frame, offset)

Il bit Modified indica invece se la pagina è stata modificata o meno. Infatti se una pagina non è stata modificata, al momento di effettuare lo swap nella memoria secondaria, non ha senso riscrivere la pagine su disco. Risparmiando così tempo, e migliorando in parte le prestazioni.

Un ultimo dettaglio tecnico. Supponiamo di avere indirizzi logici e fisici di lunghezza k bit. Di questi n saranno destinati al nr. di pagina e m all'offset. Si ha quindi k = n + m. Da questo di deduce che ogni pagina,ed ogni frame, ha dimensione 2^m bit. Supponiamo ora che volendo tradurre un indirizzo logico (nr. pagina, offset), si trovi che il frame corrispondete alla data pagina sia l'i-esimo. Questo però non corrisponde ancora al vero indirizzo fisico, ma solamente all'indice del frame. Per ottenere l'indirizzo fisico si deve ora moltiplicare i * 2^m. Il vantaggio di questa tecnica consiste nel fatto che, nel sistema binario, questa operazione può essere eseguita concatenando m zeri alla rappresentazione binaria di i. Un'operazione quindi molto veloce, che può essere eseguita direttamente in hardware.

Memoria segmentata

In questo caso il meccanismo di memoria virtuale è in parte software: i programmi che girano su sistemi con memoria segmentata sono strutturati in segmenti funzionalmente omogenei: la MMU tiene traccia di quali e quanti segmenti sono presenti in memoria e dove. Il vantaggio principale di questo sistema è che sfrutta al massimo il già citato principio di località, riducendo al minimo il ricorso allo spazio di swap: una volta che un programma ha in memoria centrale i segmenti di cui necessita, solo raramente ne chiederà di nuovi. Il grosso svantaggio di questo sistema, invece, è il grande spreco di memoria dovuto alla frammentazione esterna: con l'andare del tempo e il susseguirsi dei processi in esecuzione, la memoria viene allocata e disallocata in blocchi di varie dimensioni che lasciano un sempre maggior numero di "buchi" vuoti, troppo piccoli per poter essere utilmente allocati: questo rende necessario eseguire una dispendiosa compattazione periodica della memoria fisica allocata, e/o l'uso di algoritmi di allocazione molto sofisticati.

Thrashing

È indispensabile che la quantità di memoria fisica presente sia almeno sufficiente a mantenere la località del sistema, ovvero quella parte di dati ed informazioni che sono utilizzate nell'immediato da ogni processo. Se così non fosse, infatti, il sistema dovrebbe continuamente provvedere ad eseguire delle operazioni di swapping per far si che ogni processo abbia i dati di cui necessita.

Ad esempio supponiamo che in un dato momento la memoria fisica sia satura e contenga esattamente la località del sistema e che in questa situazione viene avviato un nuovo programma. Il processo che viene creato ha bisogno di allocare della memoria. Dato però che la memoria principale è piena il sistema operativo provvede a liberare parte dello spazio memorizzando parte delle informazioni nella memoria secondaria. Successivamente, quando il controllo torna al processo i cui dati sono stati appena spostati, viene nuovamente richiesta un'operazione di swapping per ricaricare in memoria principale gli stessi. Dato che tutte le informazioni contenute nella memoria principale sono indispensabili questo fenomeno avviene molto spesso. Essendo la memoria secondaria molto più lenta (centinaia o migliaia di volte) rispetto alla memoria principale, questo causa un considerevole rallentamento del sistema, che è impegnato quasi esclusivamente in operazioni di I/O, e diventa presto inutilizzabile e poco, o per nulla, responsivo ai comandi dell'utente. Tale fenomeno è chiamato thrashing.

Algoritmi di swapping

Esistono varie tecniche per decire quali sono le aree di memoria che è preferibile spostare dalla memoria primaria alla secondaria. Le seguenti sono le più diffuse:

Strategia ottimale

Questa tecnica consiste nel rimpiazzare la pagina di memoria che verrà riutilizzata più in là nel tempo. Chiaramente, per poter essere realmente implementata, richiederebbe che il S.O. conoscesse in anticipo le pagine utilizzate nel futuro dai processi. Non è quindi utilizzabile come algoritmo di rimpiazzamento delle pagine in memoria principale, ma come metro di confronto delle altre strategie.

FIFO

La tecnica FIFO (First In First Out) è la più semplice, si tiene traccia in una tabella di quando è stata allocata un'area di memoria. Quando vi è una nuova richiesta di allocazione di pagine di memoria, se c'è ancora spazio in memoria principale, semplicemente viene allocata la nuova pagina, altrimenti si consulta mediante la tabella quali sono le pagine allocate da più tempo e si spostano in memoria secondaria.

Questo algoritmo è molto semplice e di rapida esecuzione ma ha lo svantaggio di spostare in memoria secondaria le pagine più vecchie anche se sono utilizzate di frequente.

Seconda scelta (Algoritmo dell'orologio)

Esiste una semplice ottimizzazione della tecnica FIFO che ovvia al problema dello swap anche delle pagine molto utilizzate. È sufficiente aggiungere un bit nella tabella che tiene traccia dell'età delle pagine: ogni volta che il sistema operativo accede ad una pagine, pone questo bit ad 1 mentre l'algoritmo di swap delle pagine, se trova il bit a 1 lo pone a 0 e sposta in memoria secondaria una pagina con il bit già posto a 0. In questo modo, le pagine utilizzate di frequente hanno alta probabilità di rimanere in memoria principale.

Nel caso peggiore tutte le pagine hanno il bit impostato ad 1, in questo caso l'algoritmo azzera tutti i bit fino a tornare alla prima pagina presa in esame. Trovandola ora con bit a 0 provvede alla sua sostituzione. In questo caso la sostituzione a seconda scelta si riduce ad una sostituzione di tipo FIFO.

Esiste una versione modificata del seguente algoritmo che prevede due bit che tengono traccia dell'uso e della modifica. Si hanno infatti le seguenti combinazioni:

(0,0): né recentemente usato né modificato - migliore pagina da sostituire
(0,1): non usato recentemente, ma modificato - prima di essere sostituita deve essere riscritta nella memoria secondaria
(1,0): usato recentemente ma non modificato
(1,1): usato recentemente e modificato

Quando è necessario effettuare una sostituzione di pagina l'algoritmo prima cerca la pagina migliore da sostituire considerando non solo il fatto che essa non sia stata usata recentemente ma anche che non sia stata modificata. Infatti quando la pagina è stata modificata è necessario salvarne nuovamente il contenuto all'interno della memoria secondaria. Se invece non è stata modificata, ed è già presente una copia nella memoria secondaria, non è necessario effettuare alcuna operazione di I/O.

LRU

La migliore soluzione possibile consisterebbe nello spostare le pagine che non saranno usate per più tempo ma naturalmente il sistema operativo non è in grado di avere quest'informazione. La soluzione di compromesso consiste nello spostare le pagine inutilizzate da più tempo (LRU cioè Least Recently Used) poiché hanno buona probabilità di non essere nuovamente utilizzate nell'immediato.

Per gestire efficientemente quest'algoritmo occorre supporto hardware. È possibile implementare questa tecnica in due modi: si può aggiornare ad ogni accesso della memoria una tabella oppure si mantiene uno stack con le pagine utilizzate più recentemente poste in cima. Entrambi i metodi hanno un impatto non indifferente sulle prestazioni del sistema e per questo motivo normalmente sono realizzati in hardware.

Bibliografia

Architettura dei Sistemi di Elaborazione, volume 1 (F. Baiardi, A. Tomasi e Marco Vanneschi, 1988, editore Franco Angeli, ISBN 882042746X). Fondamenti, firmware, architetture parallele . ^*
Architettura dei Sistemi di Elaborazione, volume 2 (F. Baiardi, A. Tomasi, Marco Vanneschi, 1987, editore Franco Angeli, ISBN 882042746X) Sistemi operativi, multiprocessore e distribuiti. ^*

Voci correlate

Paging

Sistema operativo

Gourt Home::Gourt :: Memoria virtuale