SISTEMI A RILOCAZIONE STATICA

SISTEMI MONOPROGRAMMATI

La gestione della memoria più semplice da analizzare è quella presente nei sistemi monoprogrammati con un solo processo in esecuzione alla volta.

Un'area della memoria è permanentemente occupata dal sistema operativo - magari all'inizio e alla fine dello spazio degli indirizzi - e tutta la rimanente è dedicata all'unico processo/programma in esecuzione.

In alcuni casi può esistere un r e g i s t r o l i m i t e d i p r o t e z i o n e per impedire che l'unico programma vada ad interferire con le aree dedicate al SO. Questo registro limite può essere settato con il valore del primo indirizzo libero per i programmi, che è un valore costante, e quindi, runtime, controllato ad ogni accesso alla memoria, per verificare che ogni indirizzo formato non sia inferiore a quel valore contenuto nel registro limite.

Per sistemi operativi come MsDos su piattaforme Intel 8086 ove opera una struttura segmentata della memoria, la rilocazione dei programmi avviene al caricamento, con una relativa rilocazione dinamica operata sulla parte segmento dell’indirizzo (moltiplicazione per 16). Normalmente questi sistemi sono ad allocazione statica.

A volte su sistemi di questo tipo bisogna ovviare al limite dello spazio di memoria, e si interviene con la tecnica dell’O v e r l a y . La tecnica è di responsabilità del programma e non del Sistema Operativo: il programmatore inserisce nel codice speciali istruzioni per revocare e riallocare parti differenti del programma, mutuamente scorrelate tra loro in base alla logica del programma. In questo caso il sistema risulterebbe ad allocazione dinamica, benché la tecnica non sia a carico del Sistema Operativo.

TECNICA DELLE PARTIZIONI FISSE

Questa tecnica riguarda sistemi multiprogrammati.

Una prima versione, in allocazione statica, è la seguente: la memoria principale viene suddivisa rigidamente, dal sysadmin, prima di avviare programmi utente, in n zone di dimensione fissa dette p a r t i z i o n i (in figura, 6 partizioni, compresa la partizione richiesta dal Sistema Operativo).

Tutte le volte che un programma dovrà essere caricato il Sistema Operativo sceglierà, tra le partizioni libere, quella con dimensioni atte a contenere lo stesso, consultando la T a b e l l a d e l l e p a r t i z i o n i e aggiornandola in base allo stato attuale di occupazione.

La rilocazione è statica, e si ottiene al caricamento traslando tutti gli indirizzi del programma a partire dall’indirizzo base della partizione scelta. Risulta estremamente efficace la protezione, considerando i registri limite impostati sulla dimensione della partizione. A runtime sarà sufficiente controllare ogni indirizzo e verificare che sia compreso nella partizione.

Il problema maggiore che incontra questo sistema, pur potendo implementare la multiprogrammazione, si dice f r a m m e n t a z i o n e della memoria. Infatti la risorsa memoria non viene mai

SISTEMA OPERATIVO

PROGRAMMA UTENTE

Bios in Rom

SISTEMA OPERATIVO

P1

P2

P3

P5

P4

utilizzata a fondo, dato che le dimensioni dei programmi non coincidono con le dimensioni delle partizioni che li contengono. Frazioni molto importanti di memoria, quindi, rimangono inutilizzate.

TECNICA DELLE PARTIZIONI VARIABILI

Il concetto è ancora quello della sezione precedente, considerando però zone di memoria (partizioni) a dimensione ed a indirizzo variabile in base al carico del sistema. La tabella delle partizioni contiene, all’avvio del sistema, due soli elementi, per il Sistema Operativo e per il resto della memoria. Man mano che i programmi chiedono l’esecuzione, il Sistema Operativo accede alla tabella, sceglie e imposta una nuova partizione nello spazio libero e alloca (staticamente) il programma rilocandolo (staticamente) come per il metodo delle partizioni fisse. Dopo breve tempo la memoria viene partizionata in modo tale che i successivi programmi dovranno essere posti nelle partizioni libere in base ad un criterio ottimale, in grado di ridurre al minimo lo spreco della memoria.

Le strategie di allocazione dipendono dal criterio scelto per creare o scegliere le partizioni per i programmi che le richiedono.

F i r s t f i t

La tecnica First Fit individua la prima partizione atta a contenere il programma e, quindi, tra le partizioni disponibili, viene scelta quella con indirizzi più bassi. Tale tecnica è efficiente per mantenere compattate le zone rilasciate.

B e s t f i r s t

La tecnica Best Fit ritrova nella tabella la partizione più piccola atta a contenere il programma. In questo modo si vengono a creare numerose partizioni libere molto ristrette e quindi si aumenta la frammentazione.

W o r s t f i t

In modo opposto opera la tecnica Worst Fit che, tra le partizioni libere atte a contenere il programma, sceglie quella più ampia, proprio allo scopo di attenuare l'effetto della frammentazione, anche se simulazioni statistiche riportano la tecnica First Fit come la più efficiente.

SISTEMA

OPERATIVO

P1 P1

P2

P1

P2

P3

P1

P3

SISTEMA

OPERATIVO

SISTEMA

OPERATIVO

SISTEMA

OPERATIVO

SISTEMA

OPERATIVO

tempo

Rispetto al metodo con partizioni fisse la gestione con partizioni variabili è migliore dal punto di vista dell'ottimizzazione, anche se permane il problema della f r a m m e n t a z i o n e e s t e r n a ; l'implementazione è più complessa data la presenza di una tabella della memoria da mantenere continuamente aggiornata.

In alcuni casi la riduzione della frammentazione si può ottenere con una tecnica detta di c o m p a t t a z i o n e

d e l l a m e m o r i a .

In questo modo il SO predispone un algoritmo che periodicamente controlla lo stato della memoria e quando necessario interrompe le esecuzioni per compattare in modo contiguo tutta la memoria allocata eliminando i buchi e aggiornando la tabella della memoria. Un algoritmo del genere però è raramente implementato data la lunghezza dell’operazione. In questo caso, peraltro, si può parlare di allocazione dinamica.

SISTEMI A RILOCAZIONE DINAMICA

PAGINAZIONE

Rispettare la c o n t i g u i t à n e l l o s p a z i o d e g l i i n d i r i z z i f i s i c i significa inevitabilmente creare problemi di frammentazione, interna o esterna, così come mostrato nelle tecniche basate su rilocazione statica viste in precedenza.

Con questa tecnica si cerca di distinguere la contiguità degli indirizzi propri dello spazio virtuale creato dal linker, dall'allocazione in memoria fisica; quindi lo spazio degli indirizzi fisici, nel caso della paginazione, non sarà più contiguo come per gli indirizzi virtuali generati dal linker.

In sostanza si tratta di immaginare gli indirizzi virtuali suddivisi in n sottoinsiemi di uguale dimensione detti p a g i n e di memoria virtuale, riproporre in memoria fisica gli stessi contenitori in termini di ampiezza - detti p a g i n e di memoria fisica - e caricare le pagine virtuali in pagine di memoria fisica che risulteranno pertanto allocate in modo non contiguo.

