Paging

Prima ricordiamo che …

---

La memoria virtuale è un’astrazione fondamentale del OS, infatti essa risolve il problema del software bloat (o bloatware), dove le dimensioni dei programmi superano di molto la capacità della memoria fisica.

La memoria virtuale è una tecnica che permette ai programmi di essere eseguiti anche quando sono solo parzialmente nella memoria principale.

Soluzione con Overlay (no memoria virtuale)

Una soluzione adottata negli anni 60’ è quella di dividere i programmi in piccoli pezzi, chiamati overlay.

All’avvio del programma veniva caricato in memoria solo il gestore degli overlay, che caricava e avviava l’overlay 0. Gli altri overlay venivano mantenuti su disco e caricati in memoria al bisogno del gestore degli overlay.

Il lavoro pesante era fatto dal programmatore che doveva suddividere il programma in pezzi più piccoli. Questa operazione era noiosa e soggetta ad errori.

Paging :luc_file_text:

PS: c’è anche questo video che spiega bene la paginazione

Il metodo degli overlay è stato superato da una tecnica che trasferisce la responsabilità della gestione della memoria dal programmatore all’hardware e al sistema operativo.

La memoria virtuale, utilizza il concetto di paginazione (paging), che è una generalizzazione dell'idea del registro base e limite.

La paginazione consiste all'intero spazio di indirizzamento di essere rimappato sulla memoria fisica in unità di dimensione fissa chiamate pagine.

Mentre le unità fisiche mappati alle pagine (virtuali) nella memoria reale (fisica) (RAM) sono chiamate frame o page frame, e hanno le stesse dimensioni delle pagine.

Supponiamo per esempio di avere :

• pagine da 4 KB
• space address di 64 KB
• memoria fisica da 32 KB allora possiamo avere massimo 64/4 = 16 pagine e 32/4 frame (come mostrato qui di seguito).

Nella figura :

• frame “0K-4K” indica l’intervallo di indirizzi da 0 a 4095 e cosi via
• le pagine virtuali contrassegnate con una “X”, son quelle NON mappate in memoria fisica

Il vantaggio risiede nel fatto che per eseguire un programma non è necessario mantenere tutte le pagine in memoria fisica.

Infatti nella memoria principale si mantengono solo i “pezzi” (le pagine) del programma che sono necessari, a differenza dello swapping che si carica in memoria l’intero processo.

MMU

La conversione dell’indirizzo virtuale in quello fisico è gestita da un’unità hardware chiama MMU (Memory Management Unit).

In un computer con memoria virtuale, l’indirizzo virtuale (es. da 16 bit) non finisce sul bus indirizzi ma finisce prima nella MMU che :

• divide l’indirizzo in due parti:
  • numero di pagina: usato come indice per cercare la riga giusta nella tabella delle pagine
    • 4 bit : per poter avere $2^4$ combinazioni di numeri di pagine
  • offset: indica la posizione all’interno di quella pagina
    • 12 bit : per poter indirizzare $2^{12}=4096$ byte al interno di una pagina specifica da $1024\times 4=4096\text{ B}=4\text{ KB}$

• tabella delle pagine è utilizzata per tradurre l’indirizzo virtuale in uno fisico dove :
  • trova la riga nella tabella (come index utilizza il numero pagina)
  • prende il numero di frame corrispondente (es. 110)
  • ci attacca l’offest (sempre lo stesso) e ottiene l’indirizzo fisico da mandare alla RAM

In questo caso abbiamo utilizzato indirizzi da 16 bit, ma i moderni PC utilizzano indirizzi da 32 o 64 bit, infatti con 32 bit e pagine da 4 KB avremo :

• 12 bit per indirizzare 4096 byte per pagina (come prima)
• # pagine = $2^{32-12}=2^{20}$, quindi la tabella delle pagine avrà $2^{20}$ righe
• avremo quindi $2^{20}\times 4\text{ KB}$ = 4 GB di space address
• cosa che con pochi GB di RAM si può gestire

Tabella delle pagine

Ogni riga ha informazioni importanti come :

• numero frame (o page frame) (es. 110)
• bit di presenza/assenza
• bit di protezione : specifica che tipo di accesso è consentito (come i bit rwx in UNIX)
• bit supervisor : indica che la pagine è accessibile solo dal OS o anche dai programmi utente
• bit pagina modificata (o dirty): è asserito quando la pagina è stata modificata, quindi va scritta su disco prima di sovrascriverla
• bit pagina referenziata: asserito se è stato fatto un accesso (lettura o scritta) alla pagina. Utilizzato come criterio per lo swap delle pagine quando si verifica un page fault.
• bit disabilita cache: permette di disabilitare il caching della pagina

Di solito una riga della tabella delle pagine è grande 32 bit.

Per un processo l’indirizzo in memoria della sua tabella delle pagine è scritto in un registro chiamato Page Table Base Register - PTBR

Problemi e soluzioni del paging

In qualsiasi sistema di paging devono essere affrontati due aspetti critici:

1. mappatura veloce : necessaria ad ogni riferimento alla memoria
   • la sfida per esempio è che se una istruzione impiega 1 ns, la mappatura deve essere < 0.2 ns per evitare colli di bottiglia
2. dimensione tabelle delle pagine : più è ampio lo spazio di indirizzamento virtuale maggiore è la dimensione della tabella delle pagine

