Recolección de Basura en Programación: Tipos y Funcionamiento

Definición

La liberación automática de memoria dinámica se conoce como recolección de basura.

Tipos de Recolección de Basura

Desocupación sobre la marcha (Free as you go)

Consiste en desalojar los objetos en el momento en el que no están referenciados por ningún puntero. Se utiliza un contador de enlaces en cada objeto. Cuando un puntero se referencia a un objeto, se incrementa su contador. Cuando un puntero deja de referenciar a un objeto, se decrementa su contador. Si al decrementar el contador se llega a cero, se libera el objeto.

Inconvenientes:

• No permite liberar estructuras circulares (ya que los contadores nunca llegan a cero).
• Requiere muchas instrucciones para cambiar el valor de un puntero, lo que hace que el código sea más lento.

En la práctica, estos inconvenientes provocan que no se utilice esta técnica.

Marcar y barrer (Mark-and-sweep)

El origen de los enlaces a los objetos alojados en la memoria dinámica se encuentra en las variables del programa. Estas variables se conocen como raíces (roots). Todos los objetos deben tener un campo que permite marcarlos.

Consta de dos fases: marcado y barrido.

El método de marcado se ejecuta sobre todas las raíces y hace lo siguiente:

• Si el objeto ya está marcado, no hace nada.
• Si el objeto no está marcado, lo marca y ejecuta el método de marcar para todos los campos del objeto que sean referencias a otro objeto.

El método de barrido consiste en un recorrido de todos los bloques del montículo:

• Si el bloque está marcado, se desmarca.
• Si el bloque no está marcado, se libera.

Recolección por copia (Copying collection)

Se consideran dos bloques de memoria dinámica: un bloque que se utiliza realmente como montículo (from-space) y otro del mismo tamaño que se considera libre (to-space). Se copian desde from-space a to-space todos los objetos alcanzables desde las raíces y se intercambian los papeles de los bloques. El algoritmo de copia debe realizar un recorrido desde las raíces, pasando por todos los campos de cada objeto que sean referencias a otros objetos.

El método de copia hace lo siguiente:

• Si el objeto no ha sido copiado, se copia su contenido desde from-space a to-space. El original en from-space se marca como copiado y se indica la nueva posición.
• Si el objeto ya ha sido copiado, se actualiza la referencia a la nueva posición en to-space.

Ventaja: El alojamiento es secuencial y no se necesita ninguna forma de desalojo.

Desventaja: Requiere el doble de memoria.

Recolección generacional

Los objetos recién creados tienen más probabilidad de ser liberados a corto plazo. Los objetos que no se han eliminado en algunas iteraciones probablemente formen parte del núcleo duro de las estructuras de datos del programa y nunca sean desreferenciados. El montículo se divide en generaciones. Los objetos más jóvenes se encuentran en la primera generación (G0). La generación G1 contiene objetos más antiguos que los de G0. Los de G2 son más viejos que los de G1, etc. La recolección se centra en G0. Cada cierto número de recolecciones se estudia también G1. Tras un número de recolecciones mayor se estudia G2, etc. Los objetos que sobreviven un cierto número de recolecciones se copian a una generación superior. Esto permite reducir el tiempo de recolección, ya que el tamaño del montículo estudiado es menor.

Recolección incremental

La recolección de basura es muy costosa en tiempo y puede ser problemática en sistemas en tiempo real. Los algoritmos incrementales se basan en que el proceso recolector no paralice al programa, sino que se ejecute en paralelo a este. Los objetos se dividen en tres tipos:

• Blancos: No han sido estudiados por el recolector.
• Grises: Han sido estudiados, pero cuyos campos no lo han sido.
• Negros: Han sido estudiados y cuyos hijos también lo han sido.

Cuando no existen objetos de tipo gris, entonces todos los objetos de tipo blanco son basura y pueden ser eliminados. La ejecución del programa puede provocar que los objetos cambien de tipo (muten). El código del programa debe modificarse para que la creación de objetos y los cambios de punteros provoquen mutaciones en el color de los objetos.