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

12

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.

Ian Ringrose
fuente
No exactamente la paginación, pero el ruby Enterprise Edition gc se reescribió para reducir el efecto del gc en la copia en las páginas de escritura moviendo los metadatos del objeto a páginas separadas.
user1937198
Pregunta algo relacionada sobre las implementaciones malloc / free: ¿Las implementaciones malloc devolverán la memoria libre al sistema? , particularmente esta respuesta . Además: ¿free () desasigna la memoria de un proceso?
Paul A. Clayton
Sorprendentemente, afaik / afaict, casi toda la literatura (?) gc no parece analizar la paginación del sistema operativo, excepto de manera abstracta. idea: un sistema de asignación de memoria que realiza un seguimiento de los punteros entre objetos en una estructura separada de los objetos mismos podría ser más local / amigable porque solo los punteros se atraviesan (durante gc) en un espacio muy compactado en lugar de todos los objetos de diferentes tamaños que pueden extenderse en la memoria (y algunos a los que se accede con poca frecuencia y que se paginan) puede haber algunos gastos generales modestos, pero en general puede resultar en ahorros dependiendo de la implementación.
vzn
Las unidades flash deben usar una forma de copiar la recolección de basura que tenga en cuenta la disposición de la memoria en bloques, aunque no sé qué tan bien se discuten esas cosas en la literatura académica. Los problemas a resolver allí son muy diferentes (las unidades flash necesitan GC porque el espacio solo se puede reciclar en bloques muy grandes, por lo que si un bloque tiene algunas páginas vivas y muchas páginas muertas, los datos en vivo deben copiarse en otro lugar antes de la página puede ser reciclado), pero los principios de consolidación de datos podrían ser útiles.
supercat
1
Un patrón que utilicé en los casos en que los elementos de datos eran todos pequeños en relación con el tamaño de mi fragmento de memoria consistía en que cada elemento de datos constara de un encabezado de tamaño fijo que se asignara de adelante hacia atrás y datos de tamaño variable que ser asignado de atrás hacia adelante. Una tabla mantenía asignadas direcciones lógicas de fragmentos a direcciones físicas y la cantidad de espacio libre en cada fragmento; después de cada exploración, también identificaría la cantidad de espacio muerto. Las referencias se almacenaron en flash, y cada referencia tenía la forma "Elemento # 3 del fragmento lógico # 7". Un ciclo GC copiaría todos los datos en vivo de un fragmento a uno nuevo, y ...
supercat

Respuestas:

8

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 .

babou
fuente
dudo de la idea de que los recolectores de copias sean más "locales" que el rastreo. Los recopiladores de copias parecen conceptualmente bastante similares en la dinámica de acceso a la memoria (tal vez casi indistinguible) al rastreo sobre el "viejo espacio". Creo que esto necesita una referencia. Dicho esto, existe alguna posibilidad de que el mecanismo de copia mejore la contigüidad en el nuevo espacio. el nuevo espacio comienza perfectamente contiguo, pero luego esta "localidad" disminuye o se degrada con el tiempo.
vzn
Bueno, encontraste la mayor parte de la respuesta. Así que no seas dudoso. Está en las referencias básicas sobre el tema. Localidad por el hecho de que el almacenamiento está compactado y por la copia que reemplaza celdas de datos cercanas entre sí que están lógicamente cercanas de acuerdo con la estructura del puntero (que puede evolucionar con la reasignación del puntero).
babou
Todavía estoy escéptico / dudoso. parece intuitivamente que el espacio antiguo tendrá una localidad y / o una contigüidad deficientes cuando se inicie el ciclo de copia / gc. La localidad está relacionada con las lecturas (del espacio antiguo) y las escrituras (con el espacio nuevo) Para analizarlo, debe estudiarse el comportamiento gestalt / emergente. posiblemente gran parte de esto solo pueda estudiarse de manera efectiva / precisa / realista empíricamente y no mucho en teoría.
vzn
Estoy diciendo que está en la literatura, como muchas otras cosas. Pero no tengo tiempo para buscarlo y creo que mi respuesta es larga y está repleta de información. Puede buscar en Google: recolección de basura, localidad de copia, y hay una referencia a una pregunta anterior. Perdón por ser conciso, tengo que coger un tren.
babou
Lo siento ... confundir esta pregunta con otra ... que tiene más.
babou
8

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.

Ian Ringrose
fuente