In sintesi la situazione può essere schematizzata nel seguente diagramma, in cui le pagine hanno la dimensione di 4kb: le otto p a g i n e l o g i c h e del programma sono caricate in otto p a g i n e f i s i c h e della memoria, conservando in essa i propri indirizzi virtuali:

MEMORIA PROGRAMMA (indirizzi virtuali) (indirizzi fisici)

00-04k

04-08k

08-12k

12-16k

16-20k

20-24k

24-28k

28-32k

32-36k

36-40k

40-44k

44-48k

48-52k

52-56k

56-60k

60-64k

0

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

0

1

2

3

4

5

6

7

Evidentemente è necessario un meccanismo di traduzione tra pagine logiche e pagine fisiche che tenga conto di questo fatto; tale struttura dati, creata dal Sistema Operativo in fase di caricamento, è detta T a b e l l a d e l l e P a g i n e (TdP), che ha tanti elementi quante sono le possibili pagine logiche nello spazio virtuale (cioè generabili dal linker), e ciascun elemento della tabella deve riportare il n. della pagina fisica in cui quella pagina virtuale è stata caricata.

Il SO, oltre a mantenere una TdP per ogni processo caricato in memoria, deve poter ricalcolare (rilocare) dinamicamente ogni singolo indirizzo virtuale che viene sottoposto alla CPU in fase di runtime tramite tale Tabella.

00-04k

04-08k

08-12k

12-16k

16-20k

20-24k

24-28k

28-32k

32-36k

36-40k

40-44k

44-48k

48-52k

52-56k

56-60k

60-64k

0

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

0

1

2

3

4

5

6

7

MEMORIA PROGRAMMA (indirizzi virtuali) (indirizzi fisici)

3

11

5

8

14

2

4

0

TdP

Questa traduzione dipende dalla dimensione della pagina e può essere esemplificata come nell’esempio sottostante.

Esempio: Rilocazione indirizzo paginato

Ipotizziamo una memoria e un SO che usa pagine (logiche e fisiche) da 4096 bytes (4kb); ipotizziamo che la terza pagina virtuale (n. 2) sia caricata in memoria fisica nella sesta pagina fisica (n. 5), informazione presente sulla Tabella delle Pagine; consideriamo un indirizzo (virtuale), ad esempio 9051.

Il Sistema potrebbe calcolare l’indirizzo fisico corrispondente in questo

modo:

n. di pagina virtuale: 9051 DIV 4096 = 2

offset all’interno della pagina: 9051 MOD 4096 = 859

Consultando l’elemento di indice 2 della TdP, si ottiene il valore 5

Indirizzo fisico: 5*4096+859 = 21339

In definitiva:

L’indirizzo virtuale 9051 = (P2,O859) corrisponde all'indirizzo fisico

(P5,O859) = 21339

Naturalmente gli offset di pagina coincidono.

Come dall’esempio, un indirizzo virtuale può essere scomposto in due parti, una parte alta composta da tanti bit quanti sono quelle necessari per rappresentare una pagina fisica, e una parte bassa con i rimanenti bit.

La parte alta è detta c o m p o n e n t e d i p a g i n a (P) dell’indirizzo, mentre la parte bassa è detta c o m p o n e n t e

o f f s e t (O, spiazzamento) dell’indirizzo.

Questo metodo è evidentemente basato su rilocazione dinamica dato che l'operazione di traduzione viene effettuata a runtime.

Inoltre questa tecnica elimina completamente il fenomeno della frammentazione dato che le pagine fisiche non necessitano di contiguità e loro stesse sono strutturate in frammentazione.

Rimane però un concetto di frammentazione più sottile; se in un certo istante il SO possiede dieci pagine fisiche libere e il prossimo processo da caricare ne richiede necessariamente undici o più, il processo non verrà caricato e quelle dieci pagine saranno considerate memoria frammentata.

In linea di principio anche in questo caso il nuovo processo potrebbe essere caricato parzialmente, ma come vedremo esso potrà produrre effetti collaterali indesiderabili all’intero sistema operativo (trashing); in alternativa si potrà optare alla paginazione su domanda.

Finora quindi la tecnica della paginazione pura è un sistema di gestione della memoria basato su rilocazione dinamica e allocazione statica.

PAGINAZIONE SU DOMANDA

