1
Pag. 1
Struttura interna del Sistema OperativoStruttura interna del Sistema Operativo
CAP. 7. La CAP. 7. La gestionegestione delladella memoriamemoria virtualevirtuale
Il concetto di memoria virtualeIl concetto di memoria virtuale
Il concetto di memoria virtuale nasce dalla necessità di separare il concetto di
– spazio di indirizzamento di un programma eseguibile e– spazio di indirizzamento di un programma eseguibile e– dimensione effettiva della memoria fisica
Lo spazio di indirizzamento è definito dal numero di parole indirizzabili e dipende esclusivamente dal numero di bit dell’indirizzo e non dal numero di parole di memoria fisica effettivamente disponibili
La dimensione della memoria fisica è pari al numero di byte che la costituiscono
-- 22 --
– se N sono i bit di indirizzo, allora 2N è il numero massimo di byte indirizzabili (2N è lo spazio di indirizzamento della memoria fisica)
– poiché la memoria fisica deve essere tutta indirizzabile, la sua dimensione è sempre minore o uguale al suo spazio di indirizzamento
2
Pag. 2
Codifica Esadecimale Codifica Esadecimale
HEX Bin HEX Bin HEX Bin HEX Bin
0 0000 4 0100 8 1000 C 1100
1 0001 5 0101 9 1001 D 1101
Per la rappresentazione degli indirizzi di memoria si utilizza di solito la rappresentazione esadecimale:
– 32 bit di indirizzo si rappresentano con 8 cifre esadecimali:– Esempio : 0000FFFF = 0000 0000 0000 0000 1111 1111 1111 1111
1 0001 5 0101 9 1001 D 1101
2 0010 6 0110 A 1010 E 1110
3 0011 7 0111 B 1011 F 1111
-- 33 --
32 bit di indirizzo corrispondono a 232 Byte (4 G Byte) indirizzabiliLe dimensioni della memoria sono generalmente espresse in:K Byte (210 Byte), M Byte (220 Byte) , G Byte (230 Byte)
Memoria virtuale: indirizzi virtualiMemoria virtuale: indirizzi virtuali
Gli indirizzi a cui fa riferimento il programma in esecuzione sono indirizzi virtuali
Gli indirizzi virtuali sono quelli generati da linker (a partire dall’indirizzo 0): sono quindi indirizzi rilocabili
Lo spazio di indirizzamento virtuale è quello definito dalla lunghezza degli indirizzi virtuali
In un programma è possibile definire la dimensione virtuale (cioè espressa in termini di indirizzi virtuali):
– iniziale: è quella calcolata dal linker dopo la generazione del codice
-- 44 --
q p geseguibile
– durante l’esecuzione: la dimensione virtuale di un programma può variare in fase di esecuzione a causa della modifica delle dimensioni dello stackdovuta a chiamate a sottoprogrammi e a causa della modifica delle dimensioni dello heap dovuta alla gestione delle strutture dati dinamiche (allocazione dinamica della memoria).
3
Pag. 3
Memoria virtuale: indirizzi fisiciMemoria virtuale: indirizzi fisici
La memoria principale (Main Memory) è chiamata memoria fisica e i sui indirizzi sono detti indirizzi fisici
E’ presente un meccanismo di traduzione automatica degli indirizzi virtuali in indirizzi fisici
Con la memoria virtuale, la CPU genera un indirizzo virtuale, che viene tradotto da una combinazione di elementi hardware e software in un indirizzo fisico, utilizzato per accedere alla memoria principale: meccanismo di traduzione dell’ indirizzo
-- 55 --
(memory mapping)
Memoria virtuale e rilocazione dinamicaMemoria virtuale e rilocazione dinamica
Avere degli indirizzi virtuali implica che ogni programma eseguibile generato dal linker sia in formato rilocabile, cioè con indirizzi che partono dall’indirizzo 0con indirizzi che partono dall indirizzo 0
Inoltre, al momento dell’esecuzione il programma viene caricato (opportunamente) in memoria con indirizzi virtuali
Il meccanismo di rilocazione dinamica cioè di traduzione automatico degli indirizzi virtuali in indirizzi fisici, è attivato durante l’esecuzione del programma ad ogni riferimento a memoria ed è trasparente al programmatore, al compilatore e
-- 66 --
p p g , pal linker
Questa traduzione automatica consente il caricamento di un programma in una qualsiasi locazione della memoria fisica
4
Pag. 4
Vantaggi Vantaggi della memoria virtualedella memoria virtuale
Il programmatore può scrivere i propri programmi pensando di avere a disposizione l’intero spazio di indirizzamento virtuale indipendentemente dalle dimensioni effettive della memoria principale
Più programmi in esecuzione (processi) possono risiedere contemporaneamente in memoria indipendentemente dalle dimensioni effettive della memoria principale
La dimensione di memoria di un singolo programma e/o lo spazio di indirizzamento di più programmi in memoria può essere maggiore della dimensione della memoria fisica
Questo implica che generalmente un programma in esecuzione non
-- 77 --
Questo implica che generalmente un programma in esecuzione non risiede completamente in memoria
– il meccanismo di caricamento in memoria delle parti del programma e la traduzione degli indirizzi è trasparente al programmatore
LINUX e la memoria virtuale (1)LINUX e la memoria virtuale (1)
LINUX considera la memoria fisica disponibile limitata
Esiste una parte della memoria riservata alla gestione dei Esiste una parte della memoria riservata alla gestione dei buffer
– I buffer sono aree di memoria fisica allocate a contenere i dati in transito da disco (tramite adattatori DMA) a memoria centrale e viceversa.
LINUX tende a mantenere in memoria, il più a lungo possibile, i dati letti da disco e i dati scritti dai programmi per limitare
-- 88 --
i dati letti da disco e i dati scritti dai programmi per limitare gli accessi (lenti) a disco
Necessità di liberare memoria fisica: – LINUX diminuisce la zona di memoria riservata ai buffer
5
Pag. 5
LINUX e la memoria virtuale (2)LINUX e la memoria virtuale (2)
Se la zona liberata dai buffer non è sufficiente, è necessario rendere disponibili zone di memoria fisica che sono allocate a processi in esecuzione
– se la zona di memoria da liberare contiene informazioni che non sono se la zona di memoria da liberare contiene informazioni che non sono state modificate rispetto alla loro copia su disco (es. codice) la zona di memoria viene considerata libera
– se la zona di memoria da liberare contiene informazioni che sono state modificate, queste vengono salvate su disco (nello Swap file) per poter essere recuperate
Swap file = zona del disco nella quale sono scritte le porzioni di memoria salvate
-- 99 --
Condivisione di codice tra i processi (sharing): LINUX mantiene in memoria una sola copia del codice o delle librerie condivise da più processi per risparmiare sull’utilizzo della memoria fisica
Comando free serve per visualizzare la situazione attuale di utilizzo della memoria
Rilocazione Rilocazione -- PaginazionePaginazione
Tutti i meccanismi di gestione della memoria virtuale rilocano ilprogramma come un insieme di blocchi di dimensione fissa (pagine)non necessariamente contigui, eliminando così la necessità dinon necessariamente contigui, eliminando così la necessità diindividuare un blocco di memoria contigua sufficientemente ampioda potervi caricare il programma
Il sistema operativo ha solo bisogno di trovare un numero sufficientedi pagine (non necessariamente contigue) disponibili nella memoriafisica
La paginazione ha inoltre l’effetto di ridurre il fenomeno dellaframmentazione della memoria: cioè della presenza di zone di
-- 1010 --
a e ta o e della e o a: c oè della p ese a d o e dmemoria libere (e piccole) inframmezzate a zone utilizzate
E’ inoltre possibile gestire facilmente la crescita di memoria di unprocesso durante l’esecuzione
6
Pag. 6
MEMORIA CENTRALE
SISTEMA OPERATIVO
MEMORIA CENTRALE
SISTEMA OPERATIVO
Processo S
Processo P
Processo Q
Processo S(prima parte)
Processo P
Processo Q
-- 1111 --
Processo S(seconda parte)
Processo R Processo R
Processo P(crescita)
Paginazione (1)Paginazione (1)
Lo spazio di indirizzamento virtuale di ogni programma è lineare(indirizzi virtuali contigui) ed è suddiviso in un numero intero di pagineaventi dimensione fissa:aventi dimensione fissa:
– Dimensioni di pagina tipici: da 512 Byte a 64 K Byte
L’ indirizzo virtuale può essere visto come
– Ad esempio• spazio di indirizzamento virtuale di un programma 64 K (16 bit di indirizzo virtuale)
i d 512 b t (9 bit di i di i i t ll i )
Numero Pagina Virtuale (NPV) Spiazzamento (offset) nella pagina
-- 1212 --
• pagine da 512 byte (9 bit di indirizzo per spiazzamento nella pagina)• 128 pagine virtuali (7 bit di indirizzo per NPV)• l’indirizzo virtuale su 16 bit viene visto come composto da 7 bit + 9 bit:15 9 8 0 0 0 0 0 1 1 1 1 0 0 0 1 0 0 0 0
Numero Pagina Virtuale Spiazzamento nella pagina
7
Pag. 7
Paginazione (2)Paginazione (2)
Lo spazio di indirizzamento fisico (ossia della memoria centrale) viene suddiviso in un numero intero di pagine fisiche di uguale dimensione di quelle utilizzate per lo spazio di indirizzamento virtualequelle utilizzate per lo spazio di indirizzamento virtualeOgni pagina della memoria centrale può quindi contenere esattamenteuna pagina dello spazio di indirizzamento virtuale
Essendo la dimensione di una pagina virtuale uguale alla dimensione di una pagina fisica → Offset nella pagina virtuale è uguale all’offset nella pagina fisica
-- 1313 --
L’indirizzo fisico può essere visto come:
Numero Pagina Fisica (NPF) Spiazzamento (offset) nella pagina
Esempio (1)Esempio (1)
Spazio di indirizzamento virtuale 4GByte : indirizzi virtuali da 32 bit 232 indirizzi diversi
Dimensione di pagina: 4KByte 212 indirizzi per lo spiazzamento (offset)
Numero di pagine dello spazio di indirizzamento virtuale = 232 / 212 = 220 pagine virtuali
Spazio di indirizzamento fisico 4MByte: indirizzi fisici da 22 bit222 indirizzi
-- 1414 --
Numero di pagine dello spazio di indirizzamento fisico = 222
/ 212
= 210
pagine fisiche
8
Pag. 8
Esempio (1):Esempio (1):Traduzione da indirizzo virtuale in indirizzo fisicoTraduzione da indirizzo virtuale in indirizzo fisico
11 10 9 8 3 2 1 031 30 29 28 27 15 14 13
Indirizzo virtuale 32 bit
Traduzione
Spiazzamento pagina Numero di pagina virtuale
11 10 9 8 …… 3 2 1 0 31 30 29 28 27 ………… 15 14 13
12 bit
20 bit
10 bit
-- 1515 --
Indirizzo fisico
Spiazzamento pagina Numero di pagina fisica
11 10 9 8 …… 3 2 1 0 21 20 ………… 15 14 13 12
22 bit
Esempio (2)Esempio (2)
Spazio di indirizzamento virtuale 4GByte : indirizzi virtuali da 32 bit 232 indirizzi diversi
Dimensione di pagina: 4KByte 212 indirizzi per lo spiazzamento (offset)
Numero di pagine dello spazio di indirizzamento virtuale = 232 / 212 = 220 pagine virtuali
Spazio di indirizzamento fisico 1Gbyte: indirizzi fisici da 30 bit 230 indirizzi
-- 1616 --
Numero di pagine dello spazio di indirizzamento fisico = 230
/ 212
= 218
pagine fisiche
9
Pag. 9
Esempio (2):Esempio (2):Traduzione da indirizzo virtuale in indirizzo fisicoTraduzione da indirizzo virtuale in indirizzo fisico
11 10 9 8 3 2 1 031 30 29 28 27 15 14 13
Indirizzo virtuale 32 bit
Traduzione
Spiazzamento pagina Numero di pagina virtuale
11 10 9 8 …… 3 2 1 0 31 30 29 28 27 ………… 15 14 13
12 bit
20 bit
18 bit
-- 1717 --
Indirizzo fisico
Spiazzamento pagina Numero di pagina fisica
11 10 9 8 …… 3 2 1 0 29 28 ………… 15 14 13 12
30 bit
Paginazione (3)Paginazione (3)
Il meccanismo di traduzione o corrispondenza tra pagine virtuali e pagine fisiche è realizzata da una tabella delle pagine associata al processoprocesso
– Esiste una tabella delle pagine per ogni processo in esecuzione
La tabella delle pagine deve, in linea di principio, contenere una riga per ogni pagina virtuale del processo che riporta il numero della pagina fisica corrispondente
In questa ipotesi, il numero di pagina virtuale (NPV) può essere
-- 1818 --
q p , p g ( ) putilizzato come indice (indirizzo) nella tabella delle pagine del processo (tabella indicizzata)
Oppure la tabella può essere associativa sul contenuto del campo NPV
10
Pag. 10
MEMORIA FISICA
Numero dipagina
Contenutodelle pagine
0x00000 S.O.0x00001 S.O.0x00002 S.O.0 00003 S O
NPV NPF0x00000 0x000040x00001 0x000050x00002 0x000060x00003 0x00007
Tabella Pagine di PNumero di
paginaContenuto
delle pagine0x00000 AAAA
0x00001 BBBB
0x00002 CCCC
Memoria virtuale di P
0x00003 S.O.0x00004 AAAA0x00005 BBBB0x00006 CCCC0x00007 DDDD0x00008 RRRR0x00009 SSSS0x0000A TTTT0x0000B UUUU0 0000C VVVV
NPV NPF0x00000 0x000080x00001 0x000090 00002 0 0000A
Tabella Pagine di Q
0x00002 CCCC
0x00003 DDDD
Numero dipagina
Contenutodelle pagine
0x00000 RRRR
Memoria virtuale di Q
-- 1919 --
0x0000C VVVV0x0000D non usata0x0000E non usata0x0000F non usata
0x00002 0x0000A
0x00003 0x0000B
0x00004 0x0000C
0x00001 SSSS
0x00002 TTTT
0x00003 UUUU
0x00004 VVVV
Paginazione (4)Paginazione (4)
Problema: La Tabella delle Pagine per processo è una struttura dati del SO residente in memoria che può assumere grandi dimensioni (che dipendono dal numero delle pagine per processo che variano (che dipendono dal numero delle pagine per processo che variano dinamicamente)
Necessari dei meccanismi hardware per accelerare la traduzione tra NPV e NPF come la Memory Management Unit (MMU)
-- 2020 --
11
Pag. 11
Memory Management Unit (1)Memory Management Unit (1)
Per accelerare la traduzione del numero di pagina virtuale nel corrispondente numero di pagina fisica si usa un dispositivo specializzato, la Memory Management Unit (MMU), che può essere
i i l hi d ll CPU i hi posizionata nel chip della CPU, o in un chip separato
La MMU ha al suo interno una memoria molto veloce (e di dimensioni ridotte) che contiene, in un formato opportuno, una copia di una parte delle tabelle delle pagine dei processi
In generale, la tabella implementata nella MMU (detta MMU Table):
– contiene solo una parte della tabella delle pagine di ogni processo (e cioè le righe relative alle pagine recentemente utilizzate)
-- 2121 --
(e cioè le righe relative alle pagine recentemente utilizzate)• Il valore di NPV non può quindi essere utilizzato come indice della tabella ma è
memorizzato come campo
– per distinguere le pagine virtuali di ciascun processo, un campo della tabella deve contenere il PID del processo stesso
Memory Management Unit (2)Memory Management Unit (2)
PID NPV NPF PID_REG
Registro della MMU che contiene il PID del
La memoria della MMU viene realizzata spesso come memoria associativa:– la selezione di una riga della memoria non avviene tramite indirizzo (indice) ma
come associazione sul contenuto di opportuni campi (descrittore) della riga stessa
contiene il PID del processo corrente in esecuzione
-- 2222 --
– il descrittore utilizzato è la coppia (PID, NPV) per ottenere il numero di pagina fisica corrispondente (NPF). A tale valore viene giustapposto lo spiazzamento nella pagina completando la traduzione dell’indirizzo
Numero Pagina Fisica (NPF) Spiazzamento (offset) nella pagina
12
Pag. 12
Memory Management Unit (3)Memory Management Unit (3)
Si noti che il contenuto della tabella associativa è sempre una copia di una parte del contenuto delle Tabelle delle Pagine dei processi che risiedono in memoria e che costituiscono una struttura dati del risiedono in memoria e che costituiscono una struttura dati del Sistema Operativo (Tabella delle Pagine) che può assumere grandi dimensioni. La dimensione della tabella associativa è in generale molto ridotta rispetto alla dimensione delle tabelle delle pagine dei processi.Poiché la tabella associativa contiene solo una parte della tabella delle pagine dei processi, è possibile che avvenga l’accesso ad una pagina virtuale non presente nella tabella associativa (Table Miss).
-- 2323 --
pagina virtuale non presente nella tabella associativa (Table Miss).Per ridurre la probabilità di Table Miss, è necessario che la dimensione della tabella associativa per processo si avvicini al numero R di pagine del processo residenti in memoria.
CondivisioneCondivisione delledelle paginepagine
I diversi processi possono condividere delle pagine (tipicamente di codice o di libreria, ma anche di dati, tramite opportuni meccanismi messi a disposizione dal S.O.)messi a disposizione dal S.O.)
– le pagine condivise da diversi processi sono presenti una sola volta nella memoria fisica
Per ogni pagina condivisa da più processi, esiste una riga (cioè un NPV) nella corrispondente tabella delle pagine del processoI valori di NPF relativi alle pagine condivise sono identici nelle righe delle tabelle delle pagine di ogni processo che le condivide
Tabella Pa i e di P
-- 2424 --
NPV NPF0x00000 0x000040x00001 0x000050x00002 0x000060x00003 0x00007
NPV NPF
0x00000 0x000040x00001 0x00005 0x00002 0x0000A
0x00003 0x0000B
0x00004 0x0000C
Tabella Pagine di P Tabella Pagine di Q
13
Pag. 13
Protezione delle pagineProtezione delle pagine
Il meccanismo di paginazione consente di rilevare, durante l’esecuzione, un accesso a zone di memoria che non appartengono allo spazio di indirizzamento virtuale del processo in esecuzione.
– questo avviene quando viene generato un numero di pagina virtuale (NPV) che non esiste nella tabella (completa) delle pagine del processo. In questo caso, la MMU (o il Sistema Operativo stesso) generano un interrupt di violazione di memoria
E’ possibile associare ad ogni pagina virtuale di un processo alcuni bit di protezione, che definiscono le modalità di accesso (diritti) consentite per quella pagina
Lettura (R)
-- 2525 --
– Lettura (R)– Scrittura (W)– Esecuzione (X) per pagine di codice (istruzioni da leggere ed eseguire)
I diritti di accesso risultano particolarmente significativi nel caso di pagine condivise
Pagine fuori memoria Pagine fuori memoria
Non tutte le pagine virtuali di un processo sono caricate in memoria centrale.La tabella delle pagine deve prevedere la presenza di un bit di validità
Ind irizzi fis ic iIn d ir izzi v irtua li
-- 2626 --
P a ge F au lt
14
Pag. 14
Bit di validitàBit di validità
Si deve verificare se la pagina richiesta è residente in memoria centrale esaminando il bit di validità
Se il bit è a 1 la pagina è residente in memoriaSe il bit è a 1 la pagina è residente in memoria– Legge il valore contenuto nella tabella che rappresenta il
numero di pagina fisica e lo affianca come bit più significativi all’offset ottenendo l’indirizzo fisico di memoria da cercare.
Se il bit è a 0 si verifica un errore di pagina (page fault) e il processo viene sospeso in attesa che la pagina sia caricata da discoSe necessario, una pagina già residente viene scaricata su disco per liberare una pagina fisica che possa contenere la nuova pagina virtuale
-- 2727 --
liberare una pagina fisica che possa contenere la nuova pagina virtuale
Tabella delle pagine e riferimenti a discoTabella delle pagine e riferimenti a disco
Tabella delle pagine Memoria fisica
Numero dellapagina virtuale
Memorizzazione su disco
11
Valido Pagina fisica o indirizzo su disco
11
10
01
11
-- 2828 --
Memorizzazione su disco
10
15
Pag. 15
Costruzione dell’indirizzo fisicoCostruzione dell’indirizzo fisico
Ind irizzo virtua le
Il bit VALIDO indica se la pagina corrispondente è presente/assente in memoria
Sp iazzam ento i Registro de lla tabe lla de lle pag ine
N um ero d i pag ina virtua le
Num ero d i p ag ina fisica Valid
11 10 9 8 … … 3 2 1 0 31 30 29 28 27 … … … … 15 14 13
Tabella delle pag ine
12 20
Se consideriamo le tabelle delle pagine complete di ogni processo, questo registro
-- 2929 --
Se è 0 a llo ra la pag ina non è p resente in
i Ind irizzo fis ico
Sp iazzam ento i
Num ero d i p ag ina fisico
10
11 10 9 8 … … 3 2 1 0 21 20 … … 15 14 13 12
questo registro indica l’inizio della tabella delle pagine del processo
correntemente in esecuzione
MMU MMU TableTable Miss e Miss e PagePage FaultFault
In generale in caso di MMU Table Miss si possono avere 2 casi:1. Page Fault (se bit di validità = 0) la pagina NON è presente in
memoria il processo iene sospeso in attesa che la pagina memoria – il processo viene sospeso in attesa che la pagina venga caricata da disco.
2. Vero Table Miss (se bit di validità = 1) la pagina è presente in memoria – NPF deve essere recuperato dalla tabella delle pagine
Se si fa l’ipotesi che il MMU contenga solo le pagine residenti R in memoria di ogni processo (bit di validità sempre = 1), in caso di MMUTable Miss significa che si è verificato il caso 2 (Vero Table Miss) Table Miss significa che si è verificato il caso 2 (Vero Table Miss) Si noti che essendo la MMU Table di dimensione ridotta, i veri TableMiss (caso 2) saranno in genere più frequenti dei Page Fault (caso 1).
-- 3030 --
16
Pag. 16
Gestione delle pagine virtuali non residenti in memoriaGestione delle pagine virtuali non residenti in memoria
Durante l’esecuzione di un processo
un certo numero di pagine virtuali è caricato in memoria di lavoro inaltrettante pagine fisiche (pagine residenti)p g (p g )
durante un accesso a memoria, in caso di page fault, tramite un interrupt ilcontrollo deve essere passato al sistema operativo
il processo in esecuzione viene interrotto e il sistema operativo deve
– rintracciare su disco la pagina virtuale richiesta: il S.O. utilizza per questo letabelle delle pagine “complete” che contengono, per le pagine fuori memoria, ilriferimento alla posizione su disco
trovare spazio in memoria per caricare la pagina richiesta Questa operazione può
-- 3131 --
– trovare spazio in memoria per caricare la pagina richiesta. Questa operazione puòimplicare di dover scaricare da memoria un’altra pagina. Le tabelle delle pagine(e MMU) dei processi coinvolti devono essere aggiornate
– caricare la pagina da disco a memoria
– far rieseguire l’istruzione che aveva generato il page fault
Progetto di un sistema di memoria virtualeProgetto di un sistema di memoria virtuale
Problemi principali:
1 St t gi di i t d ll gi1. Strategia di caricamento delle pagine• su richiesta (on demand)• working set
2. Politica di sostituzione: nel caso di errore di pagina, se la memoria centrale non ha pagine disponibili come scegliere la pagina da sostituire per
-- 3232 --
far posto alla nuova pagina3. Dimensione delle pagine (unità trasferita tra
memoria principale e memoria secondaria)
17
Pag. 17
1.a Caricamento di pagine su 1.a Caricamento di pagine su richiesta (on richiesta (on demanddemand))
Esecuzione di un nuovo programma– La tabella delle pagine del processo ha tutti i Valid bit a 0
(nessuna pagina si trova in memoria)(nessuna pagina si trova in memoria)
– Quando la CPU cerca di accedere alla prima istruzione si verifica un errore di pagina e la prima pagina viene portata in memoria e registrata nella tabelle delle pagine
– Ogni volta che si identifica un indirizzo in una pagina non ancora in memoria, si verifica un errore di pagina (page fault)
-- 3333 --
Metodo chiamato di paginazione su richiesta (on demand paging): pagine caricate solo quando necessarie
– Questo metodo viene utilizzato per il caricamento iniziale delle pagine di un programma
Località temporale e spazialeLocalità temporale e spaziale
E’ stato rilevato che la distribuzione temporale e spaziale degli accessi a memoria da parte dei programmi non è omogenea, ma presenta caratteristiche di località:caratteristiche di località:
Località temporale: indica che un programma tende ad accedere, in un certo intervallo di tempo, agli indirizzi di memoria a cui ha acceduto di recente (esecuzione di cicli che riaccedono alle stesse istruzioni e agli stessi dati)
Località spaziale: indica che un programma accede con maggior probabilità agli indirizzi vicini a quelli che ha referenziato di recente
-- 3434 --
probabilità agli indirizzi vicini a quelli che ha referenziato di recente (istruzioni sequenziali, attraversamento strutture dati lineari come gli array)
18
Pag. 18
1.b Caricamento basato su Working set 1.b Caricamento basato su Working set
Metodo basato sul principio di località– La maggior parte dei programmi non accede al suo spazio di indirizzamento in
modo uniforme ma gli accessi tendono a raggrupparsi in un numero limitato di g gg pppagine
Working set di ordine k di un programma:– insieme di pagine referenziate durante gli ultimi k accessi alla memoria.
Se k è sufficientemente grande, il Working set di un programma varia molto lentamente per il principio di località
Il numero R di pagine residenti in memoria di ogni processo è ottenuto da una stima del Working set (in configurazione). L lt d l t R d t i l f d i f lt
-- 3535 --
La scelta del parametro R determina la frequenza dei page fault: – Se scelgo R grande: avrò pochi page fault per processo – Se scelgo R piccolo: possono convivere molti processi in memoria ma avrò più page fault
per processo
All’inizio dell’esecuzione di un programma, tramite on demand paging, è possibile caricare il working set in memoria (dopo R page fault)
2. Politica di sostituzione delle 2. Politica di sostituzione delle pagine e bit di pagine e bit di controllo controllo
Per gestire in modo efficiente la scelta della pagina fisica in cui caricare la pagina che ha causato il page fault (politica di sostituzione della pagina), ogni riga della tabella delle pagine deve p g ), g g p gprevedere altri due bit di controllo:
– bit di accesso: azzerato quando la pagina viene posta in memoria, viene posto a 1 ogni volta che si accede alla pagina fisica corrispondente (serve per aggiornare le informazioni necessarie alla gestione della sostituzione della pagine con algoritmo LRU – Least Recently Used)
– bit di modifica: azzerato quando la pagina viene posta in memoria,
-- 3636 --
viene posto a 1 quando si accede in scrittura ad una parola della pagina fisica corrispondente (serve per gestire la ricopiatura della pagina in memoria su disco, quando questa viene scaricata). Ovviamente le pagine che al momento dello scaricamento hanno il bit di modifica a 0 non richiedono la ricopiatura su disco perché non sono state modificate.
19
Pag. 19
2. Politica di sostituzione delle pagine2. Politica di sostituzione delle pagine
Definizione di un algoritmo di sostituzione– Casuale
– Least recently used (LRU): il SO cerca di sostituire la pagina meno utile nel prossimo futuro, ossia quella utilizzata meno di recente che ha minor probabilità di appartenere al working set attuale (principio di località)
– FIFO (First In First Out): si sostituisce sempre la pagina caricata meno di recente indipendentemente da quando si
-- 3737 --
caricata meno di recente, indipendentemente da quando si è fatto riferimento a questa pagina
Algoritmo LRUAlgoritmo LRU
Utilizza bit di controllo che riportano le informazioni sugli accessi alle pagine (lettura/scrittura)
La gestione più semplice prevede un bit di accesso per ogni riga La gestione più semplice prevede un bit di accesso per ogni riga della tabella delle pagine:
– il bit viene posto a 1 quando la pagina viene acceduta e azzerato periodicamente da SO
– in corrispondenza dell’azzeramento periodico, il SO controlla tali bit e incrementa una variabile di conteggio interna, per tutte le pagine con bit di accesso a 0
– viene sostituita la pagina con bit di accesso a 0 e valore di i iù l ( d iù l di ll i )
-- 3838 --
conteggio più alto (grado più alto di non-accesso alla pagina)
Ha buone prestazioni in media, ma esistono situazioni particolari in cui l’algoritmo LRU ha prestazioni pessime (ad esempio nel caso di working set di poco maggiore rispetto al numero di pagine disponibili in memoria centrale).
20
Pag. 20
Algoritmo LRU: esempio di applicazioneAlgoritmo LRU: esempio di applicazione
Esempio: – Esecuzione di un ciclo che si estende su 9 pagine virtuali– La memoria può contenere solo 8 pagine– Si assuma che le prime 8 pagine virtuali (da 0 a 7) siano in
memoria.– Al termine dell’esecuzione della pagina 7 è necessario scegliere
una pagina da scaricare per caricare la pagina 8 .
-- 3939 --
Algoritmo LRU: esempio di applicazioneAlgoritmo LRU: esempio di applicazione
Scelta della pagina da sostituire mediante algoritmo LRULa pagina utilizzata meno di recente è la pagina 0 viene sostituita con la pagina 8con la pagina 8Al termine dell’esecuzione delle istruzioni che appartengono alla pagina 8 è necessario ricominciare l’esecuzione del ciclo da pagina 0, ossia dalla pagina appena sostituita errore di pagina!La pagina 0 andrà a sostituire la pagina 1, utilizzata meno di recente: ma questa sarà la pagina da ricaricare subito dopo!!
-- 4040 --
21
Pag. 21
Fallimento dell’algoritmo Fallimento dell’algoritmo LRULRU
Pagina virtuale 7
Memoria centrale
Al termine dell’esecuzione delle
Pagina virtuale 3Pagina virtuale 4
Pagina virtuale 5
Pagina virtuale 7Pagina virtuale 6
Al termine dell esecuzione delleistruzioni di pagina 7 è necessariocaricare pagina 8 sostituendo la pagina utilizzata meno di recente, ossia pagina 0
-- 4141 --
Pagina virtuale 0Pagina virtuale 1
Pagina virtuale 2
Pagina virtuale 8
Fallimento dell’algoritmo Fallimento dell’algoritmo LRULRU
Pagina virtuale 7
Memoria centrale
Al termine dell’esecuzione delle
Pagina virtuale 3Pagina virtuale 4
Pagina virtuale 5
Pagina virtuale 7Pagina virtuale 6
Al termine dell esecuzione delleistruzioni di pagina 8 è necessariocaricare pagina 0 sostituendo la pagina utilizzata meno di recente, ossia pagina 1
-- 4242 --
Pagina virtuale 8Pagina virtuale 1
Pagina virtuale 2
Pagina virtuale 0
22
Pag. 22
Fallimento dell’algoritmo Fallimento dell’algoritmo LRULRU
Pagina virtuale 7
Memoria centrale
Al termine dell’esecuzione delle
Pagina virtuale 3Pagina virtuale 4
Pagina virtuale 5
Pagina virtuale 7Pagina virtuale 6
Al termine dell esecuzione delleistruzioni di pagina 0 è necessariocaricare nuovamente pagina 1 sostituendo la pagina utilizzata meno di recente, ossia pagina 2
-- 4343 --
Pagina virtuale 8Pagina virtuale 0
Pagina virtuale 2 Pagina virtuale 1
E così via.....
Algoritmo Algoritmo LRULRU
Fallisce quando il working set è di poco maggiore del numero di pagine disponibili in memoria centraleNel caso trattato nell’esempio il working set è di una pagina Nel caso trattato nell esempio, il working set è di una pagina superiore al numero di pagine disponibili in memoriaSe l’accesso alle pagine è sequenziale, in questo caso si sostituisce sempre la pagina che verrà richiesta subito dopo!
-- 4444 --
23
Pag. 23
Algoritmo di sostituzione FIFOAlgoritmo di sostituzione FIFO
Si mantiene l’informazione del momento in cui la pagina è stata caricata in memoria
Si i d i i fi i i i i l i Si associa un contatore ad ogni pagina fisica e inizialmente i contatori sono posti a 0
– al termine della gestione di un errore di pagina i contatori delle pagine fisiche presenti in memoria sono incrementati di 1
– il contatore della pagina appena caricata in memoria viene posto a 0
In caso di errore di pagina, la pagina da sostituire è quella con il valore del contatore più alto
-- 4545 --
– Il valore di contatore più alto significa che si tratta della pagina che ha assistito a più errori di pagina e quindi si trova in memoria da più tempo rispetto alle altre
Algoritmi di sostituzioneAlgoritmi di sostituzione
Anche l’algoritmo FIFO non ha un buon comportamento nel caso in cui il working set è di poco maggiore del numero di pagine disponibili in memorianumero di pagine disponibili in memoria
Non ci sono algoritmi che danno buoni risultati in questo caso
Un programma che genera errori di pagina frequenti si dice in trashing (situazione poco auspicabile)
-- 4646 --
dice in trashing (situazione poco auspicabile)
24
Pag. 24
Sostituzione e scrittura in memoriaSostituzione e scrittura in memoria
Nel caso di scrittura, la modifica avviene solo nelle pagine in memoria e non viene riportata immediatamente nelle pagine su disco (i tempi di accesso al disco molto elevati rispetto ai tempi di
ll i )accesso alla memoria)In caso di errore di pagina è necessario individuare se la pagina da scaricare è stata o meno modificata (bit di modifica)
– Solo se la pagina da scaricare è stata modificata è necessario copiarla su disco prima di sostituirla
– Le pagine contenenti istruzioni non possono essere modificate quindi non devono essere copiate su disco
Le pagine di un processo contenenti dati e/o allocate
-- 4747 --
Le pagine di un processo contenenti dati e/o allocate dinamicamente devono essere salvate nello swap file, nel quale viene salvata l’immagine delle pagine quando vengono scaricate
Sostituzione e scrittura in memoriaSostituzione e scrittura in memoria
Nella MMU si associa un bit (bit di modifica) ad ogni pagina fisica per indicare se la pagina è stata o meno modificataIl bit di modifica viene azzerato quando la pagina viene caricata in Il bit di modifica viene azzerato quando la pagina viene caricata in memoria e posto a 1 ogni volta che viene scritta una parola di tale pagina. Quando una pagina deve essere sostituita, il SO verifica il bit di modifica per stabilire se la pagina debba essere copiata su disco
-- 4848 --
25
Pag. 25
3. Dimensionamento delle pagine:3. Dimensionamento delle pagine:frammentazione della memoria frammentazione della memoria
Ad ogni programma viene sempre assegnato un numero intero di pagine, però possono rimanere aree di memoria assegnate ma non occupate: p
• Programma + dati = 26.000 Byte• Pagine di 4kByte (4096 Byte)• Numero di pagine: 26000/4096 ≈ 6.34
necessarie 7 pagine, ma l’ultima pagina è occupata per 1424 Byte e verranno sprecati 2672 Byte
Per pagine di n Byte la quantità media di spazio di memoria sprecato nell’ultima pagina sarà di n/2 Byte, questo porterebbe a ridurre le
-- 4949 --
nell ultima pagina sarà di n/2 Byte, questo porterebbe a ridurre le dimensioni della pagina per minimizzare lo sprecoPagine piccole numero di pagine
– dimensioni della tabella delle pagine– dimensioni della MMU– trasferimenti da disco
Dimensionamento delle pagine: trasferimenti da disco Dimensionamento delle pagine: trasferimenti da disco
Pagine piccole riducono l’efficienza dei trasferimenti dal disco:– Pagine più piccole richiedono più trasferimenti – Tempo di ricerca della pagina su disco + ritardo di rotazione
≈ 10 msec– Tempo di trasferimento di una pagina di 1KByte a 10MB/sec
richiede circa 0.1 msec– Il peso del tempo di trasferimento è di due ordini di grandezza
inferiore al tempo di ricerca
-- 5050 --
26
Pag. 26
Dimensionamento delle pagine: caratteristiche Dimensionamento delle pagine: caratteristiche del programmadel programma
Pagine piccole portano a meno trashing se il programma lavora su regioni piccole e separate all’interno dello spazio di indirizzamento
E iEsempio– matrice di 10000×10000 elementi memorizzata per righe con elementi
di 8 Byte. E’ prevista elaborazione su una colonna intera (gli elementi di una generica colonna sono a distanza di 80.000 Byte l’uno dall’altro)
– elaborazione su una colonna intera: per avere tutti gli elementi in memoria:
• con pagine da 8KB sono necessari 80MB1 elemento in memoria 8K 10000 elementi 8x107 80MB
-- 5151 --
– 1 elemento in memoria = 8K, 10000 elementi = 8x107= 80MB• con pagine da 1KB sono necessari 10MB
– 1 elemento in memoria = 1K, 10000 elementi = 1x107= 10MB
• se la memoria disponibile è di 32 MB il programma andrebbe in trashing con pagine da 8KB.
SegmentazioneSegmentazione
Nella paginazione, per ogni processo, si considera un unico spazio di indirizzamento virtuale lineare e indifferenziato
Lo spazio di indirizzamento virtuale può essere diviso in un insieme di spazi virtuali indipendenti dal punto di vista logico. Ad es. codice, dati, stack.
Gli spazi di indirizzamento virtuali indipendenti vengono chiamati segmenti
-- 5252 --
27
Pag. 27
Struttura dei segmentiStruttura dei segmenti
Ogni segmento è composto da una sequenza lineare di indirizzi.
Ogni segmento è caratterizzato da una coppia di indirizzi virtuali che Ogni segmento è caratterizzato da una coppia di indirizzi virtuali che ne definiscono l’inizio e la fine
Poiché la segmentazione delle aree virtuali si appoggia sulla paginazione della memoria fisica → i segmenti devono essere costituiti da un numero intero di pagine → è sufficiente avere un NPViniziale e un NPVfinale
Segmenti
-- 5353 --
Librerie dinamiche StackDati Statici
Condivisa (Codice, ma anche dati tramite
opportune dichiarazioni fornite dal S.O. per la comunicazione tra processi tramite condivisione della memoria)
Dati dinamici(heap)
Codice
Segmenti Segmenti -- VantaggiVantaggi
E’ possibile definire diversi diritti di accesso a seconda del segmento
I segmenti possono modificare la loro lunghezza in fase di esecuzione (ad esempio lo stack o i dati dinamici) e ogni segmento può crescere indipendentemente, senza creare problemi ad altri segmenti
E’ possibile individuare aree di memoria “logiche” da condividere come le librerie
-- 5454 --
Semplifica la gestione del collegamento di procedure compilate separatamente, ognuna in un segmento separato
28
Pag. 28
Struttura dello spazio di indirizzamento virtuale Struttura dello spazio di indirizzamento virtuale di un programma segmentato (exec)di un programma segmentato (exec)
Spazio di0Librerie condivise
Dati statici
Codice
pindirizzamento di un programmain esecuzione
Crescita heap
Librerie condivise
Dati dinamici
-- 5555 --
stackmax
Crescita heap
Crescita stack
Spazio libero per crescita dati e stack
Eventuale area condivisa
Crescita delle aree dati dinamicheCrescita delle aree dati dinamiche
Lo stack cresce automaticamente ad ogni attivazione di funzione, senza istruzioni o funzioni di sistema esplicite
Lo heap cresce tramite invocazione esplicita di servizi di sistema (la funzione malloc può chiamare al suo interno tali servizi)Il servizio di sistema LINUX che incrementa lo heap è la funzione
* void sbrk (int incremento)– che incrementa l’area di heap di un n° di pagine pari all’intero
superiore di (incremento/dimensione della pagina) e restituisce
-- 5656 --
superiore di (incremento/dimensione della pagina) e restituisce l’indirizzo iniziale della nuova area
29
Pag. 29
Confronto tra paginazione e segmentazioneConfronto tra paginazione e segmentazione
SegmentazionePaginazione
SISISpazio virtuale > spazio fisico di memoria?
Molti1Spazi di indirizzamento
SINOVisibilità al programmatore
-- 5757 --
Motivo della tecnica?Simulare memorie molto grandi
Fornire spazi multipli di indirizzamento
Indirizzo virtuale all’interno di un segmentoIndirizzo virtuale all’interno di un segmento
Lo spazio di indirizzamento virtuale di ogni segmento è lineare (indirizzi virtuali contigui) ed è suddiviso in un ( g )numero intero di pagine di dimensione fissa
Quindi all’interno di ogni segmento l’indirizzo virtuale può essere visto come
Numero pagina virtuale nel Spiazzamento nella pagina
-- 5858 --
p gsegmento
p p g
30
Pag. 30
Rappresentazione dello spazio di indirizzamento Rappresentazione dello spazio di indirizzamento virtuale del processo virtuale del processo
0
1 Segmento codice0
1
2
D
3Segmento dati
NPV del processo
0
1
NPV dei singoli segmenti
-- 5959 --
Lo spazio di indirizzamento virtuale di un processo è rappresentato in segmenti contigui, suddivisi in pagine, il cui riferimento è assoluto rispetto al processo
F
D
Stack0
Lo spazio di indirizzamento fisico (ossia della memoria centrale) viene suddiviso in un numero intero di pagine di uguale dimensione di quelle utilizzate per lo spazio di indirizzamento virtuale
Struttura dell’indirizzo fisicoStruttura dell’indirizzo fisico
di quelle utilizzate per lo spazio di indirizzamento virtuale
– Ogni pagina fisica della memoria può quindi contenere esattamente una pagina dello spazio di indirizzamento virtuale (stesso offset nella pagina virtuale e fisica)
Numero Pagina Fisica (NPF) Spiazzamento nella pagina
-- 6060 --
La MMU traduce in modo automatico l’indirizzo virtuale in indirizzo fisico tramite opportune tabelle
31
Pag. 31
Tabelle per la segmentazioneTabelle per la segmentazione
Per la traduzione dell’indirizzo virtuale in indirizzo fisico è necessaria:
– una tabella dei segmenti del processo• una riga per ogni segmento• ogni riga contiene la pagina virtuale d’inizio del segmento stesso
– la tabella delle pagine per ogni processo (con una riga per ogni pagina dello spazio di indirizzamento virtuale del processo)
Questa tabella ha la stessa struttura di quella vista nella
-- 6161 --
• Questa tabella ha la stessa struttura di quella vista nella paginazione e una parte dell’insieme delle tabelle dei processi possono essere implementate in modo più efficiente in MMU con una tabella associativa (MMU Table).
Segmentazione: calcolo dell’indirizzoSegmentazione: calcolo dell’indirizzo
# segmento # pagina virtuale spiazzamento
indirizzo virtuale
g p gnel segmento
pnella pagina
# segm NPVinizio
+NPV
PID NPV NPF
-- 6262 --
PID corrente
Tabella dei segmenti del processoTabella delle pagine del processo
(in MMU)NPV del processo
32
Pag. 32
Segmentazione: calcolo dell’indirizzoSegmentazione: calcolo dell’indirizzo
# segmento # pagina virtualenel segmento
Spiazzamentonella pagina
Dato un processo in esecuzione (PID), un indirizzo virtuale e il segmento cui appartiene:
– con #segmento si accede alla tabella dei segmenti del processo e si ottiene il # pagina virtuale d’inizio del segmento
– # pagina virtuale d’inizio + # pagina virtuale nel segmento = NPV del processo
-- 6363 --
NPV del processo
– con PID, NPV si accede alla tabella associativa (MMU Table) per recuperare NPF
– Al valore NPF viene giustapposto lo spiazzamento (offset) nella pagina per completare l’indirizzo fisico.
EsempioEsempio
Due processi P e Q Spazio di indirizzamento virtuale per ogni processo: 64KDi i d ll iDimensione delle pagine 4KSpazio di indirizzamento fisico 16M
→ Num. pagine virtuali per ogni processo = 64K /4 K = 16 pagine virtuali (4 bit NPV)→ Num. pagine fisiche = 16 M /4 K = 4 K pagine fisiche (12 bit NPF)Struttura degli indirizzi:
indirizzo virtuale: b
-- 6464 --
– 16 bit: 4 bit per NPV (16 pagine virtuali per ogni processo) e 12 bit per offset nellapagina
indirizzo fisico:– 24 bit: 12 bit per NPF (4K pagine fisiche in memoria centrale) e 12 bit per offset
nella pagina
33
Pag. 33
Caratteristiche iniziali dei segmentiCaratteristiche iniziali dei segmenti
Processo PCP (codice) = 7K (condiviso con processo R)DP (dati) = 9KDP (dati) = 9KPP (pila) = 4KCOND (dati condivisi con processo Q) = 6K
Processo QCQ (codice) = 7K (condiviso con processo S)DQ (dati) = 19KPQ (pila) = 4K
-- 6565 --
COND (dati condivisi con processo P) = 6K
In entrambi i processi il segmento COND è allocato lasciando 3 pagine libere dopo il segmento dati iniziale per permettere la crescita dello heap
SpazioSpazio didi indirizzamentoindirizzamento virtualevirtuale e e paginepagine virtualivirtuali per per processoprocesso
Processo P Processo Q
0 CP0 0 CQ 01 CP1 1 CQ 11 CP1 1 CQ 12 DP0 2 DQ03 DP1 3 DQ14 DP2 4 DQ25 5 DQ36 6 DQ47 78 COND0 89 COND1 9A A COND0
-- 6666 --
A A COND0B B COND1C CD DE EF PP0 F PQ0
34
Pag. 34
Tabelle dei segmenti e MMUTabelle dei segmenti e MMU
# s e g m e n to # p a g in a v ir tu a le n e l s e g m e n to
s p ia z z a m e n to n e lla p a g in a
PID NPV NPFP
+NPV
#seg NPViniz
C 0
D 2
Cond 8
P F
P 0 27
P 1 52
P 2 60
P 3 33
P 4 41
P 8 15
PID corrente:P
#seg NPV
Q
-- 6767 --
P 8 15
P 9 21
P F 77
Q A 15
Q B 21
Q 0 54
#seg NPViniz
C 0
D 2
Cond A
P F
Considerazione: P e QConsiderazione: P e Q
I processi P e Q NON possono condividere il segmento dati perché, come si vede dalla allocazione delle pagine virtuali, hanno segmenti dati che possono raggiungere dimensioni differenti:p gg g
– P può avere fino a 3 + 3 = 6 pagine di dati dinamici– Q può avere fino a 5 + 3 = 8 pagine di dati dinamici
Anche i segmenti stack possono raggiungere dimensioni differenti.
La definizione della dimensione dei segmenti avviene in fase di linking.
Ovviamente P e Q possono condividere il codice con altri processi (R e S).
-- 6868 --
)
35
Pag. 35
LINUX e la gestione della memoria (1) LINUX e la gestione della memoria (1)
Fork ( )• L’esecuzione della fork crea un nuovo processo che è
l’immagine del padre
• Viene aggiornata la tabella dei processi, ma non viene allocata memoria fisica e i segmenti virtuali vengono condivisi; viene duplicata la pagina di pila caricata più recentemente
• All’atto di una scrittura in memoria (segmento dati), da
-- 6969 --
parte di uno dei due processi, la pagina dati scritta viene effettivamente allocata (le pagine relative a segmenti virtuali contenenti dati vengono inizialmente poste con diritto di accesso in sola lettura)
LINUX e la gestione della memoria (2) LINUX e la gestione della memoria (2)
Exec ( )L’esecuzione della exec pone a NON VALIDO tutte le pagine • L esecuzione della exec pone a NON VALIDO tutte le pagine relative a codice e dati del processo
• Tramite la tecnica di demand paging vengono caricate le pagine di codice e dati del programma lanciato in esecuzione
-- 7070 --
36
Pag. 36
LINUX e la gestione della memoria (3) LINUX e la gestione della memoria (3)
Nel caso di page fault o errore di accesso ad una pagina virtuale V
Se la pagina V appartiene allo spazio di indirizzamento virtuale del processo, LINUX verifica i diritti di accesso:
– se l’accesso è legittimo (page fault), viene invocata la routine swap_in di caricamento della pagina da disco in memoria centrale
– se l’accesso non è legittimo
-- 7171 --
se l accesso non è legittimo• se violazione in scrittura dopo fork, allora viene creata e allocata una
copia della pagina
• altrimenti il programma viene abortito
LINUX e la gestione della memoria (4) LINUX e la gestione della memoria (4)
Nel caso di page fault o errore di accesso ad una pagina virtuale V
Se la pagina V non appartiene allo spazio di indirizzamento virtuale del processo:
– se si tratta di crescita dello stack, una nuova pagina viene allocata per lo stack
– altrimenti il programma viene abortito
-- 7272 --
Se per l’allocazione di una nuova pagina in memoria non esistono pagine libere, LINUX invoca la routine swap_out di scaricamento di una pagina secondo un algoritmo basato sulla tecnica LRU
Top Related