Tema 4. Gestión Compleja de Memoria
Asignación Dinámica de la Memoria
Lecciones 10,11,12,13
Compiladores II (96-97 01/10/2015 21:42)
- 3.1 -
Gestión del Heap (memoria dinámica)
• El heap es un espacio formado por bloques
de memoria cuyo tiempo de vida no se
conoce en tiempo de compilación.
– A estos bloques se accede por apuntador
– Hay funciones para pedir y liberar bloques
(malloc, free)
• Tipos de gestión de memoria
– Gestion Explicita: el programador llama
explicitamente a una función para liberar
los bloques de memoria. Métodos:
• Lista ordenada de bloques libres
• Bloques etiquetados en los extremos
• Bloques compañeros
– Gestión Implícita: El sistema se encarga de
liberar los bloques de memoria que no
utilice el programa. Métodos:
• Marcar y barrer
• Recolector por copia
• Contadores de referencias
Compiladores II (96-97 01/10/2015 21:42)
- 3.2 -
Lista Ordenada de Bloques Libres
• Se utiliza una lista de bloques libres
ordenada por la dirección inicial del
bloque.
• Cada bloque tiene una cabecera con su
tamaño y en el caso de los bloques libres
un apuntador al siguiente bloque de la lista
• Bloque libre
T
Sig
Espacio libre
• Bloque ocupado
T
Espacio ocupado
• Lista ordenada de bloques libres
T S libre T ocupado T S libre T ocupado
Compiladores II (96-97 01/10/2015 21:42)
- 3.3 -
Pedir Memoria (I)
• Pedir n bytes
– Buscar en la lista de bloques libres un
bloque con
• Tamaño=n bytes+ tamaño cabecera bloque
ocupado (4bytes)
• Tamaño>=n+tamaño cabecera bloque libre
(8bytes)+tamaño cabecera bloque ocupado
(4bytes)
– Para bloque de tamaño n
• Sacarlo de la lista de libres y retornar
apuntador
T
Sig
T
Espacio libre
Espacio ocupado
– Para bloque de tamaño mayor que “n”
• Dividir el bloque libre y dar la parte final
T
Sig
T
Sig
Compiladores II (96-97 01/10/2015 21:42)
Espacio libre
libre n
T
ocupado
- 3.4 -
Pedir Memoria (II)
struct bloque {
int sz;
struct bloque *sig;
} *libres;
void *malloc(int sz)
{
struct bloque *p,**ult,*p1;
for (p=libres, ult=&libres; p; ult=&(p->sig),p=p->sig) {
if (p->sz+sizeof(int)==sz) {
*ult=p->Sig;
return &p->sig;
}
else if (p->sz+sizeof(int)+sizeof(struct bloque)>=sz) {
p1=(char*) p+sz+sizeof(struct bloque);
p1->sz=sz+sizeof(int);
p->sz-=sz+sizeof(int);
return &p1->sig;
}
}
return NULL;
}
Compiladores II (96-97 01/10/2015 21:42)
- 3.5 -
Liberar Memoria (I)
• Fragmentación de los bloques libres
– Se da al liberar un bloque vecino de
bloques libres
T S libre T ocupado T S libre T ocupado
T S libre T S libre T S libre T ocupado
• Fusionar bloques para evitar la
fragmentación
T S libre T ocupado T S libre T ocupado
T S
libre
T ocupado
– Buscar el bloque vecino anterior al bloque
a liberar (vecino izquierdo)
– Como los bloques están ordenados, el
bloque siguiente será el único candidato a
vecino derecho.
Compiladores II (96-97 01/10/2015 21:42)
- 3.6 -
Liberar Memoria (II)
void free(void *address)
{
struct bloque *p,*ant,*p1;
p1=(struct bloque*) ((char*) address-sizeof(int));
for (p=libres, ult=NULL; p && p<address; ant=p,p=p->sig) ;
if (ant && (char*) ant+ant->sz+sizeof(int)==address) {
/* Juntar con el anterior */
ant->sz+=p1->sz;
p1=ant;
}
else {
/* Nuevo bloque libre */
p1->Sig=ant->Sig;
ant->Sig=p1;
}
if ((char*)p1+p1->sz==p1->Sig) {
/* Juntar con el bloque siguiente */
p1->sz+=p1->Sig->sz;
p1->Sig=p1->Sig->Sig;
}
}
Compiladores II (96-97 01/10/2015 21:42)
- 3.7 -
Problemas de la Lista de Bloques
• Hay que realizar búsquedas por una lista
secuencial para:
– Pedir memoria
– Liberar memoria
• Hay fragmentación externa de la memoria
• Soluciones a la búsqueda en la liberación
de memoria:
– Utilizar listas doblemente encadenadas
– Guardar la información del bloque en sus
extremos.
Compiladores II (96-97 01/10/2015 21:42)
- 3.8 -
Bloques Etiquetados en los Extremos
(boundary-tag)
• Se utiliza una lista doblemente encadenada
para guardar los bloques libres. De esta
forma se evita buscar el bloque anterior a
uno dado cuando hay que eliminarlo de la
lista
• Se guarda la información de los bloques en
sus extremos, para poder acceder a ella
desde los bloques contiguos.
– Bloque libre
F T A S
Espacio libre
T F
– Bloque ocupado
F T
–
–
–
–
Espacio ocupado
F
F: flag de libre/ocupado
T: tamaño
S: apuntador al siguiente
A: apuntador al anterior
Compiladores II (96-97 01/10/2015 21:42)
- 3.9 -
Pedir Memoria
• Pedir memoria es igual que en el algoritmo
anterior
– Buscar en la lista de bloques libres un
bloque con
• Tamaño=n bytes+tamaño cabecera bloque
ocupado (4bytes)
• Tamaño>=n+tamaño cabecera bloque libre
(16bytes)+tamaño cabecera bloque ocupado
(4bytes)
– Para bloque de tamaño n
• Sacarlo de la lista de libres y retornar
apuntador
– Para bloque de tamaño mayor que “n”
• Dividir el bloque libre y dar la parte final
• Diferencias:
– La lista de bloques libres es doblemente
encadenada
– La lista no está ordenada
Compiladores II (96-97 01/10/2015 21:42)
- 3.10 -
Liberar Memoria
• Para evitar la fragmentación hay que
fusionar los bloques vecinos libres
– Se puede acceder a las cabeceras de los
bloques vecinos sin realizar búsquedas
• Los flags de libre y ocupado son accesibles
desde los dos extremos de los bloques
• En el caso de estar a la derecha de un
bloque libre se puede utilizar su tamaño
para llegar a su cabecera
F T A S libre T F F T ocupado F F T A S libre T F
– Como la lista de bloques libres es
doblemente encadenada no hace falta
encontrar el bloque anterior en la lista
• Ventaja
– No hay que hacer búsquedas en la
liberación
Compiladores II (96-97 01/10/2015 21:42)
- 3.11 -
Overhead en Memoria
• Consideraciones preliminares
– Apuntadores y tamaños de 32bits
• Lista ordenada de bloques libres
– Tamaño mínimo de bloque:
• Sin cabecera 4 bytes
• Con cabecera 8 bytes
– Tamaño cabecera bloque ocupado
• 4 bytes
• Bloques etiquetados
– Tamaño mínimo de bloque:
• Sin cabecera 12 bytes
• Con cabecera 16 bytes
– Tamaño cabecera bloque ocupado
• 4 bytes
– Truco
• Suponer alineación mínima a 4bytes
• Guardar los flags de ocupado y libres en los
bits bajos del tamaño de bloque
Compiladores II (96-97 01/10/2015 21:42)
- 3.12 -
Bloques Compañeros
• El objetivo de este método es eliminar las
búsquedas al perdir y al liberar memoria
• Idea
– Los bloques solo pueden ser de una familia
de tamaños: 2n Bytes
– La búsqueda al pedir memoria quedará
reducida a un array de listas de bloques
libre de 32 posiciones como máximo.
232
231
..
.
Bloques libres 232
Bloques libres 231
24
Bloques libres 24
• Bloque libre F T C A S Espacio libre
• Bloque ocupado F T C Espacio ocupado
•
•
•
•
•
F: booleano de libre/ocupado
C: código
A: apuntador al anterior bloque
S: apuntador al siguiente bloque
T: tamaño del bloque
Compiladores II (96-97 01/10/2015 21:42)
- 3.13 -
Pedir Memoria
• Pedir m bytes
– Buscar en la lista de bloques
• 2n-TC >=m> 2n-1-TC
• TC: tamaño cabecera
– Si no vacía coger el primer bloque de la
lista
– Si lista vacía buscar en la de tamaño n+1.
Si vacia en la n+2, etc.
• Dividir el bloque y poner uno en la lista de
tamaño menor hasta llegar a la lista de
tamaño 2n.
Antes de la división de bloques
2n+2
2n+1
2n
Después de la división de bloques
2n+2
2n+1
2n
Compiladores II (96-97 01/10/2015 21:42)
- 3.14 -
Memoria Desaprovechada
• Este método sólo se utiliza en sistemas con
memoria virtual que permitan reservar
espacio de direcciones sin reservar la
memoria física.
• Ejemplo Pedimos 33K
–
–
–
–
Tamaño página 4K
Tamaño bloque 64K
Memoria desaprovechada 3K
Espacio de direcciones desaprovechado
28K
Memoria
Pedida 33K
Compiladores II (96-97 01/10/2015 21:42)
4K
4K
4K
4K
4K
4K
4K
4K
4K
4K
4K
4K
4K
4K
4K
4K
Páginas no
reservadas
Físicamente
28K
Páginas reservadas
Físicamente 36K
- 3.15 -
Liberar Memoria
• Problema: Los bloques fusionados tienen
que ser de tamaño potencia de 2.
2n+2
2n+1
• Solución:
2n
2n
2n
2n
2n+1
2n
2n
2n
2n
2n+1
2n+1 + 2n
2n
2n
2n
– Codificación de los bloques compañeros
• B. raiz: códigoraíz=códigoizquierdo-1
• B. izquierdo: códigoizquierdo=códigoraíz+1
• B. derecho: códigoderecho=0
2n+2 C=0
2n+1 C=1
2n+1 C=0
2n C=2 2n C=0 2n C=1 2n C=0
2n C=2 2n C=0 2n C=1 2n C=0
2n C=2 2n C=0 2n C=1 2n C=0
2n C=2 2n C=0 2n+1 C=0
2n+1 C=1
2n+1 C=0
2n+2 C=0
Compiladores II (96-97 01/10/2015 21:42)
- 3.16 -
Gestión de Memoria Implícita
• El gestor se encarga de liberar los bloques
de memoria que no utilice el programa.
• Ventajas
– El programador se olvida de la gestión de
memoria
• Reduce los errores
• Desarrollo rápido
• Desventajas
– Métodos lentos
– Desaprovechamiento de la memoria
• Métodos:
– Contadores de referencias
– Recolectores
• Marcar y barrer
• Recolector por copia
• Base de los métodos
– Un bloque no referenciado por apuntadores
no lo utiliza el programa y por lo tanto se
puede liberar automáticamente.
Compiladores II (96-97 01/10/2015 21:42)
- 3.17 -
Contadores de Referencias
• Este método se basa en contar el número
de apuntadores que referencian cada
bloque de memoria
• Implementación
– Cada bloque tiene un contador de
referencias y se conocen los apuntadores
que contiene.
– Cada creación, modificación o destrucción
de un apuntador supone actualizar los
contadores de los bloques a los que apunta.
– Cuando el contador de un bloque llega a
cero se libera automáticamente.
P1
P2
P3
P1
P2
P3
P1
P2
P3
1
2
2
1
1
2
0
0
3
Compiladores II (96-97 01/10/2015 21:42)
- 3.18 -
Contadores de Referencias y Estructuras
Cíclicas
• Los contadores de referencias fallan al
liberar estructuras de datos cíclicas
P1
2
1
1
P1
1
1
1
• Usos
– Gestión de objetos del sistema operativo
(handlers en windows)
– Liberación de objetos en C++
• No se usa
– Gestor de memoria de un lenguaje
– Gestor de memoria genérico
Compiladores II (96-97 01/10/2015 21:42)
- 3.19 -
Recolectores de Memoria
• Idea básica
– El programa pide memoria hasta que no
queda. Entonces se activa el recolector de
memoria que libera la memoria que no
utiliza el programa
• Necesidades de los recolectores
– Tienen que poder recorrer toda la memoria
del programa y detectar donde están los
apuntadores
– Implementación:
• Usar datos encapsulados en nodos o celdas
para facilitar la identificación de los
apuntadores en su interior
• Cada nodo o celda tiene un descriptor de su
contenido
• Los apuntadores que no se encuentren en el
heap se considerarán como apuntadores
externos y hay algún método para
localizarlos.
Compiladores II (96-97 01/10/2015 21:42)
- 3.20 -
Marcar y Barrer
• Este método actúa en dos pasos
– Marcar: marca todos los bloques a los que
tiene acceso el programa
– Barrer: libera los bloques no marcados
• El heap se divide en nodos o bloques con
la siguiente estructura
–
–
–
–
Descriptor del bloque
Marca
Apuntadores
Otros datos
• Un bloque libre tiene un descriptor que
indica que es libre y los datos que necesite
un gestor de memoria explícito para poder
pedir bloques (lista de libres).
Otros datos
Apuntadores
Descriptor Marca
Compiladores II (96-97 01/10/2015 21:42)
- 3.21 -
Pedir Memoria
• Al pedir un bloque de memoria se tiene
que especificar de que tipo es (descriptor)
y su tamaño.
• Se busca el bloque en una lista de libres y
tal como lo podría hacer un gestor de
memória explicito
• Se inicializa el bloque y se retorna al
programa
• En caso que no se encuentre el bloque se
activa la recolección de memoria
– Marcar
– Barrer
Compiladores II (96-97 01/10/2015 21:42)
- 3.22 -
Marcar
• Se siguen las cadenas de apuntadores que
empiezan en un apuntador externo
(variable local o global, etc).
• Para todo apuntador externo
– P=apuntador externo
– *P es un nodo marcado
• No hacer nada
– *P es un nodo por marcar
• Marcar el nodo
• Repetir el mismo proceso que se ha
realizado con P para todos los apuntadores
del nodo
Marcar(p) {
If (!p->Marca) {
p->Marca=true
for (q apuntador de *p) Marcar(q);
}
}
Compiladores II (96-97 01/10/2015 21:42)
- 3.23 -
Marcar sin Pila
• Problema: El proceso de marcado anterior es
recursivo y puede necesitar mucho espacio de
pila, pero resulta que esto no es posible ya que
cuando se activa el recolector no queda
memoria.
• Solución: Utilizar los apuntadores ya
recorridos como pila
– Variables:
Act= apuntador al nodo a marcar
Ant= pila de nodos marcados pero que no se han
seguido sus apuntadores
– Push
Tmp=Act;
Act=Act->Apuntador
Tmp->Apuntador=Ant
Ant=tmp
– Pop
Tmp=Act
Act=Ant
Ant=Ant->Apuntador
Act->Apuntador=Tmp
Compiladores II (96-97 01/10/2015 21:42)
- 3.24 -
Push/Pop
Ant
Act
POP
PUSH
Ant
Act
Ant
Act
Compiladores II (96-97 01/10/2015 21:42)
- 3.25 -
Barrer
• Recorrer secuencialmente todo el heap y
para cada nodo hacer
– Nodo marcado
• Desmarcar
– Nodo NO marcado
• Liberar
• Complejidad del método
– Marcar
• Complejidad lineal respecto el número de
nodos utilizados por el programa
– Barrer
• Complejidad lineal respecto el número de
nodos que hay en el heap (tamaño del heap)
– La complejidad más alta corresponde al
paso de barrer
Compiladores II (96-97 01/10/2015 21:42)
- 3.26 -
Recolección por Copia
• Idea básica
– Divide la memoria en un espacio fuente y
uno destino. El programa solo puede
utilizar el espacio fuente
– Cuando se llena el espacio fuente el
recolector copia los nodos utilizados por el
programa al espacio destino e invierte los
papeles de los dos espacios
Libre
Libre
Ocupado
Espacio
fuente
Compiladores II (96-97 01/10/2015 21:42)
Espacio
destino
- 3.27 -
Pedir Memoria
• El apuntador Libre apunta a la primera
posición libre del espacio fuente.
Pedir(n) {
if (Libre+n> Final espacio fuente)
Activar recolector();
if (Libre+n<=Final espacio fuente) {
p=Libre;
Libre=Libre+n;
return p;
} else Error por falta de memoria
}
Libre
Libre
Ocupado
Espacio
fuente
Compiladores II (96-97 01/10/2015 21:42)
Espacio
destino
- 3.28 -
Recolección
• Copiar los nodos directamente apuntados
por apuntadores externos y sustituir su
cabecera por un apuntador al espacio
destino donde se encuentra la nueva copia
del nodo
• Recorrer los nodos copiados para copiar
los nodos a que estos apunten
P1
P2
4
3
2
1
Heap lleno
4
3
2
1
3
1
Copia nodos
directamente
Apuntados por
Apuntadores
externos
4
3
2
1
4
3
1
Compiladores II (96-97 01/10/2015 21:42)
P1
P2
P1
P2
Copia
De todos los
nodos
- 3.29 -
Complejidad
• Recolección por copia
– Complejidad lineal respecto a los nodos
utilizados por el programa
– Al aumentar el tamaño del heap se reduce
el número de recolecciones y como estas
tienen el mismo coste, el tiempo dedicado a
la recolección es menor
• Marcar y barrer
– Complejidad lineal respecto al tamaño del
heap
– Al aumentar el tamaño del heap se reduce
el número de recolecciones, pero estas son
más costosas. Por lo tanto, no se “reduce”
el tiempo dedicado a la recolección.
• Se reduce para el marcado, pero no para el
barrido
Compiladores II (96-97 01/10/2015 21:42)
- 3.30 -
Descargar

Heap