GESTIONE DELLA MEMORIA
virtualizzazione
dell'interfaccia: avendo più processi in esecuzione
questi non possono “preoccuparsi” di condividere la
memoria con gli altri, quindi hanno uno spazio di memoria riservata,
anche se complessivamente questa è unica
gestire
la “competizione” per tale risorsa
deve
garantire:
rilocazione
protezione
= la memoria di un processo non può essere acceduta da altri
processi
condivisione
= deve esserci la possibilità di condividere le risorse
comuni (codice, librerie ecc.)
si
utilizza una divisione tra:
memoria logica = organizzata in base alle esigenze dei
processi
memoria fisica = organizzata per garantire
l'efficienza del sistema
RILOCAZIONE DELLA MEMORIA
la posizione di un processo in memoria è nota solo al momento
dell'esecuzione
indirizzo
logico = indirizzo generato dalla CPU
indirizzo
fisico = indirizzo visto dalla memoria, ossia caricato nel MAR
(memory address register)
multi-tasking
(time-sharing) rende necessaria la rilocazione
= un programma deve essere allocabile in un qualsiasi punto
della memoria (blocco di memoria)
ASSOCIAZIONE DI INDIRIZZI E DATI A INDIRIZZI DI
MEMORIA

tipi di
associazione degli indirizzi (in base al momento in cui si associano
le istruzioni di dati agli indirizzi di memoria):
alla
compilazione (come i .com del DOS) = il compilatore genera
codice assoluto; al tempo andava bene perchè non c'era il
multi-tasking
al
caricamento = il compilatore genera codice rilocabile che viene
istanziato al momento del caricamento (tengo traccia dei valori che
indicano gli indirizzi, i quali devono essere rilocabili; nel
momento in cui vado a rilocare, per trovare l'indirizzo nella
memoria riservata, vado a sommare il valore di cui ho tenuto traccia
(nel registro di rilocazione) a quello che indica l'inizio
della sezione di memoria riservata); tutto questo viene eseguito dal
sistema operativo
durante
l'esecuzione = gli indirizzi sono tradotti al volo da un
“hardware specifico” (il programma viene
compilato come se dovesse essere eseguito nei primi indirizzi di
memoria; poi all'esecuzione di ogni istruzione, grazie a un
meccanismo hardware di traduzione, la memoria virtuale, il PC si
sposta all'indirizzo giusto)
i primi
due tipi generano indirizzi fisici e logici identici, con l'ultimo
tipo invece sono diversi e gli indirizzi logici vengono chiamati
indirizzi virtuali
in ogni
caso il programma non lavora mai (a parte nel primo caso) con
indirizzi fisici reali, è l'architettura che si occupa
successivamente di convertirli
SEGMENTAZIONE
un
programma richiede diverse risorse:
se io
avessi un unico blocco con codice, dati e librerie, tutto in un unica
locazione (assegnazione contigua), non potrei condividere tali
risorse, dovrei copiarle per ogni processo
con la
segmentazione vengono specificati segmento e offset: questo permette
all'utente di vedere la memoria divisa in segmenti diversi, e gli
permette di condividerli tra i processi
questo
tipo di allocazione senza paginazione viene utilizzato in determinati
casi (kernel) perchè risulta più efficiente
ASSEGNAZIONE CONTIGUA: TECNICHE
DI PARTIZIONAMENTO DELLA MEMORIA
ci
sono 4 algoritmi di posizionamento
dei blocchi in memoria:
First
fit = il più semplice: inserisce il blocco nella prima
zona libera abbastanza grande a contenerlo; l'inserimento spezza la
zona in due parti, una
per il processo e una non utilizzata; lascia un blocco
grande in fondo e non frammenta in blocchi troppo piccoli
Best
fit = metto il blocco nella più piccola zona libera che
riesce a contenerlo -> problema: come faccio a calcolare la
dimensione del blocco più grande? può darsi che non
sia sufficiente per l'esecuzione se il programma è di
dimensioni maggiori
Worst
fit = vado ad occupare la zona libera più grande
Next
fit = come
First fit ma ad ogni ricerca si inizia dal punto lasciato dalla
ricerca precedente; prestazioni leggermente peggiori di First fit
le
tecniche di partizionamento possono essere di 3 tipi:
partizionamento
fisso = la memoria viene partizionata in zone di dimensione
prefissata (es. 500 blocchi grandi x, 1000 grandi y, e così
via...); viene utilizzato l'algoritmo Best fit, ricordando che ogni
zona potrà contenere un solo blocco di dati
partizionamento
dinamico = non c'è prepartizionamento e alloco un blocco
in una zona di memoria non allocata; il rischio è quello
della frammentazione esterna -> in questo caso la politica
Best-fit non va bene in quanto frammenta la memoria in zone libere
troppo piccole; utilizzo una politica Worst-fit: -> tende a non
lasciare zone libere grandi, quindi potrebbe provocare problemi in
caso di programmi di grosse dimensioni, in quanto vado sempre a
occupare la zona libera più grande, anche se si liberano
altre zone più piccole; la politica migliore è la
First-fit
“ibrido”
(buddy system, utilizzato ad esempio nel kernel di linux)
ricordati
sempre che i processi possono terminare e quindi ci può essere
frammentazione
in
ordine di efficienza:
first
fit = migliore sia per velocità che per frammentazione
next
fit = frammenta il blocco alla fine, quindi lascia poco spazio per i
grandi processi
best
fit = lascia poco spazio difficilmente utilizzabile
worst
fit = non lascia grandi zone libere, quindi per inserire processi
grandi bisogna ricompattare i blocchi
es.
abbiamo dei blocchi di memoria di 400, 300, 200 Kb liberi; ci sono 5
processi di dimensione: 150, 250, 200, 250, 400 Kb;
allocare
i processi usando i 4 algoritmi di partizionamento
First
fit:

Best fit:

P1,
P2 e P3 trovano posto
P4
deve attendere che termini sia P1 che P2 (perché il blocco in
cui era inserito P1 è troppo piccolo)
P5
deve attendere che termini P3 (che occupa l'unico blocco in grado di
contenerlo)
Worst
fit:

Next fit:

P1,
P2 e P3 trovano posto
P4
deve attendere che termini sia P1 che P2 (occupano l'unico blocco in
grado di contenerlo)
P5
deve attendere P4 (occupa l'unico blocco in grado di contenerlo)
frammentazione
esterna = lo spazio di memoria totale è sufficiente a
soddisfare una richiesta ma non è contiguo, è possibile
però fare una deframmentazione
frammentazione
interna = ho una frammentazione dei frame che sono già
stati assegnati (nel partizionamento fisso), e quindi non posso né
deframmentare e né assegnare a due processi lo stesso frame
(proprio perché il partizionamento è fisso)
quando la
memoria è troppo frammentata si esegue una procedura di
deframmentazione:
da questo
punto di vista segmentazione e paginazione possono risultano metodi
alternativi alla deframmentazione vera e propria, perché
permettono che lo spazio di indirizzamento di un processo sia non
contiguo, e che i blocchi liberi necessari ad esso possano venir
presi ovunque
BUDDY-SYSTEM (BUDDY-HEAP)
ibrido
statico-dinamico (utilizzato ad esempio nel kernel di Linux)
statico
perché le dimensioni in cui posso spezzare i blocchi sono
prefissate: i blocchi possano essere spezzati ogni volta in 2
dinamico
perché ho la dinamicità nella gestione della memoria
nel numero dei blocchi

se devo
allocare un blocco ancora più piccolo, continuo a dividere i
blocchi in 2 finché non ne trovo uno che contiene il blocco
che mi interessa ma la cui dimensione non è maggiore del
doppio del blocco
2^U =
dimensione della memoria
2^L =
dimensione minima del blocco
2^L,
2^(L+1), 2^(L+2), 2^(L+3), ..., 2^U
quando
devo allocare un blocco di dimensione S cerca un esponente K
affinché:
2^(K-1) <
S <= 2^K
così
sono sicuro che quello è il blocco più piccolo che può
contenere S
la cosa
utile è che man mano che i blocchi si liberano vengono fusi
insieme nuovamente: quando libero un blocco se il vicino (buddy)
è anch'esso libero “fondo” i blocchi in un blocco
grande il doppio
per la
sua componente statica questo algoritmo non può evitare una
frammentazione interna:
minima
nel caso in cui la dimensione dei blocchi da allocare sia una
potenza di 2
massima
(< 50 %) nel caso in cui il blocco da allocare sia poco più
grande della metà del segmento in cui vado ad inserire il
blocco stesso (che potrei spezzare e non posso farlo)
media
(circa il 25 %)
PAGINAZIONE
è un metodo di gestione della
memoria che permette che lo spazio degli indirizzi fisici di un
processo (segmento) non sia contiguo

nella
figura qui sopra:
indirizzo
logico = indirizzo generato dalla CPU; formato da p (numero
di pagina) e d (scostamento di pagina)
indirizzo
fisico = indirizzo corrispondente nella memoria fisica: lo
scostamento resta lo stesso, cambia il numero di pagina che viene
fornito dalla tabella delle pagine, che converte il numero di pagina
logico
se gli
indirizzi logici possibili che la CPU può generare sono 2^m
(dove m dipende dall'architettura: 32 bit, 64 bit ecc.) allora:
si può
vedere la paginazione come una forma più avanzata di
rilocazione della memoria

TLB (translation lookaside buffer) = cache della
page table
viene
utilizzata per velocizzare le operazioni di traduzione indirizzo
logico-fisico, perchè la page table può diventare
troppo grande

perché
è importante la dimensione di una pagina:
la
dimensione tipica di una pagina è 4/8 Kb
4Kb =
2^12 byte
32 –
12 = 20 2^20 pagine = circa 1.000.000 di pagine
i sistemi
usano architetture con almeno 2 livelli di page table (Linux supporta
fino a 3 livelli)
il
programma utente vede la memoria come un unico spazio contiguo,
contenente solo il programma stesso; in realtà è sparso
nella memoria fisica che contiene anche altri programmi (mentre con
la segmentazione il programma è consapevole di avere più
“segmenti”)
i dati
sullo stato dei vari blocchi di memoria fisica vengono forniti al
sistema operativo dalla tabella dei blocchi di memoria
MEMORIA VIRTUALE
ci
permette di eseguire programmi che non sono allocati completamente in
memoria; la sua dimensione è indipendente da quella della
memoria fisica, questo comporta dei vantaggi:
alcune
pagine vengono mappate su frame di memoria fisica altre sul disco
per
distinguere le pagine in memoria da quelle su disco si ricorre a un
bit di validità:
in
caso di page fault viene lanciato un interrupt, e la pagina richiesta
viene caricata in un frame libero, con conseguente aggiornamento
della page table
schema
di base del comportamento della memoria virtuale in caso di page
fault:
individuazione
della locazione nel disco della pagina richiesta
ricerca
di un blocco di memoria libero:
se
esiste lo si usa
altrimenti
si impiega un algoritmo di sostituzione delle pagine per scegliere
un blocco di memoria vittima
si
scrive la pagina vittima sul disco (area di swap = avvicendamento);
si modificano conseguentemente le tabelle delle pagine e dei blocchi
di memoria
si
scrive la pagina richiesta nel blocco di memoria appena liberato; si
modificano le tabella delle pagine e dei blocchi di memoria
si
riavvia il processo utente

la
memoria virtuale generalmente si realizza nella forma della
paginazione
su richiesta = anziché
caricare dalla memoria secondaria (uno o più dischi) alla
memoria principale l'intero processo, il paginatore
(modulo del sistema operativo) trasferisce nella memoria solo le
pagine che ritiene
necessarie
un'altra
tecnica per realizzare la memoria virtuale consiste nel prepaging,
che anticipa il caricamento in memoria rispetto al momento dell'uso,
sfruttando il principio della località spaziale (conviene ad
esempio nel caso dello streaming audio/video)


abbiamo
bisogno di 2 algoritmi:
SOSTITUZIONE DELLE PAGINE
un
algoritmo di sostituzione è tanto migliore quanto più
limita i page fault (estremamente costosi per il sistema poiché
costringono ad accessi al disco = periferica meccanica e quindi
lenta)
osservazione:
in caso di page fault, se nessun blocco di
memoria è libero, si rendono necessari due trasferimenti di
pagina (uno fuori e uno dentro la memoria) -> raddoppia il tempo
di gestione dell'eccezione
ALGORITMO OTTIMO
la
vittima è la pagina che non si utilizzerà per il
periodo più lungo
si
tratta di un algoritmo puramente teorico, in quanto per riuscire a
implementarlo dovremmo conoscere in anticipo la sequenza di
riferimento
servirà
da metro di misura per valutare gli altri algoritmi con i
quali tenteremo di avvicinarci alla sua efficacia

6
page fault
ALGORITMO FIFO
la
vittima è la pagina da più tempo in memoria
si
può implementare con una coda FIFO (buffer circolare) delle
pagine
problemi:

situazione
con 3 frame:

situazione
con 4 frame: avendo più memoria avvengono addirittura più
page fault!

questo
accade perché non c'è nessuna relazione tra una colonna
e l'altra della tabella; con gli algoritmi che non soffrono
dell'anomalia di Belady una colonna di n frame della tabella risulta
essere sottoinsieme della colonna corrispondente nel caso di n+1
frame
ALGORITMO LRU
la
vittima è la pagina usata meno di recente (LRU = least
recently used)
sfrutta
il principio di località -> è molto valido
(approssima l'ottimo)
è
difficile da implementare (deve salvare il "tempo"
- la cpu ha un contatore degli accessi in memoria + essendo presente
una fase di ricerca è necessario dell'hardware costoso e
complesso per implementare tale funzione (o in alternativa un
notevole overhead software), vedi le 2 implementazioni sul libro)
anche
in questo algoritmo c'è una coda e ad ogni page fault il S.O.
la scansiona per trovare la pagina giusta con il tempo più
basso (quindi quello usato meno di recente)
non
soffre dell'anomalia di Belady

alternativamente
posso tenere una pila ordinata in base al tempo di accesso (i
processi utilizzati più recentemente sono in alto)

situazione
con 3 frame:

situazione
con 4 frame:

ALGORITMO DELL'OROLOGIO / SECONDA
CHANCE
si
mantiene una coda circolare (buffer circolare) delle pagine in
memoria con un puntatore che indica la prima pagina da sostituire
si
assegna a ciascuna pagina un bit di riferimento (inizialmente posto a
0 dal sistema operativo)
quando
una pagina è acceduta (vale sia se è
stata acceduta in lettura sia in scrittura) l'hardware pone tale bit
a 1
il
puntatore (lancetta) percorre la coda:
prima
di arrivare alla pagina con bit 0 il puntatore azzera tutti i bit di
riferimento delle pagine incontrate
quando
una pagina viene rimossa il puntatore si sposta alla successiva
una
volta trovata la pagina vittima la si sostituisce e viene inserita
nella coda circolare nella posizione corrispondente

la
lancetta si sposta solo in caso di page fault,
non se si verifica un hit
nel
caso peggiore, quando tutte le pagine hanno il bit di riferimento a
1, questo algoritmo si comporta come FIFO, ma nel caso medio è
molto efficace
ALGORITMO
DELL'OROLOGIO MIGLIORATO (CON 2 BIT / LANCETTE)
se
la memoria è molto grande la lancetta ci mette molto a
compiere un giro completo -> è possibile che restino in
memoria pagine a cui si è acceduto molto tempo prima
per
evitare questo problema si può ricorrere a una seconda
lancetta che segue la prima, azzerando gli accessi più
vecchi
più
le lancette sono vicine, più richiediamo che gli accessi
siano recenti
oltre
al bit di riferimento si può inserire un bit di modifica,
distinguendo così quattro casi (in ordine di adeguatezza per
la sostituzione):
(0,0)
né usata né modificata
(0,1)
non usata ma modificata
(1,0)
usata ma non modificata
(1,1)
usata e modificata
la
ricerca del candidato con questo schema dà risultati
migliori, ma è più
complessa da
implementare
MEMORIZZAZIONE TRANSITORIA
questo
sistema non ha bisogno di hardware specifico (a differenza ad esempio
dell'algoritmo dell'orologio)
prima
che la pagina vittima sia scritta nella memoria secondaria si
trasferisce la pagina vittima in un blocco di memoria libero del
gruppo (in una lista transitoria), così il processo non deve
attendere che la pagina vittima sia scritta in memoria secondaria;
quando in seguito si scrive la vittima nella memoria secondaria
allora si aggiunge il suo blocco di memoria al gruppo dei blocchi
liberi
in caso
di page fault prima si cerca la pagina
nella lista transitoria:


questa
tecnica è indipendente da come scelgo la pagina vittima
(algoritmi vari di sostituzione)
la lista
transitoria è in memoria fisica non su disco (è una
parte riservata a gestire questo buffer temporaneo; vedi figura
sotto)
un metodo
usato nel vax era una strategia di sostituzione FIFO (per scegliere
la vittima) unita a un buffer transitorio, il che migliorava molto le
prestazioni del FIFO da solo: praticamente dava una seconda chance
alle pagine prima che venissero salvate su disco e non fossero più
presenti in memoria (infatti finché restavano nel buffer
transitorio, in caso di page fault si poteva andare a recuperarle
senza accessi al disco)
es.

nella
figura sono indicati in grassetto i page fault veri, con accesso al
disco; gli altri sono gestiti con la memorizzazione transitoria
(in
realtà io non sto spostando dati da un frame a un altro, ma
cambio semplicemente i valori dei puntatori)
questo
sistema è più efficiente del FIFO ma meno rispetto
all'LRU
ASSEGNAZIONE DEI BLOCCHI DI MEMORIA
pochi
frame -> molti page fault
molti
frame -> pochi processi in memoria
abbiamo
2 criteri di valutazione per le strategie di allocazione:
ALGORITMI DI BASE
ASSEGNAZIONE UNIFORME
divide la
memoria fisica equamente tra i vari processi; non ha senso, perché
un processo più piccolo non richiede la stessa memoria di un
processo più grande
n
processi su m blocchi => m / n blocchi per processo
ASSEGNAZIONE
PROPORZIONALE
divide la
memoria in base alla dimensione della memoria virtuale dei processi
(ossia quella effettivamente utilizzata dal processo): se il processo
P ha una memoria virtuale di dimensione Si, faccio la somma S della
memoria utilizzata complessivamente da tutti i processi
Si / S =
frazione di memoria fisica che mi serve
es. 10 /
100 = 0,1 (mi serve 1/10 della memoria fisica)
la
moltiplico per la dimensione della memoria fisica M (numero di frame)
e ottengo la quantità di memoria fisica che assegno al
processo i-esimo:
Ai = (Si
/ S) * M
il
difetto di questo schema è che:
per fare
la load non riesco con un solo frame!! ancora peggio se ho load
indirette (ho bisogno di almeno tre frame in memoria)
in certe
architetture (quindi in base alle istruzioni hardware che ho a
disposizione) ho bisogno di almeno sei frame... quindi c'è
sempre un numero minimo di frame da concedere ad un processo
questa
tecnica è quindi troppo statica, abbiamo bisogno di un
qualcosa che cambi gli assegnamenti a run-time: non è detto
che in qualsiasi momento i processi abbiano sempre bisogno della
stessa quantità di memoria: oltretutto potremmo avere processi
grandi ma molto locali (pochi frame) o piccoli ma poco locali (molti
frame)
supponiamo
di avere un programma che aggiorna una matrice in base all'algoritmo
di aggiornamento per righe e per colonne (nel caso per colonne
abbiamo molti più page fault)
ALGORITMO DEL WORKING SET
tiene
conto della località (è variabile in ambito locale)
working
set = insieme delle pagine che vengono usate all'interno di una
finestra temporale
es.

in questo
caso il working set è l'insieme delle ultime d pagine
utilizzate
il
working set rappresenta una stima delle pagine attualmente in uso:
Wsj(Pi) =
working set all'istante j
dobbiamo
ridistribuire la memoria in base all'uso della stessa stimato dei
processi, quindi utilizziamo la proporzione:

dalla
quale ricaviamo:
Ai =
(WSj(Pi) / sommatoria|WSj| ) * M
dove
|WSj| = dimensione (cardinalità) del working set al
momento j
il
programma spostandosi nella memoria (ad esempio quando cambio
l'insieme di dati su cui lavoro), ingrandisce periodicamente il
working set, che poi si ristabilizza rimpicciolendosi nuovamente
nella nuova zona di memoria su cui il programma sta lavorando

questo
algoritmo distribuisce la memoria in modo proporzionale alla località
dei processi:
+
locale -> – frame
–
locale -> + frame
ossia si
rimuovono dall'insieme dei frame assegnati ad un processo le pagine
che non sono nel suo working set e si liberano frame
nel
momento in cui il sistema fa il calcolo può essere che la
somma sia più grande o più piccola del numero di frame
(i frame sono prefissati la somma è dinamica):
∑|WSj(Pi)|
> M (M = blocchi totali che formano la
memoria):
significa
che ci sono molti processi nel sistema (oppure che c'è poca
località) -> ci sono molti page fault
finché
è poco più grande ok, ma poi si rischia, nel caso in
cui la somma sia molto maggiore, che il sistema faccia trashing
(“batosta”), ossia che non faccia altro che gestire page
fault (perde tutto il tempo a gestire la memoria); in questo caso il
sistema può decidere di sospendere dei processi per
liberare memoria (anche qui ho vari algoritmi)
nel
momento in cui ho dei frame liberi posso ripristinare i processi
sospesi
∑|WSj(Pi)|
< M: i processi usano meno pagine rispetto ai frame di memoria
totali, quindi significa che ci sono delle pagine libere e possiamo
quindi aumentare il grado di multiprogrammazione
per un
approfondimento sul trashing vedi pag. 358 - 359 del libro di testo
tenere a
run-time le informazioni sugli ultimi d accessi costa parecchio (ad
es. se ho un hardware solo col reference bit), quindi nella realtà
si usa un valore approssimato
l'implementazione
avviene controllando ogni circa d accessi i reference bit (che
usavamo per l'algoritmo dell'orologio) e li azzero dopo il controllo
grazie a
questo ottengo una stima di WSt(Pi) = working set in un
istante t qualsiasi
con
questa tecnica se mi allontano da d l'approssimazione diventa sempre
peggiore, quindi mi forza a controllare ogni d accessi
METODO DELLA FREQUENZA DELLE
ASSENZE (WINDOWS)
se ho un
processo p con un working set grande, ad es. 10 (WSt(Pi) = 10) a cui
vengono assegnati 5 frame, ho parecchi page fault
nei
sistemi windows inizialmente abbiamo molti page fault e poi le cose
si aggiustano, questo perchè quando il sistema si accorge che
il working set è troppo grande rispetto ai frame assegnati
gliene assegna di più a posteriori
se il
numero di Page Fault è maggiore di SUP:
questa
politica va bene per un sistema monoutente perchè estremamente
locale
se il
numero di page fault è minore di INF significa che fa troppi
pochi page fault e posso ridurre i frame assegnati a tale processo
METODO DEL PAGEOUT GLOBALE
(SOLARIS)
metodo
introdotto da Solaris 2
abbiamo
una lista di frame liberi dai quali i processi attingono: quando un
processo fa page fault attinge frame da questa zona
il frame
gli viene dato subito e poi il sistema controlla periodicamente la
dimensione della lista dei frame liberi
se la
dimensione della lista va sotto a una certa soglia (|lista frame
liberi|< soglia) allora effettuo “pageout” =
utilizzando l'algoritmo dell'orologio / seconda chance con 2
lancette, scansiona globalmente tutta la memoria alla ricerca di un
numero di pagine vittima sufficiente a riportarmi sopra alla soglia;
queste vengono aggiornate sul disco se necessario e messe nella lista
dei frame liberi
il
working set si ingrandisce quando serve
questo
sistema a run-time si autoconfigura sul periodo del controllo (+ page
fault -> periodo più corto); se il sistema è
sovraccaricato anche qui si ricorre alla sospensione dei processi: il
limite è che fa un controllo a ogni page fault, e quindi si
perde la località e diventa quasi FIFO -> sospensione
questo
sistema è pensato per un sistema multi-utente
|