Gestione della memoria
•
•
•
Per poter essere eseguiti, i programmi devono essere portati in memoria e posti
all’interno di un processo.
Coda di Input – collezione di processi sul disco che sono in attesa di essere portati
in memoria per essere eseguiti.
I programmi utente passano attraverso vari stati prima di essere eseguiti.
L’associazione (binding) di istruzioni e dati a indirizzi di memoria può essere
effettuata in qualunque fase del seguente percorso
•
•
•
Compilazione: Se la posizione in memoria è nota a priori, si può generare
un codice assoluto; se la locazione di inizio cambia, è necessario
ricompilare il codice.
Caricamento: Se la posizione in memoria non è nota a priori, è necessario
generare codice rilocabile.
Esecuzione: Se il processo può essere spostato durante la sua esecuzione
da un segmento di memoria in un altro, il binding viene rimandato fino al
momento dell’esecuzione. E’ necessario un opportuno supporto hardware
per mappare gli indirizzi (ad esempio con i registri base e limite).
Sistemi Operativi
8.1
Caricamento dinamico
•
•
•
•
I sottoprogrammi non vengono caricati fino a che non vengono
chiamati.
Si ha un miglior impiego della memoria: sottoprogrammi non
utilizzati non vengono mai caricati.
Utile quando si richiedono grandi quantità di codice per gestire
situazioni che avvengono raramente.
Al Sistema Operativo non è richiesto alcun supporto speciale.
Viene implementato attraverso un opportuno progetto dei
programmi.
Sistemi Operativi
8.2
Link dinamico delle librerie
•
•
Il linking viene rinviato fino al momento dell’esecuzione.
•
Lo stub rimpiazza se stesso con l’indirizzo della routine ed esegue
la routine.
•
Piccole porzioni di codice (dette stub) vengono impiegate per
localizzare la routine appropriata nella libreria residente in
memoria.
Il Sistema Operativo deve verificare che la routine si trovi nello
spazio degli indirizzi (in memoria) del processo.
Sistemi Operativi
8.3
Overlay
•
Si mantengono in memoria solo quelle istruzioni e quei dati che
vengono richiesti ad un dato istante. Quando sono necessarie
altre istruzioni, queste vengono caricate nello spazio che era
precedentemente occupato dalle istruzioni che non vengono più
utilizzate.
•
E’ richiesto quando un processo è più grande della memoria
allocatagli.
•
L’esecuzione è rallentata a causa dell’operazione di I/O
necessaria per caricare l’overlay.
•
Viene implementato dall’utente, non viene richiesto alcun
supporto speciale da parte del Sistema Operativo. Il progetto di
programmi con strutture di overlay è complesso.
Sistemi Operativi
8.4
Spazi di indirizzi logici e fisici
•
•
•
•
Il concetto di uno spazio degli indirizzi logico che viene limitato ad uno spazio
degli indirizzi fisico è centrale per una corretta gestione della memoria.
– Indirizzo logico – viene generato dalla CPU; viene anche indicato come
indirizzo virtuale.
– Indirizzo fisico – indirizzo visto dall’unità di memoria.
Gli indirizzi logico e fisico sono gli stessi negli schemi di associazione degli
indirizzi compile-time e load-time; gli indirizzi logico (virtuale) e fisico sono
diversi nello schema di associazione execution-time.
La MMU (Memory Management Unit) è un dispositivo hardware che
trasforma l’indirizzo virtuale nell’indirizzo fisico. Nello schema di MMU il
valore nel registro di rilocazione viene sommato a qualunque indirizzo
generato da un processo utente nel momento in cui viene inviato alla
memoria.
Il programma utente ha a che fare con indirizzi logici, non “vede” mai gli
indirizzi fisici reali.
Sistemi Operativi
8.5
Swapping
•
Un processo può venir temporaneamente riversato (swapped) dalla memoria
centrale alla backing store da cui, in seguito, viene portato nuovamente in
memoria per proseguire l’esecuzione.
•
Backing store – E’ un disco veloce, sufficientemente capiente da accogliere
copie di tutte le immagini di memoria per tutti gli utenti. Può essere una
partizione dedicata del disco (pochi movimenti della testina).
•
Roll out, roll in – E’ una variante dello swapping impiegata per algoritmi di
scheduling basati su priorità; un processo a priorità più bassa viene riversato
sulla memoria di massa, in modo tale da permettere che un processo a
maggior priorità sia caricato ed eseguito.
•
•
•
La maggior quantità di tempo è impiegata per il trasferimento; il tempo totale
di trasferimento è direttamente proporzionale alla quantità di memoria
riversata.
Se il binding viene effettuato al tempo dell’esecuzione, il processo può essere
riversato in uno spazio di memoria diverso.
UNIX e Microsoft Windows supportano lo swapping.
Sistemi Operativi
8.6
Swapping
Sistemi Operativi
8.7
Allocazione contigua
•
•
La memoria principale viene generalmente suddivisa in due
partizioni:
– La parte residente del Sistema Operativo è generalmente
memorizzata nella parte bassa della memoria, insieme al
vettore degli interrupt.
– I processi degli utenti sono quindi memorizzati nella memoria
alta.
Allocazione con partizione singola
– Si impiega uno schema di rilocazione basato su registri per
proteggere i programmi e i dati del SO e per proteggere
reciprocamente i programmi utente.
– Il registro di rilocazione contiene il valore del più piccolo
indirizzo fisico; il registro limite contiene l’intervallo degli
indirizzi logici: ciascun indirizzo logico deve essere inferiore
al valore del registro limite.
Sistemi Operativi
8.8
Allocazione contigua
•
Allocazione con partizioni multiple
– Inizialmente si avevano partizioni di dimensioni fisse.
– Un buco (hole) è un blocco di memoria disponibile, buchi di varie
dimensioni sono sparsi nella memoria.
– Quando viene caricato un processo, gli viene allocata la memoria di
un buco grande abbastanza da contenere il processo.
– Il SO conserva informazioni su:
a) Partizioni allocate b) Partizioni libere (buchi)
OS
OS
OS
OS
process 5
process 5
process 5
process 5
process 9
process 9
process 8
process 2
Sistemi Operativi
process 10
process 2
process 2
8.9
process 2
Problemi dell’allocazione dinamica della memoria
Come soddisfare una richiesta di dimensione n a partire da un insieme di buchi?
In ogni momento è presente un insieme di buchi di diverse dimensioni sparsi per
la memoria.
•
•
•
First–fit: Si alloca il primo buco grande abbastanza.
Best–fit: Si alloca il più piccolo buco che possa contenere il
processo. E’ necessario scandire tutta la lista dei buchi. Si
produce il più piccolo buco residuo.
Worst–fit: Si alloca il più grande buco. E’ ancora necessario
ricercare su tutta la lista. Si produce il più grande buco residuo.
First-fit e best-fit sono meglio di worst-fit in termini di velocità e
impiego di memoria.
Sistemi Operativi
8.10
Frammentazione
•
Frammentazione esterna – E’ disponibile lo spazio per soddisfare
la richiesta, ma non è contiguo.
•
Frammentazione interna – la memoria allocata può essere
leggermente maggiore della memoria richiesta (qualche byte di
differenza). Questa differenza di dimensioni è memoria interna ad
una partizione che non viene impiegata.
•
Si può ridurre la frammentazione esterna con la compattazione
– Sposta i contenuti della memoria per avere tutta la memoria
libera insieme in un grande blocco.
– La compattazione è possibile solo con la rilocazione
dinamica, e viene effettuata nel momento dell’esecuzione
(execution time).
– Si possono spostare tutti i processi verso un’estremità della
memoria (questo schema è costoso).
Sistemi Operativi
8.11
Paginazione
•
•
•
•
•
•
•
Un’altra soluzione alla frammentazione esterna è ottenuta
consentendo la non contiguità degli indirizzi logici, permettendo
così di allocare la memoria fisica ai processi ovunque essa sia
disponibile.
Si divide la memoria fisica in blocchi di dimensione fissa chiamati
frame (la dimensione è una potenza di 2, fra 512 byte e 8192
byte).
Si divide la memoria logica in blocchi della stessa dimensione
chiamati pagine.
Si tiene traccia di tutti i frame liberi.
Per eseguire un programma con dimensione di n pagine, è
necessario trovare n frame liberi prima di caricare il programma.
Si impiega una tabella delle pagine per tradurre gli indirizzi logici
negli indirizzi fisici.
Si ha solo frammentazione interna (relativa all’ultimo frame).
Sistemi Operativi
8.12
Paginazione
•
L’indirizzo generato dalla CPU viene suddiviso in:
– Numero di pagina (p) – impiegato come indice in una tabella di pagine
che contiene l’indirizzo di base di ciascuna pagina nella memoria fisica.
– Offset nella pagina (d) – viene combinato con l’indirizzo di base per
definire l’indirizzo fisico di memoria che viene inviato all’unità di memoria.
Sistemi Operativi
8.13
Esempio di paginazione
Sistemi Operativi
8.14
Tabella delle pagine
•
•
•
•
•
•
La tabella delle pagine risiede in memoria centrale. Si ha una tabella per ogni
processo.
Il registro Page-Table Base Register (PTBR) punta alla tabella.
Il registro Page-Table Length Register (PRLR) indica la dimensione della tabella.
Con questo schema, ogni accesso a dati o istruzioni richiede di fatto due accessi
alla memoria: uno per la tabella e uno per le istruzioni/dati.
Il problema dei due accessi alla memoria può essere risolto per mezzo dei registri
associativi con i quali si ha una ricerca parallela veloce su una piccola tabella.
Pagina #(A´,
| Frame
Traduzione dell’indirizzo
A´´) #
– Se A´ si trova nel registro associativo, si prende frame # dal registro (A´´).
– Altrimenti si prende frame # dalla tabella delle pagine in memoria
Sistemi Operativi
8.15
Tempo di accesso effettivo
•
•
•
•
Lookup associativo =  unità di tempo.
Si suppone che un ciclo di memoria duri 1 microsecondo.
Hit ratio – percentuale di volte che un numero di pagina viene
trovato nei registri associativi; è correlato con il numero di registri
associativi. Si indica hit ratio = .
Tempo di accesso effettivo (EAT)
EAT = (1 + )  + (2 + )(1 – )
=2+–
Sistemi Operativi
8.16
Protezione della memoria
•
•
La protezione della memoria è implementata associando un bit di
protezione a ciascun frame. Vengono impediti accessi non
autorizzati (eventualmente si possono avere bit separati per
lettura e scrittura).
Un ulteriore bit di validità viene considerato in ogni elemento della
tabella delle pagine:
– Un valore “valid” indica che la pagina associata è nello
spazio logico del processo, e quindi è una pagina legale.
– Un valore “invalid” indica che la pagina non si trova nello
spazio logico del processo.
Sistemi Operativi
8.17
Paginazione a due livelli (esempio)
•
•
•
Un indirizzo logico (in macchine a 32-bit con dimensione della
pagina di 4K) viene suddiviso in:
– un numero di pagina di 20 bit.
– Un offset nella pagina di 12 bit.
Dato che la tabella di paginazione (essendo grande) è a sua volta
paginata, il numero di pagina viene ulteriormente suddiviso in:
– un numero di pagina di 10-bit.
– Un offset nella pagina di 10-bit.
Quindi un indirizzo logico è costituito nel seguente modo:
Numero di pag
Offset in pagina
p1
p2
d
10
10
12
dove p1 è un indice nella tabella esterna, e p2 è lo spostamento
dentro la pagina della tabella esterna.
Sistemi Operativi
8.18
Paginazione a due livelli (esempio)
•
•
Sistemi Operativi
8.19
Dato che ciascun livello viene
memorizzato come una tabella
separata in memoria, la traduzione
di un indirizzo logico in uno fisico
può richiedere quattro accessi alla
memoria.
Anche se il tempo richiesto per un
accesso alla memoria è
quintuplicato, la presenza di cache
consente di avere prestazioni
ragionevoli.
Tabella delle pagine invertita
•
•
•
•
Si ha un elemento della tabella per ogni pagina reale (frame) della
memoria.
Gli elementi della tabella contengono l’indirizzo virtuale della
pagina con informazioni sul processo che possiede tale pagina.
Viene ridotta la memoria richiesta per memorizzare ciascuna
tabella di pagina, ma viene incrementato il tempo necessario per
ricercare nella tabella quando si ha un riferimento alla pagina.
Notare che è necessario ricercare su tutta la tabella! Si impiegano
tabelle hash per limitare la ricerca ad uno — o al più pochi —
elementi della tabella.
Sistemi Operativi
8.20
Architettura della tabella invertita
Ciascun indirizzo virtuale è formato dalla tripla:
<# processo, #pagina, offset>
Sistemi Operativi
8.21
Pagine condivise
•
•
Codice condiviso
– Una copia di codice a sola lettura (reentrant) viene condivisa
fra processi (ad esempio: text editors, compilatori, sistemi a
finestre).
– Il codice condiviso deve apparire nella stessa locazione nello
spazio logico di tutti i processi.
Codice e dati privati
– Ciascun processo mantiene una copia separata dei dati e
del codice.
– Le pagine del codice e dei dati privati possono apparire
ovunque nello spazio degli indirizzi logico.
Sistemi Operativi
8.22
Esempio di pagine condivise
Editor contenuto in tre pagine
Sistemi Operativi
8.23
Segmentazione
•
Schema di gestione della memoria che asseconda la visione
utente (l’utente generalmente non pensa alla memoria come ad
un array lilneare di byte).
•
Un programma è una collezione di segmenti. Un segmento è una
unità logica, come ad esempio:
programma principale (main),
procedura,
funzione,
variabili logiche, variabili globali,
blocco comune,
stack,
tabella dei simboli, matrici.
Gli elementi che si trovano all’interno di un segmento sono
identificati dal loro offset.
Sistemi Operativi
8.24
Vista logica della segmentazione
1
4
1
2
3
2
4
3
Spazio dell’utente
Sistemi Operativi
Spazio fisico di memoria
8.25
Architettura della segmentazione
•
L’indirizzo logico è costituito da due elementi:
<segment-number, offset>
•
•
•
Tabella dei segmenti – mappa lo spazio degli indirizzi bidimensionale (visto dall’utente); ciascun elemento della tabella
contiene:
– base: contiene l’indirizzo fisico di partenza dello spazio di
memoria in cui risiedono i segmenti.
– limit: indica la lunghezza del segmento.
Segment-table base register (STBR) punta alla tabella dei
segmenti.
Segment-table length register (STLR) indica il numero di segmenti
usati da un programma;
un numero di segmento s è legale se s < STLR.
Sistemi Operativi
8.26
Architettura della segmentazione
•
•
•
•
•
•
Rilocazione: dinamica, con una tabella dei segmenti.
Condivisione: si hanno segmenti condivisi, puntando allo stesso
numero di segmento.
Allocazione: first fit/best fit. Si ha frammentazione esterna.
Protezione. Si associa a ciascun elemento della tabella dei
segmenti:
– bit di validità = 0  segmento illegale
– privilegi read/write/execute
Bit di protezione vengono associati con i segmenti; la condivisione
di codice viene implementata a livello di segmento.
Dato che i segmenti variano di dimensione, l’allocazione della
memoria è dinamica, con i relativi problemi.
Sistemi Operativi
8.27
Esempio di segmentazione
Sistemi Operativi
8.28
Segmentazione con paginazione – Intel 386
•
L’Intel 386 impiega una
segmentazione con
paginazione per la
gestione della memoria
con uno schema di
paginazione a due livelli.
Sistemi Operativi
8.29