Dove memorizzare la tabella delle pagine?

In registri hardware :

• un registro hardware per ogni pagina, caricato all’avvio del processo
• vantaggi : semplice e veloce in fase di riferimento (non bisogna accedere alla memoria)
• svantaggi : diventa quasi impossibile con tabelle delle pagine molto grandi (+ registri) e fare context switch tra processi diventa pesante

In memoria principale :

• tabella interamente in RAM, con un registro (PTBR) che punta al suo indirizzo
• vantaggi : facile da cambiare ad ogni context switch, infatti richiede solo il ricaricamento del registro
• svantaggi : richiede accessi frequenti alla memoria, rendendo la mappatura lenta (ps : possiamo risolvere con TLB…)

Soluzione al problema della velocità (primo) - TLB

Il problema nelle prestazioni della paginazione, è il fatto che ogni istruzione (qualunque sia) richiede l’accesso in memoria :

• sia per accedere alla tabella della pagine (da MMU), per capire da dove prelevare l’istruzione
• sia per prelevare l’istruzione dalla memoria

La maggior parte dei programmi tende a fare un gran numero di riferimenti a un piccolo numero di pagine. Quindi la soluzione è quello di utilizzare un piccolo dispositivo hardware chiamato TLB (Translation Lookaside Buffer) che mappi gli indirizzi virtuali verso i fisici senza passare per la tabella delle pagine (che si trova in memoria).

Il TLB (o memoria associativa) è interno alla MMU e consiste di un ridotto numero di righe (es. 8-256), dove ogni riga contiene informazioni su una pagina, tra cui:

• numera pagina virtuale
• numero del frame
• bit di protezione (permessi)
• bit pagina modificata
• bit di validità (es. se in uso)

Quando un indirizzo virtuale viene presentato alla MMU per la traduzione:

• si controlla prima nel TLB se è presente in una delle sue righe
• se viene trovata una corrispondenza e valida (TLB hit), è ok
• se non viene trovata nessuna corrispondenza (TLB miss), la MMU passa il problema al OS con un TLB fault, il OS deve :
  • cercare la pagina richiesta nella tabella delle pagine in memoria
  • aggiornare la TLB con la nuova mappatura trovata
  • rieseguire l’istruzione che ha generato il trap

Considerazioni aggiuntive sul TLB

• modifiche ai permessi di una pagina nella tabella delle pagine richiedono l’aggiornamento o l’eliminazione della riga corrispondente nel TLB
• quando si verifica un TLB miss, tutte le operazioni descritte devono avvenire in poche istruzioni, siccome le TLB miss sono più frequenti delle page fault

Nel tempo sono state ideate varie soluzioni per ridurre le TLB miss :

• OS carica in anticipo la TLB con delle pagine che è probabile che nel breve possano essere utilizzate
• riservare uno spazio di posizioni fisse nella TLB in modo che le righe presenti in questo spazio non siano rimosse quando accade una TLB miss

Nella gestione della TLB via software (es. architetture RISC come SPARC, MIPS e HP PA) dobbiamo considerare un caso di “miss” (oltre a quello “soft” ovvero un normale miss) :

• hard miss:
  • condizioni :
    • pagina non è in memoria
    • pagina non è nella TLB
  • azione :
    • accesso al disco per caricare la pagina
    • aggiorna il TLB
    • riavvia l’istruzione

Soluzione della dimensione della tabella delle pagine

Esistono due approcci principali che si posso utilizzare per risolvere il secondo problema :

• tabella delle pagine multilivello
• tabella delle pagine invertite

Tabelle delle pagine multilivello

L’obiettivo è prevenire che l’intera tabella delle pagine debba risiedere in memoria.

L’approccio consiste nell’organizzare la tabella in una “gerarchia di livelli”, suddividendo l’indirizzo virtuale in campi distinti, dove un registro chiamato CR3 punta al vertice della gerarchia. Ricordiamo che la ricerca della pagina in questa gerarchia è chiamata page table walk.

A 2 livelli (32 bit)

Supponiamo per esempio di avere un indirizzo virtuale a 32-bit e lo partizioniamo in questo modo :

• PT1 : 10 bit
• PT2 : 10 bit
• Offset : 12 bit
• allora avremo $2^{10+10}$ pagine in totale ognuna da $2^{12}=4\text{ KB}$

quindi la tabella delle pagine è organizzata in 2 livelli :

1. primo indirizzato da PT1
2. secondo indirizzato da PT2

quando la MMU deve tradurre l’indirizzo virtuale 0x00403004 :

• estrae PT1 = 0000 0000 0001 e lo utilizza come indice nella tabella delle pagine di primo livello per ottenere l’indirizzo della riga della tabella delle pagine di secondo livello
• una volta arrivato nella tabella delle pagine di secondo livello, la MMU estrae PT2 = 0000 0000 0011 e lo utilizza come indice nella tabella delle pagine di secondo livello in cui è appena arrivato
• la riga trovata nella tabella delle pagine di secondo livello contiene il numero del frame fisico, che viene combinato con Offset per costruire l’indirizzo fisico reale

Quindi la tabella di primo livello sta sempre in memoria, mentre le tabelle di secondo livello vengono allocate solo per le zone di memoria virtuale che il processo usa davvero.

4 livelli (64 bit)

---

Algoritmi di sostituzione pagine