El algoritmo de Cheney , descrito por primera vez en un artículo de ACM de 1970 por CJ Cheney, es un método de detener y copiar para rastrear la recolección de basura en sistemas de software de computadora. En este esquema, el montón se divide en dos mitades iguales, de las cuales solo una está en uso a la vez. La recolección de basura se realiza copiando objetos en vivo de un semispacio (el espacio desde el espacio) al otro (el espacio hacia el espacio), que luego se convierte en el nuevo montón. Luego, todo el montón viejo se desecha en una sola pieza. Es una mejora con respecto a la técnica anterior de detener y copiar. [ cita requerida ]
El algoritmo de Cheney recupera elementos de la siguiente manera:
- Referencias de objetos en la pila. Se comprueban las referencias a objetos en la pila. Se toma una de las dos siguientes acciones para cada referencia de objeto que apunta a un objeto desde el espacio:
- Si el objeto aún no se ha movido al espacio al espacio, esto se hace creando una copia idéntica en el espacio al espacio y luego reemplazando la versión desde el espacio con un puntero de reenvío a la copia al espacio. Luego actualice la referencia del objeto para hacer referencia a la nueva versión en el espacio.
- Si el objeto ya se ha movido al espacio, simplemente actualice la referencia desde el puntero de reenvío en el espacio.
- Objetos en el espacio-to. El recolector de basura examina todas las referencias a objetos en los objetos que se han migrado al espacio al y realiza una de las dos acciones anteriores en los objetos a los que se hace referencia.
Una vez que se han examinado y actualizado todas las referencias al espacio, se completa la recolección de basura.
El algoritmo no necesita una pila y solo dos punteros fuera del espacio desde el espacio y hacia el espacio: un puntero al comienzo del espacio libre en el espacio a, y un puntero a la siguiente palabra en el espacio que necesita ser examinado. . Por esta razón, a veces se le llama colector de "dos dedos"; solo necesita "dos dedos" apuntando hacia el espacio para realizar un seguimiento de su estado. Los datos entre los dos dedos representan el trabajo que le queda por hacer.
El puntero de reenvío (a veces llamado "corazón roto") se usa solo durante el proceso de recolección de basura; cuando se encuentra una referencia a un objeto que ya está en el espacio (por lo tanto, tiene un puntero de reenvío desde el espacio), la referencia se puede actualizar rápidamente simplemente actualizando su puntero para que coincida con el puntero de reenvío.
Debido a que la estrategia es agotar todas las referencias en vivo, y luego todas las referencias en los objetos referenciados, esto se conoce como un esquema de recolección de basura de copia de lista de amplitud primero .
Algoritmo de muestra
inicializar () = tospace = N / 2 fromspace = 0 allocPtr = fromspace scanPtr = lo que sea - solo se usa durante la recolección
asignar (n) = Si allocPtr + n> fromspace + tospace recoger() Terminara si Si allocPtr + n> fromspace + tospace falla "memoria insuficiente" Terminara si o = allocPtr allocPtr = allocPtr + n volver o
recolectar () = swap (desde el espacio, hacia el espacio) allocPtr = tospace scanPtr = tospace - escanea cada raíz que tienes Para cada raíz de la pila, o en otro lugar root = copiar (root) EndForEach - escanear objetos en el espacio (incluidos los objetos agregados por este bucle) Mientras scanPtrForEach referencia r de o (apuntado por scanPtr) r = copiar (r) EndForEach scanPtr = scanPtr + o.size () - apunta al siguiente objeto en el espacio to, si lo hay EndWhile
copiar (o) = Si o no tiene dirección de reenvío o '= allocPtr allocPtr = allocPtr + tamaño (o) copiar el contenido de o a o ' dirección-de-reenvío (o) = o ' Terminara si devolver dirección-reenvío (o)
Semiespacio
Cheney basó su trabajo en el recolector de basura semiespacial , que fue publicado un año antes por RR Fenichel y JC Yochelson.
Equivalencia a la abstracción tricolor
El algoritmo de Cheney es un ejemplo de un recolector de basura de marcado tricolor . El primer miembro del conjunto gris es la propia pila. Los objetos a los que se hace referencia en la pila se copian en el espacio to, que contiene miembros de los conjuntos negro y gris.
El algoritmo mueve cualquier objeto blanco (equivalente a objetos en el espacio desde el espacio sin punteros de reenvío) al conjunto gris copiándolos en el espacio hacia. Los objetos que se encuentran entre el puntero de escaneo y el puntero de espacio libre en el área de espacio son miembros del conjunto gris que aún deben escanearse. Los objetos debajo del puntero de escaneo pertenecen al conjunto negro. Los objetos se mueven al conjunto negro simplemente moviendo el puntero de escaneo sobre ellos.
Cuando el puntero de exploración alcanza el puntero de espacio libre, el conjunto gris está vacío y el algoritmo finaliza.
Referencias
- Cheney, CJ (noviembre de 1970). "Un algoritmo de compactación de lista no recursiva". Comunicaciones de la ACM . 13 (11): 677–678. doi : 10.1145 / 362790.362798 .
- Fenichel, RR; Yochelson, Jerome C. (1969). "Un recolector de basura LISP para sistemas informáticos de memoria virtual". Comunicaciones de la ACM . 12 (11): 611–612. doi : 10.1145 / 363269.363280 .
- Byers, Rick (2007). "Algoritmos de recolección de basura" (PDF) . Algoritmos de recolección de basura . 12 (11): 3–4.
- Tutorial en la Universidad de Maryland, College Park