Universita' di Ferrara
Facolta' di Scienze Matematiche, Fisiche e Naturali
Laurea Specialistica in Informatica
Algoritmi Avanzati
Gestione Dinamica della Memoria:
boundary-tag method
• Vedi: E. Horowitz, S. Sahni, Fundamentals of data structures,
Computer Science Press
• F. de Luigi, C. Salati, Fondamenti di Informatica - Esercitazioni,
Gabriele Corbo Editore
Copyright © 2006-2009 by Claudio Salati.
Lez. 7
1
Gestione dinamica della memoria
• La gestione della memoria dinamica in linguaggi come Pascal, C e
C++ non e' soggetta ad alcuna particolare disciplina
(come accade invece alla memoria automatica che e' allocata e
disallocata con disciplina LIFO, ed e' quindi facilmente
implementata utilizzando uno stack)
• Inoltre, i blocchi di memoria che sono allocati e liberati sono di
dimensione variabile.
• Problema (si pone anche per i Sistemi Operativi):
• tenere traccia dei blocchi di memoria libera e dei blocchi
occupati
• realizzare due operazioni:
• la prima per consentire di allocare un blocco di memoria
della dimensione desiderata (malloc() in C)
• la seconda per consentire di liberare un blocco di memoria
(free() in C)
2
Gestione dinamica della memoria: lista dei blocchi liberi
• Per tenere traccia dei blocchi di memoria libera si potrebbe pensare
di utilizzare una lista
 ogni blocco libero riferisce il prossimo blocco libero della lista.
• La responsabilita' di tenere traccia di quali siano i blocchi occupati
e' lasciata invece al programma utente
 se un blocco e' occupato, il programma utente lo sta utilizzando!
