Nell'informatica, il meccanismo della memoria virtuale è stato sviluppato negli anni '60 . Si basa sull'utilizzo della traduzione al volo degli indirizzi (virtuali) visti dal software, in indirizzi fisici nella RAM . La memoria virtuale consente:
L'articolo del 1962 di James Kilburn descrive il primo computer con un sistema di gestione della memoria virtuale a pagine che utilizza un tamburo come estensione della memoria del nucleo di ferrite : l' Atlas .
Oggi tutti i computer dispongono di un meccanismo di gestione della memoria virtuale, ad eccezione di alcuni supercomputer o sistemi di bordo in tempo reale.
Il principio è il seguente:
La tabella delle pagine è indicizzata dal numero di pagina. Ogni riga è chiamata "voce nella tabella delle pagine " (voce nella tabella delle pagine , abbreviato PTE) e contiene il numero del frame. Poiché la tabella delle pagine può essere posizionata ovunque nella memoria, un registro speciale (PTBR per registro di base della tabella delle pagine ) mantiene il suo indirizzo.
In pratica, il meccanismo di traduzione fa parte di un circuito elettronico denominato MMU ( memory management unit ) che contiene anche parte della tabella delle pagine, immagazzinata in una memoria associativa formata da registri veloci. Ciò evita di dover consultare la tabella delle pagine (in memoria) per ogni accesso alla memoria.
Ecco un esempio reale di macchina il cui processore genera indirizzi virtuali a 32 bit, potendo così accedere a 4 GiB di memoria. La dimensione della pagina è 4KiB . Da ciò si deduce che il campo di spostamento occupa i 12 bit meno significativi e il campo del numero di pagina i 20 bit più significativi.
Notare la presenza di un campo speciale appartenente a ciascuna PTE. Per semplificare, abbiamo ridotto la larghezza di questo campo a un bit: il bit di validità . Se è 0, significa che il numero di frame non è valido. È quindi necessario acquisire una tecnica che permetta di aggiornare questo PTE per renderlo valido.
Possono verificarsi tre casi:
Negli ultimi due casi, un'interruzione - chiamata pagina predefinita (o talvolta page fault , traduzione dall'inglese page fault ) viene generata dal materiale e dà la mano al sistema operativo. Questo è responsabile della ricerca di un frame disponibile nella memoria principale per assegnarlo al processo responsabile di questo errore di pagina, ed eventualmente ricaricare il contenuto di questo frame con il contenuto salvato sulla memoria di massa (attualmente il disco rigido su un'area chiamata area di scambio o scambio ).
Potrebbero non esserci più frame liberi nella memoria principale: questa sarà quindi occupata al 100%. In questo caso, un algoritmo di impaginazione è responsabile della scelta di una pagina "vittima". Questa pagina verrà immediatamente riassegnata al processo di richiesta, oppure verrà prima salvata su disco rigido e verrà aggiornata la voce nella tabella delle pagine che fa riferimento ad essa. La pagina della vittima può benissimo appartenere al processo che manca di spazio.
Di seguito sono elencati alcuni esempi di algoritmi. La prima riga corrisponde alla catena di riferimenti , vale a dire l'ordine in cui il processo accederà alle pagine. Si presume che la memoria principale sia composta da tre frame . La cornice della vittima apparirà sottolineata. Gli errori di pagina iniziale non vengono conteggiati (sono identici in numero indipendentemente dall'algoritmo scelto).
7 | 0 | 1 | 2 | 0 | 3 | 0 | 4 | 2 | 3 | 0 | 3 | 2 | 1 | 2 | 0 | 1 | 7 | 0 | 1 | |||||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
7 | 7 | 7 | 2 | 2 | 2 | 2 | 2 | 7 | ||||||||||||||||||||||||||||||||
0 | 0 | 0 | 0 | 4 | 0 | 0 | 0 | |||||||||||||||||||||||||||||||||
1 | 1 | 3 | 3 | 3 | 1 | 1 |
7 | 0 | 1 | 2 | 0 | 3 | 0 | 4 | 2 | 3 | 0 | 3 | 2 | 1 | 2 | 0 | 1 | 7 | 0 | 1 | ||||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
7 | 7 | 7 | 2 | 2 | 2 | 4 | 4 | 4 | 0 | 0 | 0 | 7 | 7 | 7 | |||||||||||||||||||||||||
0 | 0 | 0 | 3 | 3 | 3 | 2 | 2 | 2 | 1 | 1 | 1 | 0 | 0 | ||||||||||||||||||||||||||
1 | 1 | 1 | 0 | 0 | 0 | 3 | 3 | 3 | 2 | 2 | 2 | 1 |
7 | 0 | 1 | 2 | 0 | 3 | 0 | 4 | 2 | 3 | 0 | 3 | 2 | 1 | 2 | 0 | 1 | 7 | 0 | 1 | ||||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
7 | 7 | 7 | 2 | 2 | 4 | 4 | 4 | 0 | 1 | 1 | 1 | ||||||||||||||||||||||||||||
0 | 0 | 0 | 0 | 0 | 0 | 3 | 3 | 3 | 0 | 0 | |||||||||||||||||||||||||||||
1 | 1 | 3 | 3 | 2 | 2 | 2 | 2 | 2 | 7 |
Può essere relativamente facile trovare casi patologici che rendono inutilizzabile un algoritmo. Ad esempio, per l'algoritmo LRU, questo sarebbe un programma che utilizza 5 pagine in un loop su una macchina che ha solo 4 frame '. Per prima cosa utilizzerà i primi 4 frame in sequenza (1, 2, 3, 4), quindi si verificherà un errore di pagina ed è la pagina 1, la più vecchia caricata, che sarà la vittima. Le pagine utilizzate sono ora (5, 2, 3, 4). Poiché il programma si ripete, necessita della pagina 1 (continua da pagina 5). Questa volta, la pagina della vittima è la pagina 2, sostituita da 1: (5, 1, 3, 4), quindi (5, 1, 2, 4), (5, 1, 2, 3), ecc. Ad ogni iterazione viene generato un errore di pagina ...
Intuitivamente, aumentando il numero di frame di pagina (cioè aumentando la memoria principale) si dovrebbe ridurre il numero di errori di pagina.
L' anomalia di Belady (1970) è un controesempio che mostra che questo non è assolutamente vero con l'algoritmo FIFO , anzi il lettore potrà verificare da solo che la sequenza dei riferimenti (3, 2, 1, 0, 3, 2 , 4, 3, 2, 1, 0, 4) porta a
Nota : la portata di questa curiosità non deve essere esagerata. Certamente mostra che l'algoritmo FIFO in generale non ha una proprietà che ci si aspetterebbe (l'aggiunta di memoria riduce gli errori di pagina) ma non mostra che in media non ce l'ha . E comunque l'algoritmo FIFO non viene mai utilizzato per la sostituzione della pagina.
Inoltre, si può dimostrare che alcuni algoritmi di sostituzione della pagina ( ad esempio LRU ) non sono soggetti a questo tipo di anomalia.
Le modalità di selezione della pagina vittima sopra citate possono essere applicate sia alle pagine appartenenti ad un processo (si parla quindi di “allocazione locale”), oppure a tutte le pagine e quindi a tutta la memoria (in questo caso la tecnica di allocazione è si dice che sia "globale").
In un sistema di allocazione globale, il tempo di esecuzione di un processo può variare notevolmente da istanza a istanza perché il numero di errori di pagina non dipende dal processo stesso. D'altra parte, questo sistema consente al numero di dirigenti assegnati a un processo di evolversi.
Il diagramma seguente mostra tre processi in esecuzione, ad esempio un editor di testo denominato Ed. Le tre istanze si trovano tutte negli stessi indirizzi virtuali (1, 2, 3, 4, 5). Questo programma utilizza due distinte aree di memoria: le pagine che contengono il codice, cioè le istruzioni che descrivono il programma, e l'area dati, il file in editazione. È sufficiente mantenere le stesse voci nella tabella delle pagine affinché le tre istanze condividano l'area del codice. D'altra parte, le voci corrispondenti alle pagine di dati sono distinte.
Alcune protezioni bit vengono aggiunte a ciascuna voce nella tabella delle pagine. Quindi possiamo facilmente distinguere tra le pagine allocate al kernel, di sola lettura, ecc. Vedi l'esempio sotto.
Ci sono tre problemi principali:
Il comportamento dei programmi non è caotico: il programma si avvia, chiama funzioni (o parti di codice) che a loro volta ne chiamano altre, ecc. Ciascuna di queste chiamate definisce una regione. È probabile che il programma possa impiegare molto tempo in alcune regioni: questo è il principio della località. Lo stesso principio può essere applicato alle pagine contenenti dati.
In altre parole, un programma accede frequentemente a un piccolo insieme di pagine e quell'insieme di pagine cambia lentamente nel tempo.
Se siamo in grado di mantenere in memoria questi spazi a cui si accede spesso, riduciamo le possibilità di vedere un programma iniziare a cestinare , vale a dire rivendicare pagine che sono state appena rimosse da esso di recente.
Il set di lavoro: spazio di lavoroPossiamo definire un parametro, Δ, che è il numero di riferimenti alle pagine a cui il processo accede durante un certo periodo di tempo. La figura seguente mostra il valore dell'area di lavoro in due momenti diversi:
Il valore di Δ deve essere scelto con cura: troppo piccolo non copre lo spazio di lavoro nominale del processo; troppo grande include pagine non necessarie. Se Δ è uguale a infinito, ovviamente copre l'intero programma.
Per un singolo processo, possiamo rappresentare graficamente come viene allocata la memoria e visualizzare gli spazi di lavoro:
I “vassoi” sono aree in cui non ci sono errori di pagina: lo spazio allocato è sufficientemente ampio da contenere tutti i frame di cui il processo necessita per un tempo relativamente lungo. Gli errori di pagina si verificano nella parte ascendente della transizione, mentre la memoria si libera quando la curva ritorna allo spazio di lavoro successivo: la zona di equilibrio.
Spetta al sistema operativo implementare gli algoritmi in modo che il valore di Δ sia ottimale in modo da massimizzare la velocità di multiprogrammazione e l'utilizzo dell'unità centrale . In altre parole: evita di cestinare . Se la somma degli spazi di lavoro di ogni processo è maggiore del numero di frame disponibili, ci sarà necessariamente un collasso.
Uno dei vantaggi della memoria virtuale è quello di poter avviare l'esecuzione di un programma non appena la sua prima tabella codici viene caricata in memoria. La prepaginazione non caricherà solo la prima pagina, ma anche le successive, che hanno un'elevata probabilità di essere accedute.
Macchina | Spazio indirizzabile | Campi numero di pagina | Campi "Spostamento" |
---|---|---|---|
Atlante | 11 | 9 | |
PDP-10 | 9 | 9 | |
IBM-370 | 13 o 12 | 11 o 12 | |
Pentium Pro | 12 o 20 | 20 o 12 | |
Alpha 21064 | 13 | 30 |
I campi M, U, N e NDP sono validi solo se il bit V è 1. Quando V è 0, il campo NDP contiene l'indirizzo sul disco rigido in cui si trova la pagina.
Valore | Protezione |
---|---|
0000 | Nessun accesso |
1000 | Lettura per il kernel |
1100 | Lettura / scrittura per il kernel |
1010 | Lettura utente e kernel |
1110 | Lettura dell'utente, lettura / scrittura del kernel |
1111 | Lettura / scrittura utente e kernel |
Bit 24, N ( N on-nascosto), significa che la pagina non è memorizzata nella cache e il sistema dovrebbe leggere o scrivere direttamente da o nella memoria.
Il bit M ( M odificato) viene modificato dall'hardware se viene modificato il contenuto della pagina.
Il bit U ( U tilisée) indica se la pagina è stata letta o scritta da un processo. È utile, in associazione con gli altri, per determinare il Working Set di un processo (vedi sopra).
La segmentazione fornisce una visualizzazione della memoria più coerente con quella dell'utente. In effetti, questa non considera (o raramente!) La memoria come una serie di pagine ma piuttosto come spazi, o regioni, destinati ad un uso particolare ad esempio: il codice di un programma, i dati, lo stack, un insieme di subroutine, moduli, un array, ecc. La segmentazione riflette questa organizzazione.
Ogni oggetto logico sarà designato da un segmento. In un segmento l'indirizzamento verrà eseguito utilizzando uno spostamento. La coppia (segmento, cilindrata) verrà tradotta in un indirizzo di memoria mediante una tabella dei segmenti contenente due campi, limite e base . La base è l'indirizzo iniziale del segmento e limita l'ultimo indirizzo dello stesso segmento:
I sistemi impaginati hanno un problema di frammentazione interna : lo spazio viene sprecato alla fine di una pagina. I sistemi segmentati hanno un problema di frammentazione esterna : gli spazi tra i segmenti sono troppo piccoli per accogliere nuovi frammenti, quindi lo spazio viene sprecato.
È possibile recuperarlo compattando la memoria, cioè spostando i segmenti - riflettendo queste modifiche nelle tabelle dei segmenti - in modo che siano contigui. Tuttavia, questa operazione è costosa.
È possibile condividere segmenti tra processi, come mostrato nella figura seguente, dove due processi Ed1 e Ed2 condividono lo stesso segmento di codice (programma) ma hanno segmenti di dati disgiunti di dimensioni diverse.
Questa protezione sarà assicurata da bit aggiuntivi aggiunti nella tabella dei segmenti, come per un sistema paginato.
L'esempio più noto è l' Intel 8086 e i suoi quattro registri:
Anche i successori dell'8086 sono segmentati:
È possibile combinare le due modalità precedenti:
A volte è necessario eliminare tutte le pagine o segmenti di un processo dalla memoria principale. In questo caso si dirà che il processo è stato scambiato e tutti i dati ad esso appartenenti verranno memorizzati nella memoria di massa. Ciò può accadere per processi inattivi a lungo quando il sistema operativo deve allocare memoria per i processi attivi. Le pagine o segmenti di codice (programma) non verranno mai scambiati , ma semplicemente riassegnati, perché si trovano nel file corrispondente al programma ( il file eseguibile ). Per questo motivo, il sistema operativo proibisce l'accesso in scrittura a un file eseguibile in uso; simmetricamente, non è possibile avviare l'esecuzione di un file mentre è tenuto aperto per l'accesso in scrittura da un altro processo.
La compressione della memoria virtuale può migliorare le prestazioni di un sistema di memoria virtuale. Questa tecnica di gestione della memoria virtuale utilizza la compressione dei dati per ridurre la dimensione o il numero di richieste di paging da e verso la memoria ausiliaria.
In un sistema di compressione della memoria virtuale, le pagine vengono compresse e archiviate nella memoria fisica, in genere RAM , o inviate compresse a una memoria ausiliaria, come un disco rigido o un SSD . In entrambi i casi, l'intervallo di memoria virtuale i cui contenuti sono stati compressi è inaccessibile, quindi i tentativi di accedere alle pagine compresse generano errori di pagina e invertono il processo di compressione (recupero della memoria ausiliaria e decompressione). Il footprint dei dati di paging viene ridotto dal processo di compressione e la memoria RAM liberata viene restituita al pool di memoria fisica disponibile. Nel caso in cui le pagine compresse siano conservate nella memoria RAM, le pagine compresse ovviamente occupano meno spazio rispetto alle pagine originali. Nel caso in cui le pagine compresse siano conservate nella memoria ausiliaria, la memoria RAM viene completamente liberata e le operazioni di scrittura e lettura sulla memoria ausiliaria sono più veloci che se le pagine non fossero state compresse.