Tabella dei frame
Oltre alla tabella delle pagina che abbiamo per ogni processo, abbiamo anche la tabella dei frame, ogni record è formato in questo modo:
- stato: occupato/libero
- author: quale processo lo occupa
Progettazione di una tabella delle pagine
Per creare un ottima tabella delle pagine è importante curare i seguenti aspetti:
- velocità: la velocità di consultazione
- dimensione
Affrontiamo il problema della velocità
Soluzione storica: avere un registro per ogni entry della tabella delle pagine (per ogni processo), questa è una soluzione molto veloce, ma funziona solo se ho una dimensione ridotta. Inoltre il context switch diventa lento.
Soluzione moderna: tabella interamente residente in memoria con registro PTBR (Page Table Base Register) che vive anche esso in RAM - questo registro indica alla MMU quale tabella di paginazione usare in base al processo in esescuzione. In pratica in quel registro troviamo l’indirizzo fisico del primo record della tabella di paginazione. Servono due accessi alla memoria per prelevare il dato (uno al PTBR, uno al dato dopo aver calcolato il suo offset rispetto all’indirizzo PTBR)
La soluzione moderna è ottima, ma pagare due accessi alla RAM non è ottimo, cerchiamo una strategia migliore
Translation Lookaside Buffer (TLB): una memoria ultra veloce che si frappone tra l’MMU e la RAM (la tabella delle pagine), è praticamente una cache per l’MMU, in questa memoria troviamo gli indirizzi fisici delle pagine virtuali più frequenti richiesti dall’MMU alla RAM.
Un programma userà sempre maggiormente una parte ridotta del codice, mettendo in conto questa cosa questo buffer diventa molto utile.
Di seguito varie specifiche:
- viene chiamata anche memoria associativa
- ha un numero ridotto di entry (registri interni) tra 64 e 1024, ognuna di queste ha le seguenti voci:
- numero di pagina virtuale
- bit per validità della voce della TLB: indica se la voce è valida (se contiene dati)
- codice di protezione;
- dirty bit: indica se la pagina è stata modificata in RAM rispetto alla versione originale in disco
- numero di frame: questo insieme alla prima voce ci permette di trovare l’indirizzo fisico della pagina specificata
- la ricerca viene fatta parallelizzando su tutte le voci (per questo è molto costosa e piccola, se fosse troppo grande non riusciremmo a parallelizzare)
- essendo molto simile ad una cache abbiamo i concetti di TLB miss e TLB hit
- una volta che una pagina viene liberata dalla RAM il suo rispetto bit di validità dentro la TLB deve essere modificato
- Ci consente di vincolare alcune pagine alla TLB - è uno strumento che sfrutta il sistema operativo per pagina molto importanti
- Quando faccio un context swtich faccio un flush della TLB - la prima ricerca di un processo dopo un flush sarà sempre un miss perché la TLB è vuota.
Per evitare il flush (è una perdita di tempo assurda se ci sono sempre gli stessi processi) andiamo ad aggiungere un una voce extra detta ASID(address-space identifiers) che identifica il processo dentro la tabella TLB. In pratica adesso la ricerca viene eseguita usando la chiave (page number, ASID).
Quanto impatta l’utilizzo di una TLB? Di seguito calcoli ci permettono di calcolare il tempo medio (EAT: Effective access time)
Affrontiamo il problema della dimensione
Nella realtà la tabella delle pagine è enorme e quindi non è mai mono-dimensione
In pratica dovremmo avere 4MB di ram per ogni pagina (una memoria assurda). Da questo tipo di problema nascono le pagine multi-livello. (sarebbe la gestione multi livello di basi di dati)
Tabelle delle pagine multi-livello: il PTBR punta alla tabella di primo livello, nella tabella di primo livello troviamo dei gruppi di pagine. In pratica il PTRB punta ad uno dei gruppi. Dentro al record di primo livello troviamo il puntatore ad una tabella di secondo livello. La tabella di secondo livello è la solita tabella delle pagine (come la conosciamo).
Vantaggio: consumo molta meno memoria
Svantaggio: facciamo più accessi alla memoria quindi riduciamo la velocità
Cosa faccio per creare l’indirizzo fisico: avendo in input solo il numero di pagina virtuale (che chiameremo n) e l’offset - devo capire a quale gruppo appartiene questa pagina. Per farlo eseguo: otterrò:
- quoziente: che diventa l’identificatore del gruppo
- resto: l’offset dentro il gruppo specificato Usando questi due dati arrivo alla pagina specifica che mi indicherà l’indirizzo fisico.
Gestire i casi reali con 64 bit il numero di livelli aumenta (almeno 4 o 5 livelli), quindi aumenta il numero di accessi alla RAM, sulla carta questa soluzione non sembra ottima, ma realmente grazie all’utilizzo di diverse TLB lo diventa.
TIP
Se le pagine non hanno valore (il bit di validità è a 0) non ha senso gestirle. La struttura multi-livello viene usata solo per le pagine veramente utili
Tabella delle pagine invertite (non ho capito)
Questa è un’altra soluzione nella gestione delle pagine in memoria, in pratica al posto di avere una tabella delle pagine enorme, creiamo una tabella dei frame ma con le seguenti voci:
- idprocesso
- pagina virtuale questo ci permette di sostituire le n tabelle della pagine usate per ogni processo ad una singola tabella usata per qualsiasi processo. Grazie al pid riesco a trovare velocemente la pagina virtuale necessaria, dalla quale trovo poi l’indirizzo fisico (?). Questa è una tabella hash con key == pid.
Non ho capito se abbiamo una singola tabella per tutti i processi o una singola per ogni processo.