SO: Paginazione e segmentazione

Concetti sulla paginazione
La paginazione è un metodo di gestione della memoria che fa si che lo spazio degli indirizzi fisici di un processo non sia contiguo. In questo modo si elimina il gravoso problema della compattazione riscontrato con l'uso del partizionamento dinamico. La memoria in particolare è suddivisa in tanti memory hole della stessa taglia, chiamati frame di memory frame, e la memoria logica in blocchi di eguale dimensione detti pagine.

Ciascuna pagina può essere quindi caricata semplicemente in un memory hole disponibile della memoria di lavoro.

In questo modo si sfrutta bene la ram a disposizione senza lasciare delle porzioni vuote dovute all'inserimento dei blocchi in locazioni contigue. Con questa tecnica è possibile allocare un qualsiasi processo in memoria sfruttandola al meglio senza ricorrere quindi alla sua compattazione (il problema della frammentazione si crea quando un frame non è completamente occupato ma è comunque un problema trascurabile).


La dimensione di una pagina, così come quella del frame è stabilita dall'architettura del calcolatore ed è in genere compresa tra 512byte-16Mb (si và per potenze di due in modo da facilitare l'indirizzamento. Se, ad esempio, le pagine sono di 2048 byte, un processo che occupa 72.766 byte necessita di 35 pagine e 1086 byte. In questo caso vengono assegnate 36 pagine, ottenendo quindi una frammentazione interna di 962 byte. In generale la perdita per ogni processo attivo è di x/2 bytes.

Per ridurre questo genere di perdita si può pensare di creare pagine di dimensione minore (si potrebbero persino creare pagine di 1byte; in questo modo si annullerebbero le perdite) ma all'aumentare del numero di pagine aumenta automaticamente anche la complessità dell'algoritmo preposto alla traduzione degli indirizzi.

La paginazione quindi non è altro che una forma di rilocazione dinamica: a ogni indirizzo logico l'architettura di paginazione fa corrispondere un indirizzo fisico. Quindi un processo non deve essere necessariamente caricato in una zona contigua della memoria.
Il binding degli indirizzi (a tempo di caricamento ed esecuzione)
E' possibile utilizzare due tecniche per il binding degli indirizzi. La prima è quella di farlo a tempo di caricamento: una volta stabiliti i frame ogni riferimento a una specifica pagina diventa il corrispondente riferimento fisico del frame dove questa è caricata. Tuttavia questa tecnica non è usata poichè richiederebbe che una certa porzione di software del loader sia in grado di risolvere un mapping complesso pagina per pagina di ogni riferimento all'interno del processo.

La seconda tecnica (quella utilizzata comunemente) è quella di usare il mapping a tempo di esecuzione: ci sono quindi dei supporti nel sistema in grado di traslare runtime gli indirizzi logici in indirizzi fisici. In questo modo ci si evita in primo luogo di sobbarcare il loader nella traduzione e contemporaneamente si può utilizzare anche il supporto swap-in e out.

La tavola delle pagine
La struttura dati che permette il mapping è la tavola delle pagine; c'è una tavola delle pagine per ogni processo e si tratta in buona sostanza di una lista con una serie di entry. Per ogni entry (che è un indirizzo logico) l'informazione contenuta è composta da due parti che corrispondono alla parte più singificativa e meno significativa della cifra. Il numero che si ottiene è il blocco di memoria fisica e lo scostamento dove si trova il dato.
La parte più significativa contiene il numero di pagina, mentre la parte meno significativa l'offset/scostamento all'interno della pagina. A questo punto la traduzione consiste nel ritornare il frame che contiene il dato (nello spazio di indirizzi fisico) e poi l'offset (ereditato dalla lettura della tavola, e che non cambia nella traduzione e che non cambia visto che pagine e frame hanno egual taglia).


La tavola delle pagine di un processo viene copiata in un registro speciale (CR3 su x86) quando esso diventa il processo attivo.

E' possibile che ad ogni swap-in la tabella delle pagine venga aggiornata con nuovi valori.
Tabella delle pagine invertita
Generalmente si associa una tabella delle pagine a ogni processo contenente le entry delle relative zone di memoria usate. Questa tecnica ha comunque un grosso limite: ciascuna tabella delle pagine può contenere milioni di elementi occupando quindi una gran quantità di memoria fisica soltanto per sapere dove è impiegata quella rimanente.
Per risolvere questo problema si utilizza la t.invertita. Questa ha un elemento per ogni pagina relae (blocco di memoria). Ciascun elemento è quindi costituto dall'indirizzo virtuale della pagina di memorizzata in quella reale locazione di memoria, insieme ad altre informazioni sul processo che la usa.
Nel sistema esiste quindi una sola tabella delle pagine che ha un solo elemento per ciascuna pagina di memoria fisica.
Ogni elemento della tabella delle pagine invertita è una coppia dove il primo elemento assolve al ruolo di identificazione del progetto.
Quando si fa un riferimento alla memoria, si presenta una parte dell'indirizzo virtuale formato da al sottosistema di memoria. Quindi si cerca una corrispondenza nella tabella delle pagine invertita. Se si trova si genera quindi l'indirizzo fisico .


Il problema di questa tecnica è che la ricerca è molto dispendiosa. Tuttavia è possibile diminuirne il carico utilizzandola nella forma di tabella hash (che ad ogni modo richiederebbe due letture).

TLB (Translation Look-aside buffer)
Per funzionare in maniera adeguata la paginazione deve avere dei supporti hardware. Grazie a questi è possibile ridurre il tempo dovuto all'esecuzione di più operazioni lato software accellerando quindi l'operazione di binding.
Il TLB è in sostanza una cache che mantiene alcune translazioni tra numero di pagina logica e numero di frame. Può contenere un numero molto limitato di dati e contiene soltanto quelli recenti. Questo significa che non sempre è sicuro che i dati si trovino al suo interno: in questo caso ovviamente mi dovrò rivolgere alla tavola delle pagine che ha una rappresentazione complete del mapping degli indirizzi.

Il TLB funziona molto bene (secondo un hitradio: percentuale di successi) per il principio della località: quando un'applicazione incomincia a lavorare su una specifica regione di indirizzi (ad eempio esegue un ciclo for/while) significa che un determinato numero di pagine verranno riferite più volte. Si può risparmiare almeno il 10% del tempo necessario alla lettura normale.
Segmentazione
L'uso della paginazione fa si che ci sia una separazione tra la visione della memoria dell'utente e l'effettiva memoria fisica. Lo spazio d'indirizzi 'visto' dall'utente non corrisponde all'effettiva memoria fisica, ma lo si fa corrispondere.
La tipica struttura di un programma è costituita da:

• parte principale
• gruppo di procedure
• tabella dei simboli
• funzione sqrt
• pila

Nella segmentazione una volta che il compilatore ha suddiviso le varie parti, esse vengono presi e messi all'interno di ciascun segmento di lunghezza variabile.Gli elementi che si trovano all'interno di un segmento sono quindi identificati da . Quindi viene creato un segmento separato per ogni blocco comune.
I segmenti possono essere caricati anche in zone non contigue. Essi vengono poi mappati attraverso la tabella descrittore dei segmenti.

Al contrario della paginazione, la segmentazione può aiutare il programmatore nel modularizzare il software. La segmentazione presenta comunque il problema della frammentazione esterna, che può essere ridotto tramite segmentazione paginata.

(18-01-2007)