Sistemi operativi - Teoria

SEGMENTAZIONE CON PAGINAZIONE IN MULTICS

Si parte sempre da un indirizzo logico segmentato formato da (s, d). S è il riferimento al segmento e d è l'offset rispetto al segmento. S passa per STBR, e si accede alla tabella dei segmenti, in cui troviamo una coppia di valori: la dimensione del segmento e l'indirizzo di partenza della tabella delle pagine che contengono le informazioni di quel segmento.

Adesso si prendono strade diverse, ovvero:

• La lunghezza del segmento: viene confrontato con d, ovvero d non deve essere più grande della lunghezza del segmento. Se risulta essere più grande, ci sarà una trap (un'eccezione); invece, se la disuguaglianza viene rispettata, allora si va avanti.
• L'offset d viene considerato come formato da 2 elementi (p, d'). Questa operazione è molto semplice se l'organizzazione degli indirizzi deve essere costruita in maniera sofisticata apposta per questa parte dello svolgimento, dove d' è lo...

spiazzamento del dato rispetto alla pagina, che infatti va sommato all'indirizzo del frame che è venuto fuori dalla tabella delle pagine;

L'indirizzo base della tabella di pagine: va direttamente nella tabella delle pagine sommato a p (che è stato splittato dal primo offset) e si raggiunge l'indirizzo del frame (f) che sommato a d ci da il dato.

ESEMPIO INTEL PENTIUM:

Il Pentium supporta sia segmentazione pura (con segmenti grandi fino a 4 GB), sia segmentazione con paginazione (le pagine sono di 4KB o di 4 MB).

La CPU genera indirizzi logici:

• Passati all'unità di segmentazione che produce indirizzi lineari;
• Gli indirizzi lineari sono forniti all'unità di paginazione, la quale genera indirizzi fisici in memoria centrale;

Le unità di segmentazione e paginazione formano l'equivalente della MMU.

TRADUZIONE DEGLI INDIRIZZI LOGICI IN INDIRIZZI FISICI NELL'INTEL PENTIUM:

Ci sono 2 partizioni per lo spazio degli indirizzi

di un processo (max 16K segmenti – 8K per partizione): la partizione dei segmenti privati e la partizione dei segmenti condivisi. I segmenti privati contengono dati e istruzioni del processo che non condivide con altri processi, se invece ci sono dati, istruzioni o file condivisi con altri processi, stanno nella partizione dei segmenti condivisi. Due tabelle dei descrittori – una partizione. Tabella locale e tabella globale.

L’indirizzo logico nell’Intel Pentium è fatto da un Selettore a 16 bit e da un Offset a 32 bit. Il Selettore è a sua volta diviso in:

• S: numero del segmento;
• G: partizione;
• P: protezione;

L’indirizzo lineare (32 bit) costruito con il valore dell’offset + base del segmento:

L’indirizzo lineare è un indirizzo di paginazione, costituito da una paginazione a 2 livelli e l’offset, che è un offset di pagina. Quindi si parte dall’indirizzo logico (48 bit), da cui si prende il selettore e si porta nella

Descrittore	Indirizzo lineare formato da 32 bit
Primi 10 bit	Indirizzo della tabella delle pagine esterna (p1)
1 bit	Indirizzo della tabella delle pagine interna (p2)
Restanti 12 bit	Offset di pagina interna chiamato scostamento (d)

La paginazione all'interno dell'architettura del Pentium avviene nel seguente modo:

Si prende p1, ora possono accadere 2 cose, si possono avere dei riferimenti a directory di 4Kb o di 4Mb. Se fa riferimento a pagine di 4Mb, il riferimento è diretto, ovvero il valore trovato attraverso l'indirizzo nella directory delle pagine è il valore del frame. Se invece fa riferimento a una pagina di 4Kb allora il riferimento non è per la directory delle pagine ma per la tabella delle pagine.

interne.Quindi tramite p1 trovo l’indirizzo della tabella delle pagine,ci aggiungo p2 e trovo il frame, ci aggiungo lo scostamento(d) e trovo il dato.

MEMORIA VIRTUALE:Per completare la parte sulla gestione della memoriacentrale.La memoria virtuale è una tecnica per gestire in manierapiù flessibile la RAM di un computer basata sia susegmentazione e paginazione. L’argomento è cosìsuddiviso:

• Introduzione;
• Paginazione su richiesta;
• Copiatura su scrittura;
• Sostituzione delle pagine;
• Allocazione di frame;
• Paginazione degenere (Thrashing);
• File mappati in memoria;
• Allocazione di memoria nel kernel;
• Ulteriori considerazioni;
• Esempi di sistemi operativi;

INTRODUZIONE:La memoria virtuale è una tecnica di gestione dellamemoria centrale che realizza la separazione dellamemoria logica dalla memoria fisica. Ovveroindipendentemente dalla memoria che si ha a disposizionein hardware, i programmi hanno una visione unicamentefisica della

memoria.(Anche se noi avessimo a disposizione 1 gb di memoria fisica, potremmo comunque eseguire programmi da 10 gb)
Solo una parte del programma è caricato in memoria per l'esecuzione. Lo spazio degli indirizzi logici è quindi più grande dello spazio degli indirizzi fisici. Lo spazio degli indirizzi può essere diviso meglio tra più processi. Permette una più efficiente creazione dei processi.
La memoria virtuale può essere implementata tramite:
- Paginazione su richiesta;
- Segmentazione su richiesta;

