+Recolección
+ *mark(pbot, ptop)*
+ Marca un rango de memoria. Este método es análogo al ``mark_range()``
+ presentado en la sección :ref:`dgc_algo_mark`.
+
+ *fullcollectshell()*
+ Guarda los registros del procesador asignado al hilo actual en su
+ *stack* y llama a ``fullcollect()``. El resto de los hilos son pausados
+ y sus registros apilados por la función del *runtime*
+ ``thread_suspendAll()`` (y restablecidos y reiniciados por
+ ``thread_resumeAll()``.
+
+ *fullcollect(stackTop)*
+ Realiza la recolección de basura. Es análoga a ``collect()`` pero es
+ considerablemente menos modular, todos los pasos se hacen directamente
+ en esta función: marcado del *root set*, marcado iterativo del *heap*,
+ barrido y reconstrucción de la lista de libres. Además devuelve la
+ cantidad de páginas que se liberaron en la recolección, lo que permite
+ optimizar levemente la función ``bigAlloc()``.
+
+
+Finalización
+^^^^^^^^^^^^
+El recolector actual, por omisión, solamente efectúa una recolección al
+finalizar. Por lo tanto, no se ejecutan los destructores de todos aquellos
+objetos que son alcanzables desde el *root set* en ese momento. Existe la
+opción de no realizar una recolección al finalizar el recolector, pero no de
+finalizar *todos* los objetos (alcanzables o no desde el *root set*). Si bien
+la especificación de D_ permite este comportamiento (de hecho la
+especificación de D_ es tan vaga que permite un recolector que no llame jamás
+a ningún destructor), para el usuario puede ser una garantía muy débil
+y proveer finalización asegurada puede ser muy deseable.
+
+
+.. _dgc_committed:
+
+Memoria *encomendada*
+^^^^^^^^^^^^^^^^^^^^^
+El algoritmo actual divide un *pool* en dos áreas: memoria *encomendada*
+(*committed* en inglés) y *no-encomendada*. Esto se debe a que originalmente
+el compilador de D_ DMD_ solo funcionaba en Microsoft Windows y este sistema
+operativo puede asignar memoria en dos niveles. En principio se puede asignar
+al proceso un espacio de memoria (*address space*) pero sin asignarle la
+memoria virtual correspondiente. En un paso posterior se puede *encomendar* la
+memoria (es decir, asignar realmente la memoria virtual).
+
+Para aprovechar esta característica el recolector diferencia estos dos
+niveles. Sin embargo, esta diferenciación introduce una gran complejidad (que
+se omitió en las secciones anteriores para facilitar la comprensión),
+y convierte lo que es una ventaja en un sistema operativo en una desventaja
+para todos los demás (ya que los cálculos extra se realizan pero sin ningún
+sentido). De hecho hay sistemas operativos, como Linux_, que realizan este
+trabajo automáticamente (la memoria no es asignada realmente al programa hasta
+que el programa no haga uso de ella; a esta capacidad se la denomina
+*overcommit*).
+
+Como se vio en la figura :vref:`fig:dgc-pool`, las páginas de un *pool* se
+dividen en *committed* y *uncommitted*. Siempre que el recolector recorre un
+*pool* en busca de una página o bloque, lo hace hasta la memoria *committed*,
+porque la *uncommitted* es como si jamás se hubiera pedido al sistema
+operativo a efectos prácticos. Además, al buscar páginas libres, si no se
+encuentran entre las *encomendadas* se intenta primero *encomendar* páginas
+nuevas antes de crear un nuevo *pool*.
+
+
+Sincronización
+^^^^^^^^^^^^^^
+Si bien el recolector no es paralelo ni concurrente (ver :ref:`gc_art`),
+soporta múltiples *mutator*\ s. La forma de implementarlo es la más simple.
+Todas las operaciones sobre el recolector que se llaman externamente están
+sincronizadas utilizando un *lock* global (excepto cuando hay un solo hilo
+*mutator*, en cuyo caso se omite la sincronización). Esto afecta también a la
+asignación de memoria y cualquier otro servicio provisto por el recolector.
+
+
+
+.. _dgc_good:
+
+Características destacadas
+~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
+
+Si bien el recolector en términos generales no se aleja mucho de un
+:ref:`marcado y barrido clásico <gc_mark_sweep>`, tiene algunas mejoras por
+sobre el algoritmo más básicos que vale la pena destacar:
+
+
+Organización del *heap*
+^^^^^^^^^^^^^^^^^^^^^^^
+El *heap* está organizado de una forma que, si bien no emplea las técnicas más
+modernas que pueden observarse en el estado del arte (como :ref:`regiones
+<gc_free_list>`), es relativamente sofisticada. El esquema de *pools*
+y bloques permite disminuir considerablemente los problemas de *fragmentación*
+de memoria y evita búsquedas de *huecos* que pueden ser costosas (como
+*best-fit* [#dgcbestfit]_) o desperdiciar mucho espacio (como *first-fit*
+[#dgcfirstfit]_), logrando un buen equilibrio entre velocidad y espacio
+desperdiciado.
+
+.. [#dgcbestfit] Las búsquedas de tipo *best-fit* son aquellas donde se busca
+ el *hueco* en el *heap* (es decir, una región contínua de memoria
+ libre) que mejor se ajuste al tamaño del objeto a asignar. Es decir, el
+ *hueco* más pequeño lo suficientemente grande como para almacenarlo.
+
+.. [#dgcfirstfit] Las búsquedas de tipo *first-fit* son aquellas donde se busca
+ el primer *hueco* en el *heap* (es decir, una región contínua de memoria
+ libre) que sea lo suficientemente grande como para almacenar el objeto
+ a asignar.
+
+
+Fase de marcado iterativa
+^^^^^^^^^^^^^^^^^^^^^^^^^
+A diferencia del algoritmo clásico recursivo, el algoritmo del recolector
+actual es iterativo. El algoritmo recursivo tiene un problema fundamental: se
+puede llegar a un desbordamiento de pila (o *stack overflow*). La cantidad de
+recursiones necesarias es, en el peor caso, :math:`O(|Live \thickspace set|)`
+(por ejemplo, si todas las celdas del *heap* formaran una lista simplemente
+enlazada). Hay muchas técnicas para lidiar con este problema, algunas que
+podrían aplicarse a D_ y otras que no (como *pointer reversal*) [JOLI96]_. El
+recolector actual, sin embargo, cambia complejidad en espacio por complejidad
+en tiempo, utilizando un algoritmo iterativo que es constante (:math:`O(1)`)
+en espacio, pero que requiere varias pasada sobre el *heap* en vez de una (la
+cantidad de pasadas en el peor caso es :math:`O(|Live \thickspace set|)`, al
+igual que la profundidad del algoritmo recursivo, pero cada pasada se realiza
+sobre todo el *heap*).
+
+
+Conjuntos de bits para indicadores
+^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
+El algoritmo clásico propone almacenar en la propia celda la marca (para la
+fase de marcado) y otros indicadores. El algoritmo del recolector actual
+utiliza conjuntos de bits. Esto trae dos ventajas principales:
+
+* Permite minimizar el espacio requerido, ya que de otra forma en general se
+ desperdicia una palabra entera como cabecera de celda para guardar este tipo
+ de información.
+
+* Mejora la localidad de referencia, ya que los indicadores se escriben de
+ forma muy compacta y en una región de memoria contigua que generalmente
+ puede entrar en el cache o en pocas páginas de memoria acelerando
+ considerablemente la fase de marcado.
+
+
+.. _dgc_debug:
+
+Herramientas para depuración
+^^^^^^^^^^^^^^^^^^^^^^^^^^^^
+
+El recolector provee algunas opciones para simplificar el diagnóstico
+y depuración de problemas, tanto del mismo recolector como del programa del
+usuario.
+
+Las opciones más importantes son:
+
+
+``MEMSTOMP``
+ Su función es escribir un patrón determinado de bits en todos los bytes de
+ un bloque de memoria según se haya:
+
+ * Pedido un bloque menor a una página (``0xF0``).
+ * Pedido un bloque mayor a una página (``0xF1``).
+ * Dejado de usar debido a un pedido de achicamiento de un bloque
+ (``0xF2``).
+ * Pedido más páginas debido a un pedido de agrandamiento de un bloque
+ (``0xF0``).
+ * Liberado intencionalmente por el usuario (``0xF2``).
+ * Barrido (``0xF3``).
+
+ Esto permite al diagnosticar un problema saber, por ejemplo, si un
+ determinado área de memoria fue recolectada recientemente, o liberada por
+ el usuario, o recién adquirida, etc. con tan solo ver si un patrón de bits
+ determinado está presente. Por supuesto puede existir *falsos positivos*
+ pero su probabilidad es lo suficientemente baja como para que sea útil en
+ la práctica.
+
+``SENTINEL``
+ Su función detectar errores producidos por escribir más allá (o antes) del
+ área de memoria solicitada. Está implementado reservando un poco más de
+ memoria de la que pide el usuario y devolviendo un puntero a un bloque
+ ubicado dentro del bloque real reservado (en vez de al inicio). Escribiendo
+ un patrón de bits en los extremos del bloque real (ver figura
+ :vref:`fig:sentinel`) se puede verificar, en distintas situaciones (como
+ por ejemplo al barrer el bloque), que esas guardas con los patrones de bits
+ estén intactas (en caso contrario se ha escrito por fuera de los límites
+ del bloque solicitado). Esto permite detectar de forma temprana errores
+ tanto en el recolector como en el programa del usuario.
+
+ .. flt:: fig:sentinel
+
+ Esquema de un bloque cuando está activada la opción ``SENTINEL``
+
+ .. aafig::
+ :textual:
+
+ | | | | |
+ +-- Palabra ---+-- Palabra ---+-- Tamaño bloque de usuario --+- Byte -+
+ | | | | |
+
+ +--------------+--------------+------------------------------+--------+
+ | "Tamaño del" | Pre | | Post |
+ | "bloque de" | | Bloque de usuario | |
+ | "usuario" | 0xF4F4F4F4 | | 0xF5 |
+ +--------------+--------------+------------------------------+--------+
+ A
+ |
+ Puntero devuleto ---/
+
+Ambas opciones son seleccionables sólo en tiempo de compilación del
+recolector, por lo que su utilidad real, al menos para el usuario, se ve
+severamente reducida.
+
+
+.. _dgc_bad:
projects / z.facultad / 75.00 / informe.git / blobdiff