Memoria dinámica
Objetivos
- Entender el concepto de memoria dinámica.
- Conocer los mecanismos para reservar y liberar memoria.
Introducción
Hasta ahora hemos trabajado con memoria estática, es decir, toda la memoria que utilizábamos estaba fijada desde un inicio y se reservaba al ejecutar nuestro programa. Esto tiene un conjunto de inconvenientes, ya que, por ejemplo, al crear una tabla debemos definir un tamaño máximo, ocupando mucho espacio innecesario cuando esta tabla está vacía y con una limitación en el número máximo de elementos que esta tabla puede contener. En esta unidad veremos cómo podemos reservar memoria de forma dinámica, durante la ejecución de nuestro programa.
1. Gestión de la memoria
A continuación se muestra una evolución del esquema de memoria que vimos en la unidad de memoria estática:
Podemos ver que a las zonas ya vistas anteriormente, se ha añadido el stack y el heap. Estas zonas crecen en sentido opuesto, y cuando se encuentran significa que el sistema se ha quedado sin memoria. El stack o pila de programa es una estructura tipo LIFO (Last In First Out). Cada vez que nuestro programa hace una llamada a una función o acción, toda la información referente a esta acción o función se añade a esta pila, y al finalizar su ejecución se elimina de la pila. No entraremos en detalles de lo que se guarda, pero hay información sobre dónde se guarda el retorno, las variables y los parámetros de la función. Por otro lado tenemos el heap, que se encuentra justo a continuación del BSS. Cuando en un programa reservamos memoria dinámicamente, esta se reserva a partir del heap y este se desplaza.
Gestionar la memoria significa pedir memoria al sistema operativo para guardar nuestros datos y, cuando ya no la necesitamos, liberarla para que otros programas la puedan usar. La clave de todo este proceso son los punteros, que nos permiten apuntar las zonas de memoria que reservamos. Vamos a ver un ejemplo de cómo funciona este mecanismo. Primero utilizando solo memoria estática:
var
a: integer;
end var
a:=4;
writeInteger(a);
int a;
a=4;
printf("%d\n", a);
Ahora una versión del mismo programa, pero utilizando memoria dinámica:
var
a: pointer to integer;
end var
a:=NULL;
a:=getMemory(1);
if a=NULL then
error("Not enough memory");
end if
a^:=4;
writeInteger(a^);
freeMemory(a);
int *a=NULL;
/* malloc allocate a number of bytes from memory. Since we want an integer, we use the sizeof command to get the length in bytes for the type int*/
a=(int*)malloc(sizeof(int));
if(a==NULL) {
printf("Error: Not enough memory\n");
return;
}
*a=4;
printf("%d\n", *a);
free(a);
Fijaos en los siguientes puntos:
- Trabajamos con punteros, por lo tanto, la variable a, que es un entero en el primer caso, pasa de puntero a entero en el segundo caso.
- La memoria se debe reservar antes de poder utilizarla. En lenguaje C, habrá que asignar el tipo correcto al retorno del método malloc.
- Comprobad que se ha podido reservar la memoria solicitada. Si toda la memoria está ocupada, el puntero queda asignado a null y, por tanto, no podemos utilizarlo.
- Al finalizar, o cuando ya no la necesitamos, hay que liberar la memoria.
2. Tablas con memoria dinámica
Una de las grandes limitaciones de trabajar con memoria estática la encontramos a la hora de definir tablas, ya que estamos obligados a fijar un tamaño para el vector que se utiliza para definir la tabla. Por este motivo, hasta ahora nos hemos visto obligados a especificar siempre un número máximo de elementos para la tabla. Este hecho tiene dos consecuencias no deseables:
- Estamos limitados en el número de registros que guarda la tabla.
- Estamos ocupando siempre el máximo de memoria (como si la tabla estuviera llena), incluso cuando la tabla está vacía.
Cuando trabajamos con memoria dinámica, tenemos la posibilidad de ir pidiendo memoria a medida que la necesitamos. Fijaos en el siguiente ejemplo, que muestra cómo cambiar el tamaño de un vector de reales:
var
v: pointer to real;
end var
v:=NULL;
v:=getMemory(2)
if v=NULL then
error("Not enough memory");
end if
v[1]:=1.5;
v[2]:=3;
resizeMemory(v, 3);
if v=NULL then
error("Not enough memory");
end if
v[3]:=5.4;
v[1]:=v[1] + v[2] + v[3];
resizeMemory(v, 1);
writeReal(v^);
freeMemory(v);
float *v=NULL;
/* Allocate memory for a vector of 2 float values*/
v=(float*)malloc(2*sizeof(float));
if(v==NULL) {
printf("Error: Not enough memory\n");
return;
}
v[0]=1.5;
v[1]=3;
/* Change the size of the vector to 3 float values*/
v=(float*)realloc(v, 3*sizeof(float));
if (v==NULL) {
error("Not enough memory");
return;
}
v[2]=5.4;
v[0]=v[0] + v[1] + v[2];
/* Change the size of the vector to 1 float value*/
v=(float*)realloc(v, sizeof(float));
printf("%f\n", *v);
free(v);
Fijaos en que en este código:
- Creamos un vector de 2 reales.
- Asignamos valores a las dos posiciones del vector.
- Redimensionamos el vector añadiéndole una tercera posición. No podemos asegurar que la zona de memoria que se nos asigne comience en el mismo lugar, por tanto, hay que apuntar el puntero a la nueva zona de memoria.
- Asignamos un valor a esta tercera posición (las dos anteriores mantienen sus valores). Se libera la memoria que utilizaban estas dos posiciones.
- Guardamos en la primera posición la suma de las tres posiciones del vector.
- Volvemos a redimensionar el vector, pero ahora reducimos la memoria que ocupa a una sola posición, por tanto ahora es equivalente a un real normal.
- Mostramos el resultado.
- Liberamos la memoria que todavía ocupamos.
Una vez tenemos un vector que puede cambiar de tamaño, la definición de una tabla con memoria dinámica quedaría tal y como se muestra en el siguiente apartado.
2.1. Definición de tabla con memoria dinámica
Recordemos que una tabla se define por un vector que contiene los elementos de la tabla y un entero que nos indica cuántos elementos hay guardados. Como en este caso queremos que el vector pueda cambiar su tamaño, en vez de que tenga un tamaño fijado, definiremos la tabla con un puntero. Ahora ya no tendremos un tamaño máximo de la tabla. A continuación se muestra la definición de una tabla de enteros.
type
tTable = record
elements: pointer to integer;
numElements: integer;
end record
end type
int *elements;
int numElements;
} tTable;
}
2.2. Operaciones de tablas con memoria dinámica
Al utilizar memoria dinámica habrá que hacer algunos pequeños cambios en las operaciones sobre este tipo. Debemos tener en cuenta los siguientes hechos:
- Todo puntero tiene que ser inicializado al valor null, para saber que no tiene memoria asignada. Por tanto, al inicializar la tabla habrá que inicializar el puntero.
- Cuando se añaden elementos, ya no hay un número máximo de elementos, pero hay que redimensionar el tamaño del vector.
- Cuando se eliminan elementos, si no queremos utilizar más espacio del necesario, también habrá que redimensionar el tamaño del vector.
- Cuando no necesitamos la tabla, tenemos que liberar toda la memoria que utiliza.
Teniendo en cuenta estos puntos, las operaciones para la tabla anterior quedan redefinidas como:
2.2.1. Inicialización
Inicializa una tabla pasada como parámetro.
action initTable(inout table : tTable)
table.numElements := 0;
table.elements := NULL;
end action
table->nElements=0;
table->elements=NULL;
}
2.2.2. Añadir elemento
Dada una tabla y un nuevo elemento, añade este elemento al final de la tabla. Tened en cuenta que cuando el puntero aún no apunta a ninguna zona de memoria, reservamos memoria y no redimensionamos el vector.
action addElement(inout table : tTable, e : integer)
if table.numElements = 0 then
table.elements:=getMemory(1);
else
resizeMemory(table.elements, table.numElements+1);
end if
if v=NULL then
error("Not enough memory");
end if
table.numElements := table.numElements + 1;
table.elements[table.numElements] := e;
end action
if(table->numElements == 0) {
table->elements=(int*)malloc(sizeof(int));
} else {
table->elements=(int*)realloc(table->elements, (table->numElements+1) * sizeof(int));
}
if(table->elements == NULL) {
printf("Error: Not enough memory\n");
return;
}
table->numElements++;
table->elements[table->numElements-1] = e;
}
2.2.3. Eliminar elemento
Dada una tabla y la posición del elemento que queremos eliminar, elimina el elemento que se encuentra en la posición indicada y compacta la tabla. Tened en cuenta que en el caso de que la tabla quede vacía, hay que liberar la memoria y asignar el puntero a NULL, indicando que no hay memoria reservada.
action delElement(inout table : tTable, pos : integer)
var
i : integer;
end var
if pos >=1 and pos <= table.numElements then
for i:=pos to table.numElements-1 do
table.elements[i]:=table.elements[i+1];
end for
table.numElements:=table.numElements-1;
resizeMemory(table.elements, table.numElements);
end if
end action
int i;
if(pos>=0 && pos<table->numElements) {
for(i=pos; i< table->numElements-1; i++) {
table->elements[i]=table->elements[i+1];
}
table->numElements--;
if(table->numElements==0) {
free(table->elements);
table->elements=NULL;
} else {
table->elements=(int*)realloc(table->elements, table->numElements * sizeof(int));
if(table->elements == NULL) {
printf("Error: resize memory fail\n");
}
}
}
}
2.2.4. Eliminar tabla
Una operación que no era necesaria en el caso de utilizar memoria estática era la eliminación de la tabla. A continuación se define un método para hacerlo.
action releaseTable(inout table : tTable)
if table.elements ≠ NULL then
freeMemory(table.elements);
table.numElements:=0;
table.elements:=NULL;
end if
end action
if(table->elements != NULL) {
free(table->elements);
table->numElements=0;
table->elements=NULL;
}
}
Resumen
En esta unidad hemos visto:
- El concepto de memoria dinámica.
- Cómo se gestiona la memoria dinámica, con los tres comandos principales para reservar, redimensionar y liberar.