Mark-and-Sweep: Algoritmo de recolección de basura

Hay muchos algoritmos de recolección de basura que se ejecutan en segundo plano, uno de los cuales es marcar y barrer.

A todos los objetos que se crean dinámicamente (usando new en C++ y Java) se les asigna memoria en el montón. Si continuamos creando objetos, es posible que obtengamos un error de falta de memoria, ya que no es posible asignar memoria de almacenamiento dinámico a los objetos. Por lo tanto, debemos borrar la memoria del montón liberando memoria para todos aquellos objetos a los que el programa ya no hace referencia (o los objetos inalcanzables) para que el espacio esté disponible para los nuevos objetos posteriores. Esta memoria puede ser liberada por el propio programador, pero parece ser una sobrecarga para el programador, aquí la recolección de basura viene a nuestro rescate y libera automáticamente la memoria del montón para todos los objetos no referenciados. 

Algoritmo de marca y barrido 

Cualquier algoritmo de recolección de basura debe realizar 2 operaciones básicas. En primer lugar, debe poder detectar todos los objetos inalcanzables y, en segundo lugar, debe recuperar el espacio de almacenamiento dinámico utilizado por los objetos basura y hacer que el espacio vuelva a estar disponible para el programa. Las operaciones anteriores son realizadas por Mark and Sweep Algorithm en dos fases como se enumeran y se describen a continuación: 

• Fase de marca
• Fase de barrido

Fase 1: Marcar Fase 

Cuando se crea un objeto, su bit de marca se establece en 0 (falso). En la fase Marcar, establecemos el bit marcado para todos los objetos accesibles (o los objetos a los que un usuario puede hacer referencia) en 1 (verdadero). Ahora, para realizar esta operación, simplemente necesitamos hacer un recorrido gráfico, un enfoque de búsqueda en profundidad funcionaría para nosotros. Aquí podemos considerar cada objeto como un Node y luego se visitan todos los Nodes (objetos) que son accesibles desde este Node (objeto) y continúa hasta que hayamos visitado todos los Nodes accesibles.

• La raíz es una variable que se refiere a un objeto y es directamente accesible por una variable local. Supondremos que tenemos una sola raíz.
• Podemos acceder al bit de marca de un objeto mediante ‘markedBit(obj)’ .

Algoritmo: Marcar fase 

Mark(root)
If markedBit(root) = false then
                     markedBit(root) = true
                                       For each v referenced by root
                                       Mark(v)

Nota: si tenemos más de una raíz, simplemente tenemos que llamar a Mark() para todas las variables raíz. 

Fase 2: Fase de barrido 

Como sugiere el nombre, «barre» los objetos inalcanzables, es decir, borra la memoria del montón para todos los objetos inalcanzables. Todos aquellos objetos cuyo valor marcado se establece en falso se borran de la memoria del montón, para todos los demás objetos (objetos alcanzables) el bit marcado se establece en verdadero. 
Ahora el valor de marca para todos los objetos alcanzables se establece en falso, ya que ejecutaremos el algoritmo (si es necesario) y nuevamente pasaremos por la fase de marca para marcar todos los objetos alcanzables. 

Algoritmo: fase de barrido 

Sweep()
For each object p in heap
If markedBit(p) = true then
                  markedBit(p) = false
                                 else
                                     heap.release(p)

El algoritmo de marcar y barrer se denomina recolector de basura de rastreo porque rastrea la colección completa de objetos a los que el programa puede acceder directa o indirectamente. 

Ejemplo: 

A. Todos los objetos tienen sus bits marcados establecidos en falso. 
 

B. Los objetos accesibles se marcan como verdaderos

C. Los objetos no accesibles se borran del montón. 

Las ventajas del algoritmo Mark and Sweep son las siguientes: 

• Maneja el caso con referencias cíclicas, incluso en el caso de un ciclo, este algoritmo nunca termina en un bucle infinito.
• No se incurre en gastos generales adicionales durante la ejecución del algoritmo.

Las desventajas del algoritmo Mark and Sweep son las siguientes:

• La principal desventaja del enfoque de marcar y barrer es el hecho de que la ejecución normal del programa se suspende mientras se ejecuta el algoritmo de recolección de elementos no utilizados.
• Otra desventaja es que, después de que el algoritmo Mark and Sweep se ejecuta varias veces en un programa, los objetos accesibles terminan separados por muchas regiones pequeñas de memoria no utilizadas. Mire la siguiente figura para una mejor comprensión. 

Aquí los bloques blancos indican la memoria libre, mientras que los bloques grises indican la memoria ocupada por todos los objetos alcanzables. 

Ahora los segmentos libres (que se indican con color blanco) son de diferentes tamaños, digamos que los 5 segmentos libres son de tamaño 1, 1, 2, 3, 5 (tamaño en unidades). 
Ahora necesitamos crear un objeto que tome 10 unidades de memoria, ahora suponiendo que la memoria se puede asignar solo en forma de bloques contiguos, la creación de un objeto no es posible aunque tenemos un espacio de memoria disponible de 12 unidades y lo hará. causa el error OutOfMemory . 

Este problema se denomina «Fragmentación». Tenemos memoria disponible en «fragmentos», pero no podemos utilizar ese espacio de memoria. Podemos reducir la fragmentación por compactación; barajamos el contenido de la memoria para colocar todos los bloques de memoria libres juntos para formar un bloque grande. Ahora considere el ejemplo anterior, después de la compactación tenemos un bloque contiguo de memoria libre de 12 unidades de tamaño, por lo que ahora podemos asignar memoria a un objeto de 10 unidades de tamaño. 

Este artículo es una contribución de Chirag Agarwal. Si le gusta GeeksforGeeks y le gustaría contribuir, también puede escribir un artículo y enviarlo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks. Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.