+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:`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:`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
+<gc_direct>` y :ref:`no incremental <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 <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.
+
+
+
+.. _gc_copy:
+
+Copia de semi-espacio
+~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
+
+Este algoritmo consiste en hacer una partición del *heap* en 2 mitades
+o *semi-espacios*, llamados usualmente *Fromspace* y *Tospace*. El primero se
+utiliza para asignar nuevas celdas de forma lineal, asumiendo un *heap*
+contiguo, incrementando un puntero (ver figura :vref:`fig:gc-copy`). Esto se
+conoce como *pointer bump allocation* y es, probablemente, la forma más
+eficiente de asignar memoria (tan eficiente como asignar memoria en el
+*stack*). Esto permite además evitar el problema de la *fragmentación* de
+memoria [#gcfrag]_ que normalmente afectan a los otros algoritmos clásicos (o
+sus *low level allocators*).
+
+.. [#gcfrag] La *fragmentación* de memoria sucede cuando se asignan objetos
+ de distintos tamaños y luego libera alguno intermedio, produciendo
+ *huecos*. Estos *huecos* quedan inutilizables hasta que se quiera
+ asignar un nuevo objeto de tamaño igual al *hueco* (o menor). Si esto no
+ sucede y se acumulan muchos *huecos* se dice que la memoria está
+ *fragmentada*.
+
+.. flt:: fig:gc-copy
+
+ Estructura del *heap* de un recolector con copia de semi-espacios
+
+ .. aafig::
+ :aspect: 70
+ :scale: 115
+
+ zzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzz
+
+ /---+"Fromspace" /---+"Tospace"
+ | |
+ V_______________________________V_______________________________
+ | XXXX X XXX aaaaaaaaaaaaaaaa|bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb|
+ | XXXX X XXX aaaaaaaaaaaaaaaa|bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb|
+ | XXXX X XXX aaaaaaaaaaaaaaaa|bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb|
+ |~~~~~~~~~~~~~~~A~~~~~~~~~~~~~~~|~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
+ |
+ | | | XX "Fromspace usado"
+ \---+"libre"
+ | | ZZ "Fromspace basura"
+
+ |/ "longitud del semi-espacio" |/ AA "Fromspace libre"
+ +- - - - - - - - - - - - - - - -+
+ /| /| BB "Tospace"
+
+
+La segunda mitad (*Tospace*) permanece inutilizada hasta que se agota el
+espacio en el *Fromspace*; en ese momento comienza el proceso de recolección
+de basura que consiste en recorrer el grafo de conectividad, copiando las
+celdas *vivas* del *Fromspace* al *Tospace* de manera contigua, como si
+estuvieran asignando por primera vez. Como la posición en memoria de las
+celdas cambia al ser movidas, es necesario actualizar la dirección de memoria
+de todas las celdas *vivas*. Para esto se almacena una dirección de memoria de
+re-dirección, *forwarding address*, en las celdas que mueven. La *forwarding
+address* sirve a su vez de marca, para no recorrer una celda dos veces (como
+se explica en :ref:`gc_intro_mark`). Cuando se encuentra una celda que ya fue
+movida, simplemente se actualiza la referencia por la cual se llegó a esa
+celda para que apunte a la nueva dirección, almacenada en la *forwarding
+address*. Una vez finalizado este proceso, el *Fromspace* y *Tospace*
+invierten roles y se prosigue de la misma manera (todo lo que quedó en el
+viejo *Fromspace* es *basura* por definición, por lo que se convierte el
+*Tospace*).
+
+A continuación se presenta una implementación sencilla de los servicios
+provistos por este tipo de recolectores. Cabe destacar que este tipo de
+recolectores deben estar íntimamente relacionados con el *low level
+allocator*, ya que la organización del *heap* y la forma de asignar memoria es
+parte fundamental de este algoritmo. Se asume que ya hay dos áreas de memoria
+del mismo tamaño destinadas al *Fromspace* y *Tospace*, y la existencia de
+4 variables globales: ``fromspace`` (que apunta a la base del *Fromspace*),
+``tospace`` (que apunta a la base del *Tospace*), ``spacesize`` (que contiene
+el tamaño de un semi-espacio) y ``free`` (que apunta al lugar del *Fromspace*
+donde comienza la memoria libre). También vale aclarar que este algoritmo
+soporta inherentemente celdas de tamaño variable, por lo que los servicios
+``alloc()`` y ``new()`` [#gccopynew]_ reciben como parámetro el tamaño de la
+celda a asignar::
+
+ function alloc(size) is
+ if free + size > fromspace + spacesize
+ return null
+ else
+ cell = free
+ free = free + size
+ return cell
+
+ function new(size) is
+ cell = alloc(size)
+ if cell is null
+ collect()
+ cell = alloc(size)
+ if cell is null
+ throw out_of_memory
+ return cell
+
+ function collect() is
+ free = tospace
+ foreach r in root_set
+ r = copy(r)
+ fromspace, tospace = tospace, fromspace
+
+ function copy(cell) is
+ if cell.forwarding_address is null
+ cell.forwarding_address = free
+ cell.copy_to(free)
+ free = free + cell.size
+ foreach child in cell
+ child = copy(child)
+ return cell.forwarding_address
+ else
+ return cell.forwarding_address
+
+.. [#gccopynew] Notar que ``new()`` es igual que en el marcado y barrido con
+ la salvedad de que en este caso toma como parámetro el tamaño de la celda.
+
+Esta técnica tiene nombres variados en inglés: *semi-space*, *two-space*
+o simplemente *copying collector*. En este documento se denomina "copia de
+semi-espacio" porque los otros nombres son demasiado generales y pueden
+describir, por ejemplo, algoritmos donde no hay copia de celdas o donde no hay
+2 semi-espacios (como se verá en :ref:`gc_art`).
+
+Al igual que el :ref:`gc_mark_sweep` este algoritmo es :ref:`indirecto
+<gc_direct>`, :ref:`no incremental <gc_inc>` y :ref:`stop-the-world
+<gc_concurrent>`. Las diferencias con los esquemas vistos hasta ahora son
+evidentes. La principal ventaja sobre el marcado y barrido (que requiere una
+pasada sobre el *live set*, el marcado, y otra sobre el *heap* entero, el
+barrido) es que este método requiere una sola pasada y sobre las celdas vivas
+del *heap* solamente. La principal desventaja es copia memoria, lo que puede
+ser particularmente costoso, además de requerir, como mínimo, el doble de
+memoria de lo que el *mutator* realmente necesita. Esto puede traer en
+particular problemas con la memoria virtual y el caché, por la pobre localidad
+de referencia.
+
+Por lo tanto los recolectores de este tipo pueden ser convenientes por sobre
+el marcado y barrido cuando se espera que el *live set* sea muy pequeño luego
+de una recolección. En estos casos el trabajo realizado por este tipo de
+recolectores puede ser considerablemente menor que el del marcado y barrido.
+Y por el contrario, si el *working set* es pequeño, al ser *compactado* en
+memoria puede mejorar la localidad de referencia (si el *working set* es
+grande se corre el riesgo de que la localidad de referencia empeore al moverse
+las celdas).
projects / z.facultad / 75.00 / informe.git / blobdiff