Sartomiki.net

Paginazione
La paginazione prevede che gli indirizzi fisici di uno stesso processo potrebbero non essere allocati in modo contiguo.
Il metodo base della paginazione prevede di dividere la memoria fisica in blocchi di dimensione costante detti frame e la memoria logica in blocchi di uguale dimensione, detti pagine (teoricamente le dimensioni potrebbero anche essere diverse). Quando si deve eseguire un processo, si caricano le sue pagine nei frame disponibili, prelevandole dalla memoria secondaria, divisa anch'essa in blocchi di dimensione fissa.
In questo modo il processo è allocato in memoria fisica in qualunque parte sia possibile. Per eseguire un processo di dimensione n pagine, è necessario trovare n frame disponibile e caricare il programma.
La paginazione risolve la frammentazione esterna, ma crea frammentazione interna, in quanti non tutti i blocchi avranno dimensione multipla della quantità fissa dei blocchi. La dimensione di ogni pagina dipende dall'architettura del calcolatore ed è in genere un multiplo di 2.
Il problema della frammentazione interna potrebbe far pensare, che una minore dimensione delle pagine, garantistica prestazioni migliori. Questo ragionamento è vero solo in parte, in quanto, aumentando le dimensioni delle pagine, si riduce l'overhead portato dalla tabella che garantisce la conversione degli indirizzi logici e di quelli fisici.
Per garantire il corretto funzionamento della paginazione è necessario un meccanismo di traduzione degli indirizzi logici in indirizzi fisici. Gli indirizzi generati dalla CPU sono divisi in due:
-numero della pagina, utilizzato come un indice nella tabella delle pagine, che consente di trovare ogni pagina nella memoria fisica.
-offset di pagina, che definisce all'interno della pagina l'indirizzo fisico in cui si trova un dato.
L'implementazione di questo meccanismo avviene memorizzando la tabella di paginazione in memoria principale.
Poiché il SO gestisce la memoria fisica, esso deve conoscere quali frame siano liberi e a chi appartengono (per verificare se le operazioni siano sicure). La memorizzazione di queste informazioni avviene con una struttura chiamata tabella dei frame.
Le prestazioni della paginazione dipendono molto dalla dimensione delle pagine. Questo parametro non è normalmente settabile dal programmatore, ma è definito durante la fase di progettazione del calcolatore. E' comunque importante capire quali siano i fattori che determinano questa dimensione:
-Aumentando la dimensione della tabella delle pagine si aumenta il numero delle pagine in essa contenute, migliorando le prestazioni.
-Diminuendo la dimensione delle pagine, la memoria è meglio utilizzata.

Architettura di paginazione
La maggior parte dei sistemi impiega una tabella delle pagine diversa per ciascun processo. Il PCB contiene, tra gli altri, anche un puntatore alla tabella delle pagine fisiche.
L'architettura di supporto alla tabella delle pagine si può realizzare in diversi modi:
-insieme di registri, che sono costruiti in modo da operare a velocità elevata. Questo metodo è utilizzabile solo quando il numero delle pagine è limitato, in quanto i registri sono molto costosi.
-usando un registro di base alla tabella delle pagine (PTRB), che però ha un costo in termini di tempo molto elevato in quanto è richiesto un accesso alla memoria.
-cache associativa TLB, che memorizza solo parte dei record della tabella. Essi sono memorizzati in base ad una chiave e ad un valore. Nel caso però nella TLB non sia presente il record da analizzare è necessario un accesso a memoria.
-TLB con ASID, permettono di memorizzare anche informazioni riguardanti la protezione dello spazio di indirizzamento.
Il tasso di successi di una TLB è dato dalla percentuale di traduzioni di indirizzi virtuali risolti dalla TLB anziché dalla tabella delle pagine. La portata della TLB è invece la quantità di memoria accessibile da una TLB (numero di elementi della TLB * dimensione delle pagine).

Protezione e paginazione
In caso di utilizzo della paginazione la protezione della memoria è assicurata mediante alcuni bit di protezione. Grazie a questi bit è possibile stabilire se una pagina si può leggere/scrivere. Questi dati possono essere analizzati quando viene calcolato l'indirizzo fisico.
Un ulteriore bit aggiuntivo è detto bit di validità e permette di stabilire se una pagina fa parte dello spazio di indirizzamento logico di un processo.
Grazie a questo sistema è anche possibile condividere parti di codice. L'unica condizione necessaria per condividere parti di codice tra più processi è che esse siano rientranti (pure), nel senso che non devono modificarsi durante l'esecuzione.

