Paging
Da Wikipedia, l'enciclopedia libera.
Nei sistemi operativi dei computer gli algoritmi di paging dividono la memoria in parti di dimensioni minori, e la allocano usando pagine come blocco minimo di lavoro.
Indice |
[modifica] Vantaggi
Uno dei principali vantaggi del paging rispetto ad altri metodi più semplici, come ad esempio la tecnica cosiddetta buddy memory allocation o quella dell'allocazione dinamica, è che la memoria allocata non deve essere necessariamente composta da blocchi contigui, e di conseguenza la frammentazione viene ridotta, e lo spazio disponibile utilizzato in modo più efficiente. Poiché i programmi raramente utilizzano contemporaneamente tutte le parti del proprio codice e dei propri dati, è conveniente implementare il meccanismo della memoria virtuale, che consiste nello scrivere su disco blocchi di memoria, detti "pagine", e di ricaricarli in memoria, leggendoli dallo stesso disco, quando necessario. La possibilità di implementare questo meccanismo è un altro dei vantaggi del paging rispetto ad altre tecniche concorrenti.
[modifica] Svantaggi
L'unico vero svantaggio del paging è la natura relativamente più complessa del codice di programma necessario per realizzarlo, specialmente nel caso sia implementata la memoria virtuale. Uno svantaggio minore è costituito dalla necessità di disporre di processori dotati della funzionalità detta memory management unit (MMU), non presente su quelli delle vecchie generazioni (ad esempio nella famiglia Intel x86, solo gli 80386 e superiori dispongono della MMU).
Si può anche verificare il caso che si producano frammentazioni, ad esempio quando, per memorizzare una certa quantità di dati, sia necessario uno spazio leggermente maggiore di quello messo a disposizione da una pagina. In questo caso si rende necessario allocare un'intera nuova pagina, di cui viene utilizzata solo una piccola parte dello spazio disponibile. Lo stesso tipo di frammentazione si verifica quando la quantità di memoria da salvare è minore delle dimensioni di una pagina.
[modifica] Principio di funzionamento
Nel paging l'accesso alla memoria è realizzato a livello hardware, secondo uno schema a tabella di pagine gestito dalla MMU. Come spiegato sopra, la memoria fisica è suddivisa in piccoli blocchi (tipicamente minori di 4 kilobytes), e ad ogni blocco è assegnato un numero di pagina. Il sistema operativo mantiene nella propria memoria interna una lista di queste pagine, oppure, più raramente, può decidere di testare la memoria ogni volta che viene inviata una richiesta di allocazione. In ogni caso, ogni volta che un programma invia una richiesta di memoria, il sistema operativo alloca un sufficiente numero di pagine al programma, e mantiene una lista delle pagine allocate. Ecco di seguito un esempio:
| Frame | Programma richiedente | Indirizzo della memoria fisica |
|---|---|---|
| 0 | Programma A.0 | 1000:0000 |
| 1 | Programma A.1 | 1000:1000 |
| 2 | Programma A.2 | 1000:2000 |
| 3 | Programma B.0 | 1000:3000 |
| 4 | Programma B.1 | 1000:4000 |
| 5 | Programma D.0 | 1000:5000 |
| 6 | Programma D.1 | 1000:6000 |
| 7 | Programma B.2 | 1000:7000 |
Questo elenco è un esempio di tabella di allocazione, dove ciascuna pagina occupa 4 kilobytes. L'effettiva allocazione avrebbe potuto avvenire in questa sequenza:
- Il programma A richiede 3 pagine di memoria
- Il programma C richiede 2 pagine di memoria
- Il programma D richiede 2 pagine di memoria
- Il programma C termina, lasciando 2 pagine vuote
- Il programma B richiede 3 pagine di memoria, ed ottiene le 2 pagine vuote lasciate dal programma C, più una pagina aggiuntiva dopo il programma D.
Di conseguenza la tabella di mapping conterrà:
- Programma A: 0=>0, 1=>1, 2=>2
- Programma B: 0=>3, 1=>4, 2=>7
- Programma D: 0=>5, 1=>6
Vediamo ora cosa accade quando un programma deve accedere alla propria memoria. Supponendo che il Programma A contenga l'istruzione:
CARICA i dati memorizzati all'indirizzo 20FE
In un sistema a 16-bit, la rappresentazione binaria di 20FE è 0010000011111110, e quindi, quando viene inviata la richiesta l'unità di gestione della memoria (memory management unit), la "vede" in questo modo:
0010000011111110 = 20FE |__||__________| | | | v v Indirizzo di memoria relativo all'interno della pagina (00FE) Numero di pagina (2)
Poiché vi sono pagine lunghe 4096 byte (4096-1 = 4095 può essere rappresentato in forma binaria da 12 bit), la MMU usa per indirizzarle i primi 4 bit come numero di pagina, ed i successivi 12 per l'indirizzo relativo all'interno della pagina. Se le pagine fossero lunghe 2048 byte, la MMU utilizzerebbe i primi 5 bit per il numero di pagina, ed i successivi 11 bit per l'indirizzo relativo. Ne consegue che quando le dimensioni della pagina sono minori, con il paging è possibile indirizzare un numero maggiore di pagine.
Quando un programma inoltra una richiesta di accesso alla memoria, l'MMU esamina la tabella delle pagine di memoria occupate dal programma per mappare il numero di pagina appropriato. Quindi, quando questa richiesta di allocazione di memoria viene inoltrata, la MMU utilizza la tabella delle pagine occupate dal programma per mappare le corrispondenti pagine del sistema operativo. Nell'esempio qui riportato, la seconda pagina del Programma A mappa la seconda pagina del S.O., e successivamente mappa "fisicamente" la pagina del S.O. La seconda pagina mappata dal S.O. si trova all'indirizzo fisico di memoria 1000:2000 mentre l'indirizzo relativo a cui il programma richiede di accedere è 00FE; di conseguenza la MMU restituirà al programma i dati contenuti all'indirizzo fisico 1000:20FE.
[modifica] Implementazioni del paging
Quella che precede è una introduzione di carattere generale, ma ci sono varianti nel modo in cui le varie piattaforme implementano la tecnica del paging. Ad esempio nei PC basati sull'architettura i386, la CPU utilizza una speciale cache chiamata Translation Lookaside Buffer (TLB), che contiene la mappatura fra gli indirizzi della memoria virtuale e la memoria fisica che ne costituisce il backup. Di conseguenza, una volta generata la tabella di look-up, e prima che le pagine di memoria fisica siano liberate o sottoposte a swapping, le tabelle di look-up non devono essere rigenerate (a spese della potenza di calcolo del processore) poiché il loro contenuto è già memorizzato nella cache del TLB. Il sistema operativo si occuperà poi di eliminare dalla tabella i mappaggi quando questi non puntano più a indirizzi validi. L'utilità della tecnica di mappatura del paging si può ben comprendere se si considera che può far risparmiare migliaia (o addirittura milioni) di indirizzamenti realizzati con la tecnica tradizionale.
[modifica] Paging e memoria virtuale
Quando la tecnica del paging è usata contemporaneamente a quella della memoria virtuale, il sistema operativo deve tenere memoria di quali pagine sono attualmente in uso e quali no (oppure di quelle che non sono in uso da un certo tempo). Quando il sistema operativo ritiene che sia giunto il momento più opportuno, oppure quando un programma richiede una pagina salvata su disco, un'altra pagina viene salvata su disco e un'altra ancora è caricata in memoria. Questo meccanismo consente di "vedere" una quantità di memoria maggiore di quella fisicamente disponibile nel computer.
