Estructura de Datos : Almacenamiento Dinamico


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.


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.

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|
          *------*-------------*                                *------*-------------*

Variante 2.

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|
          *------*-------------*                                *------*-------------*

Variante 3.

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   |
          *------*-------------*            *------*--------------*   *------*--------------*   *------*--------------*

Variante 4.

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   |
          *-------------*                      *--------------*   *--------------*   *--------------*

Variante 5.

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   |
          *-------------*                      *--------------*   *--------------*   *--------------*   *--------------*

Variante 6.

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   |
          *-------------*                      *--------------*   *--------------*   *--------------*   *--------------*

Variante 7.

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   |
          *-------------*                      *--------------*   *--------------*   *--------------*   *--------------*

Variante 8.

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 --------------------------------------------------------------+

Variante 9.

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 --------------------------------------------------------------+

Variante 10.

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 |
*-----------------------*

Variante 11.

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 |
*-------------------------------*

Variante 12.

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 |       |
          *-------------------------------*         *-------------------------------*

Variante 13.

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 )


Ejemplo 2. Almacenamiento de 5.000 palabras.

Aceptacion de 6 requerimientos de Bloques.

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

El requerimiento 5 libera los nodos, 4 enlaces cambian.

                                                                                +--------------------------------------+
 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

El requerimiento 4 libera los nodos, 4 enlaces cambian.

                                                                +-----------------------------------------------------+
 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

El requerimiento 3 libera los nodos, 0 enlaces cambian.

                                                +-----------------------------------------------------+
 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

El requerimiento 5 libera los nodos, 4 enlaces fijados.

                                +-----------------------------------------------------+
 1               4101           |                        1001           4701          |
*----------*    *----------*    +-->*-----------*------>*----------*-->*----------*---+
| 1 | 1000 |    | 1 |  600 |        |   | 0 |   |       | 0 | 3100 |   | 0 |  300 |
|----------|    |----------|    +---*-----------*<------|----------|<--|----------|<--+
|          |    |          |    |                       |          |   |          |   |
|          |    |          |    +-----------------------|          |---|          |---+
|    P6    |    |    P2    |                            |          |   |          |
|          |    |          |                            |          |   |          |
|          |    |          |                            |          |   |          |
|----------|    |----------|                            |----------|   |----------|
| 1 |      |    | 1 |      |                            | 0 | 1001 |   | 0 | 4701 |
*----------*    *----------*                            *----------*   *----------*
 1000            4700

El requerimiento 2 libera los nodos, 2 enlaces cambian.




                +--------------------------------------+
 1              |                        1001          |
*----------*    +-->*-----------*------>*----------*---+
| 1 | 1000 |        |   | 0 |   |       | 0 | 4000 |
|----------|    +---*-----------*<------|----------|<--+
|          |    |                       |          |   |
|          |    +-----------------------|          |---+
|    P6    |                            |          |
|          |                            |          |
|          |                            |          |
|----------|                            |----------|
| 1 |      |                            | 0 | 1001 |
*----------*                            *----------*
 1000