+Todos los :ref:`algoritmos clásicos <gc_classic>` que se han citado son del
+tipo *stop-the-world*.
+
+
+
+.. _gc_free_list:
+
+Lista de libres / *pointer bump allocation*
+~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
+
+Esta clasificación se refiere principalmente a la forma en que se organiza el
+*heap*, íntimamente relacionado al *low level allocator*. Si bien se ha dicho
+que en este trabajo no se prestará particular atención a este aspecto, en
+ciertos algoritmos es tan relevante que tampoco es sensato pasarlo por alto
+completamente.
+
+En términos generales, hay dos formas fundamentales de organizar el *heap*,
+manteniendo una lista de libres o realizando *pointer bump allocation*, como
+se explicó en :ref:`gc_copy`. La primera forma consiste, a grandes rasgos, en
+separar el *heap* en celdas (que pueden agruparse según tamaño) y enlazarlas
+en una lista de libres. Al solicitarse una nueva celda simplemente se la
+desenlaza de la lista de libres. Por otro lado, cuando el recolector detecta
+una celda *muerta*, la vuelve a enlazar en la lista de libres. Este es un
+esquema simple pero con limitaciones, entre las principales, el costo de
+asignar puede ser alto si hay muchos tamaños distintos de celda y soportar
+tamaño de celda variable puede ser complejo o acarrear muchas otras
+ineficiencias. :ref:`gc_mark_sweep` en general usa este esquema, al igual que
+:ref:`gc_rc`.
+
+Otro forma de organizar el *heap* es utilizándolo como una especie de *stack*
+en el cual para asignar simplemente se incrementa un puntero. Este esquema es
+simple y eficiente, si el recolector puede mover celdas (ver
+:ref:`gc_moving`); de otra manera asignar puede ser muy costoso si hay que
+buscar un *hueco* en el heap (es decir, deja de reducirse a incrementar un
+puntero). El clásico ejemplo de esta familia es :ref:`gc_copy`.
+
+Sin embargo, entre estos dos extremos, hay todo tipo de híbridos. Existen
+recolectores basados en *regiones*, que se encuentran en un punto intermedio.
+Dentro de una región se utiliza un esquema de *pointer bump allocation* pero
+las regiones en sí se administran como una lista de libres (como por ejemplo
+[BLAC08]_). Otra variación (más común) de este esquema son los *two level
+allocators* que asignan páginas completas (similar a las regiones) y dentro de
+cada página se asignan las celdas. Ambas, páginas y celdas, se administran
+como listas de libres (ejemplos que utilizan este esquema son [BOEHWD]_ y el
+:ref:`recolector actual de D <dgc_actual>`).
+
+
+
+.. _gc_moving:
+
+Movimiento de celdas
+~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
+
+Otra característica muy importante del recolector de basura es si mueve las
+celdas o no. En general el movimiento de celdas viene de la mano del esquema
+de :ref:`pointer bump allocation <gc_free_list>`, ya que *compacta* todas las
+celdas *vivas* al comienzo del *heap* luego de una recolección, permitiendo
+este esquema para asignar nuevas celdas, pero puede utilizarse en esquemas
+híbridos como recolectores basados en *regiones* (por ejemplo [BLAC08]_).
+
+Además los recolectores con movimiento de celdas deben ser :ref:`precisos
+<gc_conserv>`, porque es necesario tener la información completa de los tipos
+para saber cuando actualizar los punteros (de otra manera se podría escribir
+un dato de una celda que no era un puntero). Para que un recolector pueda
+mover celdas, aunque sea parcialmente, en recolectores *semi-precisos* se
+utiliza un método conocido como *pinning* (que significa algo como *pinchar
+con un alfiler*); una celda es *pinned* (*pinchada*) cuando hay alguna
+referencia no-precisa a ella, y por lo tanto no puede ser movida (porque no se
+puede estar seguro si es posible actualizar dicha referencia).
+
+La ventaja principal de los colectores con movimiento es la posibilidad de
+utilizar :ref:`pointer bump allocation <gc_free_list>` y que es sencillo
+implementar recolectores :ref:`generacionales <gc_part>` sobre estos.
+
+De los algoritmos clásicos sólo la :ref:`copia de semi-espacios <gc_copy>`
+mueve celdas, el :ref:`conteo de referencias <gc_rc>` y :ref:`marcado
+y barrido <gc_mark_sweep>` no lo hacen. Además hay otro algoritmo bastante
+básico que mueve celdas, el **marcado y compactado**. Éste no tiene
+2 semi-espacios, directamente mueve las celdas compactándolas al comienzo del
+*heap*. El algoritmo es un poco más complejo que la :ref:`copia de
+semi-espacios <gc_copy>` pero suele poder proveer una mayor localidad de
+referencia y *desperdicia* un semi-espacio que está inutilizado salgo en el
+momento de la recolección. Por ejemplo para Mono_, que antes usaba un
+recolector conservativo sin movimiento ([BOEHWD]_) se está implementando un
+recolector de este tipo [MOLAWE]_ [MOLA06]_.
+
+
+
+.. _gc_conserv:
+
+Recolectores conservativos vs precisos
+~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
+
+Los recolectores *conservativos* son aquellos que tienen la capacidad de poder
+lidiar con un *root set* o celdas que no tengan información de tipos asociada.
+Esto significa que el recolector no sabe donde hay punteros (o referencias) en
+una celda o raiz dada. Es decir, una ubicación particular puede ser un puntero
+o no. Esto trae una variada cantidad de problemas, como retención de celdas
+que en realidad son *basura* simplemente porque hay algún dato que coincide
+con la dirección de memoria en la que está almacenada esa celda *basura*
+[#gcflasepos]_. Además los recolectores puramente conservativos no puede mover
+celdas (ver :ref:`gc_moving`), porque no pueden arriesgarse a actualizar los
+punteros por el riesgo que existe de que sean falsos positivos.
+
+.. [#gcflasepos] Esto es lo que se conoce como un *falso positivo*, algo que
+ aparenta ser un puntero pero en realidad no lo es.
+
+Sin embargo hay ciertas circunstancias que hacen que no quede más remedio que
+el recolector sea conservativo, por ejemplo cuando se utiliza un recolector de
+basura para un lenguaje que no ha sido pensado para tener uno (como C o C++).
+
+Por el contrario, los recolectores que poseen a su disposición información
+completa sobre el tipo de la celda, y por ende información sobre cuales de sus
+campos son realmente punteros, son denominados *precisos*. Estos recolectores
+no están sujetos a estas limitaciones y por lo tanto son potencialmente más
+eficientes en cuanto a tiempo y espacio. Los lenguajes que fueron diseñados
+para tener un recolector de basura (y en especial aquellos que son de relativo
+alto nivel) en general disponen de recolectores precisos.
+
+Hay casos donde se posee información de tipos para algunas celdas solamente,
+o más comunmente se posee información de tipos de celdas que se encuentran en
+el *heap* pero no para el *stack* y registros (por ejemplo [MOLA06]_). En
+estos casos se puede adoptar un esquema híbrido y tratar algunas referencias
+de forma conservativa y otras de forma precisa, de manera de mitigar, aunque
+sea de forma parcial, los efectos adversos de los recolectores conservativos.
+Estos recolectores son conocidos como *semi-precisos*. Los recolectores
+semi-precisos pueden mover celdas si utilizan un mecanismo de *pinning* (ver
+:ref:`gc_moving`).
+
+El ejemplo de recolector conservativo por excelencia es el recolector
+`Boehm-Demers-Wiser`_ ([BOEH88]_, [BOEH91]_, [BOEH93]_, [BOEHWD]_) aunque
+puede comportarse de forma semi-precisa si el usuario se encarga de darle la
+información de tipos (en cuyo caso el recolector deja de ser transparente para
+el usuario). Otros ejemplos de recolectores con cierto grado de
+conservativismo son el :ref:`recolector actual de D <dgc_actual>` y [BLAC08]_.
+
+
+
+.. _gc_part:
+
+Recolección particionada / generacional
+~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
projects / z.facultad / 75.00 / informe.git / blobdiff