Completar sección de marcado y barrido

[z.facultad/75.00/informe.git] / source / gc.rst

diff --git a/source/gc.rst b/source/gc.rst
index 96da51bc7cba15b9c756bfcb71680884804a9e41..b6db7a09052aaa374f2566b1c6355091b8d64d65 100644 (file)
--- a/source/gc.rst
+++ b/source/gc.rst
@@ -1609,7 +1609,71 @@ figura :vref:`fig:gc-rc-cycle`).
 Marcado y barrido
 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
 
 Marcado y barrido
 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
 

-TODO
+Este algoritmo es el más parecido a la teoría sobre recolección de basura.
+Consiste en realizar la recolección en 2 fases: marcado y barrido. La primera
+fase consiste en el proceso de marcar el grafo de conectividad del *heap* para
+descubrir qué celdas son alcanzables desde el *root set*, tal y como se
+describió en :ref:`ref_gc_intro_mark`.
+
+Una vez marcadas todas las celdas, se sabe que las celdas *blancas* son
+*basura*, por lo tanto el paso que queda es el *barrido* de estas celdas,
+liberándolas. Esto se efectúa recorriendo todo el *heap*. Por lo tanto cada
+recolección es :math:`O(\lvert Heap \rvert)`, a diferencia del conteo de
+referencia que dijimos que en el peor caso es :math:`O(\lvert Live \thickspace
+set \rvert)`. Sin embargo el conteo de referencias se ejecuta **cada vez que
+se actualiza una referencia** mientras que la recolección en el marcado
+y barrido se realiza típicamente solo cuando el *mutator* pide una celda pero
+no hay ninguna libre. Esto hace que la constante del conteo de referencias sea
+típicamente varios órdenes de magnitud mayores que en el marcado y barrido.
+
+A continuación se presentan los servicios básicos de este algoritmo::
+
+   function new() is
+      cell = alloc()
+      if cell is null
+         collect()
+      cell = alloc()
+      if cell is null
+         throw out_of_memory
+      return cell
+
+   function collect() is
+      mark_phase()
+      sweep_phase()
+
+   function sweep_phase() is
+      foreach cell in heap
+         if cell.marked
+            cell.marked = false
+         else
+            free(cell)
+
+El algoritmo ``mark_sweep()`` es exactamente igual al presentado en
+:ref:`ref_gc_intro_mark`. Es preciso notar que la fase de barrido
+(``sweep_phase()``) debe tener una comunicación extra con el *low level
+allocator* para poder obtener todas las celdas de memoria que existen en el
+*heap*.
+
+A diferencia del conteo de referencias, este algoritmo es :ref:`indirecto
+<ref_gc_direct>` y :ref:`no incremental <ref_gc_inc>`, ya que se realiza un
+recorrido de todo el *heap* de forma espaciada a través de la ejecución del
+programa. En general el *mutator* sufre pausas considerablemente mayores (en
+promedio) que con el conteo de referencias, lo que puede ser problemático para
+aplicaciones con requerimientos rígidos de tiempo, como aplicaciones
+*real-time*. Debido a la percepción de las pausas grandes, este tipo de
+colectores se conocen como :ref:`stop-the-world <ref_gc_concurrent>` (o
+*detener el mundo*).
+
+Una ventaja fundamental sobre el conteo de referencias es la posibilidad de
+reclamar estructuras cíclicas sin consideraciones especiales. Podemos observar
+como esto es posible analizando el ejemplo en las figuras
+:r:`fig:gc-mark-1` y :vref:`fig:gc-mark-2`. Si se eliminaran las referencias
+:math:`r0 \to h1` y :math:`h6 \to h2`, la fase de marcado consistiría
+solamente en marcar la celda :math:`h6`, pues es la única alcanzable desde el
+*root set*. Todas las demás celdas permanecerían blancas y por lo tanto pueden
+ser liberadas sin inconvenientes en la fase de barrido, que recorre el *heap*
+linealmente.
+