• Un blocco libero viene frazionato a fronte di una operazione di
allocazione che non lo occupi completamente.
• Ogni blocco, libero o occupato, deve mantenere registrata la
propria dimensione
• ai blocchi liberi serve per gestire la operazione di allocazione
• ai blocchi occupati serve perche' la funzione di free() non
indica la dimensione del blocco che si libera (quindi
l'informazione deve essere presente nel blocco stesso!)
• All'inizio tutta la memoria (che e' libera) e' costituita da un unico
blocco.
3
Gestione dinamica della memoria: lista dei blocchi liberi
testata
size
testata
size
size
testata
size
size
size
size
size
testata
size
size
size
size
size
size
occupato
size
libero
4
Gestione dinamica della memoria: lista dei blocchi liberi
• Dopo un po' la memoria libera risulta frammentata!
• Anche blocchi liberi adiacenti non sono ricompattati in un unico
blocco
• Puo' capitare che una richiesta di allocazione di un blocco di
dimensione S venga rifiutata
• anche se complessivamente la memoria libera e' piu' di S, e
• anche se esiste una quantita' di memoria libera adiacente
(ma frammentata in piu' blocchi) maggiore di S.
 la memoria libera non e' gestibile secondo una semplice lista di
blocchi liberi perche' un frazionamento irreversibile porterebbe
alla frammentazione
(l'entropia aumenta continuamente!)
5
Politiche di allocazione: Best-Fit vs. First-Fit
• L'operazione di allocazione non acquisisce necessariamente un
blocco intero: puo' ottenere solo una frazione di blocco.
• E' possibile limitare la frammentazione tramite una opportuna
politica di allocazione/frazionamento?
• Si possono ad esempio immaginare 2 diverse politiche di
allocazione/frazionamento:
• best-fit
• first-fit
6
Politiche di allocazione: Best-Fit vs. First-Fit
• Politica di allocazione Best-Fit:
 tra i blocchi liberi di dimensione maggiore o uguale a
quella desiderata cerchiamo quello di dimensione minima.
• Per trovarlo occorre (durante l'allocazione):
• scandire tutta la lista dei liberi, se questa non e' ordinata
per dimensione (crescente) dei blocchi
• scandire "in media" meta' della lista dei liberi, se questa e'
ordinata per dimensione (crescente) dei blocchi
In ogni caso l'operazione di allocazione ha complessita' O(n),
essendo n la lunghezza della lista dei blocchi liberi
• L'operazione di rilascio
• ha complessita' O(1) se la lista dei liberi non e' mantenuta
ordinata
• ha complessita' O(n) se la lista dei liberi e' mantenuta
ordinata (bisogna scandire "in media" meta' della lista)
7
Politiche di allocazione: Best-Fit vs. First-Fit
• Politica di allocazione First-Fit:
 ci si accontenta di qualunque blocco libero di dimensione
maggiore o uguale a quella desiderata.
• Per trovarlo occorre (durante l'allocazione):
• scandire la lista dei liberi fino a che si trova il primo blocco
di dimensione sufficiente
• in questo caso non ha molto senso volere mantenere la
lista ordinata per dimensione dei blocchi
• In ogni caso l'operazione di allocazione ha complessita' O(n),
ma anche se i blocchi non sono ordinati non e' mediamente
necessario scandire tutta la lista
• L'operazione di rilascio
• ha complessita' O(1) perche' la lista dei liberi non e'
mantenuta ordinata
8
Politiche di allocazione: Best-Fit vs. First-Fit
• L'ordine di complessita' delle due politiche e' lo stesso.
• Sperimentalmente pero' risulta migliore First-Fit.
• Questo risulta anche abbastanza intuitivo dall'analisi dei casi che
abbiamo fatto.
• Nel seguito faremo sempre riferimento alla politica First-Fit

e quindi non manterremo alcun ordine (per dimensione)
nella lista dei blocchi liberi
 Per una analisi (anche sperimentale) molto dettagliata del
problema vedi in particolare:
D.E. Knuth, The art of computer programming, Vol. 1,
Fundamental Algorithms, Addison-Wesley, sez. 2.5, Dynamic
storage allocation
che ha anche introdotto l'algoritmo presentato in questa lezione
9
Politiche di allocazione: Ottimizzazioni euristiche - 1
• E' conveniente effettuare il frazionamento di un blocco
occupandone il fondo:
• in questo modo la struttura della lista dei blocchi liberi non
viene modificata,
• eccetto nel caso in cui il blocco selezionato abbia
esattamente la dimensione richiesta
 in questo caso esso non viene frazionato ma diventa di
per se' un blocco occupato.
• Ovviamente, se c'e' frazionamento, la dimensione del blocco
libero deve essere aggiornata
 ma non occorre ri-ordinare la lista dei liberi, visto che
questa non e' ordinata per dimensione dei blocchi.
10
Politiche di allocazione: Ottimizzazioni euristiche - 2
• Il frazionamento puo' comunque provocare la generazione di
blocchi troppo piccoli per essere mai utilizzati:
 se li teniamo nella lista dei liberi perderemo comunque tempo
per scandirli (inutilmente);
 ma allora, perche' crearli?
• Definiamo un quanto di frazionamento minimo:
• se il frazionamento portasse a creare un blocco di dimensione
minore del quanto minimo, per non frazionare daremo al
cliente un blocco piu' grande di quello che ha richiesto.
 il cliente non sa quanta memoria riceve esattamente
 e' almeno tanta quanta ne ha richiesta
• Poiche' il cliente non sa quanto e' grande esattamente un blocco
occupato, deve essere il blocco occupato stesso a tenere
registrata la propria dimensione.
11
Politiche di allocazione: Ottimizzazioni euristiche - 3
• Se durante l'operazione di allocazione cominciamo la ricerca di
un blocco adatto sempre nel medesimo punto della lista dei
blocchi liberi, cio' portera' ad ammassare in quel punto blocchi di
piccola dimensione (a causa dei frazionamenti).
• Anche se non violano la regola del quanto di frazionamento
minimo questi blocchi spesso risulteranno troppo piccoli.
• Conviene quindi distribuire i blocchi piccoli su tutta la lista dei
blocchi liberi:
 cio' puo' essere fatto iniziando la ricerca, ad ogni
richiesta di allocazione, da un punto diverso della lista;
 basta utilizzare per la lista dei liberi una lista circolare,
e cominciare la ricerca dal blocco successivo a quello
che si e' scelto durante l'operazione di allocazione
precedente.
• Questi miglioramenti non cambiano l'ordine di complessita'
dell'algoritmo, ma ne migliorano i coefficienti moltiplicativi e i
termini di ordine inferiore
12
Rilascio con compattamento - 1
• Il problema vero e' di eliminare per quanto possibile la
frammentazione della memoria.
• Non ci possiamo accontentare di inserire un blocco che vogliamo
liberare nella lista dei liberi:
 in questo modo i frazionamenti sarebbero irreversibili.
• Quando liberiamo un blocco di memoria lo vogliamo ricompattare
con eventuali blocchi adiacenti gia' liberi
 ricreando in questo modo blocchi contigui di dimensione
massima possibile.
13
Rilascio con compattamento - 1
• Ci sono due punti da prendere in considerazione:
1. Come sapere se i blocchi fisicamente adiacenti (precedente
e/o successivo) a quello che vogliamo liberare sono liberi o
occupati?
2. Una volta stabilito che uno o entrambi i blocchi adiacenti sono
liberi, come effettuare il compattamento?
N.B.: in generale sara' necessario alterare la struttura della
lista.
• Se per fare tutto questo (o l'una o l'altra cosa) occorresse scandire
la lista dei blocchi liberi il costo di un rilascio sarebbe O(n)!
14
Identificazione di blocchi liberi adiacenti
• La prima soluzione consiste nello scandire la lista dei blocchi liberi
per verificare se ce ne sono di adiacenti
•
in questo senso si potrebbe ipotizzare che fosse conveniente
mantenere la lista dei blocchi liberi ordinata (non per
dimensione ma) per indirizzo di inizio del blocco
•
in questo modo non si sarebbe costretti a scandirla tutta, ma
solo fino a che si incontra un blocco con indirizzo di inizio
maggiore della fine dell blocco in via di liberazione + 1
• Ma anche in questo modo l'identificazione di eventuali blocchi liberi
adiacenti avrebbe complessita' O(n)
15
Compattamento e ristrutturazione della lista dei
blocchi liberi
• Una volta individuati gli eventuali blocchi liberi adiacenti e'
veramente necessario rimuoverli dalla lista dei liberi per inserirci poi
il nuovo blocco compattato o si puo' fare di meglio?
• La ristrutturazione della lista risulta comunque O(1) una volta che
essa sia doppiamente linkata!
• Notare che una eventuale scansione della lista dei blocchi liberi per
identificare eventuali blocchi liberi adiacenti ci faciliterebbe anche
un inserimento ordinato (per indirizzo) del nuovo blocco libero nella
lista!
16
Rilascio con compattamento - 2
• Ogni blocco e' comunque contiguo ad almeno un altro blocco
(perche' non sempre a 2?), libero o occupato che sia.
• Allora strutturo ogni blocco, libero od occupato che sia,
introducendo in esso delle informazioni aggiuntive,
che nel caso di un blocco occupato sono comunque nascoste al
programma cliente
• Ad ogni blocco, libero od occupato, diamo la seguente struttura:
Indirizzo ritornato al
cliente al momento
dell'allocazione (per un
blocco occupato)
Tag = occupato vs. libero
Dimensione del blocco
…
Tag = occupato vs. libero
17
Rilascio con compattamento - 3
• Con questa strutturazione, dato un blocco, guardando i campi tag
dei blocchi fisicamente adiacenti, possiamo dire (in tempo O(1)) se
questi sono liberi o occupati
• Questa strutturazione interna e' sufficiente per i blocchi occupati,
Infatti e' responsabilita' del programma cliente mantenere l'identita'
dei blocchi occupati
• La struttura interna di un blocco libero deve invece essere ancora
arricchita:
•
perche' devo mantenere il blocco libero nella lista dei blocchi
liberi;
•
perche' la lista dei blocchi liberi deve essere doppiamente
linkata (per consentire l'eliminazione di un blocco dalla lista in
tempo O(1) conoscendone l'indirizzo);
•
perche' se il blocco precedente a quello che voglio liberare e'
gia' libero devo potere recuperare il suo indirizzo di inizio per
poter operare il compattamento.
18
Rilascio con compattamento - 3'
• Nota che l'utilizzo dei campi tag di libero/occupato ha eliminato
ogni necessita' di mantenere ordinati i blocchi nella lista dei liberi.
•
Un ordinamento per dimensione avrebbe potuto servire per
implementare la politica best-fit, alla quale abbiamo pero'
rinunciato.
•
Un ordinamento per indirizzo di inizio avrebbe potuto essere
utile nella ricerca di eventuali blocchi liberi adiacenti, ma non
se per questo scopo utilizziamo i campi tag.
• Quindi, in assenza di blocchi liberi fisicamente adiacenti a quello
che stiamo liberando, basta semplicemente inserire quest'ultimo
in qualunque posizione della lista dei liberi, e.g. in coda.
•
In realta' bisogna anche completarne la strutturazione interna
aggiungendo tutte le informazioni necessarie ad un blocco
libero.
19
Rilascio con compattamento - 4
• Struttura completa di un blocco libero:
Tag = libero
Dimensione del blocco
lLink
rLink
…
upLink
Tag = libero
20
Rilascio con compattamento - 5
• Al momento del rilascio si presentano 4 casi, a seconda che i due
blocchi fisicamente adiacenti, il precedente ed il successivo, siano
liberi od occupati.
• La lista dei blocchi liberi deve essere doppiamente connessa per
poterla ristrutturare in caso di compattamento (casi 2 e 4).
1. Se sono occupati sia il blocco fisicamente precedente che quello
fisicamente successivo bisogna
•
inserire il blocco che andiamo a liberare nella lista dei blocchi
liberi
2. Se e' libero solo il blocco fisicamente successivo a quello che
vogliamo liberare (e quello precedente e' occupato) bisogna
•
estrarre il blocco successivo dalla lista dei liberi e
•
inserirci il blocco che liberiamo,
•
estendendolo per inglobare anche il blocco libero che abbiamo
eliminato (quello successivo).
21
Continua alla pagina successiva 
Rilascio con compattamento - 6
3. Se e' libero solo in blocco fisicamente precedente a quello che
vogliamo liberare (e quello successivo e' occupato) basta
•
estendenderlo per inglobare anche il blocco che stiamo
liberando
4. Se sono liberi sia il blocco fisicamente precedente che quello
fisicamente successivo a quello che vogliamo liberare occorre
•
estrarre il blocco successivo dalla lista dei liberi e
•
estendendere il blocco precedente per inglobare sia il blocco
che stiamo liberando che quello successivo
• Ovviamente quando inseriamo un nuovo blocco libero lo dobbiamo
strutturare internamente in modo appropriato.
22
Campo Dimensione
• Il campo dimensione del blocco deve essere comunque presente,
sia nei blocchi liberi che in quelli occupati
• Di un blocco libero occorre conoscerne la dimensione:
• durante l'operazione di allocazione, per vedere se e'
sufficientemente grande ed eventualmente gestirne il
frazionamento
• durante l'operazione di liberazione, per gestire l'eventuale
compattamento
• In un blocco occupato deve esserci registrata la sua (vera)
dimensione perche' il cliente non la conosce:
 per evitare creare blocchi liberi di dimensione inferiore al
quanto minimo di frazionamento potrebbe essergli stata data
piu' memoria di quanta ne avesse richiesta
• Un quanto di frazionamento minimo deve comunque essere
considerato, perche' un blocco libero deve essere grande almeno
abbastanza da contenere i sei campi strutturali necessari a gestirlo.
23
Eliminazione dei casi particolari
• Nella coda dei liberi inseriamo un nodo di testata di dimensione 0
(quindi non allocabile) per evitare di gestire il caso di coda dei
liberi vuota in inserzione e cancellazione
 Il nodo di testata non deve mai potere essere adiacente ad
un blocco libero (liberato), per non essere compattato con
questo
• Ai margini fisici dell'area di memoria gestita dinamicamente
inseriamo due pseudo campi tag con valore occupato.
 Questi campi evitano di dovere considerare come casi
particolari il rilascio dei blocchi ai bordi dell'area dinamica
 In questo modo ogni blocco che liberiamo ha sempre
esattamente 2 blocchi adiacenti (liberi o occupati, veri o
pseudo), uno prima e uno dopo
24
Tag = libero
Dimensione del blocco = 0
lLink
rLink
upLink
Tag = libero
Tag = occupato
Tag = libero
Dimensione del blocco
lLink
rLink
…
upLink
Tag = libero
Tag = occupato
Struttura iniziale della
memoria dinamica
Testata della coda dei
blocchi liberi
Blocco libero dummy di
dimensione 0
memoria dinamica
Pseudo-tag di bordo fisico
della memoria dinamica
25
Complessita' delle operazioni
• L'operazione di rilascio di un blocco, compreso l'eventuale
compattamento con i blocchi liberi adiacenti (se ci sono), e' di
complessita' O(1) (costante).
• Tramite boundary-tag e campo upLink posso verificare se i blocchi
adiacenti sono liberi o occupati e recuperarne l'identita', cioe'
l'indirizzo di inizio (in tempo O(1))
• l'identita' del blocco fisicamente successivo e' calcolata come
indirizzo successivo all'indirizzo dell'ultima cella del blocco
• l'identita' del blocco fisicamente precedente e' calcolata tramite
l'uplink di questo blocco dopo che l'indirizzo della sua ultima cella
e' stato calcolato come indirizzo precedente quello della prima
cella del blocco
• Utilizzando una lista doppiamente linkata e' possibile ristrutturare in
tempo O(1) la lista dei blocchi liberi in caso di compattamento
• Utilizzando una struttura dati piu' semplice (lista semplicemente
connessa, non utilizzo di boundary tag) sarebbe stata di complessita'
O(n): il miglioramento e' stato quindi di un ordine.
26
Complessita' delle operazioni
• L'operazione di allocazione di un blocco continua ad avere
complessita' O(n), ma la complessita' attesa non coincide con il
caso peggiore (un qualunque blocco sufficientemente grande va
bene!)
• Per ottenere questi risultati si e' dovuto assumere una politica di
allocazione First-Fit
 questo ci evita di dovere mantenere qualunque ordinamento
nella lista dei blocchi liberi
• L'introduzione di un blocco libero di testata e degli pseudo-tag di
bordo fisico dell'area della memoria dinamica
•
migliorano i coefficienti moltiplicativi e additivi della
complessita' a parita' di ordine
•
semplificano la scrittura del codice
27