+Durante el desarrollo de este trabajo se introdujo al lenguaje de programación
+D_ y a los conceptos básicos de recolección de basura. Luego se analizó el
+recolector de basura actual y se señalaron sus principales falencias,
+proponiendo un conjunto de modificaciones con el objeto de subsanarlas.
+Para evaluar los resultados de las modificaciones se construyó un banco de
+pruebas variado para poder analizar tanto aspectos particulares como el
+funcionamiento de programas reales; y se establecieron métricas para
+cuantificar dichos resultados.
+
+El objetivo principal fue bajar la latencia del recolector, es decir el tiempo
+máximo de pausa real, y se pudo comprobar que, salvo en casos muy
+particulares, esto fue conseguido de manera contundente (con tiempos de pausa
+hasta 200 veces menores que el recolector original de D_). La inclusión del
+marcado concurrente demostró ser una forma eficaz de atacar el problema.
+
+La aceptación de la solución por parte de la comunidad también ha sido un
+objetivo importante de este trabajo, y si bien en este sentido sigue siendo un
+trabajo en progreso, la recepción ha sido ampliamente positiva por parte de la
+comunidad y se espera que el resultado de este trabajo sea incorporado en el
+corto plazo tanto a `D 1.0`_ a través de Tango_, como a `D 2.0`_.
+
+Además de los objetivos principales se cumplieron otros objetivos anexos, pero
+no por eso menos importantes. Para la aplicación real el tiempo total de
+ejecución se ha reducido hasta casi una tercera parte, y para otras
+aplicaciones pequeñas se ha reducido más de 17 veces. Estos resultados han
+sido particularmente sorprendentes, siendo que la reducción del tiempo total
+de ejecución no ha sido parte del objetivo principal y no se habían encontrado
+referencias en la bibliografía de casos similares (por el contrario, en
+general la baja de la latencia suele estar acompañada de una suba en el tiempo
+total de ejecución).
+
+Se ha podido experimentar además con el marcado preciso, otro de los problemas
+del recolector más presentes en la comunidad. Los resultados obtenidos son
+variados, encontrando casos donde se consigue una mejoría notoria y otros en
+donde la forma de almacenar la información de tipos produce resultados poco
+satisfactorios.
+
+La mayor flexibilidad del recolector al ser configurable también ha demostrado
+ser útil. Por un lado para este mismo trabajo, al permitir realizar mediciones
+sobre el mismo binario utilizando diferentes configuraciones. Por otro, la
+amplia gama de resultados dispares obtenidos son una buena muestra de que no
+existen *balas de plata*, y cada programa tiene necesidades particulares en
+cuanto a recolección de basura. Por lo tanto, distintos programas pueden verse
+beneficiados o perjudicados por diferentes configuraciones. Esto hace que la
+posibilidad de configurar el recolector en tiempo de inicialización sea
+particularmente útil.
+
+Finalmente, algunas optimizaciones muy pequeñas demostraron ser también muy
+valiosas para ciertos casos particulares, logrando reducciones en el tiempo
+total de ejecución de hasta 5 veces.
+
+
+
+.. _con_pending:
+
+Puntos pendientes, problemas y limitaciones
+----------------------------------------------------------------------------
+
+Si bien los objetivos de este trabajo han sido alcanzados con éxito, hay
+varias pequeñas mejoras que han quedado pendientes y algunos problemas
+y limitaciones conocidas. A continuación se describe cada una de ellos.
+
+* Emisión de mensajes informativos para depuración.
+
+ Entre las herramientas de depuración que provee el recolector, no se ha
+ mencionado la posibilidad de emitir opcionalmente mensajes informativos para
+ ayudar a depurar tanto problemas en el recolector como en el programa que lo
+ usa. El recolector actual tiene esa posibilidad pero es configurable en
+ tiempo de compilación. En este trabajo se agregaron las opciones en tiempo
+ de inicialización ``log_file`` y ``verbose`` con el propósito de poder
+ elegir un archivo en donde guardar los mensajes informativos y el nivel de
+ detalle de dichos mensajes respectivamente, pero finalmente nunca se
+ implementaron.
+
+* Predicción para estimar cuando lanzar una recolección temprana.
+
+ Las recolecciones se lanzan de manera temprana según la opción ``min_free``.
+ Una mejor aproximación podría ser predecir cuando se va a agotar la memoria
+ libre de forma adaptativa, calculando la tasa de asignación de memoria
+ y el tiempo total que tomó la recolección. Esta estimación se podría mejorar
+ guardando un historial de que tan acertada fue para recolecciones pasadas. La
+ predicción ideal debería ser capaz de:
+
+ * Evitar tiempos de pausa (es decir, que la recolección temprana termine antes
+ de que se agote la memoria libre).
+ * No realizar recolecciones innecesarias (es decir, no lanzar recolecciones
+ tempranas si el programa no está pidiendo memoria a una tasa suficientemente
+ alta).
+
+* Explosión del uso de memoria con creación ansiosa de *pools*.
+
+ Se ha observado que en situaciones muy particulares, al usar creación
+ ansiosa de *pools* (o *eager allocation*), el uso de memoria crece
+ desmesuradamente. Si bien este efecto se ve principalmente en las pruebas
+ sintetizadas con tal fin, algunos programas reales lo sufren también, pero
+ en general se puede atenuar utilizando también *early collection*.
+ Recordemos además, que lo analizado es el consumo **máximo** de memoria, por
+ lo que una ráfaga de pedidos de memoria podría crear un pico, pero durante
+ la mayor parte del transcurso del programa el consumo de memoria podría ser
+ mucho menor. Queda pendiente analizar los casos puntuales con alguna métrica
+ más detallada sobre el progreso del uso de memoria.
+
+ También queda pendiente buscar alguna estimación de cuándo es conveniente
+ utilizar *eager allocation* de forma adaptativa, dado que en general se ve
+ que cuando explota el consumo de memoria, también explota el tiempo de
+ pausa, lo que quita gran parte del sentido de usar *eager allocation* en
+ primer lugar. Estimando de alguna manera cuanto va a crecer el tiempo de
+ pausa debido a esta opción, se podría desactivar temporalmente cuando no
+ haya ganancia en el tiempo de pausa para evitar esta explosión ante ráfagas
+ de pedidos de memoria.
+
+* Reestructuración y limpieza del código.
+
+ Si bien se han hecho muchas mejoras a nivel de estructura y limpieza de
+ código, ha quedado mucho pendiente. Todavía hay bastante repetición en el
+ código y se mantiene la arquitectura básica del recolector.
+
+* Experimentación con la llamada al sistema :manpage:`clone(2)`.
+
+ Linux_ implementa la llamada al sistema :manpage:`fork(2)` a través de otra de
+ más bajo nivel llamada :manpage:`clone(2)`. :manpage:`clone(2)` permite una
+ granularidad a la hora de indicar que partes del proceso deben ser copiadas al
+ hijo y cuales deben ser compartidas mucho mayor que :manpage:`fork(2)`. Por
+ ejemplo, se puede compartir toda la memoria del proceso, siendo este el
+ mecanismo por el cual Linux_ implementa los hilos. Para este trabajo podría
+ ser beneficioso usar :manpage:`clone(2)` para evitar copiar otro tipo de
+ estructuras dado que el proceso
+ hijo, al correr solo la fase de marcado, nunca va a interferir el *mutator*.
+ Se podría experimentar no copiando las siguientes estructuras, por ejemplo:
+
+ ``CLONE_FILES``
+ Tabla de descriptores de archivo.
+
+ ``CLONE_FS``
+ Tabla de sistemas de archivo montados.
+
+ ``CLONE_IO``
+ Contextos de entrada/salida.
+
+ ``CLONE_SIGHAND``
+ Tabla de manejadores de señales.
+
+* Uso de memoria compartida.
+
+ Al realizar marcado concurrente, si el *mutator* usa memoria compartida entre
+ procesos que almacene punteros al *heap* podría haber problemas, dado que la
+ fase de barrido no estaría trabajando con una *fotografía* de la memoria. El
+ grafo de conectividad podría efectivamente cambiar mientras se corre la fase
+ de barrido y por lo tanto el algoritmo deja de ser correcto, existiendo la
+ posibilidad de que se reciclen celdas *vivas*.
+
+ Dado que el usuario debe registrar cualquier puntero que no sea parte de la
+ memoria estática, *stack* o *heap* del recolector como parte del *root set*,
+ se podría agregar un parámetro extra a la función de registro que indique si
+ los punteros agregados residen en memoria compartida. De este modo, al momento
+ de hacer el :manpage:`fork(2)`, el recolector debería realizar una copia de
+ esos punteros mientras todos los hilos están pausados para obtener
+ efectivamente una *fotografía* estable del *root set*.
+
+* Condición de carrera al utilizar :manpage:`fork(2)`.
+
+ Existe una condición de carrera si se lanzan hilos usando directamente las
+ llamadas al sistema operativo, es decir si no se lanzan a través del soporte
+ de hilos de D_, si el hilo lanzado utiliza archivos con *buffer* de
+ C (``FILE*``). Esto se debe a la siguiente porción de código (introducida por
+ el marcado concurrente)::
+
+ function collect() is
+ stop_the_world()
+ fflush(null) // <-------------------------
+ child_pid = fork()
+ if child_pid is 0
+ mark_phase()
+ exit(0)
+ // proceso padre
+ start_the_world()
+ wait(child_pid)
+ sweep()
+
+ La llamada a :manpage:`fflush(3)` es necesaria para evitar que los archivos
+ con *buffer* escriban su contenido dos veces al dispositivo, ya que la llamada
+ a :manpage:`fork(2)` duplica el *buffer*, y si bien el archivo no se usa en el
+ proceso con la fase de marcado, la biblioteca estándar de C escribe todos los
+ *buffers* pendientes al terminar el proceso. Esto funciona para los hilos
+ registrados por D_ gracias a que :manpage:`fflush(3)` se llama cuando todos
+ los hilos están pausados, si no un hilo podría escribir al *buffer* justo
+ después de llamar a :manpage:`fflush(3)` pero antes de llamar
+ a :manpage:`fflush(2)`. Es por esto que si hay hilos no registrados por D_ que
+ utilicen manejo de archivos con *buffer* de C, esta condición sí se puede dar
+ y se pueden observar contenidos duplicados en dichos archivos.
+
+ Esta condición de carrera no tiene una solución simple, pero es de esperarse
+ que no sea un problema real dado que no es un escenario común. Sin embargo
+ eventualmente debería analizarse alguna solución más robusta.
projects / z.facultad / 75.00 / informe.git / blobdiff