Estructura de Datos: Almacenamiento Dinámico
Definicion.
Almacenamiento dinámico es una Estructura de Datos que permite solicitar bloques de ancho
variable de N nodos cada uno y contiguos en memoria. La provisión de los nodos se hace desde un
conjunto de nodos de ancho fijo, de M nodos, conocido con el nombre de Almacenamiento Dinámico.
Una vez utilizados, estos bloques de ancho variable, de N nodos, deben ser devueltos todos juntos,
cuando ya se los haya utilizado. En los siguientes ejemplos la dirección de los nodos del
Almacenamiento Dinámico es de 1 a M.
Se preguntarán ¿De qué estamos hablando?
Bueno, como todos saben, los programas necesitan memoria para su procesamiento, dependiendo
de las necesidades de cada programa es la cantidad de memoria que requiere, no todos requieren la
misma cantidad y si nuestra memoria está constituida por bloques de tamaño fijo, puede ser que
partes de estos bloques se desperdiciaran, es decir si cada bloque es de 10 palabras (palabra es una
unidad de medida que consta de 2 bytes) o 10 bytes para que no se revuelvan y un programa necesita
13, el sistema operativo tendría que asignarle dos bloques, ya que con uno no sería suficiente, de tal
manera que se estarían desperdiciando 7, ya que solo requería trece y dos bloques serían 20.
Es por eso que los sistemas operativos utilizan el almacenamiento dinámico para poder otorgar el
tamaño exacto que cada programa requiere aunque el tamaño de los bloques sea fijo.
Ejemplo 1. Almacenamiento de 100.000 palabras.
Variante 1.
Un ejemplo de uso simultaneo de bloques de memoria, son los programas que se ejecutan
concurrentemente en un sistema operativo. Estos programas inician su procesamiento en un órden
no previsible de antemano y requieren bloques de memoria de diversos tamaños. Tampoco puede
predecirse cuando terminan su ejecución, y por tanto cuando liberan los bloques de memoria
previamente solicitados. Así el órden de solicitud de bloques de memoria puede diferir en mucho del
órden de devolución de los mismos. Asumamos un almacenamiento dinámico de 100.000 palabras,
inicializada de la siguiente forma, antes de la ejecución de programa alguno.
Aquí toda la memoria estaría disponible, es decir el primer bloque disponible está en la dirección 1
tiene una capacidad de 100,000 palabras.
Ubiquemosnos ahora, luego de que cinco programas, P1, P2, P3, P4 y P5, han iniciado su
procesamiento, luego de requerir 10.000, 15.000, 6.000, 8.000 y 20.000 palabras de memoria
contigua. Puede observarse que el area libre se ha reducido a 41.000 palabras.
La memoria se vería más o menos así:
Donde cada número es el número del programa y la cantidad de veces que se repite son las palabras
otorgadas. P1 10,000 es 1111111111
|1111111111|2222222222|2222233333|3444444445|5555555555|555555555 | | | |
|
*-------------------------------------------------------------------------------------------------------------*
P1 P2 P3 P4 P5 Libres
P1, P2, P3, P4 y P5 son requirieron
10000 15000 6000 8000 20000 41000
Aquí el primer bloque libre empieza en la dirección 59000 y hay 41000 libres
Definicion.
Almacenamiento dinámico es una Estructura de Datos que permite solicitar bloques de ancho
variable de N nodos cada uno y contiguos en memoria. La provisión de los nodos se hace desde un
conjunto de nodos de ancho fijo, de M nodos, conocido con el nombre de Almacenamiento Dinámico.
Una vez utilizados, estos bloques de ancho variable, de N nodos, deben ser devueltos todos juntos,
cuando ya se los haya utilizado. En los siguientes ejemplos la dirección de los nodos del
Almacenamiento Dinámico es de 1 a M.
Se preguntarán ¿De qué estamos hablando?
Bueno, como todos saben, los programas necesitan memoria para su procesamiento, dependiendo
de las necesidades de cada programa es la cantidad de memoria que requiere, no todos requieren la
misma cantidad y si nuestra memoria está constituida por bloques de tamaño fijo, puede ser que
partes de estos bloques se desperdiciaran, es decir si cada bloque es de 10 palabras (palabra es una
unidad de medida que consta de 2 bytes) o 10 bytes para que no se revuelvan y un programa necesita
13, el sistema operativo tendría que asignarle dos bloques, ya que con uno no sería suficiente, de tal
manera que se estarían desperdiciando 7, ya que solo requería trece y dos bloques serían 20.
Es por eso que los sistemas operativos utilizan el almacenamiento dinámico para poder otorgar el
tamaño exacto que cada programa requiere aunque el tamaño de los bloques sea fijo.
Ejemplo 1. Almacenamiento de 100.000 palabras.
Variante 1.
Un ejemplo de uso simultaneo de bloques de memoria, son los programas que se ejecutan
concurrentemente en un sistema operativo. Estos programas inician su procesamiento en un órden
no previsible de antemano y requieren bloques de memoria de diversos tamaños. Tampoco puede
predecirse cuando terminan su ejecución, y por tanto cuando liberan los bloques de memoria
previamente solicitados. Así el órden de solicitud de bloques de memoria puede diferir en mucho del
órden de devolución de los mismos. Asumamos un almacenamiento dinámico de 100.000 palabras,
inicializada de la siguiente forma, antes de la ejecución de programa alguno.
Aquí toda la memoria estaría disponible, es decir el primer bloque disponible está en la dirección 1
tiene una capacidad de 100,000 palabras.
Ubiquemosnos ahora, luego de que cinco programas, P1, P2, P3, P4 y P5, han iniciado su
procesamiento, luego de requerir 10.000, 15.000, 6.000, 8.000 y 20.000 palabras de memoria
contigua. Puede observarse que el area libre se ha reducido a 41.000 palabras.
La memoria se vería más o menos así:
Donde cada número es el número del programa y la cantidad de veces que se repite son las palabras
otorgadas. P1 10,000 es 1111111111
|1111111111|2222222222|2222233333|3444444445|5555555555|555555555 | | | |
|
*-------------------------------------------------------------------------------------------------------------*
P1 P2 P3 P4 P5 Libres
P1, P2, P3, P4 y P5 son requirieron
10000 15000 6000 8000 20000 41000
Aquí el primer bloque libre empieza en la dirección 59000 y hay 41000 libres
