El algoritmo de Cheney

El algoritmo de Cheney , descrito por primera vez en un artículo de ACM de 1970 por C.J. Cheney, es un método de detención y copia para rastrear la recolección de basura en sistemas de software. En este esquema, el montón se divide en dos mitades iguales, de las cuales solo una está en uso en cada momento. La recolección de basura se realiza copiando los objetos activos de un semiespacio (el espacio de origen) al otro (el espacio de destino), que luego se convierte en el nuevo montón. El montón antiguo se descarta por completo. Representa una mejora con respecto a la técnica anterior de detención y copia.

El algoritmo de Cheney recupera los artículos de la siguiente manera:

• Referencias a objetos en la pila. Se comprueban las referencias a objetos en la pila. Se realiza una de las dos acciones siguientes para cada referencia a un objeto que apunta a un objeto en el espacio de origen:
  • Si el objeto aún no se ha movido al espacio de destino, esto se realiza creando una copia idéntica en dicho espacio y reemplazando la versión del espacio de origen con un puntero que apunte a la copia en el espacio de destino. A continuación, se actualiza la referencia del objeto para que apunte a la nueva versión en el espacio de destino.
  • Si el objeto ya se ha movido al espacio de destino, simplemente actualice la referencia desde el puntero de reenvío en el espacio de origen.
• Objetos en el espacio de destino. El recolector de basura examina todas las referencias a objetos en los objetos que se han migrado al espacio de destino y realiza una de las dos acciones anteriores en los objetos referenciados.

Una vez que se hayan examinado y actualizado todas las referencias al espacio, la recolección de basura habrá finalizado.

El algoritmo no necesita pila y solo dos punteros fuera del espacio de origen y del espacio de destino: un puntero al inicio del espacio libre en el espacio de destino y un puntero a la siguiente palabra en el espacio de destino que debe examinarse. Los datos entre los dos punteros representan el trabajo restante (estos objetos aparecen en gris en la terminología tricolor; véase más adelante).

El puntero de reenvío (a veces llamado "corazón roto") se utiliza únicamente durante el proceso de recolección de basura; cuando se encuentra una referencia a un objeto que ya se encuentra en el espacio de destino (y que, por lo tanto, tiene un puntero de reenvío en el espacio de origen), la referencia se puede actualizar rápidamente simplemente actualizando su puntero para que coincida con el puntero de reenvío.

Dado que la estrategia consiste en agotar todas las referencias activas y, posteriormente, todas las referencias en los objetos referenciados, esto se conoce como un esquema de recolección de basura por copia de lista en amplitud .

Cheney basó su trabajo en el recolector de basura semiespacial , que había sido publicado un año antes por RR Fenichel y JC Yochelson.

El algoritmo de Cheney es un ejemplo de recolector de basura con marcado tricolor . El primer elemento del conjunto gris es la pila misma. Los objetos referenciados en la pila se copian al espacio de destino, que contiene elementos de los conjuntos negro y gris.

El algoritmo mueve los objetos blancos (equivalentes a los objetos en el espacio de origen sin punteros de reenvío) al conjunto gris copiándolos al espacio de destino. Los objetos que se encuentran entre el puntero de escaneo y el puntero de espacio libre en el área del espacio de destino pertenecen al conjunto gris que aún debe escanearse. Los objetos que se encuentran debajo del puntero de escaneo pertenecen al conjunto negro. Los objetos se mueven al conjunto negro simplemente desplazando el puntero de escaneo sobre ellos.

Cuando el puntero de escaneo alcanza el puntero de espacio libre, el conjunto gris está vacío y el algoritmo finaliza.

• Cheney, CJ (noviembre de 1970). "Un algoritmo de compactación de listas no recursivo" . Communications of the ACM . 13 (11): 677– 678. doi : 10.1145/362790.362798 . S2CID 36538112 . 
• Fenichel, RR; Yochelson, Jerome C. (1969). "Un recolector de basura LISP para sistemas informáticos de memoria virtual" . Communications of the ACM . 12 (11): 611– 612. doi : 10.1145/363269.363280 . S2CID 36616954 . 
• Byers, Rick (2007). "Algoritmos de recolección de basura" (PDF) . Algoritmos de recolección de basura . 12 (11): 3– 4.

• Comprender el entorno de ejecución de Android (Google I/O'19) en YouTube : Android utiliza una variante del recolector de basura semi-espacial.