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.
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.
Inicializar ( Initialization ) Init(int m) -----> boolean r m = ancho almacenamiento
r = retorno
1
1 2 3 4 5 6 7 8 9 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
*-------------------------------------------------------------------------------------------------------------* Direccion del primer nodo = 1
| | | | | | | | | | |
*-------------------------------------------------------------------------------------------------------------* Direccion del ultimo nodo = 100.000
*------*-------------* *------*-------------*
AV ---> | POSI | SIZE | LINK | AV ---> | 1|100000| 0|
*------*-------------* *------*-------------*
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.
Requerir ( Require ) Requ(int n) -----> int p n = cantidad solicitada
p = posicion otorgada
*-------------------------------------------------------------------------------------------------------------*
|1111111111|2222222222|2222233333|3444444445|5555555555|555555555 | | | | |
*-------------------------------------------------------------------------------------------------------------*
P1 P2 P3 P4 P5 Libres P1, P2, P3, P4 y P5 son requerimientos
10000 15000 6000 8000 20000 41000
*------*-------------* *------*-------------*
AV ---> | POSI | SIZE | LINK | AV ---> | 59001| 41000| 0|
*------*-------------* *------*-------------*
Asumamos ahora que los programas P2 y P4 han terminado y devuelto sus
bloques de memoria. Los bloques de memoria devueltos han sido incorporados
a la lista de palabras libres.
Observar que los nodos de la lista de palabras libres debe
contar con los siguientes campos de información :
Liberar ( Release ) Rele(int p, int n) -----> boolean r p = posicion devolucion
n = cantidad devuelta
r = retorno
*-------------------------------------------------------------------------------------------------------------*
|1111111111| | 33333|3 5|5555555555|555555555 | | | | |
*-------------------------------------------------------------------------------------------------------------*
P1 P3 P5 Libres P2 y P4 devolvieron nodos solicitados
10000 6000 20000 41000
*------*-------------* *------*--------------* *------*--------------* *------*--------------*
AV ---> | POSI | SIZE | LINK | AV ---> | 10001| 15000| *---|-->| 31001| 8000| *---|-->| 59001| 41000| 0 |
*------*-------------* *------*--------------* *------*--------------* *------*--------------*
Hasta este punto hemos propuesto una lista de palabras libres escendidas
del propio almacenamiento dinámico.
La variable AV apuntaba el primer nodo de esa lista existente fuera del
almacenamiento dinámico.
Incorporemos al mismisimo almacenamiento dinámico la lista de bloques de
palabras libres. Ubicaremos cada nodo de la lista de bloques de palabras libres
al comienso del respectivo bloque libre. Al hacerlo habremos reducido
la cantidad de campos necesarios a :
Ahora la variable AV apuntará al primer bloque de palabras libre, la
que será una dirección dentro del rango 1 a M del almacenamiento dinámico.
Para simplificar nuestros razonamientos, estamos asumiendo que un nodo
de la lista de de bloques libres ocupa una palabra. O lo que es lo mismo,
el ancho del nodo, establece la unidad de almacenamiento del almacenamiento
dinámico.
Problema 1 - Lista de Nodos Libres no inmersa en Lista de Nodos Ocupados
Mejora 1 - La lista de Nodos Libres dentro del Almacenamiento
*-------------------------------------------------------------------------------------------------------------*
|1111111111| | 33333|3 5|5555555555|555555555 | | | | |
*-------------------------------------------------------------------------------------------------------------*
P1 P3 P5 Libres
10000 6000 20000 41000
*------*-------------* *------*--------------* *------*--------------* *------*--------------*
AV ---> | POSI | SIZE | LINK | AV ---> | 10001| 15000| 31001 |-->| 31001| 8000| 59001 |-->| 59001| 41000| 0 |
*------*-------------* *------*--------------* *------*--------------* *------*--------------*
*-------------* *--------------* *--------------* *--------------*
AV ---> | SIZE | LINK | AV ---> | 15000| 31001|-->| 8000| 59001|-->| 41000| 0 |
*-------------* *--------------* *--------------* *--------------*
El uso de nodos cabeza en las estrucuturas de datos tiene la virtud
de simplificar los algoritmos de dicha estructura.
Usaremos aquí este concepto, incorporando un nodo cabeza en la primer
posición del almacenamiento dinámico. Reducimos así en una palabra
las palabras disponibles del almacenamiento dinámico.
Dicho nodo cabeza tiene la misma estructura de todos los nodos, salvo
que el campo que indica el tamaño, es simpre 0.
Ahora la variable AV apunta al nodo cabeza, o sea, a la posición 1 del
rango 1 a M del almacenamiento dinámico.
Por la aparición de este nodo, todos los bloques otorgados se desplazan
una unidad.
Observar que la cantidad de palabras libres disponibles en cada bloque
incluye la palabra que se usa como nodo para el enlace de los bloques
libres.
Problema 2 - Algoritmos complejos por tratamiento diferencial del primer nodo libre
Mejora 2 - Lista Simplemente Enlazada con nodo cabecera de ancho cero
*-------------* *--------------* *--------------* *--------------* *--------------*
AV ---> | SIZE | LINK | AV ---> | 0| 10002|-->| 15000| 31002|-->| 8000| 59002|-->| 40999| 0 |
*-------------* *--------------* *--------------* *--------------* *--------------*
Introduzcamos una nueva reforma.
Una mejor disposición se obtiene si otorgamos memoria desde las posiciones
altas hacia las posiciones bajas.
Así, en la posición 1 está el nodo cabeza, en la posición 2 está el
nodo del primer bloque de palabras libres.
Problema 3 - Se modifican mucho los campos de enlace
Mejora 3 - Otorgar memoria desde la posicion mas alta hacia la mas baja
*-------------------------------------------------------------------------------------------------------------*
| | | | | 555555555|5555555555|5444444443|3333322222|2222222222|1111111111|
*-------------------------------------------------------------------------------------------------------------*
Libres P5 P4 P3 P2 P1
41000 20000 8000 6000 15000 10000
*-------------------------------------------------------------------------------------------------------------*
| | | | | 555555555|5555555555|5 3|33333 | |1111111111|
*-------------------------------------------------------------------------------------------------------------*
Libres P5 P3 P1
41000 20000 6000 10000
*-------------* *--------------* *--------------* *--------------* *--------------*
AV ---> | SIZE | LINK | AV ---> | 0| 1 |-->| 40999| |-->| 8000| |-->| 15000| 0 |
*-------------* *--------------* *--------------* *--------------* *--------------*
Consideremos ahora dos nuevos programas listos a comenzar su procesamiento.
P6 solicita 13.000 palabras libres. P7 solicita 4.000 palabras libres.
Veamos que ocurre con P6, si es el primero que arranca de los dos.
Veamos que ocurre con P7, si es el primero que arranca de los dos.
A continuación se grafica la alternativa BestFit.
Observar que no hay cambio de enlaces, solo cambios de tamaño de palabras
libres en los bloques respectivos.
Problema 4 - No se investiga cual es el mejor lugar para otorgar memoria
Mejora 4 - Implementar algoritmos que exploran la cadena de nodos libres
FirstFit(int n) -----> int p n = cantidad requerida
BestFit(int n) -----> int p p = posicion otorgada
BestFitExtended(int n) -----> int p, int o o = cantidad otorgada
*-------------------------------------------------------------------------------------------------------------*
| | | | | 555555555|5555555555|5 77773|33333 666|6666666666|1111111111|
*-------------------------------------------------------------------------------------------------------------*
Libres P5 P7 P3 P6 P1
41000 20000 4000 6000 13000 10000
*-------------* *--------------* *--------------* *--------------* *--------------*
AV ---> | SIZE | LINK | AV ---> | 0| 1 |-->| 40999| |-->| 4000| |-->| 2000| 0 |
*-------------* *--------------* *--------------* *--------------* *--------------*
Para evitar la formación de grupos de bloques de palabras libres chicos
en determinadas areas del almacenamiento dinámico, utilizo una lista
circular para la lista de bloques de palabras libres.
Problema 5 - La Lista de Nodos Libres acumula nodos chicos en las posiciones bajas
Mejora 5 - Implementar Lista de Nodos Libres circulares con comienzo en el ultimo bloque otorgado
+------------------------------------------------------------------------------+
| |
*-------------* | *--------------* *--------------* *--------------* *--------------* |
AV ---> | SIZE | LINK | +-->| 0| 1 |-->| 40999| |-->| 4000| |-->| 2000| |--+
*-------------* *--------------* *--------------* *--------------* *--------------*
A
|
AV --------------------------------------------------------------+
Observemos que ocurre si P3 termina y devuelve su bloque de palabras.
P3 ocupaba 6.000 palabras. A lado de ese bloque existe un bloque de
2.000 palabras libres. La idea es unir los bloques de palabras libres
contiguos.
En lugar de crear un nodo nuevo de 6.000 palabras libres, ajusto el nodo
libre de 2.000 palabras a uno de 8.000 palabras libres que comience en
el bloque dejado por P3.
Problema 6 - No se detectan los bloques libres contiguos
Mejora 6 - Implementar examen de bloques libres contiguos
*-------------------------------------------------------------------------------------------------------------*
| | | | | 555555555|5555555555|5 7777 | 666|6666666666|1111111111|
*-------------------------------------------------------------------------------------------------------------*
Libres P5 P7 P6 P1
41000 20000 4000 13000 10000
Condicion de Bloque Contiguo del Bloque Q de ancho N y comienzo en P
Bloque Contiguo Libre Derecho de Q -----> Si comienza en p + n
Bloque Contiguo Libre Isquierdo de Q -----> Si termina en p - 1
+------------------------------------------------------------------------------+
| |
*-------------* | *--------------* *--------------* *--------------* *--------------* |
AV ---> | SIZE | LINK | +-->| 0| 1 |-->| 40999| |-->| 4000| |-->| 8000| |--+
*-------------* *--------------* *--------------* *--------------* *--------------*
A
|
AV --------------------------------------------------------------+
Para mejorar la navegación de la lista de nodos de bloques de palabras libres
implemento una lista enlazada doble.
Problema 7 - Dificultad para examinar las condiciones de bloques libres contiguos
Mejora 7 - Implementar Lista de Nodos Libres doblemente enlazadas circulares
*-----------------------*
| LLINK | SIZE | RLINK |
*-----------------------*
Si interesa administrar tanto lo bloques de palabras libres como los
bloques de palabras ocupadas, dispongo la misma estructura de lista
para ambas categorías. El nodo a utilizar tiene ahora un cuarto campo,
el campo TAG. Si TAG = 1 el bloque es un bloque de palabras ocupadas.
Si TAG = 0 el bloque es un bloque de palabras libres.
*-------------------------------*
| LLINK | TAG | SIZE | RLINK |
*-------------------------------*
Para mejorar aún más la navegación de la lista de nodos de bloques libres
incorporo un nodo al final de cada uno de estos bloques, donde un enlace
nos lleva directamente al comienzo del bloque en cuestión.
Con el campo SIZE puedo ir desde el nodo de comienzo de bloque al nodo
de final de bloque.
Para conservar la simetría hago lo mismo con la lista de nodos de bloques
ocupados.
*-------------------------------* *-------------------------------*
| | TAG=1 | SIZE | | | LLINK | TAG=0 | SIZE | RLINK |
*-------------------------------* *-------------------------------*
| | | |
| | | |
| Bloque Ocupado | | Bloque Libre |
| | | |
| | | |
*-------------------------------* *-------------------------------*
| | TAG=1 | | | | | TAG=0 | ULINK | |
*-------------------------------* *-------------------------------*
Observemos la disposición de las listas de nodos de bloques libres y ocupados,
ubicando el nodo cabeza dentro y fuera del almacenamiento dinámico.
*-------------------------------*
AV ---->| LLINK | TAG=0 | 0 | RLINK |
+-->*-------------------------------*---+
| |
| |
*------* +-----*-------------------------------*<----+ +---*-------------------------------*<--+
| | 1 | | LLINK | TAG=0 | 0 | RLINK | | | LLINK | TAG=0 | SIZE | RLINK |
| | | +-->*-------------------------------*---+ | *-------------------------------*
| | | +---*-------------------------------*<--+ | | |
| | | | LLINK | TAG=0 | SIZE | RLINK | | | |
| | | +-->*-------------------------------*---+ | | |
| | | | | | | | | |
| | | | | | | | | |
| | | | | Bloque Libre | | | | Bloque Libre |
| | | | | | | | | |
| | | | | | | | | |
/ / / / / /
/ / / / / /
| | | | | | | | | |
| | | | | | | | | |
| | | | | Bloque Libre | | | | Bloque Libre |
| | | | | | | | | |
| | | | | | | | | |
| | | | *-------------------------------* | | *-------------------------------*
| | | | | | TAG=0 | ULINK | | | | | | TAG=0 | ULINK | |
| | | | *-------------------------------* | | *-------------------------------*
| | | +---*-------------------------------*<--+ | *-------------------------------*
| | | | LLINK | TAG=0 | SIZE | RLINK |---+ | | LLINK | TAG=0 | SIZE | RLINK |
| | | +-->*-------------------------------* | | *-------------------------------*
| | | | | | | | | |
| | | | | | | | | |
| | | | | Bloque Libre | | | | Bloque Libre |
| | | | | | | | | |
| | | | | | | | | |
| | | | *-------------------------------* | | *-------------------------------*
| | | | | | TAG=0 | ULINK | | | | | | TAG=0 | ULINK | |
| | | | *-------------------------------* | | *-------------------------------*
| | | | *-------------------------------* | | *-------------------------------*
| | | | | | TAG=1 | SIZE | | | | | | TAG=0 | SIZE | |
| | | | *-------------------------------* | | *-------------------------------*
| | | | | | | | | |
| | | | | | | | | |
| | | | | Bloque Ocupado | | | | Bloque Ocupado |
| | | | | | | | | |
| | | | | | | | | |
/ / / / / /
/ / / / / /
| | | | | | | | | |
| | | | | | | | | |
| | | | | Bloque Ocupado | | | | Bloque Ocupado |
| | | | | | | | | |
| | | | | | | | | |
| | | | *-------------------------------* | | *-------------------------------*
| | | | | | TAG=1 | | | | | | | TAG=0 | | |
| | | | *-------------------------------* | | *-------------------------------*
| | | +---*-------------------------------*<--+ | *-------------------------------*
| | | | LLINK | TAG=0 | SIZE | RLINK | | | LLINK | TAG=0 | SIZE | RLINK |
| | +---->*-------------------------------*-----+ *-------------------------------*
| | | | | |
| | | | | |
| | | Bloque Libre | | Bloque Libre |
| | | | | |
| | | | | |
| | *-------------------------------* *-------------------------------*
| | m | | TAG=0 | ULINK | | | | TAG=0 | ULINK | |
*------* *-------------------------------* *-------------------------------*
Almacenamiento Nodo Cabeza dentro Nodo Cabeza fuera
de M palabras del Almacenamiento del Almacenamiento
( 1 a m )
M = 5000
1 1 2 2 3 3 4 4 5
5 0 5 0 5 0 5 0 5 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
*-------------------------------------------------------------------------------------------------------------*
|6666666666|6666666666|5555555555|5555555555|5555555555|4444444444|4444333333|3333333333|3322222222|2222111111|
*-------------------------------------------------------------------------------------------------------------*
P6 P5 P4 P3 P2 P1
1000 1500 700 900 600 300
+-------------------+
1 1001 2501 3201 4101 4701 | |
*----------* *----------* *----------* *----------* *----------* *----------* +-->*-----------*---+
| 1 | 1000 | | 1 | 1500 | | 1 | 700 | | 1 | 900 | | 1 | 600 | | 1 | 300 | | | 0 | |
|----------| |----------| |----------| |----------| |----------| |----------| +---*-----------*<--+
| | | | | | | | | | | | | |
| | | | | | | | | | | | +-------------------+
| P6 | | P5 | | P4 | | P3 | | P2 | | P1 |
| | | | | | | | | | | |
| | | | | | | | | | | |
|----------| |----------| |----------| |----------| |----------| |----------|
| 1 | | | 1 | | | 1 | | | 1 | | | 1 | | | 1 | |
*----------* *----------* *----------* *----------* *----------* *----------*
1000 2500 3200 4100 4700 5000
+--------------------------------------+
1 1001 2501 3201 4101 | 4701 |
*----------* *----------* *----------* *----------* *----------* +-->*-----------*------>*----------*---+
| 1 | 1000 | | 1 | 1500 | | 1 | 700 | | 1 | 900 | | 1 | 600 | | | 0 | | | 0 | 300 |
|----------| |----------| |----------| |----------| |----------| +---*-----------*<------|----------|
| | | | | | | | | | | | |
| | | | | | | | | | +---------------------->| |
| P6 | | P5 | | P4 | | P3 | | P2 | | |
| | | | | | | | | | | |
| | | | | | | | | | | |
|----------| |----------| |----------| |----------| |----------| |----------|
| 1 | | | 1 | | | 1 | | | 1 | | | 1 | | | 0 | 4701 |
*----------* *----------* *----------* *----------* *----------* *----------*
1000 2500 3200 4100 4700
+-----------------------------------------------------+
1 1001 3201 4101 | 2501 4701 |
*----------* *----------* *----------* *----------* +-->*-----------*------>*----------*-->*----------*---+
| 1 | 1000 | | 1 | 1500 | | 1 | 900 | | 1 | 600 | | | 0 | | | 0 | 700 | | 0 | 300 |
|----------| |----------| |----------| |----------| +---*-----------*<------|----------|<--|----------|<--+
| | | | | | | | | | | | | |
| | | | | | | | +-----------------------| |---| |---+
| P6 | | P5 | | P3 | | P2 | | | | |
| | | | | | | | | | | |
| | | | | | | | | | | |
|----------| |----------| |----------| |----------| |----------| |----------|
| 1 | | | 1 | | | 1 | | | 1 | | | 0 | 2501 | | 0 | 4701 |
*----------* *----------* *----------* *----------* *----------* *----------*
1000 2500 4100 4700
+-----------------------------------------------------+
1 1001 4101 | 2501 4701 |
*----------* *----------* *----------* +-->*-----------*------>*----------*-->*----------*---+
| 1 | 1000 | | 1 | 1500 | | 1 | 600 | | | 0 | | | 0 | 1600 | | 0 | 300 |
|----------| |----------| |----------| +---*-----------*<------|----------|<--|----------|<--+
| | | | | | | | | | | |
| | | | | | +-----------------------| |---| |---+
| P6 | | P5 | | P2 | | | | |
| | | | | | | | | |
| | | | | | | | | |
|----------| |----------| |----------| |----------| |----------|
| 1 | | | 1 | | | 1 | | | 0 | 2501 | | 0 | 4701 |
*----------* *----------* *----------* *----------* *----------*
1000 2500 4700
+-----------------------------------------------------+
1 4101 | 1001 4701 |
*----------* *----------* +-->*-----------*------>*----------*-->*----------*---+
| 1 | 1000 | | 1 | 600 | | | 0 | | | 0 | 3100 | | 0 | 300 |
|----------| |----------| +---*-----------*<------|----------|<--|----------|<--+
| | | | | | | | | |
| | | | +-----------------------| |---| |---+
| P6 | | P2 | | | | |
| | | | | | | |
| | | | | | | |
|----------| |----------| |----------| |----------|
| 1 | | | 1 | | | 0 | 1001 | | 0 | 4701 |
*----------* *----------* *----------* *----------*
1000 4700
+--------------------------------------+
1 | 1001 |
*----------* +-->*-----------*------>*----------*---+
| 1 | 1000 | | | 0 | | | 0 | 4000 |
|----------| +---*-----------*<------|----------|<--+
| | | | | |
| | +-----------------------| |---+
| P6 | | |
| | | |
| | | |
|----------| |----------|
| 1 | | | 0 | 1001 |
*----------* *----------*
1000