¿Hay recolectores de basura que tengan en cuenta la paginación?

Las recolecciones de basura deben visitar todos los objetos que están vivos, para encontrar la memoria que se pueda recuperar. (Tener muchas generaciones solo retrasa esto un poco)

En igualdad de condiciones, es claramente mejor visitar primero el objeto que ya está paginado en la RAM, antes de paginar otro bloque y, por lo tanto, paginar algún objeto.

Otra posibilidad es que cuando el sistema operativo desea quitar una página de RAM del proceso, primero se le pregunta al GC si tiene una página que se puede abandonar sin necesidad de paginar. El GC se puede hacer principalmente con objetos en movimiento desde una página, por lo que puede borrar esa página dentro del límite de tiempo que tiene el sistema operativo para necesitar una página.

Sin embargo, no puedo recordar ningún recolector de basura que se integre con el sistema de paginación del sistema operativo que controla el orden en que funciona el GC.

Como recuerdo, se supone que los recopiladores de copias deben ser compatibles con la paginación, ya que el rastreo mediante la copia tiende a mejorar la localidad de las referencias de puntero. Esto tiene un efecto positivo en el programa (mutador) que causará menos fallas de página al seguir los enlaces, y también mejorará el próximo ciclo de recolección ya que el rastreo también causará menos fallas de página. La agenda de rastreo (qué punteros deben procesarse primero) puede tener un impacto en la efectividad para mejorar la localidad de los datos. Esto puede mejorarse midiendo estadísticas sobre el número de acceso a diferentes punteros en diferentes tipos de celdas.

Ahora, si considera un recopilador de rastreo en general, generalmente debe mantener una estructura que haga un seguimiento de los punteros que aún no se han rastreado. Es posible organizar esta estructura para que todos los punteros en espera que apunten en la misma página se mantengan juntos (aunque eso puede tomar más espacio, en algunos casos, dependiendo de las técnicas disponibles para mantener la lista de dichos punteros). Entonces, una posible política es rastrear siempre el conjunto más grande de punteros de espera que apuntan a la misma página, cuando no queda ningún puntero de espera en las páginas de la memoria.

Con respecto a la pregunta en el tercer párrafo, que se agregó después de que respondí, la recopilación de copias es nuevamente una respuesta. El sistema operativo puede reducir el número de páginas físicas asignadas en el momento de la recopilación, ya que las páginas están completamente libres. Con un colector de marcas y barridos, el evento de que una página completa esté libre es probablemente mucho más raro, por lo que no vale la pena tener en cuenta un mecanismo específico.

Este tipo de ideas es natural, y probablemente se describe en algunos de los documentos. Pero no lo recuerdo de la mano. Creo que los primeros documentos sobre Lisp GC contienen algunas de estas ideas (como: ¿deberían seguirse primero el automóvil o el cdr?).

La buena noticia en este papel de la recopilación de copias también es que la paginación es fácil de copiar, ya que aumenta el espacio de almacenamiento disponible. Recuerde que el recopilador de copias requiere en principio el doble de espacio que el utilizado para el almacenamiento de datos real. Ahora, el efecto de la paginación depende también del espacio de direcciones de la máquina y de la memoria física disponible. En una computadora más antigua, la memoria física era mucho menor que el espacio de direcciones disponible, por lo que la paginación era realmente una bonificación de espacio, permitiendo políticas como copiar GC. Incluso cuando el espacio físico es tan grande como el espacio de direcciones, es posible que desee compartirlo, de modo que el proceso que usa un GC tenga menos espacio de direcciones sin paginación (consulte paginación) Estas observaciones son algo superadas por el uso de coleccionistas generacionales. Generalmente usan la colección de copias para la generación joven precisamente por estas cualidades, y porque la generación joven es principalmente de corta duración.

Entonces tiene todas las interacciones de GC generacional con el sistema de caché, que se discutió en una pregunta anterior: ¿Son los recolectores de basura generacionales inherentemente amigables con el caché?

Para obtener más información sobre este tema, buscaría en la web con, por ejemplo, las palabras clave recolección de basura y localidad .

Emery Berger, Matthew Hertz y Yi Feng trabajaron un poco en esto.

La recolección de basura ofrece numerosas ventajas de ingeniería de software, pero interactúa mal con los administradores de memoria virtual. Los recolectores de basura existentes requieren muchas más páginas que el conjunto de trabajo de la aplicación y las páginas táctiles sin tener en cuenta cuáles están en la memoria, especialmente durante la recolección de basura de montón completo. La paginación resultante puede hacer que el rendimiento caiga en picado y que los tiempos de pausa aumenten hasta segundos o incluso minutos.

Les presento un recolector de basura que evita la paginación. Este colector de marcadores coopera con el administrador de memoria virtual para guiar sus decisiones de desalojo.

Este es un video de la charla de Emery al respecto, y él escribió una recolección de basura en papel sin paginación

Por alguna razón, no parece haber mucho trabajo posterior en él, ni ningún uso del "mundo real". Al final del documento dice "Estamos desarrollando una variante concurrente del algoritmo de colección de marcadores" , pero no puedo rastrearlo.

CRAMM: el soporte de memoria virtual para aplicaciones recolectadas de basura analiza el cambio del sistema operativo para hacer que GC cree menos paginación.

Uso de la residencia de la página para equilibrar las compensaciones en el seguimiento de la recolección de basura

Introducimos una extensión de copia mayormente de colección que usa la residencia de la página para determinar cuándo reubicar objetos. Nuestro colector promueve páginas con alta residencia en el lugar, evitando el trabajo innecesario y el desperdicio de espacio. Predice la residencia de cada página, pero cuando sus predicciones demuestran ser inexactas, nuestro recolector reclama el espacio desocupado al usarlo para satisfacer las solicitudes de asignación. El uso de la residencia permite a nuestro recolector equilibrar dinámicamente las compensaciones de la colección de copia y no copia. Nuestra técnica requiere menos espacio que un recopilador de copia puro y admite la fijación de objetos sin sacrificar la capacidad de reubicar objetos. A diferencia de otros híbridos, nuestro recopilador no depende de la configuración específica de la aplicación y puede responder rápidamente a los cambios en el comportamiento de la aplicación. Nuestras mediciones muestran que nuestro híbrido funciona bien bajo una variedad de condiciones; prefiere copiar la colección cuando hay un amplio espacio de almacenamiento dinámico, pero recurre a la colección sin copia cuando el espacio se vuelve limitado.