Paginazione

La paginazione (o paging), in informatica, è la tecnica attraverso la quale il sistema operativo del computer, per mezzo dei rispettivi algoritmi di paging, suddivide la memoria in parti di dimensioni minori, e la alloca al programma da eseguire usando pagine come blocco minimo di lavoro.^[1]

Descrizione

Vantaggi

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 è uno dei vantaggi del paging rispetto ad altre tecniche concorrenti.

Svantaggi

Il più grande 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, dagli 80386 in poi 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. In questo caso si parla di frammentazione interna.

Un altro svantaggio è sicuramente quello delle prestazioni. Senza paginazione il computer funziona sicuramente più velocemente. Però con una perdita di funzionalità eccessiva rispetto alla velocità guadagnata. Non si possono implementare tantissime cose, compreso tecniche per diminuire l'utilizzo della memoria (come ad esempio lo Swapping su disco).

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 sarebbe potuta 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, 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 (0FE)
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.

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.

Swapping e paginazione

Nel caso in cui la memoria fisica richiesta dall'insieme dei vari processi superi un certo limite (ogni sistema operativo ha un proprio limite stabilito e in alcuni casi, come in Linux, modificabile), alcune pagine debbono essere temporaneamente depositate sul disco fisso e ricaricate nel momento del bisogno. Questa tecnica si chiama swapping, e permette di abbattere l'utilizzo di memoria. Tuttavia, l'accesso alla memoria di massa, tipicamente un disco fisso, avviene in tempi molto più grandi che alla memoria di lavoro -l'accesso alla RAM è dell'ordine dei nanosecondi, quello a disco dei millisecondi- rischiando di rallentare in maniera inaccettabile l'elaboratore, senza contare l'usura dei dischi che vengono usati eccessivamente. Lo swapping è implementato da tutti i sistemi operativi moderni, compresi Linux e Windows. Naturalmente il meccanismo di swap entra in gioco solo quando il sistema è sotto stress e ci sono molti processi in esecuzione e poca memoria fisica disponibile. È per questo che quando abbiamo molti programmi aperti la velocità di esecuzione di ognuno di loro scende sensibilmente, sia perché il tempo di esecuzione si divide per ogni processo utilizzato, sia perché l'utilizzo della memoria fisica è alto e quindi scatta lo swapping delle pagine.

È quindi necessario che l'accesso al disco venga ridotto al minimo, memorizzando solo le pagine che si prevede verranno richiamate di meno. Per farlo, esistono degli algoritmi chiamati LRU che scelgono le pagine adatte ad essere swappate tra quelle LRU (Least Recent Used - meno recentemente usate). Comunque è impossibile prevedere con esattezza le pagine che non verranno utilizzate, perciò molto spesso questi algoritmi sbagliano swappando una pagina che sarà utilizzata a breve e quindi rallentando il computer (infatti deve prima scrivere la pagina sul disco, poi rileggerla subito dopo) senza diminuire l'utilizzo di memoria.

Pagine condivise

Alcune pagine di memoria possono essere disponibili per più processi oltre al sistema operativo, in tal caso si parla di pagine condivise o shared pages. Le pagine condivise sono usate ad esempio per permettere ai processi di comunicare tra di loro (si pensi al semplice "copia e incolla" che permette a un programma di incollare testo copiato da un altro). Un altro importante utilizzo delle shared pages è la gestione ottimale dei processi creati tramite fork(). Un processo figlio, infatti, ha in teoria una copia esatta della memoria del padre, ossia di tutte le variabili e anche dei file e delle connessioni aperte, ma spesso la sua esecuzione si riduce all'utilizzo di pochissime pagine e di pochissimo codice, rendendo inutile l'eventuale operazione di copia di tutte le pagine del padre. Di solito quindi si ricopiano solo le prime pagine e poi, eventualmente, quelle che vengono richieste tramite la tecnica del Copy on Write, inoltre le pagine contenenti il codice possono essere le stesse.

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 siano 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.

Generalmente si sconsiglia l'uso di una memoria virtuale superiore a 3 volte o più della memoria RAM^[2] e generalmente viene consigliata una dimensione compresa tra 1,5x a 2x rispetto alle dimensioni della RAM di sistema^[3], In Windows viene impostata automaticamente ad 1,5 volte la RAM^[4].