X-Git-Url: https://git.llucax.com/z.facultad/75.00/informe.git/blobdiff_plain/091cdd95c568cccf18d45c297a7caa076b1ba4b3..6df26c6a0fb0c0783760fad32b9ea66c352402d1:/source/gc.rst?ds=sidebyside diff --git a/source/gc.rst b/source/gc.rst index 7b91082..ff79b4f 100644 --- a/source/gc.rst +++ b/source/gc.rst @@ -2,7 +2,7 @@ .. Introducción a la importancia de la recolección de basura y sus principales técnicas, con sus ventajas y desventajas. También se da un breve recorrido sobre el estado del arte. - ESTADO: TERMINADO, CORREGIDO + ESTADO: TERMINADO .. _gc: @@ -244,9 +244,9 @@ Esto es, efectivamente, una partición del *heap* (ver figura :vref:`fig:gc-heap-parts`). -.. fig:: fig:gc-heap-parts +.. flt:: fig:gc-heap-parts - Distintas partes de la memoria *heap*. + Distintas partes de la memoria *heap* Distintas partes de la memoria, incluyendo relación entre *basura*, *live set*, *heap* y *root set*. @@ -321,7 +321,7 @@ siguiente (asumiendo que partimos con todos los vértices sin marcar) function mark(v) is if not v.marked v.marked = true - for (src, dst) in v.edges + foreach (src, dst) in v.edges mark(dst) function mark_phase() is @@ -349,11 +349,11 @@ con el marcado del grafo completo, dejando sin marcar solamente las celdas *basura* (en blanco). -.. fig:: fig:gc-mark-1 +.. flt:: fig:gc-mark-1 - Ejemplo de marcado del grafo de conectividad (parte 1). + Ejemplo de marcado del grafo de conectividad (parte 1) - .. subfig:: + .. subflt:: Se comienza a marcar el grafo por la raíz r0. @@ -386,7 +386,7 @@ con el marcado del grafo completo, dejando sin marcar solamente las celdas } - .. subfig:: + .. subflt:: Luego de marcar el nodo ``h1``, se procede al ``h2``. @@ -420,7 +420,7 @@ con el marcado del grafo completo, dejando sin marcar solamente las celdas } - .. subfig:: + .. subflt:: Luego sigue el nodo h5. @@ -456,11 +456,11 @@ con el marcado del grafo completo, dejando sin marcar solamente las celdas } -.. fig:: fig:gc-mark-2 +.. flt:: fig:gc-mark-2 - Ejemplo de marcado del grafo de conectividad (parte 2). + Ejemplo de marcado del grafo de conectividad (parte 2) - .. subfig:: + .. subflt:: El nodo h5 tiene una arista al h1, pero el h1 ya fue visitado, por lo tanto no se visita nuevamente. @@ -496,7 +496,7 @@ con el marcado del grafo completo, dejando sin marcar solamente las celdas } - .. subfig:: + .. subflt:: Se concluye el marcado del sub-grafo al que conecta r0, se procede a marcar el sub-grafo al que conecta r1, marcando al nodo h6. @@ -533,7 +533,7 @@ con el marcado del grafo completo, dejando sin marcar solamente las celdas } - .. subfig:: + .. subflt:: El nodo h6 tiene una arista al h2, pero éste ya fue marcado por lo que no se vuelve a visitar. No hay más raíces, se finaliza el marcado @@ -608,7 +608,7 @@ vacíos):: while not gray_set.empty() v = gray_set.pop() black_set.add(v) - for (src, dst) in v.edges + foreach (src, dst) in v.edges if dst in white_set white_set.remove(dst) gray_set.add(dst) @@ -821,7 +821,7 @@ en cuanto a la detección y recolección de ciclos fue utilizado en muchos lenguajes de programación sin que su necesidad sea tan evidente. Por ejemplo Python_ agregó recolección de ciclos en la versión 2.0 [NAS00]_ (liberada en octubre de 2000) y PHP_ recién agrega detección de ciclos en la versión 5.3 -(todavía no liberada al momento de escribir este documento) [PHP081]_. +[PHP530]_. .. _gc_rc_example: @@ -844,13 +844,13 @@ conduce al decremento del contador de ``h2`` y ``h3`` que permanecen en el *live set* ya que sus contadores siguen siendo mayores a 0 (ver figura :vref:`fig:gc-rc-rm-2`). -.. fig:: fig:gc-rc-rm-1 +.. flt:: fig:gc-rc-rm-1 - Ejemplo de conteo de referencias: eliminación de una referencia (parte 1). + Ejemplo de conteo de referencias: eliminación de una referencia (parte 1) Eliminación de la referencia ``r0`` :math:`\to` ``h1`` (parte 1). - .. subfig:: + .. subflt:: Estado inicial del grafo de conectividad. @@ -897,7 +897,7 @@ conduce al decremento del contador de ``h2`` y ``h3`` que permanecen en el } - .. subfig:: + .. subflt:: Al ejecutarse ``update(r0, null)``, se comienza por visitar la celda ``h1``. @@ -945,7 +945,7 @@ conduce al decremento del contador de ``h2`` y ``h3`` que permanecen en el } - .. subfig:: + .. subflt:: Se decrementa el contador de ``h1`` quedando en 0 (pasa a ser *basura*). Se elimina primero ``h1.l`` y luego ``h1.r``. @@ -999,14 +999,14 @@ conduce al decremento del contador de ``h2`` y ``h3`` que permanecen en el } -.. fig:: fig:gc-rc-rm-2 +.. flt:: fig:gc-rc-rm-2 :padding: 0.5 - Ejemplo de conteo de referencias: eliminación de una referencia (parte 2). + Ejemplo de conteo de referencias: eliminación de una referencia (parte 2) Eliminación de la referencia ``r0`` :math:`\to` ``h1`` (parte 2). - .. subfig:: + .. subflt:: Se decrementa el contador de ``h2`` pero no queda en 0 (permanece en el *live set*). @@ -1059,7 +1059,7 @@ conduce al decremento del contador de ``h2`` y ``h3`` que permanecen en el } - .. subfig:: + .. subflt:: El contador de ``h3`` tampoco queda en 0, sigue en el *live set*. @@ -1119,14 +1119,14 @@ se elimina alguna celda que apuntaba a ésta. Luego se procede a decrementar el contador de ``h2`` que queda en 0, transformándose en *basura* (ver figura :vref:`fig:gc-rc-up-1`). -.. fig:: fig:gc-rc-up-1 +.. flt:: fig:gc-rc-up-1 - Ejemplo de conteo de referencias: actualización de una referencia (parte 1). + Ejemplo de conteo de referencias: actualización de una referencia (parte 1) Cambio en la referencia ``h3.l`` :math:`\to` ``h2`` a ``h3.l`` :math:`\to` ``h5`` (parte 1). - .. subfig:: + .. subflt:: Comienza ``update(h3.l, h5)``, se incrementa el contador de ``h5``. @@ -1179,7 +1179,7 @@ contador de ``h2`` que queda en 0, transformándose en *basura* (ver figura } - .. subfig:: + .. subflt:: Luego se procede a visitar la antigua referencia de ``h3.l`` (``h2``). @@ -1232,7 +1232,7 @@ contador de ``h2`` que queda en 0, transformándose en *basura* (ver figura } - .. subfig:: + .. subflt:: Se decrementa el contador de ``h2`` y queda en 0 (pasa a ser *basura*). Se eliminan las referencias a las hijas. @@ -1293,14 +1293,14 @@ a apuntar a ``h5``) así que permanece en el *live set*. Finalmente se termina de actualizar la referencia ``h3.l`` para que apunte a ``h5`` (ver figura :vref:`fig:gc-rc-up-2`). -.. fig:: fig:gc-rc-up-2 +.. flt:: fig:gc-rc-up-2 - Ejemplo de conteo de referencias: actualización de una referencia (parte 2). + Ejemplo de conteo de referencias: actualización de una referencia (parte 2) Cambio en la referencia ``h3.l`` :math:`\to` ``h2`` a ``h3.l`` :math:`\to` ``h5`` (parte 2). - .. subfig:: + .. subflt:: Se decrementa el contador de ``h4`` quedando en 0, pasa a ser *basura*. Se continúa con ``h5``. @@ -1354,7 +1354,7 @@ de actualizar la referencia ``h3.l`` para que apunte a ``h5`` (ver figura } - .. subfig:: + .. subflt:: Se decrementa el contador de ``h5`` pero sigue siendo mayor que 0. @@ -1407,7 +1407,7 @@ de actualizar la referencia ``h3.l`` para que apunte a ``h5`` (ver figura } - .. subfig:: + .. subflt:: Se termina por actualizar la referencia de ``h3.l`` para que apunte a ``h5``. @@ -1473,15 +1473,15 @@ referencias externas y por lo tanto deberían ser *basura* también (``h5``), no pueden ser recicladas y su memoria es perdida (ver figura :vref:`fig:gc-rc-cycle`). -.. fig:: fig:gc-rc-cycle +.. flt:: fig:gc-rc-cycle :padding: 0.5 - Ejemplo de conteo de referencias: pérdida de memoria debido a un ciclo. + Ejemplo de conteo de referencias: pérdida de memoria debido a un ciclo Eliminación de la referencia ``r1`` :math:`\to` ``h3`` (pérdida de memoria debido a un ciclo). - .. subfig:: + .. subflt:: El ejecutarse ``update(r1, null)`` se visita la celda ``h3``. @@ -1535,7 +1535,7 @@ pueden ser recicladas y su memoria es perdida (ver figura } - .. subfig:: + .. subflt:: Se decrementa el contador de ``h3`` pero sigue siendo mayor que 0 por el ciclo. @@ -1684,9 +1684,9 @@ sus *low level allocators*). sucede y se acumulan muchos *huecos* se dice que la memoria está *fragmentada*. -.. fig:: fig:gc-copy +.. flt:: fig:gc-copy - Estructura del *heap* de un recolector con copia de semi-espacios. + Estructura del *heap* de un recolector con copia de semi-espacios .. aafig:: :aspect: 70 @@ -1818,11 +1818,11 @@ apunta a ``h3``, por lo tanto ésta es movida al *Tospace* primero, dejando una *forwarding address* a la nueva ubicación (ver figura :vref:`fig:gc-copy-ex-1`). -.. fig:: fig:gc-copy-ex-1 +.. flt:: fig:gc-copy-ex-1 - Ejemplo de recolección con copia de semi-espacios (parte 1). + Ejemplo de recolección con copia de semi-espacios (parte 1) - .. subfig:: + .. subflt:: Estructura inicial del *heap*. El *Fromspace* está complete y se inicial la recolección. @@ -1853,7 +1853,7 @@ apunta a ``h3``, por lo tanto ésta es movida al *Tospace* primero, dejando una | "Tospace" | +--------------------------------------------------+ - .. subfig:: + .. subflt:: Se sigue la referencia del *root set*, copiando ``h3`` al *Tospace* y dejando una *forwarding address*. @@ -1895,11 +1895,11 @@ sido visitada, solamente se actualiza la referencia apuntando a la nueva ubicación de ``h2`` pero no se vuelve a copiar la celda (ver figura :vref:`fig:gc-copy-ex-2`). -.. fig:: fig:gc-copy-ex-2 +.. flt:: fig:gc-copy-ex-2 - Ejemplo de recolección con copia de semi-espacios (parte 2). + Ejemplo de recolección con copia de semi-espacios (parte 2) - .. subfig:: + .. subflt:: Se sigue :math:`h3 \to h2`, copiando ``h2`` al *Tospace* y dejando una *forwarding address*. @@ -1930,7 +1930,7 @@ ubicación de ``h2`` pero no se vuelve a copiar la celda (ver figura | "Tospace" | +--------------------------------------------------+ - .. subfig:: + .. subflt:: Se sigue :math:`h2 \to h1`, copiando ``h1``. Luego :math:`h1 \to h2` pero ``h2`` no se copia, sólo se actualiza la referencia con la @@ -1969,11 +1969,11 @@ semi-espacios y se actualiza la referencia del *root set* para que apunte a la nueva ubicación de ``h3``, como se muestra en la figura :vref:`fig:gc-copy-ex-3`. -.. fig:: fig:gc-copy-ex-3 +.. flt:: fig:gc-copy-ex-3 - Ejemplo de recolección con copia de semi-espacios (parte 3). + Ejemplo de recolección con copia de semi-espacios (parte 3) - .. subfig:: + .. subflt:: Se sigue :math:`h1 \to h4` copiando `h4`` al *Tospace* y dejando una *forwarding address*. @@ -2004,7 +2004,7 @@ nueva ubicación de ``h3``, como se muestra en la figura | "Tospace" \------/ | +--------------------------------------------------+ - .. subfig:: + .. subflt:: Se finaliza la recolección, se intercambian los roles de los semi-espacios y se actualiza la referencia del *root set*. @@ -2165,12 +2165,12 @@ clase de colectores que si bien son *stop-the-world*, utilizan todos los hilos disponibles para realizar la recolección (ver figura :vref:`fig:gc-concurrent`). -.. fig:: fig:gc-concurrent +.. flt:: fig:gc-concurrent Distintos tipos de recolectores según el comportamiento en ambientes - multi-hilo. + multi-hilo - .. subfig:: + .. subflt:: *Stop-the-world*. @@ -2189,7 +2189,7 @@ disponibles para realizar la recolección (ver figura | HH Mutator ZZ Inactivo XX Recolector | |___________________________________________________________________| - .. subfig:: + .. subflt:: Paralelo. @@ -2208,7 +2208,7 @@ disponibles para realizar la recolección (ver figura | HH Mutator ZZ Inactivo XX Recolector | |___________________________________________________________________| - .. subfig:: + .. subflt:: Concurrente. @@ -2406,11 +2406,11 @@ haya. Entonces, si el recolector tiene algún mecanismo para identificar zonas de alta concentración de *basura* puede hacer la recolección solo en ese área -donde el trabajo va a ser mejor recompensado (ver :vref:`fig:gc-part`). +donde el trabajo va a ser mejor recompensado (ver figura :vref:`fig:gc-part`). -.. fig:: fig:gc-part +.. flt:: fig:gc-part - Concentración de basura en distintas particiones del *heap*. + Concentración de basura en distintas particiones del *heap* .. aafig:: :scale: 110