Struttura delle tabelle delle pagine
I computer moderni hanno a disposizione uno spazio di indirizzi logici molto ampio e quindi le tabelle di paginazione lineari non possono più essere utilizzate. Esistono quindi diverse tecniche per diminuire le dimensioni:
-tabella di paginazione a due livelli, in cui la tabella stessa è paginata. La traduzione degli indirizzi si svolge dalla tabella esterna verso quella più interna. Questo metodo è anche noto come tabella delle pagine ad associazione diretta (forward-mapped page table). Con questo meccanismo i primi bit dell'indirizzo identificano una sezione, mentre i successivi rappresentano il numero logico di pagina e l'offset all'interno della pagina.
-tabella di paginazione a tre livelli, in cui la tabella esterna delle pagine è anche essa paginata. Questo metodo è utilizzato per le architetture a 64bit e può essere esteso anche a più livelli.
-tabella di tipo hash, in cui il numero della pagina virtuale è usato come argomento di una funzione di hash. Per gestire le collisioni in modo efficiente, ogni elemento della tabella di hash contiene una lista concatenata di elementi.
-tabella delle pagine a gruppi, meccanismo simile alla tabella di hash. Ciascun elemento della tabella delle pagine contiene i riferimenti alle pagine fisiche corrispondenti ad un gruppo di pagine virtuali contigue.
-tabella delle pagine invertita. Questo tipo di meccanismo prevede un approccio molto diverso al problema. In questo caso la tabella ha un elemento per ogni pagina reale (frame), che è quindi costituito dall'indirizzo virtuale della pagina memorizzata in quella locazione e dalle informazioni del processo a cui appartiene. Ogni elemento è quindi costituito da una coppia id processo e numero di pagina. Quando si fa riferimento alla memoria si accede all'indirizzo formato da id+numero di pagina, si cerca una corrispondenza nella tabella e se si trova si genera l'indirizzo fisico. La ricerca nella tabella è molto onerosa, in quanto bisogna scorrere tutta la tabella. Con questo metodo, inoltre, risulta essere molto difficile implementare schemi di memoria condivisa.

File e I/O mappati in memoria
Le tecniche derivate dal concetto della memoria virtuale sono applicabili anche ai file e al sistema di I/O:
-file. Il meccanismo prende il nome di mappatura dei file in memoria e prevede di attribuire una parte dello spazio degli indirizzi in memoria virtuale ai file. Una volta che un file è caricato in una pagina è possibile accedere alle informazioni contenute in quel file in modo diretto, senza appesantire il sistema con onerose operazioni di I/O (non devono più usare read, write). E' importante sottolineare che le scritture in memoria principale non corrispondono ad una immediata scrittura su disco, ma questa operazione è svolta di tanto in tanto dall'OS. Nel momento in cui un file viene chiuso, il file, se ha subito modifiche, viene ricopiato in memoria secondaria. Questa tecnica consente la condivisione dei dati tra più processi. Ogni sistema operativo ha tecniche diverse per la gestione dei file mappati in memoria.
-I/O. Molti OS prevedono la mappatura in memoria dell'I/O, che prevede che determinate parti della memoria principale siano utilizzati per memorizzare gli indirizzi dei registri di I/O. La mappatura dei dispositivi di I/O è utile per i dispositivi con rapido tempo di risposta o che hanno bisogno di trasferire lunghe sequenze di bit. Gli I/O possono essere gestiti con una politica di I/O programmato (ad es. polling) oppure mediante interrupt.

Allocazione della memoria per i processi kernel
Il kernel, come tutti gli altri processi, necessita per funzionare di molte pagine in memoria. Esso è costituito da strutture di dimensioni variabili (molte delle quali di dimensioni inferiori rispetto ad una pagina), che, se non allocate in modo oculato, creano frammentazione interna. E' per questo che esistono diverse strategie per la gestione della memoria libera assegnata ai processi kernel:
-sistema buddy (gemellare). Secondo questo metodo viene utilizzato un segmento di lunghezza fissa per allocare la memoria, che contiene pagine fisicamente vicine. La memoria viene assegnata al kernel secondo potenze di 2. In questo modo è possibile congiungere in modo rapido buddy (porzioni di memoria kernel) vicine, mediante una tecnica detta di fusione (coalescing). Il problema di questo sistema è senz'altro lo spreco di memoria, che genera quindi frammentazione interna.
-sistema slab (allocazione a lastre).  Secondo questa tecnica ogni lastra è composta da pagine fisicamente contigue. Una cache raggruppa tra loro più lastre con all'interno strutture uguali. Ad esempio la cache dei semafori contiene tutti i semafori attivi per un determinato kernel.  Nel momento in cui viene creata una cache, vengono inizializzate delle strutture dati vuote al suo interno (slab liberi). Nel momento in cui il kernel necessita di un determinato tipo di struttura viene utilizzato uno slab libero (slab usato) in una cache. Nel caso non siano presenti cache di quel tipo con slam liberi allora viene allocata una nuova cache. In questo modo si annulla lo spreco di memoria derivante dalla frammentazione e le richieste di memoria possono essere soddisfatte in tempi brevi.

Segmentazione
La segmentazione è uno schema di memoria lato utente, che consente di gestire una rappresentazione della memoria familiare all'utente. Siccome i programmi sono divisi in entità con diverse funzioni, lo scopo della segmentazione è quello di definire queste entità e di associarle a degli indirizzi fisici. Nel linguaggio C, ad esempio, un programma è diviso in diverse parti (codice, variabili, heap, libreria, pile,…). Ad ogni parte è associato un segmento diverso e ad ogni entità in esso contenute uno scostamento all'interno dell'entità.
Ad ogni segmento è poi attribuito un numero, in modo da renderlo più facilmente riconoscibile.
L'indirizzo fisico dell'oggetto è spesso dato dalla somma dell'id di segmento e dello scostamento. Prima di effettuare questa operazione bisogna però consultare la tabella dei segmenti, in cui ad ogni indirizzo di segmento è associato il limite del segmento (cioè il valore massimo che lo scostamento associato può assumere).