X-Git-Url: https://git.llucax.com/z.facultad/75.00/informe.git/blobdiff_plain/f422261911478248a1e54e69bae05ad51cea60a0..9d97e3ff2b7234037d4e78de0cb126a5ede881ed:/source/gc.rst?ds=sidebyside diff --git a/source/gc.rst b/source/gc.rst index 43626eb..0b91155 100644 --- a/source/gc.rst +++ b/source/gc.rst @@ -863,6 +863,11 @@ o cambiar una referencia (cambios en la conectividad del grafo). En un comienzo todas las celdas son accesibles desde el *root set* por lo tanto son todas parte del *live set*. +Se comienza por eliminar la referencia de ``r0`` a ``h1``, que determina +que ``h1`` se convirtió en *basura* (ver figura :vref:`fig:gc-rc-rm-1`). Esto +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 @@ -1128,12 +1133,13 @@ son todas parte del *live set*. } -Se comienza por eliminar la referencia de ``r0`` a ``h1``, que determina -que ``h1`` se convirtió en *basura* (ver figura :vref:`fig:gc-rc-rm-1`). Esto -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`). +Luego se cambia una referencia (en vez de eliminarse) realizándose la +operación ``update(h3.l, h5)``. Para esto primero se incrementa el contador +de referencias de ``h5`` para evitar confundirlo accidentalmente con +*basura* si 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 @@ -1301,6 +1307,12 @@ conduce al decremento del contador de ``h2`` y ``h3`` que permanecen en el } +Lo mismo pasa cuando se desciende a ``h4``, pero al descender a ``h5`` +y decrementar el contador, éste sigue siendo mayor que 0 (pues ``h3`` va +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 Cambio en la referencia ``h2.l`` :math:`\to` ``h2`` a ``h2.l`` @@ -1469,18 +1481,15 @@ conduce al decremento del contador de ``h2`` y ``h3`` que permanecen en el } -Luego se cambia una referencia (en vez de eliminarse) realizándose la -operación ``update(h3.l, h5)``. Para esto primero se incrementa el contador -de referencias de ``h5`` para evitar confundirlo accidentalmente con -*basura* si 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`). Lo mismo pasa cuando se -desciende a ``h4``, pero al descender a ``h5`` y decrementar el contador, -éste sigue siendo mayor que 0 (pues ``h3`` va 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`). - +Finalmente se presenta lo que sucede cuando se elimina la última referencia +a un ciclo (en este caso un ciclo simple de 2 celdas: ``h3`` y ``h6``). Se +elimina la única referencia externa al ciclo (``r1``), por lo que se visita +la celda ``h3`` decrementando su contador de referencias, pero éste +continúa siendo mayor que 0 porque la celda ``h6`` (parte del ciclo) la +referencia. Por lo tanto el ciclo, y todas las celdas a las que apunta que +no tienen otras 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 :padding: 0.5 @@ -1598,16 +1607,6 @@ referencia ``h3.l`` para que apunte a ``h5`` (ver figura } -Finalmente se presenta lo que sucede cuando se elimina la última referencia -a un ciclo (en este caso un ciclo simple de 2 celdas: ``h3`` y ``h6``). Se -elimina la única referencia externa al ciclo (``r1``), por lo que se visita -la celda ``h3`` decrementando su contador de referencias, pero éste -continúa siendo mayor que 0 porque la celda ``h6`` (parte del ciclo) la -referencia. Por lo tanto el ciclo, y todas las celdas a las que apunta que -no tienen otras 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`). - .. _ref_gc_mark_sweep: @@ -1682,11 +1681,387 @@ linealmente. +.. _ref_gc_copy: -Copia/Semi-espacio +Copia de semi-espacio ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ -TODO +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 alocar 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 alocar memoria (tan eficiente como alocar memoria en el *stack*). + +.. fig:: fig:gc-copy + + Estructura del *heap* de un recolector con copia de semi-espacios. + + .. aafig:: + :aspect: 0.7 + :scale: 1.4 + :proportional: + + 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 alocando 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 +redirecció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:`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 alocar +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: ``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 alocar:: + + 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 + 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:`ref_gc_art`). + +Al igual que el :ref:`ref_gc_mark_sweep` este algoritmo es :ref:`indirecto +`, :ref:`no incremental ` y :ref:`stop-the-world +`. 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 require 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). + + +Ejemplo +^^^^^^^ + +A continuación se presenta un sencillo ejemplo del algoritmo. Se parte de una +estructura simple con 4 celdas en el *Fromspace* (que incluye un pequeño ciclo +para mostrar que este algoritmo tampoco tiene inconvenientes para +recolectarlos). Asumimos que ya no queda lugar en el *Fromspace* por lo que +comienza la ejecución de ``collect()``. Se comienza por el *root set* que +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 + + Ejemplo de recolección con copia de semi-espacios (parte 1). + + .. subfig:: + + Estructura inicial del *heap*. El *Fromspace* está complete y se inicial + la recolección. + + .. aafig:: + :aspect: 0.5 + :scale: 1.25 + :proportional: + + +--------------------------------------------------+ + | "Fromspace" | + | /--------------------------------\ | + | | /--------\ /------\ | | + | | | | | | | | + | ______|_V________|__V______|___________V______ | + | ZZZZGGGGGGGGZZZZGGGGGGGGggggggggZZZZGGGGGGGGZZZZ | + | ZZZZGGGGGGGGZZZZGGGGGGGGggggggggZZZZGGGGGGGGZZZZ | + | ~~~~~~~~~|~~~~~~~~~~A~~~~~~~A~~~~~~~~~~~~~~~~~ | + | h1 | h2 | h3 | h4 | + | \----------/ | | + | \----+"root set" | + | | + | | + | | + | ______________________________________________ | + | BBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB | + | BBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB | + | A~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ | + | | | + | \----+"free" | + | "Tospace" | + +--------------------------------------------------+ + + .. subfig:: + + Se sigue la referencia del *root set*, copiando ``h3`` al *Tospace* + y dejando una *forwarding address*. + + .. aafig:: + :aspect: 0.5 + :scale: 1.25 + :proportional: + + +--------------------------------------------------+ + | "Fromspace" | + | /--------------------------------\ | + | | /--------\ /------\ | | + | | | | | | | | + | ______|_V________|__V______|___________V______ | + | ZZZZGGGGGGGGZZZZGGGGGGGGffffffffZZZZGGGGGGGGZZZZ | + | ZZZZGGGGGGGGZZZZGGGGGGGGffffffffZZZZGGGGGGGGZZZZ | + | ~~~~~~~~~|~~~~~~~~~~A~~~~~~~|A~~~~~~~~~~~~~~~~ | + | h1 | h2 | h3 || h4 | + | \----------/ || | + | +\----+"root set" | + | / | + | /-------------------------+ | + | | h3 | + | V_____________________________________________ | + | HHHHHHHHBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB | + | HHHHHHHHBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB | + | ~~~~~~~A~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ | + | | | + | \----+"free" | + | "Tospace" | + +--------------------------------------------------+ + + +A continuación se copian las *hijas* de ``h3``, en este caso sólo ``h2``, que +se ubica en el *Tospace* a continuación de ``h3``, dejando nuevamente su +``forwarding address`` en la celda original. Al proceder recursivamente, se +procede a copiar ``h1`` al *Tospace*, dejando una vez más la *forwarding +address* en la celda original y procediendo con las hijas. Aquí podemos +observar que al seguirse la referencia :math:`h1 \to h2`, como ``h2`` ya había +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 + + Ejemplo de recolección con copia de semi-espacios (parte 2). + + .. subfig:: + + Se sigue :math:`h3 \to h2`, copiando ``h2`` al *Tospace* y dejando una + *forwarding address*. + + .. aafig:: + :aspect: 0.5 + :scale: 1.25 + :proportional: + + +--------------------------------------------------+ + | "Fromspace" | + | /--------------------------------\ | + | | /--------\ /------\ | | + | | | | | | | | + | ______|_V________|__V______|___________V______ | + | ZZZZGGGGGGGGZZZZFFFFFFFFffffffffZZZZGGGGGGGGZZZZ | + | ZZZZGGGGGGGGZZZZFFFFFFFFffffffffZZZZGGGGGGGGZZZZ | + | ~~~~~~~~~|~~~~~~~~~~A|~~~~~~|A~~~~~~~~~~~~~~~~ | + | h1 | h2 || h3 || h4 | + | \----------/+ || | + | / +\----+"root set" | + | +-----------+ / | + | /------+------------------+ | + | | h3 | h2 | + | V______V______________________________________ | + | HHHHHHHHhhhhhhhhBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB | + | HHHHHHHHhhhhhhhhBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB | + | ~~|~~~~~~A~~~~~A~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ | + | | | | | + | \------/ \----+"free" | + | "Tospace" | + +--------------------------------------------------+ + + .. subfig:: + + 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 + *forwarding address*. + + .. aafig:: + :aspect: 0.5 + :scale: 1.25 + :proportional: + + +--------------------------------------------------+ + | "Fromspace" | + | /--------------------------------\ | + | | /--------\ /------\ | | + | | | | | | | | + | ______|_V________|__V______|___________V______ | + | ZZZZFFFFFFFFZZZZFFFFFFFFffffffffZZZZGGGGGGGGZZZZ | + | ZZZZFFFFFFFFZZZZFFFFFFFFffffffffZZZZGGGGGGGGZZZZ | + | ~~~~~~~|~|~~~~~~~~~~A|~~~~~~|A~~~~~~~~~~~~~~~~ | + | h1 | | h2 || h3 || h4 | + | \-+----------/+ || | + | +-----+ / +\-----+"root set" | + | +-------+---+ / | + | /------+-------+----------+ | + | | h3 | h2 | h1 | + | V______V_______V______________________________ | + | HHHHHHHHhhhhhhhhHHHHHHHHBBBBBBBBBBBBBBBBBBBBBBBB | + | HHHHHHHHhhhhhhhhHHHHHHHHBBBBBBBBBBBBBBBBBBBBBBBB | + | ~~|~~~~~~A~|~A~~|~A~~~~A~~~~~~~~~~~~~~~~~~~~~~ | + | | | | | | | | | + | \------/ | \--/ | \----+"free" | + | "Tospace" \------/ | + +--------------------------------------------------+ + + +Se termina de copiar recursivamente las hijas de ``h1`` al copiar ``h4`` que +resulta la última celda (sin hijas). Finalmente se invierten los roles de los +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 + + Ejemplo de recolección con copia de semi-espacios (parte 3). + + .. subfig:: + + Se sigue :math:`h1 \to h4` copiando `h4`` al *Tospace* y dejando una + *forwarding address*. + + .. aafig:: + :aspect: 0.5 + :scale: 1.25 + :proportional: + + +--------------------------------------------------+ + | "Fromspace" | + | /--------------------------------\ | + | | /--------\ /------\ | | + | | | | | | | | + | ______|_V________|__V______|___________V______ | + | ZZZZFFFFFFFFZZZZFFFFFFFFffffffffZZZZFFFFFFFFZZZZ | + | ZZZZFFFFFFFFZZZZFFFFFFFFffffffffZZZZFFFFFFFFZZZZ | + | ~~~~~~~|~|~~~~~~~~~~A|~~~~~~|A~~~~~~~~~~|~~~~~ | + | h1 | | h2 || h3 || h4 \----\ | + | \-+----------/+ || | | + | +-----+ / +----/\---+"root set" | | + | +-------+---+ / | | + | /------+-------+-----+ /--------------------/ | + | | h3 | h2 | h1 | h4 | + | V______V_______V________V_____________________ | + | HHHHHHHHhhhhhhhhHHHHHHHHhhhhhhhhBBBBBBBBBBBBBBBB | + | HHHHHHHHhhhhhhhhHHHHHHHHhhhhhhhhBBBBBBBBBBBBBBBB | + | ~~|~~~~~~A~|~A~~|~A~|~~~~~~A~~~A~~~~~~~~~~~~~~ | + | | | | | | | | | | | + | \------/ | \--/ | \------/ \----+"free" | + | "Tospace" \------/ | + +--------------------------------------------------+ + + .. subfig:: + + Se finaliza la recolección, se intercambian los roles de los + semi-espacios y se actualiza la referencia del *root set*. + + .. aafig:: + :aspect: 0.5 + :scale: 1.25 + :proportional: + + +--------------------------------------------------+ + | "Tospace" | + | | + | | + | | + | ______________________________________________ | + | AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA | + | AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA | + | ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ | + | | + | | + | | + | /---+"root set" | + | | | + | | h3 h2 h1 h4 | + | V______________________________________________ | + | HHHHHHHHhhhhhhhhHHHHHHHHhhhhhhhhBBBBBBBBBBBBBBBB | + | HHHHHHHHhhhhhhhhHHHHHHHHhhhhhhhhBBBBBBBBBBBBBBBB | + | ~~|~~~~~~A~|~A~~|~A~|~~~~~~A~~~A~~~~~~~~~~~~~~ | + | | | | | | | | | | | + | \------/ | \--/ | \------/ \---+"free" | + | "Fromspace" \------/ | + +--------------------------------------------------+