Per ovviare a questo ulteriore fenomeno di frammentazione, e per concedere al Sistema Operativo di poter caricare quanti processi voglia, la tecnica di p a g i n a z i o n e s u d o m a n d a (demand paging) cerca di utilizzare la paginazione in accordo ad una tecnica paragonabile al caricamento parziale tramite overlay, evitando di coinvolgere direttamente il programmatore (come avviene invece per l'overlay classico); sarà il SO ad occuparsi del caricamento parziale in modo trasparente all'utilizzatore e al programmatore.

Il concetto base quindi risiede nel modo in cui il sistema riesce a capire quando caricare le pagine virtuali che il programma in esecuzione richiede e che evidentemente non sono attualmente presenti nelle pagine fisiche della memoria principale.

Ciò si ottiene facendo in modo che tutte le volte che un indirizzo viene generato dal programma in esecuzione, il sistema - tramite meccanismi hardware di MMU - controlli se è presente in memoria la pagina virtuale a cui quell’indirizzo appartiene; in caso contrario, esso generia automaticamente una speciale interruzione detta di P a g e F a u l t (fallimento di pagina).

Tale interruzione sarà gestita dal Kernel del SO che provvederà ad ricordare la pagina virtuale opportuna, a individuare una pagina fisica da deallocare e a caricare la pagina virtuale richiesta in quella pagina fisica.

E’ evidente che il sistema debba mantenere aggiornata una tabella globale che riassuma lo stato delle pagine di memoria fisica, in modo che in ogni istante sappia sempre individuare una pagina fisica libera o, se il caso, segnalare che nessuna pagina fisica e’ libera. Chiameremo questa tabella, come di consueto, T a b e l l a d e l l a M e m o r i a (TdM).

Inoltre bisogna arricchire la TdP con una nuova informazione per ogni elemento della tabella, che indichi se quella pagina virtuale è caricata o meno in memoria fisica. Tale informazione è di solito rappresentata su un bit detto b i t d i p r e s e n z a i n m e m o r i a . Naturalmente le pagine virtuali non caricate in memoria fisica risiedono generalmente su disco da dove possono essere, in futuro, recuperate.

00-04k

04-08k

08-12k

12-16k

16-20k

20-24k

24-28k

28-32k

32-36k

36-40k

40-44k

44-48k

48-52k

52-56k

56-60k

60-64k

0

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

0

1

2

3

4

5

6

7

MEMORIA (indirizzi fisici)

0

1

2

3

4

5 6

-

1

ˉ 7

ˉ ̄

100 15

ˉ

1

0

1

0

0

1

1

-

0

1

2

3

4

5

-

-

ˉ

6

9

12 ̄

13

ˉ

ˉ

0

1

1

1

0

1

-

-

PROGRAMMA 3 TdP

TdP

3

11

5

8 14

2

4

0

1

1

1 1

1 1 1

1

TdP

PROGRAMMA 2

PROGRAMMA 1

TdM

1

1 1

1

1

1 1

1 1 1 1

1

1

1 1

1

Nel disegno i tre programmi sono caricati in memoria. Il primo, completamente, gli altri parzialmente. Vengono mostrate le tre TdP con l’informazione sul bit di presenza (1= in memoria).

Si nota come questi due ultimi sono programmi più piccoli rispetto al primo, dato che alcune pagine logiche finali sono vuote, così come le rispettive righe della TdP.

Siccome la memoria è completamente occupata, la TdM contiene tutti i bit a 1.

La tecnica di paginazione su domanda così descritta è di allocazione dinamica dato che le pagine sono caricate o revocate durante l'esecuzione del programma.

Questo metodo consente l'esecuzione di processi con un totale di memoria virtuale superiore al totale di memoria fisica disponibile. Il problema della frammentazione è totalmente eliminato. La protezione degli indirizzi virtuali è ottenuta automaticamente: non c'è nessuna possibilità che gli indirizzi di un processo vadano ad interferire con gli indirizzi di un altro processo perchè i due processi possiederanno due diverse TdP che garantiscono la separazione degli spazi virtuali singoli (come nel metodo ad allocazione statica, peraltro).

Nel descrittore (PCB) di ogni processo è necessario riportare l'indirizzo della sua TdP; a questo scopo spesso esiste un registro speciale di CPU detto registro Puntatore Tabella Pagine che in ogni istante contiene l'indirizzo della TdP relativa al processo attualmente in esecuzione; valore in tale registro sarà modificato dal SO ad ogni commutazione di contesto.

La logica della routine associata all'interruzione di Page Fault può essere descritta per sommi capi.

1. L’MMU rileva che il prossimo indirizzo virtuale risiede su una pagina virtuale NON presente in Memoria fisica (il bit di presenza vale 0)

2. Viene generata l’eccezione di Page Fault e si ottiene l’ingresso nel Nucleo;

3. Salvataggio dello stato del processo (esso infatti non può proseguire) e commutazione del processo in stato di BLOCCO;

4. Individuazione della pagina virtuale da caricare (che si trova su disco);

5. Verifica esistenza di una pagina fisica libera (tramite la TdM)

6. Se non esiste nessuna pagina fisica libera si sceglie una pagina fisica da scaricare su memoria di massa (R i m p i a z z a m e n t o d e l l a P a g i n a ); è necessario scaricarla su memoria di massa solo se dal momento in cui era stata caricata il suo contenuto è cambiato, altrimenti la si può eliminare senz’altro.

7. Caricamento della pagina virtuale richiesta nella pagina fisica scelta.

8. Al termine del caricamento il Sistema lancia una eccezione di fine caricamento associata alla routine per l'aggiornamento della TdP.

9. Riallineamento del registo Program Counter - l'istruzione che aveva generato il Page Fault deve essere rieseguita - nel descrittore di processo.

10.Il processo può essere commutato in stato di PRONTO.

A supporto della pagina su domanda i Sistemi Operativi usano il disco e speciali file che contengono le pagine scartate e rimpiazzate dalla memoria, files detti di P a g i n g (o file di S w a p ).

Sui files di paging vengono collocate solo le pagine virtuali modificate dall’esecuzione (es. pagine di dati), mentre le pagine non modificate (es. pagine di codice) vengono sempre prelevate dal file eseguibile, che risulterà bloccato su disco per tutto il runtime.

TIPOLOGIA DELLA TABELLA DELLE PAGINE

Per una corretta gestione del meccanismo di memoria paginata su domanda, il Sistema Operativo deve raggruppare, per ogni pagina logica, una serie di informazioni che, con il bit di presenza, consentono di garantire la protezione della memoria e una più efficace metodologia per l’algoritmo del rimpiazzamento delle pagine. Queste informazioni, sottoforma di bit, vengono memorizzate (e aggiornate) su ogni elemento della TdP di un processo, aumentando la dimensione della tabella.

Tra i bit di servizio più importanti, ricordiamo:

Il b i t d i P r e s e n z a segnala se una pagina logica è caricata in memoria o meno.

I b i t d i P r o t e z i o n e , se gestiti, riguardano i consueti diritti di accesso in lettura, scrittura e esecuzione per quella pagina logica, quindi in genere si tratta di una terna di bit;

Il b i t d ’ U s o viene settato via software a zero quando una pagina virtuale è caricata in memoria fisica; quando il programma accede ad essa, il bit viene messo a 1. Serve all’algoritmo di rimpiazzamento delle pagine per sapere se, da quando è stata caricata, la pagina è stata usata (riferita).

Il b i t d i M o d i f i c a (d i r t y b i t ), azzerato via software in caricamento e settato a 1 via hardware dall’MMU in ogni accesso in modifica, in modo da sapere se la pagina sar{ da riscrivere (aggiornare) su disco in caso di revoca;

Il b i t d i T r a n s i t o viene settato quando l’algoritmo di rimpiazzamento ha deciso che la pagina è da rimpiazzare; durante il rimpiazzamento, cioè durante le operazioni di I/O da disco, un altro processo potrebbe generare un altro Page Fault su quella pagina, e quindi la pagina in transito non dovrà essere soggetta ad un ulteriore rimpiazzamento.

Il b i t d i L o c k invece è settato quando una pagina non deve essere rimpiazzata anche se l’algoritmo può averla scelta in base al suo criterio di rimpiazzamento. Ad esempio se un processo sta aspettando dati da una periferica in una sua pagina fisica tale pagina non dovrà essere rimpiazzata almeno fino a quando il processo di I/O dalla periferica non termina.

00-04k

04-08k

08-12k

12-16k

16-20k

20-24k

24-28k

28-32k

32-36k

36-40k

40-44k

44-48k

48-52k

52-56k

56-60k

60-64k

0

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

MEMORIA (indirizzi fisici)

0

1

2

3

4

5 6

-

0001

----

0111

----

----

1010

1111

----

TdP PROGRAMMA 2

1

0

1

0

0

1

1

-

111

---

111

---

---

001

101

-

1

-

1

-

-

1

0

-

0

-

0

-

-

1

0

-

0

-

0

-

-

0

1

-

1

-

1

-

-

0

0

-

Pag P PRO U M T L

PROGRAMMA 1

PROGRAMMA 3

Esempio: calcolo della dimensione della TdP

Si ipotizzi una macchina che può indirizzare a 16 bit e adotti pagine da 4Kb. I linker del Sistema operativo possono creare eseguibili per un massimo di 15 bit (max eseguibile = 2^15 = 32768 byte).

Si usino tutti i bit di informazione elencati per ogni pagina (presenza, protezione, uso, modifica, transito, lock), ovvero 1+3+1+1+1+1 = 8 bit di informazioni di pagina.

N. di pagine logiche per programma: max eseguibile / pagina = 2^15/4096 =

2^15/2^12 = 2^3 = 8

N. di pagine fisiche del sistema: memoria / pagina = 2^16/4096 =

2^16/2^12 = 2^4 = 16

N. di bit per rappresentare una pagina fisica: 4 (infatti 2^4 = 16)

N. di bit per un elemento della Tdp: N. bit pagina + N. bit info = 4+8 =

12 bit

N. di bit della Tdp: N. pagine logiche * N. bit elemento Tdp = 8*12 = 96

bit

Ampiezza della Tdp in byte: 96/8 = 12 byte

Gli aspetti critici della gestione della memoria tramite paginazione su domanda si possono sintetizzare nei seguenti:

eccessiva occupazione di memoria da parte delle TdP; ogni processo ha una TdP e quindi si ha una notevole occupazione in memoria principale delle strutture dati per la gestione della memoria; si veda l’esempio sul calcolo del numero di entrate per una TdP reale riportato più sopra.

minimizzazione dei tempi del calcolo degli indirizzi; infatti per ogni indirizzo generato è necessario accedere alla TdP per il calcolo dell'indirizzo fisico. I tempi di accesso per ogni indirizzo è praticamente raddoppiato rispetto ad una gestione diretta senza paginazione;

scelta delle pagine da rimpiazzare; infatti se la scelta della pagina non è oculata potrebbe generarsi un circolo vizioso in cui ogni pagina caricata genera un page fault, causando un tipico problema di Trashing.

TABELLE DELLE PAGINE SU PIÙ LIVELLI

Un aspetto molto critico della gestione paginata è la dimensione delle TdP su sistemi che possono indirizzare su molti bit, cioè con address bus molto ampi.

Esempio: calcolo del numero di pagine virtuali e della dimensione della TdP su Intel 386+

Si ipotizzi una macchina che può indirizzare a 32 bit e adotti pagine da 4Kb.

Calcoliamo il numero di pagine virtuali necessarie a questo sistema se si usassero solo 4 bit di servizio per le informazioni di pagina

- Spazio virtuale degli indirizzi di un programma: 2^32 = 4294967296,

locazioni indirizzabili.

- Dimensione della pagina: 4Kb = 4096, in byte.

- N. di pagine per ogni processo: 4294967296 / 4096 = 1048576

Pertanto la TdP per un processo deve contenere 1.048.576 elementi.

Siccome le pagine fisiche su questo sistema sono 2^20 (per un totale di

2^20*4kb = 4Gbyte di memoria), un singolo elemento della TdP dovrà

contenere 20 bit (per rappresentare la pagina fisica) più 4 bit di

servizio, ovvero 24 bit per ogni elemento della TdP, cioè 3 byte.

In totale una TdP diventa ampia 3 Mbyte

Una soluzione interessante e molto efficace per ridurre la dimensione delle TdP consiste nel suddividere la TdP su più livelli, in modo da generare TdP che contengono solo elementi significativi.

In effetti, anche se lo spazio di indirizzamento di un processo può essere molto ampio (es. 32 bit, cioè 4 GigaByte), quasi nessun programma è altrettanto ampio.

Si immagini un programma da 12 Mbyte, quindi già sufficientemente ampio, di cui 4 Mbyte per il codice, 4 Mbyte per i dati e 4 Mbyte per lo stack in un sistema a 32 bit con pagine da 12 bit (4Kb). Le

pagine virtuali effettivamente utilizzate dal pgm sarebbero 12*1048576/4096 = 3072 contro le 1048576 per i 4 Gbyte teorici.

INDIRIZZO VIRTUALE: 4231339

1 TdP 1° livello

(elemento=32 bit)

0 1

1023

0000000001 0000001001 000010101011

0

1023

0

1023

0

1023

1024 TdP 2° livello

(elemento=20 bit)

PG 1 PG 2 Offset 10 bit 10 bit 12 bit

1 9 171

9

Per ottenere questo obiettivo è sufficiente suddividere un indirizzo virtuale in tre parti (PG1, PG2 e Offset) invece delle solite due (PG e Offset), scomponendo la parte pagina (PG) in due parti (PG1 e PG2). Nel nostro esempio, considerando quindi PG composto da 20 bit, PG1 coincide con i 10 bit MSB di PG e PG2 con i 10 bit LSB di PG. I rimanenti 12 bit sono la consueta parte Offset dell’indirizzo.

Ora il Sistema Operativo può costruire una Tabella TdP (di 1° livello) di soli 2^10=1024 elementi, tabella che il Sistema Operativo sa raggiungere autonomamente (vedi nel disegno).

All’interno di questa tabella si seleziona un elemento in base al valore di PG1. L’elemento individuato contiene l’indirizzo completo (su 32 bit) di una delle 1024 TdP (di 2° livello, vedi nel disegno).

(Attenzione: siccome solo tre elementi della TdP del 1° livello hanno un contenuto valido, in memoria ci saranno solo 3 TdP di 2° livello)

Ora si accede alla TdP di 2° livello con il valore PG2, individuando un elemento da 20 bit, che è l’effettivo valore della pagina fisica cercata.

Infine, con il n. di pagina fisica e l’offset (nell’indirizzo virtuale), si può rilocare l’indirizzo virtuale in indirizzo fisico (vedi nel disegno).

Si noti come i 1024 elementi della TdP di 1° livello ‘scompongano’ lo spazio virtuale totale del programma in blocchi da 4Mbyte (1024*4Mbyte=4Gbyte): i tre elementi significativi per il nostro programma sono appunto quello che si ‘occupa’ dei 4 Mbyte di Codice, quello che si occupa dei 4Mbyte di Dati ed infine quello che si occupa dei 4 Mbyte di Stack, per il totale di 12 Mb ipotizzati.

I rimanenti 1021 elementi della TdP di 1° livello, seppur fisicamente presenti, contengono una informazione che indicherà al SO un indirizzo non valido per questo programma.

Allora, delle 1024 tabelle dell TdP di 2° livello, solo 3 sono realmente create dal SO per questo programma.

In definitiva questo metodo, applicato all’esempio citato, genera un TdP su due livelli che occupa:

TdP 1°livello: 1024*32bit / 8 = 4096 byte

TdP 2° livello (codice): 1024*20bit / 8 = 2560 byte

TdP 2° livello (dati): 1024*20bit / 8 = 2560 byte

TdP 2° livello (stack): 1024*20bit / 8 = 2560 byte

Totale: 4096 + 2560 + 2560 + 2560 = 14336 byte

Rispetto ad una organizzazione su un solo livello, il risparmio è sull’ordine di alcuni Mbyte, cioè notevolissimo.

TLB, WS, PREPAGING, TRASHING E COPY ON WRITE

Per ottimizzare la gestione delle pagine, riparmiare sulle pagine fisiche allocate e velocizzare il loro accesso si possono usare varie tecniche anche combinate tra loro.

Per recuperare velocemente i valori nelle TdP e velocizzare il loro accesso, l’MMU fornisce registri specifici che mantengono i valori degli ultimi accessi alle TdP in una memoria associativa detta T r a n s l a t i o n L o o k a s i d e B u f f e r (TLB). Ad ogni nuova richiesta di indirizzo fisico la MMU consulta i registri cache, risolvendo velocemente il problema della traduzione in caso di successo. Per la proprietà di località spazio-temporale dei programmi (cioè la circostanza per cui i prossimi indirizzi generati dalle istruzioni di un programma sono gli stessi generati poco tempo prima, come ad esempio nei cicli) ciò succede abbastanza frequentemente, ma se la ricerca non avesse successo, si deve per forza ricorrere alla TdP in memoria principale.

Per cercare di evitare il più possibile il fault di pagina si possono usare algoritmi che cercano di mantenere in memoria le pagine virtuali più utilizzate da un determinato processo. L’insieme delle pagine più utilizzate da un processo è detto W o r k i n g S e t e speciali algoritmi consentono di calcolarlo, in modo euristico, a run time, evitando di scaricare le pagine appartenenti al Working set che causerebbero fault di pagina.

Analogamente alla tecnica precedente, si può implementare una tecnica che precarica in anticipo le pagine virtuali di un processo, ritenute accessibili più frequentemente. Speciali algoritmi consentono di individuare le pagine che il processo dovrà comunque caricare tramite fault di pagina. Questi metodi sono detti di P r e p a g i n g , e consentono di prevedere quali pagine causeranno il fault, precaricandole all’avvio del processo.

Sia il modo del working set che il modo del prepaging tendono a evitare il fenomeno del T r a s h i n g , ovvero l’eccessiva quantit{ di fault di pagina causati da rimpiazzamenti non oculati (pagine scartate ma molto spesso riferite o insieme minimo di pagine caricate insufficiente per un processo). Il trashing

si rende evidente quando le operazioni sul file di swap sono numerose e l’esecuzione dei processi risulta rallentata.

Infine, per risparmiare il numero di pagine fisiche occupate, qualora una pagina fisica fosse in comune per più processi (es. codice di Sistema operativo) è possibile caricarne in memoria fisica una sola per tutti i processi che la richiedono, evitando copie della stessa pagina in memoria. Se la pagina comune dovesse essere modificata, solo in questo momento il gestore delle pagine ne crea una copia privata per il processo che ne ha cambiato il contenuto, tramite un fault di pagina ad hoc. Questa tecnica è detta C o p y o n w r i t e .

ALGORITMI DI RIMPIAZZAMENTO DELLE PAGINE

Come già osservato, la scelta della pagina fisica da rimpiazzare con una nuova pagina virtuale da prelevare su disco rappresenta uno dei momenti fondamentali per evitare il problema di trashing e quindi per ottenere una velocità e una prestazione maggiore per l’intero sistema.

Abbiamo anche già osservato che il criterio di scelta può operare in ambito locale o globale rispetto ai processi e ciò non dipender{ dall’algoritmo scelto per l’individuazione.

E’ evidente che ogni algoritmo dovr{ poter disporre di informazioni tali che gli consentano di effettuare una scelta tra le pagine descritte in nella TdP; alcune di queste informazioni le abbiamo riportate nello schema in cui è stato rappresentato un generico elemento della TdP; in alcuni casi certi algoritmi necessitano di informazioni ulteriori che dovremo sempre immaginare essere riportate sulla TdP.

Un’altra considerazione generale riguarda l’overhead generato dall’algoritmo: la necessit{ di un algoritmo sofisticato per ridurre il trashing potrebbe generare un notevole overhead e in definitiva il SO potrebbe addirittura risentirne.

E’ utile rappresentare il problema della scelta della pagina da rimpiazzare pensando a ciò che il SO dovrebbe fare in linea di principio:

in presenza di un pagefault il SO dovrebbe individuare quella pagina in memoria fisica che sarà meno utilizzata in futuro e rimpiazzarla. Evidentemente un algoritmo del genere non è implementabile dato che il SO non ha poteri paranormali.

Gli algoritmi che si analizzeranno dovranno però tendere a questo tipo di approccio.

ALGORITMO NRU (NON USATE DI RECENTE)

Tale algoritmo (N o t R e c e n t l y U s e d ) necessita delle informazioni R e M, organizzate a bit all’interno dell TdP, e dal seguente significato:

R: settato se quella pagina è stata riferita da un fault di pagina;

M: settato se la pagina è stata modificata in memoria.

Il SO resetterà il bit R periodicamente - ad esempio ogni n intervalli di clock - in modo che la presenza del settaggio in R rappresenti un certo tempo. Analogamente il bit M sarà resettato quando la pagina sarà scaricata e scritta su disco.

Le operazioni di set e reset in genere sono previste tramite ausilio hardware (set). Se ciò non è possibile si può gestire l’intero sistema via sw.

Ad ogni fault di pagina il SO analizza le pagine in memoria fisica e le classifica in quattro categorie in base allo stato dei bit R e M:

0 - pagina non usata non modificata

1 - pagina non usata ma modificata

2 - pagina usata ma non modificata

3 - pagina usata e modificata

L’algoritmo quindi sceglie una pagina a caso dalla classe non vuota di numero più basso.

Questo algoritmo possiede poco overhead data la semplicit{ dell’implementazione.

ALGORITMO FIFO (PRIMO ARRIVATO, PRIMO AD USCIRE)

In questo caso (F i r s t I n , F i r s t O u t ) la pagina da rimpiazzare è la prima che è arrivata in memoria e quindi quella che da più tempo è in memoria.E’ sufficiente che il SO mantenga una lista supplementare di tutte le pagine attualmente in memoria, dove la pagina in testa alla lista è la più vecchia (da rimpiazzare) e quella in coda è la più giovane (l’ultima ad essere prelevata da disco dopo un pagefault).

Purtroppo anche se l’overhead è molto basso, il criterio non è efficiente perchè spesso la pagina che da più tempo è in memoria coincide con una pagina molto utilizzata dal processo che la possiede.

Una variante dell’algoritmo FIFO consiste nell’utilizzare l’informazione del bit R (riferita) accanto alla gestione della lista delle pagine; se la pagina in testa alla lista contiene il bit R settato allora essa non viene rimpiazzata ma posta in fondo alla lista dopo avergli resettato il bit R a zero.

In questo caso l’algoritmo FIFO diventa apprezzabilmente più efficace e viene detto della S e c o n d a

o p p o r t u n i t à .

ALGORITMO "DELL'OROLOGIO"

Una variante significativa dell’algoritmo della Seconda opportunit{ è l’a l g o r i t m o d e l l ’ O r o l o g i o il quale elimina lo spostamento forzato di una pagina destinata al rimpiazzamento (ma non soggetta perchè avente il bit R settato a uno) in fondo alla lista.

La lista stessa viene gestita in modo circolare e quindi un puntatore sempre indicante la pagina che da più tempo è in memoria, quando succede un pagefault si limita a controllare il bit R della pagina puntata; se esso è a zero la rimpiazza e la nuova pagina si ritroverà il bit R a zero, mentre se il bit era a uno, si limiterà a resettarlo a zero e a controllare la prossima pagina in lista.

In questo modo si trova sempre sicuramente una pagina vittima; non si individua la pagina che da più tempo è in memoria e non è utilizzata, ma la prima delle non utilizzate da molto tempo.

ALGORITMO LRU (USATA MENO DI RECENTE)

L’osservazione che le pagine che sono state frequentemente usate nelle ultime istruzioni lo saranno probabilmente anche durante le prossime future istruzioni, mentre le pagine che non sono state usate da tempo non saranno usate ancora per molto tempo sta alla base dell’algoritmo LRU (L e a s t R e c e n t l y

U s e d ).

L’implementazione in questo caso diventa pesante perchè si tratta di gestire una lista simile a quella dell’algoritmo FIFO che però deve essere continuamente aggiornata con cancellazioni e reinserimenti in modo da tenere in testa la pagina usata più recentemente e in coda la prossima vittima del rimpiazzamento.

L’implementazione dell’algoritmo LRU puro necessiterebbe di un supporto pesante di MMU e in molti casi non viene addirittura utilizzata; in ogni caso esistono alcuni algoritmi che tendono ad una gestione

LRU con qualche semplificazione che ne rende possibile l’implementazione, come l’algoritmo dell’Invecchiamento.

SEGMENTAZIONE

Quando in memoria si hanno due o più processi provenienti dallo stesso programma, caso estremamente consueto, è auspicabile che in memoria esista una sola copia del codice, che risulterà essere pertanto condiviso.

Nel disegno si notano due processi (hanno le stesse pagine di codice) che hanno il codice condiviso in memoria e le parti private (dati e stack) separate.

00-04k

04-08k

08-12k

12-16k

16-20k

20-24k

24-28k

28-32k

32-36k

36-40k

40-44k

44-48k

48-52k

52-56k

56-60k

60-64k

0

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

MEMORIA (indirizzi fisici)

0

1

2

3

4

5

6

-

PROGRAMMA

(processo 2) 4

5

6

13

11

2

14

-

TdP

0

1

2

3

4

5

-

-

PROGRAMMA

(processo 1)

4

5

6

8

9

1

-

-

TdP

}

}

Pagine di CODICE

Pagine di DATI

Pagine di STACK

Pagine di CODICE

Pagine di DATI

Pagine di STACK

Gran parte della protezione degli spazi virtuali è garantita automaticamente dalla struttura paginata ovvero gli indirizzi virtuali privati dei due processi sono completamente autonomi (andranno su pagine fisiche differenti).

Ma la contiguità – stavolta dello spazio virtuale, ingenera alcuni problemi sia sulla protezione che sulla condivisione del codice eseguibile.

Le diverse aree funzionali di un programma (codice, dati e stack) non possono essere completamente partizionate alla dimensione della pagina. Es., ognuna di queste tre aree, nella pagina finale, contiene elementi misti, ovvero in memoria fisica potrebbero presentarsi pagine contenenti codice e dati, o dati e stack o tutte le tre categorie di aree contemporaneamente.

In questi casi sia la condivisione del codice che si è auspicata, sia la protezione della memoria, divengono estremamente difficoltose.

Tutte queste considerazioni conducono alla conclusione di evitare la costruzione di indirizzi virtuali di programma contigui.

La tecnica della s e g m e n t a z i o n e prevede di scomporre anche gli indirizzi virtuali in uno spazio non contiguo, così come la tecnica della paginazione scomponeva lo spazio fisico degli indirizzi in aree non contigue.

Si tratta della strutturazione della memoria così come naturalmente il programmatore è portato a pensarla, cioè organizzando i programmi in moduli differenti, raggruppati in zone logiche indipendenti e separate, ognuna con un differenti scopi logico-strutturale.

All’interno di ognuno di questo sottospazi la memoria virtuale è naturalmente contigua. Queste zone virtuali sono dette s e g m e n t i .

In genere si considerano il segmento riservato al codice (s e g m e n t o d i t e s t o ), il segmento riservato ai dati (s e g m e n t o d a t a ), il segmento riservato allo stack (s e g m e n t o d i s t a c k ).

Colui che genera lo spazio di indirizzi virtuali, cioè il linker, ha più facilità nella creazione di tali sottospazi virtuali perché essi corrispondono alla struttura logica di ogni programma.

Anche il processo di compilazione viene facilitato e ottimizzato, in quanto in uno spazio lineare completamente contiguo la modifica anche di un solo indirizzo nel sorgente - es. introduzione di una nuova variabile - obbliga il compilatore a modificare tutti gli indirizzi a partire dalla zona in cui allocherà il nuovo indirizzo, mentre la stessa operazione in un modello di memoria segmentata consente la modifica di indirizzi in alpiù un segmento e non in tutto il programma.

Ogni segmento quindi è un sottospazio virtuale indipendente con indirizzi compresi tra 0 e un massimo; ogni segmento è separato dagli altri, nel senso che aggiungendo una unit{ all’ultimo indirizzo disponibile di un segmento NON si ottiene il primo indirizzo del segmento successivo; ogni segmento può avere una propria lunghezza e in alcuni casi modificabile runtime; all’interno di ogni segmento lo spazio degli indirizzi è lineare.

Ciò conduce a considerare gli indirizzi virtuali come composti da due elementi, una parte s e g m e n t o e una parte s p i a z z a m e n t o (offset).

Con lo spazio virtuale segmentato si ottiene automaticamente anche quella separazione logica che consente la massima protezione e la massima condivisibilità per i programmi in memoria.

L’allocazione di memoria è simile a quella vista per il metodo delle partizioni, ma considerando che in questo caso le partizioni-segmenti rilocabili sono più di una per ogni processo.

Per la gestione della memoria segmentata, il Sistema Operativo usa una struttura dati detta T a b e l l a d e i

S e g m e n t i (TdS), del tutto analoga alla Tabella delle partizioni, anche se più articolata. Ogni elemento della TdS è detto D e s c r i t t o r e d i S e g m e n t o (DdS), e contiene le informazioni necessarie alla riloazione del segmento (più DdS consentono la rilocazione dell’intero programma).

Nel DdS diventa molto efficace l’informazione sulla protezione del segmento, dato che ogni segmento contiene una porzione logica del programma: es., i segmenti di codice potranno essere protetti in scrittura, ottenendo una protezione esemplare.

Con il metodo della memoria segmentata l’allocazione è spesso dinamica, dato che i segmenti possono essere caricati e scaricati più volte dalla memoria per far posto ad altri segmenti. In questo caso, analogamente alla memoria paginata, si avranno eventi di Segment Fault. In questo caso il sistema segmentato subisce anche una rilocazione dinamica.

SEGMENTAZIONE PAGINATA

Come appare naturale il metodo preferibile per la gestione della memoria sarà quello che gestisce la non contiguità dello spazio fisico (paginazione) e la non contiguità dello spazio logico (segmentazione), cioè un metodo di gestione della memoria con s e g m e n t a z i o n e p a g i n a t a .

I sistemi di allocazione e gestione della memoria più efficaci sono quindi quelli che utilizzano uno spazio virtuale segmentato e una allocazione di memoria fisica dei segmenti paginata, suddividendo cioè i segmenti autonomi e all’interno lineari in pagine fisiche non lineari allocate dinamicamente in memoria.

Evidentemente questi sistemi possiedono una gestione più complessa che in genere è coadiuvata da elementi hardware di MMU: tutti i sistemi hw moderni usano il sistema di gestione della memoria con segmentazione paginata.

In pratica ogni segmento di un programma viene allocato in memoria per pagine.

Per la rilocazione, un indirizzo virtuale in questo caso dovrà essere scomposto in tre parti: una indicante il numero di segmento, una indicante il numero di pagina virtuale nel segmento e una che conterr{ l’offset di pagina.

Per ogni processo il Sistema Operativo (e MMU) prevede quindi una Tabella di segmenti e, per ogni segmento, una Tabella delle Pagine. All’interno della TdS il campo indirizzo conterr{ la locazione in memoria della TdP di quel segmento.

Il sistema inoltre dovrà prevedere due tipi di Fault: Segment Fault e Page Fault (senza contare un terzo fault eventuale se le TdP sono gestite a più livelli).

00-04k

04-08k

08-12k

12-16k

16-20k

20-24k

24-28k

28-32k

32-36k

36-40k

40-44k

44-48k

48-52k

52-56k

56-60k

60-64k

0

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

MEMORIA (indirizzi fisici)

0

1

2

0

1

0

-

-

PROGRAMMA

Segmento di CODICE (0)

Segmento di DATI (1)

Segmento di STACK (2)

0000

0001

0010

TdS

1

0

1

111

---

001

0000000000000000

-

0010000000000000

Seg P PRO indirizzo TdP

TdM

1

0 1

0

0

0 1

0 0 1 0

0

0

1 0

0

ˉ

6

9

0

1

1

TdP

13

1

TdP

Esempio: Rilocazione nel modello di Segmentazione Paginata

Dato l’indirizzo virtuale segmento-paginato (S2, P0, O849) generato dal processo P, individuare l’indirizzo fisico associato.

- Dalla TdS del processo si entra al n. di segmento S=0 e si trova

l’indirizzo della TdP per il segmento 0 del processo. Nel disegno:

0010000000000000b = 8192, cioè l’inizio della pagina fisica 2.

- All’interno della Tdp del segmento, si cerca l’elemento P=0, cioè 13,

la pagina fisica.

- A questo punto possiamo individuare l’indirizzo fisico, la 849ma

locazione all’interno della pagina fisica 13, cioè l’indirizzo paginato

(P13,O849): 13*4096 + 849 = 54097

Si noti che nella pagina fisica 0 c’e’ la TdP del primo segmento

(segmento di Codice);

Nella pagina fisica 2 c’e’ la TdP del terzo segmento (segmento di Stack);

Il segmento Dati non è allocato in memoria (causerà un Segment fault)

La prima pagina logica del segmento di Codice non è in memoria (causerà

un Page fault)

RILOCAZIONE IN IA-32

Dato un indirizzo virtuale generato dal linker nel formato segmentato (S,A), avendo a disposizione le tabelle GDT, LDT, PD e le varie TP create dal Sistema Operativo al caricamento e aggiornate a runtime, localizzabili con i registri GDTR, LDTR, CR3, mantenuti aggiornati dal Sistema Operativo ad ogni cambio di contesto per il processo corrente, la rilocazione avviene secondo queste fasi:

1. Dal valore S dell’indirizzo si deduce se l’indirizzo appartiene all’area Local o Global. Un bit nel valore di S, impostato dal linker, indica questa informazione. In ogni caso, da qui in avanti, la rilocazione è del tutto analoga per entrambi i casi (usando LDTR o GDTR a seconda).

2. Si raggiunge la Tabella dei Segmenti del processo (LDT o GDT) tramite 32 bit di LDTR (o di GDTR).

3. Dentro la Tabella dei Segmenti si individua l’elemento appropriato, contenuto nel valore S dell’indirizzo virtuale. In S, tredici bit contengono il numero del segmento. Si individua percio’ il descrittore di segmento per il segmento dell’indirizzo virtuale.

4. Nel descrittore di segmento, 32 bit rappresentano l’indirizzo base del segmento. Prelevati, essi vanno sommati con la parte A dell’indirizzo virtuale dato. Questa somma è l’indirizzo lineare (virtuale) effettivo. Ora bisogna rilocare l’indirizzo lineare effettivo tramite un meccanismo paginato a due livelli. Nell’indirizzo lineare effettivo si scompongono le tre parti PG1 (12 bit), PG2 (12 bit) e OFFSET (8 bit).

5. Con 20 bit di CR3 si individua la PD del processo. 6. Nella PD si localizza l’elemento indicato da PG1 7. Con l’elemento in PG1, 20 bit di indirizzo pagina-base, si trova la posizione in memoria della

Tabella delle Pagine di secondo livello

8. Sulla Tabella delle Pagine di secondo livello si entra individuando l’elemento con PG2, e prelevando da esso 20 bit, il n. di pagina fisica.

9. Ora si puo’ rilocare, trovando l’indirizzo fisico corrispondente: il n. di pagina fisica viene moltiplicato per l’ampiezza di pagina (4kb) e sommato con l’OFFSET dell’indirizzo lineare effettivo (vedi punto 5.)

LDT

INDIRIZZO VIRTUALE SEGMENTATO (S,A)

S A 16 bit 32 bit

LDTR/GDTR

+ PG1 PG2 OFFSET 10 bit 10 bit 12 bit

CR3 PD

PT

pg*4Kb+OFFSET

INDIRIZZO VIRTUALE EFFETTIVO

32 bit

INDIRIZZO FISICO

NB. I Sistemi Operativi a 32 bit di classe Linux e Windows è come se non supportassero la segmentazione paginata, dato che i linker generano sempre un solo segmento comune e sovrapposto per codice, dati e stack. Pertanto questi sistemi operativi usano solo la paginazione (sull’unico segmento).

Questa limitazione è stata introdotta per poter avere programmi con spazi di indirizzamento completamente lineari (flat addressing) su ogni componente del programma.

I formati dell’indirizzo virtuale segmentato, dei registri coinvolti e delle tabelle create dal Sistema Operativo sono i seguenti.

S E L E T T O R E – P a r t e S e g m e n t o d e l l ’ i n d i r i z z o v i r t u a l e s e g m e n t a t o

Parte S di un indirizzo virtuale segmentato, generato dal linker assieme all’Offset di segmento (parte A dell’indirizzo).

Dimensione: 16 bit.

Descrizione

15 3 2 1 0

└─────────────┘ │ └─┘ privilegio segmento

segmento(13bit) │

└ 0=GDT, 1=LDT

C R 3 – R e g i s t r o d i c o n t r o l l o

Registro del microprocessore che contiene l’indirizzo pagina-base della PD del processo corrente, cioè della TdP di 1°

livello. Impostato dal Sistema Operativo sul cambio di contesto.

Dimensione: 32 bit.

Descrizione

31 12 11 0

└─────────────────────────┘ └─────────┘

indirizzo PD (20bit) servizio

L D T R – R e g i s t r o M M U

Registro MMU del microprocessore che contiene l’indirizzo lineare della LDT del processo corrente, cioè della TdS

locale. Impostato dal Sistema Operativo sul cambio di contesto.

Dimensione: 48 bit (in realtà è più grande, almeno 64bit, ma non trovo documentazione).

Descrizione

47 16 15 0

└─────────────────────|───────────────┘ └─────────────┘

indirizzo LDT (20bit) dimensione LDT

G D T R – R e g i s t r o M M U

Registro MMU del microprocessore che contiene l’indirizzo lineare della GDT del sistema, cioè della TdS globale.

Impostato dal Sistema Operativo all’avvio.

Dimensione: 48 bit.

Descrizione

47 16 15 0

└─────────────────────|───────────────┘ └─────────────┘

indirizzo GDT (20bit) dimensione GDT

D E S C R I T T O R E – E l e m e n t o d e l l a L D T o G D T

Elemento generico della tabella LDT (o GDT). Ogni processo ha una LDT e il Sistema Operativo la raggiunge in

memoria tramite il registro LDTR. Esiste invece una unica GDT, raggiunta tramite il registro GDTR

Dimensione: 64 bit.

Descrizione

63 32 31 12 11 0

└─────────────────────────┘ └─────────────────┘ └─────────┘

indirizzo (32bit) dim. Segmento servizio

P A G E D I R E C T O R Y – P D , e l e m e n t o d e l l a T d P d i 1 ° l i v e l l o

Elemento generico della tabella PD. Ogni processo ha una PD, raggiunta in memoria tramite il registro CR3.

Dimensione: 32 bit.

Descrizione

31 12 11 0

└─────────────────────────┘ └─────────┘

indirizzo TdP 2°liv.(20bit) servizio

P A G E T A B L E – P T , e l e m e n t o d e l l a T d P d i 2 ° l i v e l l o

Elemento generico della tabella PT. Ogni processo può avere molte TP a seconda della sua dimensione o numero di

segmenti.

Dimensione: 32 bit.

Descrizione

31 12 11 0

└─────────────────────────┘ └─────────┘

N. pag. fisica (20bit) servizio

Esempio: rilocazione di un indirizzo segmentato in IA-32

Dato l’indirizzo segmentato (S,A)=(18,C0301E)h in IA-32 e le condizioni seguenti sui registri MMU e stato della memoria, rilocarlo in indirizzo fisico.

Sia la memoria come di seguito (su ogni riga una pagina da 4kb,

incompleta)

0 00 00 00 00 00 00 0E 00 - 00 00 09 00 03 D9 00 06 - 00 00 00 00 00 00 00 03 - 00 00 E9 00 00 09 00 00 - 00 00 00 00 00 00 00

00 - ...

1 AD 00 00 00 00 00 00 00 - 00 00 00 20 00 00 00 00 - 20 00 90 00 03 0D 00 00 - 00 00 00 00 00 03 00 00 - 00 00 00 00 00 00 00

00 - ...

2 00 03 66 B7 00 0C 07 00 - B0 00 00 10 00 00 00 0E - E8 C0 03 00 10 BB 00 00 - 08 11 70 0B 0E 86 00 99 - 00 00 00 E2 09 B8 00

00 - ...

3 02 0D 09 00 FB 00 20 00 - 0D 00 02 00 00 26 00 00 - 00 00 09 20 03 D9 00 06 - 00 00 73 0F 00 00 00 00 - 00 00 00 00 00 00 00

00 - ...

4 51 03 00 00 - 00 03 00 CC 0E 00 0E D0 - 00 00 00 C0 10 00 00 0D - 00 10 10 00 00 00 0D 00 - 77 00 00 00 00 0D 00 00

- ...

5 00 00 00 00 00 00 04 00 - 00 00 00 10 00 00 00 00 - 00 00 90 00 00 00 00 00 - 0E 00 00 00 00 00 00 00 - 00 00 00 C0 00 00 00

00 - ...

6 20 00 00 00 00 C9 00 00 - 00 FF FF 00 00 00 20 00 - 00 00 00 00 00 00 00 00 - 00 0E 00 00 22 0A C9 00 - 00 00 00 20 00 00 00

00 - ...

7 00 00 00 00 00 00 00 00 - 00 00 00 00 00 00 00 00 - 00 00 00 A3 00 09 00 00 - 00 00 00 03 0E 00 B0 00 - 00 00 0B 00 00 B0 00

00 - ...

8 00 00 00 23 00 04 99 00 - 00 00 00 00 00 00 00 00 - 00 00 00 00 00 00 00 00 - 00 00 00 00 00 00 00 00 - 00 00 00 03 ED 00 00

00 - ...

9 00 00 D4 00 F4 00 00 00 - 00 01 0A CD 00 01 0A CD - 00 00 04 00 10 09 00 00 - 00 F4 00 00 00 06 00 00 - 00 00 00 00 00 00 00

00 - ...

10 1D 00 00 00 00 00 00 00 - 00 00 00 00 00 00 00 00 - 00 00 90 00 03 0D 00 00 - 00 00 00 00 00 03 00 00 - 00 00 00 00 00 00 00

00 - ...

11 00 00 00 00 00 C0 00 00 - 00 07 00 00 00 00 00 D0 - 00 0C 00 00 00 00 00 00 - 00 00 00 00 00 00 04 00 - 00 00 00 00 00 00 00

00 - ...

12 01 00 0E 00 03 0F 60 00 - 82 F0 00 F3 00 10 00 6F - 0A 00 01 20 00 00 0F 00 - 0A 0F 00 00 00 0A 00 00 - 00 00 0C C0 00 00 00

00 - ..

13 00 00 00 00 0A 00 00 00 - 00 00 00 00 00 00 0E 00 - 00 00 E9 00 00 09 00 00 - 0E 00 00 00 00 00 00 F0 - 00 00 D0 00 0D 00 00

00 - ...

14 00 03 66 B7 00 0C 07 00 - B0 00 00 10 00 00 00 0E - E8 C0 03 00 10 BB 00 00 - 08 11 70 0B 0E 86 00 99 - 00 00 00 E2 09 B8 00

00 - ...

15 C2 00 06 20 A8 00 00 00 - 00 00 00 00 00 00 00 00 - 00 00 00 00 00 00 D3 00 - 00 0D 00 00 DD 83 70 00 - 00 00 00 00 00 00 00

00 - ...

16 0D 3D 09 00 08 00 04 00 - 00 00 00 00 00 A7 00 F6 - 00 00 00 00 04 00 F0 A6 - 00 00 00 00 00 00 00 0F - 00 00 04 00 00 92 00

00 - ...

Siano i registri MMU come di seguito:

LDTR: 00005000 (Pagina 5)

GDTR: 00007000 (Pagina 7)

CRW3: 00009000 (Pagina 9)

Dall’indirizzo (0018,00C0301E)h, si ricavano: (0028,00F0301E)

0 0 1 8

0000 0000 0001 1000

gdt, descrittore 3 Pagina 7, elemento 3 -> 00 00 00 03 +

00 C0 30 1E =

-------------

00 C0 30 21

Indirizzo lineare effettivo:

0 0 C 0 3 0 2 1

0000 0000 1100 0000 0011 0000 0010 0001

3 3

Nella PD a pagina 9, si trova l’elemento 3 -> 00 01 0, cioè pagina 16

Nella PT a pagina 16, si trova l’elemento 3 -> 00 A7 0, cioe' pagina fisica

(2672)d

Infine l’indirizzo fisico: pf*4096+21h = 2672*4096+33 = 10944545 = A70021h