Embed Size (px)
Citation preview
Compiladores II (96-97 04/22/23 03:17) - 3.1 -
Tema 4. Gestión Compleja de Memoria
Asignación Dinámica de la Memoria
Lecciones 10,11,12,13
Compiladores II (96-97 04/22/23 03:17) - 3.2 -
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 04/22/23 03:17) - 3.3 -
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
• Bloque ocupado
• Lista ordenada de bloques libres
Espacio libreT Sig
Espacio ocupadoT
libreT S ocupadoT libreT S ocupadoT
Compiladores II (96-97 04/22/23 03:17) - 3.4 -
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
– Para bloque de tamaño mayor que “n”• Dividir el bloque libre y dar la parte final
Espacio libreT Sig
Espacio ocupadoT
Espacio libreT Sig
ocupadoSigT nlibre T
Compiladores II (96-97 04/22/23 03:17) - 3.5 -
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 04/22/23 03:17) - 3.6 -
Liberar Memoria (I)
• Fragmentación de los bloques libres– Se da al liberar un bloque vecino de
bloques libres
• Fusionar bloques para evitar la fragmentación
– 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.
libreT S ocupadoT libreT S ocupadoT
libreT S libreT libreT S ocupadoTS
libreT S ocupadoT libreT S ocupadoT
libreT S ocupadoT
Compiladores II (96-97 04/22/23 03:17) - 3.7 -
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 04/22/23 03:17) - 3.8 -
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 04/22/23 03:17) - 3.9 -
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
– Bloque ocupado
– F: flag de libre/ocupado
– T: tamaño
– S: apuntador al siguiente
– A: apuntador al anterior
Espacio libreF S
Espacio ocupadoT
AT T F
F F
Compiladores II (96-97 04/22/23 03:17) - 3.10 -
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 04/22/23 03:17) - 3.11 -
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
– 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
libreF SAT T F ocupadoTF F libreF SAT T F
Compiladores II (96-97 04/22/23 03:17) - 3.12 -
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 04/22/23 03:17) - 3.13 -
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.
• Bloque libre
• Bloque ocupado• F: booleano de libre/ocupado
• C: código
• A: apuntador al anterior bloque
• S: apuntador al siguiente bloque
• T: tamaño del bloque
232 Bloques libres 232
231 Bloques libres 231
24 Bloques libres 24
...
Espacio libreSACTF
Espacio ocupadoCTF
Compiladores II (96-97 04/22/23 03:17) - 3.14 -
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.
2n+1
2n
2n+2
2n+1
2n
2n+2
Después de la división de bloques
Antes de la división de bloques
Compiladores II (96-97 04/22/23 03:17) - 3.15 -
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
4K4K4K4K4K4K4K4K4K4K4K4K4K4K4K4K
Memoria Pedida 33K
Páginas reservadasFísicamente 36K
Páginas no reservadasFísicamente28K
Compiladores II (96-97 04/22/23 03:17) - 3.16 -
Liberar Memoria
• Problema: Los bloques fusionados tienen que ser de tamaño potencia de 2.
• Solución:– 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 2n 2n 2n
2n+1 2n+1
2n+2
2n 2n 2n 2n
2n 2n+1 2n
2n 2n+1 + 2n
2n C=2 2n C=0 2n C=1 2n C=02n+1 C=1 2n+1 C=0
2n+2 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=02n+1 C=1
2n+2 C=0
Compiladores II (96-97 04/22/23 03:17) - 3.17 -
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 04/22/23 03:17) - 3.18 -
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.
P1P2P3
1 2 2
P1P2P3
1 1 2
P1P2P3
0 0 3
Compiladores II (96-97 04/22/23 03:17) - 3.19 -
Contadores de Referencias y Estructuras Cíclicas
• Los contadores de referencias fallan al liberar estructuras de datos cíclicas
• 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
P1 2 1
1
P1 1 1
1
Compiladores II (96-97 04/22/23 03:17) - 3.20 -
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 04/22/23 03:17) - 3.21 -
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).
Descriptor Marca
Apuntadores
Otros datos
Compiladores II (96-97 04/22/23 03:17) - 3.22 -
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 04/22/23 03:17) - 3.23 -
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=truefor (q apuntador de *p) Marcar(q);
}}
Compiladores II (96-97 04/22/23 03:17) - 3.24 -
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 marcarAnt= pila de nodos marcados pero que no se han
seguido sus apuntadores
– PushTmp=Act;Act=Act->ApuntadorTmp->Apuntador=AntAnt=tmp
– PopTmp=ActAct=AntAnt=Ant->ApuntadorAct->Apuntador=Tmp
Compiladores II (96-97 04/22/23 03:17) - 3.25 -
Push/Pop
Act
Ant
Act
Ant
Act
AntP
US
H
PO
P
Compiladores II (96-97 04/22/23 03:17) - 3.26 -
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 04/22/23 03:17) - 3.27 -
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
Ocupado
Libre
Espaciofuente
Espaciodestino
Compiladores II (96-97 04/22/23 03:17) - 3.28 -
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
Ocupado
Espaciofuente
Espaciodestino
Libre
Compiladores II (96-97 04/22/23 03:17) - 3.29 -
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
4321
P1
P2
4321
P1
P213
4321
P1
P2134
Heap lleno
Copia nodosdirectamenteApuntados por Apuntadoresexternos
CopiaDe todos los nodos
Compiladores II (96-97 04/22/23 03:17) - 3.30 -
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
