+.. _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_gc_direct>`, :ref:`no incremental <ref_gc_inc>` y :ref:`stop-the-world
+<ref_gc_concurrent>`. 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" \------/ |
+ +--------------------------------------------------+
projects / z.facultad / 75.00 / informe.git / blobdiff