PAGINAZIONE SU RICHIESTA:
Nella paginazione su richiesta si porta una pagina in memoria solo quando serve:
- Minore I/O perché se ci sono blocchi di codice che non verranno mai eseguiti che contengono operazioni di I/O allora queste non saranno mai eseguite;
- Minore memoria necessaria;
- Risposta più veloce;
- Maggior numero di processi;
Quando serve una pagina riferimento ad essa;
- Se il riferimento non è valido abort;
- Se

Il riferimento non è in memoria page fault; Il page fault è un segnale di richiesta di trasferimento di una pagina da disco a RAM, operazione che richiede del tempo "perso", ma poi complessivamente la gestione della memoria è notevolmente migliorata.

BIT VALIDO/NON VALIDO: Ad ogni entry della tabella è associato un bit di validità (1 in memoria, 0 non in memoria). Inizialmente il bit di validità è settato a 0 per ogni entry, e, durante la traduzione degli indirizzi, se il bit è 0 allora page fault.

PAGE FAULT:

1. Se si tenta di accedere una pagina non in memoria page fault;
2. Il Sistema Operativo controlla in una tabella interna del processo, se il riferimento non è corretto allora è abort. Se il riferimento è corretto occorre caricare la pagina;
3. Si trova un frame libero;
4. Si carica la pagina nel frame;
5. Si aggiorna la tabella ed il bit di validazione = 1;
6. Viene riavviata l'esecuzione: la

pagina diventa quella più recente;

PRESTAZIONI DELLA PAGINAZIONE SU RICHIESTA:

Probabilità di page fault: 0 <= p <= 1;

se p = 0 allora nessun page fault;

se p = 1 allora ogni accesso provoca un page fault;

se p = 0.5 allora metà degli accessi provocano un page fault;

TEMPO DI ACCESSO EFFETTIVO:

TAE = (1 - p) x tma + p x tpf

tma = tempo di memory access (nanosecondi);

tpf = tempo di page fault (nanosecondi);

LEZIONE 12:

ASSENZA FRAME LIBERI:

Durante la gestione di page fault, la situazione più sfortunata è l'assenza di un frame libero. In questo caso vengono utilizzati degli algoritmi di sostituzione delle pagine.

Occorre trovare una pagina in memoria che non è usata e si porta sul disco (swap out). Per fare questo occorre usare un algoritmo apposito.

Prestazioni: ci vuole un algoritmo che dia il numero minimo di page fault, poiché se si trasferisce su disco una pagina, bisogna assicurarsi che questa non debba tornare a breve nella memoria

utilizzando la sostituzione delle pagine. Questo meccanismo richiede la modifica del gestore dei page fault per gestire questa possibilità. Si utilizza un bit di modifica (dirty bit) per ridurre il costo del trasferimento delle pagine: solo le pagine modificate vengono scritte sul disco. La sostituzione delle pagine completa la separazione tra memoria logica e memoria fisica. Si può realizzare una grande memoria virtuale su una piccola memoria fisica. In altre parole, durante la gestione del page fault, quando è necessario caricare una pagina nella memoria fisica e non c'è un frame libero, è necessario liberarne temporaneamente uno.spostando la pagina sul disco possibilmente che non è più utilizzato, o che verrà utilizzato molto più in là. Nel frangente in cui la pagina è sul disco bisogna tenere in conto che i dati corrispondenti al frame dove questa era locata potrebbero essere stati modificati o aver subito variazioni, per questo motivo si utilizza il dirty bit, ovvero se la pagina ha subito variazioni (anche solo un dato) il bit prende il valore 1, altrimenti 0. Quando la pagina deve "essere sacrificata" per inserire un'altra pagina, se il bit è 0 allora il Sistema Operativo si risparmia la fase di copia dei dati dal disco alla RAM poiché una copia della pagina nel disco c'è già, se il bit ha valore 1 allora il Sistema Operativo deve ricopiare tutta la pagina con i dati poiché questi hanno subito variazioni dalla copia che c'è sul disco. RIASSUNTO DELLA SOSTITUZIONE DELLE PAGINE: 1) Trovare la locazione della pagina da sostituire 2) Verificare se il dirty bit è 0 o 1 3) Se il dirty bit è 0, la pagina può essere sostituita direttamente senza copiare i dati dal disco alla RAM 4) Se il dirty bit è 1, copiare i dati dalla pagina sul disco alla RAM 5) Sostituire la pagina con la nuova pagina da inserire 6) Aggiornare le informazioni di gestione delle pagine

pagina richiesta sul disco;

1. Trova un frame libero.
   1. Se esiste viene utilizzato.
   2. Se non c'è un frame libero seleziona un frame vittima secondo un algoritmo di sostituzione cercando di non sacrificare una pagina che servirà presto. Scrivere la pagina vittima su disco e aggiornare le tabelle.
2. Leggi la pagina richiesta nel frame liberato ed aggiorna le tabelle.
3. Riavvia il processo.

ALGORITMI DI SOSTITUZIONE DELLE PAGINE:

Il criterio utilizzato per selezionare la pagina vittima può variare a seconda dell'algoritmo di sostituzione utilizzato.