ASIGNACION DINAMICA DE MEMORIA: INTRODUCCION
Conceptos básicos.
Tiempo compartido y reparto de memoria
La forma en que se ejecuta un programa en una computadora se parece bastante a dos personas que tuvieran encomendada una tarea, como sumar una larga lista de números. Una de las personas tiene un cuaderno (la memoria de la computadora), en el que están apuntados los datos que hay que sumar, y en el que habrá que escribir los resultados. La otra persona tiene una calculadora, y va preguntando lo que tiene que hacer al encargado del cuaderno. A medida que hace las cuentas, indica al del cuaderno los resultados. El usuario es el que va escribiendo en el cuaderno lo que hay que hacer, y luego la otra pareja se encarga de realizar las tareas indicadas por el usuario. Por cierto, y aunque no se le vea, hay una tercera persona: es el sistema operativo, que es quien dice a la pareja cuaderno-calculadora cosas tan importantes como que empiece a trabajar, que se detenga cuando acabe, que espere un momentito porque le traen una hoja de papel con información de última hora [un disquette], etc.
Con el paso del tiempo, tanto el encargado de las cuentas (el procesador) como el encargado del cuaderno (la memoria) se han vuelto muy rápidos. De hecho, hemos observado que en muchas ocasiones nosotros tardamos mucho en escribir los datos en el cuaderno, y la pareja cuaderno-ordenador queda a la espera de tareas: están perdiendo el tiempo. Para evitar esto, nos ponemos de acuerdo con el usuario de al lado, que tiene cosas por hacer, y le permitimos que conecte su propio ordenador al nuestro. Como somos generosos, le decimos que él puede hacer uso de nuestro ordenador en segundos pares, y nosotros usaremos los impares. O mejor, le decimos que él puede hacer uso de los milisegundos pares, y nosotros usaremos los impares. El ordenador invertirá en atender al vecino el tiempo que antes pasaba esperando nuestras peticiones, y de este modo, sin pérdida de velocidad por nuestra parte, aprovecharemos mejor la máquina. Este proceso se denomina "de tiempo compartido".
¿Cómo se ha organizado la pareja cuaderno-calculadora? Fácilmente: la mitad del cuaderno se destina a nosotros, y la otra mitad al vecino. Para que no haya confusiones, la tercera persona de que hablabamos (el sistema operativo) se asegura de que nosotros sólo podamos escribir en nuestras páginas, y de que el vecino sólo pueda escribir en las suyas. A veces nos ponemos de acuerdo y reservamos unas cuantas páginas que vamos a compartir con el vecino; a esto se le llama comunicación entre procesos. Pero cada programa o proceso tiene asignada una zona propia de memoria, que le ha sido asignada para el sistema operativo.
Sigamos adelante: aun cuando tanto nosotros como el vecino nos esforzamos por dar tareas al ordenador, éste sigue esperando sin hacer nada la mayor parte del tiempo. Por tanto, tiene sentido permitir su utilización a más personas, asignando a cada una ciertas páginas del cuaderno; el sistema operativo irá prestando atención a las distintas tareas, que se ejecutarán aparentemente a la vez. En realidad, yo sólo estoy utilizando un milisegundo cuando me hace falta, pero no aprecio pérdida de velocidad. En mi ordenador se ejecutan múltiples programas, de los que algunos son míos y otros no. Cada programa tiene asignada una zona de memoria propia; sólo ése programa puede escribir en ella, y ése programa sólo puede escribir en esa zona, pero no en la memoria de los demás programas. Esta normativa, que impone el sistema operativo, recibe el nombre de protección de memoria.
Uso de la memoria asignada a una aplicación - reserva y liberación de memoria en el cúmulo
¿De qué forma se utiliza la memoria asignada a una aplicación? Básicamente, se descompone en tres zonas: pila, cúmulo y código.
-
La
pila
es una zona de memoria que se parece bastante a la parte de atrás del cuaderno: sirve para hacer operaciones intermedias, para tomar pequeñas notas que luego descartaremos, para escribir, tachar y borrar con objeto de llegar a los resultados finales. Se implementa, como su nombre indica, mediante una pila o stack. Crece hacia abajo, hacia las direcciones bajas de memoria (son las últimas páginas del cuaderno; si seguimos retrocediendo podemos llegar a la parte utilizada). Cuando la pila invade la zona usada del cuaderno, diremos que se produce una colisión entre pila y cúmulo.
-
El
código
y los
datos estáticos
ocupan otra parte de la memoria asignada; el código es el programa en sí; la colección de instrucciones que hay que ejecutar y los datos estáticos son la información fija del programa (meses del año, tablas de factores de conversión, etc.) Esta información suele ubicarse ubicarse por encima de la pila, para evitar invasiones, o bien al otro extremo de la memoria, por idéntica razón.
-
Por último, el
cúmulo
es toda la memoria restante: la fracción de memoria que no pertenece a la pila ni al código. Normalmente, el cúmulo contiene la mayor parte de la memoria de la aplicación, y es precisamente aquí donde se van a ir
creando
y
destruyendo
variables (que llamaremos
variables dinámicas
) a medida que lo haga necesario la ejecución de la aplicación.
Asignación y liberación de memoria.
Las variables dinámicas se crean y destruyen al arbitrio del programador. El objetivo que se persigue es racionalizar la utilización de un recurso escaso, la memoria RAM. El método que se emplea sigue los pasos indicados a continuación:
-
Reservar bloques de memoria. Estos bloques tendrán el tamaño y tipo deseado, si es que el sistema operativo dispone de RAM suficiente. En caso afirmativo, la llamada a una función específica nos proporciona un puntero genérico (un
void *
) del bloque solicitado. Entonces el programa accede al bloque a través de ese puntero; las variables dinámicas carecen de nombre (pero los punteros son operativamente equivalentes a nombres).
-
Cargar información en ellos. Esto se hace leyendo información de disco, o a partir de teclado, o copiando información residente en otras zonas de RAM, etc. Téngase en cuenta que el espacio reservado puede contener cualquier cosa, con o sin sentido. No hay garantías, y será preciso asignar valores iniciales antes de poder usar con confianza el contenido de las variables dinámicas.
-
Procesar esa información. Esto se hace a través de punteros.
-
Guardar los resultados obtenidos (en disco o en RAM). Téngase en cuenta que es frecuente procesar una volumen considerable de información para obtener unos resultados de volumen muy inferior al procesado.
-
Y liberar la memoria reservada, que estará de nuevo a nuestra disposición para ser reservada en forma de otras variables. Entonces el gran volumen de información que era preciso procesar sólo existe en memoria mientras es necesario; cuando ya no se necesita, se descarta, y seguimos teniendo la memoria disponible para otras tareas.
Fragmentación del cúmulo.
Existen dos grandes bloques de estructuras dinámicas de datos:
-
Estructuras lineales. Se caracterizan porque ocupan un bloque contiguo de memoria. Estos bloques pueden ser grandes o pequeños, y por tanto contendrán muchos o pocos elementos, pero su organización interna es la de una lista, tabla, matriz, etc. El acceso a su contenido se realiza mediante uno o más índices, o desde otro punto de vista, sumando a la dirección base (el comienzo del bloque) un desplazamiento que nos lleva hasta el comienzo del elemento deseado. El cálculo de este desplazamiento es completamente regular, porque los elementos de la lista ocupan posiciones totalmente previsibles. Dicho en términos algorítmicos, el coste de acceso a una estructura lineal es constante (igual para todos sus elementos), aunque irá creciendo de forma fácilmente calculable con el número de índices. En este aspecto, las estructuras lineales son las más eficientes (en términos de acceso), aunque, como se verá, no son las más flexibles.
-
Estructuras no lineales. Se caracterizan por estar formadas por múltiples bloques de memoria, distantes más o menos entre sí, que forman una cadena. Estos bloques, pequeños o grandes, están organizados de tal modo que cada bloque contiene no sólo la información procesada, sino también la dirección del próximo bloque. La información, entonces, se almacena en toda una colección de estructuras dispersas; en cada estructura, además de la información en sí, se almacenan punteros que nos permiten acceder a otros bloques de información. Desde el punto de vista algorítmico, el coste de acceso no es constante: cuanto más larga sea la cadena, mayor será el tiempo necesario para acceder a sus últimos elementos, porque es preciso recorrer los anteriores.
Entonces cabe pensar que no tiene sentido construir estructuras no lineales, porque son menos eficientes. Pero la realidad es distinta: a medida que se crean y destruyen variables dinámicas, el cúmulo va siendo "invadido" por bloques. Algunos de estos bloques se destruyen (se libera su memoria) al cabo de unos instantes, pero otros permanecen, porque la información que contienen es precisa a lo largo de un periodo de tiempo mayor. Entonces la memoria disponible ya no forma un único bloque libre, como al principio de la ejecución del programa, sino múltiples bloques de dimensiones menores. Cuanto mayor sea el número de variable dinámicas de cierta duración que haya en el programa, más fragmentado estará el cúmulo. Y aquí surge el problema: los bloques que utilizan las estructuras dinámicas lineales suelen ser de gran tamaño, porque el número de elementos almacenados en el bloque es elevado. Cuanto mayor sea el bloque necesario para albergar una estructura lineal dinámica, más probabilidades hay de que no sea posible encontrar espacio para él. No es que nos hayamos quedado sin memoria: es que no hay espacio
contiguo
suficiente. Resumiendo, la fragmentación del cúmulo puede hacer imposible utilizar variables dinámicas lineales. Pero este problema no va a existir en las variables dinámicas no lineales, porque éstas están formadas por múltiples bloques, de dimensiones necesariamente menores a igualdad de información total almacenada. Entonces, aún cuando el cúmulo esté notablemente fragmentado, una estructura dinámica no lineal tiene grandes probabilidades de ir hallando pequeños bloques libres, suficientes para albergar sus elementos y adecuados para formar finalmente toda la cadena necesaria.
Por esta razón, es muy frecuente emplear estructuras dinámicas no lineales cuando se prevé que puede aparecer fragmentación en el cúmulo como consecuencia de una gran cantidad de creaciones y destrucciones de variables, o si la memoria no es excesivamente abundante.
En las próximas secciones abordaremos la construcción de variables dinámicas, tanto lineales como no lineales. Nuestro objetivo es optimizar el uso de la memoria disponible en el cúmulo, y también mostrar ciertos métodos de trabajo de uso frecuente.