Sistemi Operativi - DIMES Unicaltalia/aa0203/sisop/lezione7x2.pdf · Tabella dei segmenti–...
Transcript of Sistemi Operativi - DIMES Unicaltalia/aa0203/sisop/lezione7x2.pdf · Tabella dei segmenti–...
1
D. Talia - UNICAL7.1Sistemi Operativi
Sistemi Operativi
GESTIONE DELLA MEMORIA
CENTRALE
E
MEMORIA VIRTUALE
D. Talia - UNICAL7.2Sistemi Operativi
Gestione della memoria
Segmentazione
Segmentazione con paginazione
Memoria Virtuale
Paginazione su richiesta
Sostituzione delle pagine
Trashing
Esempi: Windows NT e Solaris
2
D. Talia - UNICAL7.3Sistemi Operativi
Segmentazione
La segmentazione è uno schema di gestione della memoria che corrisponde alla vista della memoria che in genere ha l’utente.
Un programma è una collezione di segmenti.
Un segmento è una unità logica di memoria come:
programma principale,procedura e/o funzione, metodo,oggetto,variabili locali, variabili globali,stack,tabella dei simboli, array.
D. Talia - UNICAL7.4Sistemi Operativi
Vista utente di un programma
3
D. Talia - UNICAL7.5Sistemi Operativi
Vista logica della segmentazione
1
3
2
4
1
4
2
3
spazio del processo utente spazio della memoria fisica
D. Talia - UNICAL7.6Sistemi Operativi
Architettura di segmentazione
Un indirizzo logico consiste di una coppia di valori :<numero-segmento, offset>
Tabella dei segmenti – assegna indirizzi fisici bi-dimensionali.Ogni elemento della tabella ha:
base – indirizzo di partenza del segmento in memoria.limite – lunghezza del segmento.
Segment-table base register (STBR) punta alla locazione di memoria dove si trova la tabella.Segment-table length register (STLR) indica il numero dei segmenti appartenenti ad un programma;
numero di segmento s è legale se s < STLR.
4
D. Talia - UNICAL7.7Sistemi Operativi
Hardware di segmentazione
D. Talia - UNICAL7.8Sistemi Operativi
Architettura di segmentazione
Rilocazionedinamicatramite la tabella dei segmenti
CondivisioneSegmenti condivisistesso numero di segmento
Allocazionefirst fit / best fitframmentazione esterna
5
D. Talia - UNICAL7.9Sistemi Operativi
Architettura di segmentazione
ProtezioneCon ogni entry nella tabella dei segmenti associata:
bit di validazione = 0 ⇒ segmento illegaleprivilegi read/write/execute
Bit di protezione associati ai segmenti; condivisione di codice a livello di segmento.
Poiché i segmenti variano in lunghezza, l’allocazione di memoria è un problema di allocazione dinamica.
D. Talia - UNICAL7.10Sistemi Operativi
Esempio di segmentazione
6
D. Talia - UNICAL7.11Sistemi Operativi
Condivisione di segmenti
D. Talia - UNICAL7.12Sistemi Operativi
Segmentazione con Paginazione
Il S.O. MULTICS ha risolto i problemi di frammentazione esterna e dei tempi lunghi di ricerca tramite la paginazione dei segmenti.
Un segmento viene realizzato tramite un insieme di pagine.
Soluzione differisce dalla segmentazione “pura” poiché una entry nella tabella dei segmenti non contiene l’indirizzo base di un segmento, ma l’indirizzo base della tabella delle pagine di quel segmento.
7
D. Talia - UNICAL7.13Sistemi Operativi
Schema di traduzione degli indirizzi in MULTICS
D. Talia - UNICAL7.14Sistemi Operativi
Segmentazione con Paginazione – Intel 386
L’Intel 386 per la gestione della memoria usa segmentazione con paginazione usando uno schema di paginazione a due livelli.
8
D. Talia - UNICAL7.15Sistemi Operativi
Memoria virtuale
Memoria Virtuale – separazione della memoria logica dalla memoria fisica.
Solo una parte del programma sta 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 tra più processi.Permette una più efficiente creazione dei processi.
La memoria virtuale può essere implementata tramite:Paginazione su richiesta
Segmentazione su richiesta
D. Talia - UNICAL7.16Sistemi Operativi
Memoria Virtuale maggiore della Memoria Fisica
9
D. Talia - UNICAL7.17Sistemi Operativi
Paginazione su richiesta
Si porta una pagina in memoria solo quando serve.minore I/Ominore memoria necessariarisposta più veloceMaggior numero di utenti
Quando serve una pagina ⇒ riferimento ad essariferimento non valido ⇒ abortnon in memoria ⇒ trasferire in memoria
D. Talia - UNICAL7.18Sistemi Operativi
Trasferimento di memoria paginata su disco contiguo
10
D. Talia - UNICAL7.19Sistemi Operativi
Bit Valido/Non validoAd ogni entry della tabella è associato un bit di validità(1 ⇒ in memoria, 0 ⇒ non in memoria ma su disco)Inizialmente il bit di validità è uguale a 0 per ogni entry.Esempio di tabella delle pagine:
Durante la traduzione degli indirizzi, se il bit è 0 ⇒ page fault.
11110
00
Frame # Bit valido- nonvalido
Tabella delle pagine
11
D. Talia - UNICAL7.20Sistemi Operativi
Tabella delle pagine con alcune pagine non in memoria
11
D. Talia - UNICAL7.21Sistemi Operativi
Page FaultSe si tenta di accedere una pagine non in memoria ⇒page fault.
Il S.O. controlla in una tabella interna del processo:se il riferimento non è valido ⇒ abort.Se il riferimento è valido occorre caricare la pagina.
Si trova un frame libero.
Si carica la pagina nel frame.
Si aggiorna le tabelle, bit di validazione = 1.
Viene riavviata l’esecuzione: la pagina diventa quella più
recente.
D. Talia - UNICAL7.22Sistemi Operativi
Passi della gestione di un Page Fault
12
D. Talia - UNICAL7.23Sistemi Operativi
Cosa accade quando non c’è un frame libero ?
Sostituzione delle paginesi trova una pagina in memoria che non è usata e si porta sul disco (swap out).
algoritmoprestazioni si vuole un algoritmo che dia il numero minimo di page fault.
Alcune pagine possono essere portate in memoria varie volte.
D. Talia - UNICAL7.24Sistemi Operativi
Prestazioni della paginazione su richiesta
Probabilità di page fault: 0 ≤ p ≤ 1.0
se p = 0 nessun page fault se p = 1 ogni accesso provoca un page fault.
Tempo di accesso effettivo (TAE)
TAE = (1 – p) x ma + p (tempo di page fault)
13
D. Talia - UNICAL7.25Sistemi Operativi
Esempio di paginazione su richiesta
Tempo di accesso in memoria = 100 nanosecondi
Il 50% del tempo la pagina che è stata rimpiazzata è stata modificata e quindi ha bisogno di essere portata sul disco.
Tempo di page fault = 25 msec = 25000 µsecTAE = (1 – p) x 100 + p x (25000000)
= 100 + (25000000-100) x p (in msec)
D. Talia - UNICAL7.26Sistemi Operativi
Sostituzione delle pagine
Quando occorre caricare una pagina e non c’è un framelibero si può usare la sostituzione delle pagine.
Il meccanismo di gestione dei page fault deve essere modificato per gestire questa possibilità.
Uso di un modify (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: un grande memoria virtuale si può realizzare su una piccola memoria fisica.
14
D. Talia - UNICAL7.27Sistemi Operativi
Necessità di sostituzione delle pagine
D. Talia - UNICAL7.28Sistemi Operativi
Sostituzione delle pagine
Operazioni per la sostituzione:1. Trova la locazione della pagina richiesta sul disco.
2. Trova un frame liberoa. Se esiste usalo;b. Se non c’è un frame libero seleziona un frame vittima
secondo un algoritmo di sostituzione;c. Scrivi la pagina vittima sul disco e aggiorna le tabelle;
3. Leggi la pagina richiesta nel frame liberato e aggiorna le tabelle
4. Riavvia il processo.
15
D. Talia - UNICAL7.29Sistemi Operativi
Sostituzione di una pagina
D. Talia - UNICAL7.30Sistemi Operativi
Algoritmi di sostituzione delle pagine
Criterio di scelta: L’algoritmo con la minima frequenza di page fault.
Si valuta gli algoritmi eseguendoli su una particolare sequenza (stringa) di riferimenti alla memoria e calcolando il numero di page fault che si verificano.
Negli esempi la stringa usata è: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5.
16
D. Talia - UNICAL7.31Sistemi Operativi
Numero di page fault in funzione del numero di frame
D. Talia - UNICAL7.32Sistemi Operativi
Algoritmo First-In-First-Out (FIFO)
Si sostituisce la pagina più vecchia.Stringa: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5
3 frame (3 pagine possono essere in memoria per processo)
4 frame
9 page fault
10 page fault
1
2
3
1
2
3
4
1
2
5
3
4
1
2
3
1
2
3
5
1
2
4
5
44 3
Anomalia di Beladypiù frame ⇒ più page fault
17
D. Talia - UNICAL7.33Sistemi Operativi
Sostituzione FIFO
D. Talia - UNICAL7.34Sistemi Operativi
Anomalia di Belady
18
D. Talia - UNICAL7.35Sistemi Operativi
Algoritmo Ottimale
Sostituisce la pagina che non verrà usata per il periodo di tempo più lungo.Esempio: 4 frame
stringa: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5
Come predire il futuro (uso delle pagine) ?Usato come paragone per valutare altri algoritmi.
1
2
3
46 page fault
4 5
D. Talia - UNICAL7.36Sistemi Operativi
Algoritmo Ottimale
19
D. Talia - UNICAL7.37Sistemi Operativi
Algoritmo Least Recently Used (LRU)
Sostituisce la pagina che non è stata usata per il periodo di tempo più lungo.
Stringa: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5
Implementazione con contatore
Implementazione con stack
1
2
3
5
4
4 3
5
D. Talia - UNICAL7.38Sistemi Operativi
Sostituzione LRU
20
D. Talia - UNICAL7.39Sistemi Operativi
Sostituzione LRU
Implementazione con contatoreOgni entry di pagina ha un contatore; ogni volta che la pagina viene referenziata si copia il clock nel contatore.Quando occorre sostituire una pagina, occorre cercare la pagina con il valore del clock più piccolo.
Implementazione con stackSi mantiene uno stack con i numeri delle pagina con la pagina più recente sta in cima e la LRU in fondo:La pagina referenziata si mette in cima:
spostare il numero di pagina in prima posizionerichiede la modifica di sei puntatori
Non bisogna fare la ricerca.
D. Talia - UNICAL7.40Sistemi Operativi
Implementazione LRU con lo stack
21
D. Talia - UNICAL7.41Sistemi Operativi
Algoritmi di approssimazione ad LRUL’algoritmo LRU richiede l’uso di un supporto hardware.Se non esiste si usano algoritmi approssimati:Bit di riferimento
Ad ogni pagina è associato un bit, inizialmente = 0Quando la pagina è usata viene messo ad 1.Si sostituisce una pagina con bit a 0 (se esiste). L’ordine di uso non si conosce.
Seconda chanceSi usa il bit di riferimento.Clock (o coda circolare).Se una pagina (in senso orario) ha il bit = 1, allora:
bit <-- 0.Lascia la pagina in memoria.Sostituisce la prossima pagina (in senso orario) con bit=0.
D. Talia - UNICAL7.42Sistemi Operativi
Algoritmo Seconda Chance (clock)
22
D. Talia - UNICAL7.43Sistemi Operativi
Algoritmi con conteggio
Usano un contatore del numero dei riferimenti che sonotati fatti su ogni pagina.
Algoritmo LFU: sostituisce le pagine con il contatore minimo.
Algoritmo MFU: sostituisce le pagine con il contatore massimo.
(basato sull’idea che con la pagina con il contatore minimo è stata inserita da poco e non è stata usata)
D. Talia - UNICAL7.44Sistemi Operativi
Thrashing
Se un processo non ha abbastanza pagine in memoria il tasso di page fault è molto alto. Questo crea:
bassa utilizzazione della CPU.Il S.O. può credere che occorre aumentare il grado di multiprogrammazione.Un nuovo processo viene inserito in memoria.
Thrashing ≡ un processo è occupato principalmente nella attività di paginazione.
23
D. Talia - UNICAL7.45Sistemi Operativi
Thrashing
Quando la paginazione funziona ?Modello di località (set di pagine usate insieme)
Un processo di sposta da una località all’altraLe località si possono sovrapporre.
Perché si verifica il thrashing ?
Σ spazi di località > spazio di memoria locale
D. Talia - UNICAL7.46Sistemi Operativi
Località in sequenze di riferimenti a memoria
24
D. Talia - UNICAL7.47Sistemi Operativi
Esempi di gestione di memoria virtuale
Windows NT
Usa la paginazione su richiesta paging con clustering. Il clustering mantiene le pagine vicine all pagina che ha creato il page fault.
Solaris 2
Mantiene una lista di pagine libere da assegnare ai processi che hanno avuto un page fault.
D. Talia - UNICAL7.48Sistemi Operativi
Windows NT
Ai processi viene assegnato un working set minimo e un working set massimo.
Working set minimo è delle pagine che il processo avrà in memoria (garantito)Gli potranno essere assegnate altre pagine fino al working set massimo.
Quando l’ammontare di memoria libera nel sistema è minore di una data soglia viene eseguito un algoritmo di automatic working set trimming per aumentare la dimensione della memoria libera.
Il working set trimming rimuove dai processi le pagine in eccesso rispetto al loro working set minimo.
25
D. Talia - UNICAL7.49Sistemi Operativi
Solaris 2
Lotsfree: parametro di soglia per iniziare la paginazione.
Paginazione è eseguita dal processo pageout.
Pageout scandisce le pagine usando un algoritmo basato sulla coda circolare modificato.
Scanrate è la velocità con cui le pagine sono scandite. Varia tradue valori: slowscan e fastscan.
Pageout è invocato più o meno frequentemente in dipendenza della memoria libera disponibile.
D. Talia - UNICAL7.50Sistemi Operativi
Scanner delle pagine di Solaris
26
D. Talia - UNICAL7.51Sistemi Operativi
Domande
Discutere le differenze principali tra paginazione e segmentazione.
Quali sono i benefici di usare la segmentazione paginata ?
Spiegare le operazioni da eseguire per la gestione di un page fault.
Discutere le differenze tra gli algoritmi di sostituzione FIFO e LRU.
Spiegare il funzionamento dell’algoritmo LRU con implementazione a stack.
Analizzare una situazione in cui si verifica trashing di pagine.