¿Qué algoritmos determinísticos de recolección de basura existen?

Question

Por determinista, me refiero vagamente a que se puede usar en software crítico en tiempo real como el software de vuelo aeroespacial. Recolectores de basura (y asignación de memoria dinámica para el caso) son grandes no-no en el software de vuelo porque se consideran no deterministas. Sin embargo, sé que hay investigaciones en curso sobre esto, así que me pregunto si este problema ya se ha resuelto.

También incluyo en la pregunta cualquier algoritmo de recolección de basura que impone restricciones sobre cómo se usan.

Answer 1

Sé que los sistemas azules tienen un jvm cuyo GC es asistido por hardware. También se puede ejecutar al mismo tiempo y recolectar cantidades masivas de datos bastante rápido.

No estoy seguro de qué tan determinista es.

Answer 2

Metronome GC y BEA JRockit son dos implementaciones deterministas de GC que conozco (ambas para Java).

Answer 3

Para mí, el 100% de Java en tiempo real sigue siendo una tecnología de golpe y error, pero no pretendo ser un experto.

Recomiendo leer estos artículos - Cliff Click blog. Es el arquitecto de Azul, ha codificado prácticamente todas las clases simultáneas de Java 1.5, etc ... FYI, Azul está diseñado para sistemas que requieren tamaños de montón muy grandes, en lugar de solo los requisitos de RT estándar.

Answer 4

Puede tener un poco de suerte con la siguiente tesis doctoral CMU-CS-01-174 - Scalable Real-time Parallel Garbage Collection for Symmetric Multiprocessors.

Answer 5

Sé que podría obtener muchos votos negativos para esta respuesta, pero si ya está tratando de evitar la memoria dinámica en primer lugar, porque dijo que es un no-no, ¿por qué usa GC en absoluto? ? Nunca usaría GC en un sistema en tiempo real donde la velocidad de tiempo de ejecución predecible es la principal preocupación. Evitaría la memoria dinámica siempre que sea posible, así que hay muy, muy pocos objetos dinámicos para empezar y luego manejaría las pocas asignaciones dinámicas que tengo manualmente, así que tengo control al 100% cuando se lanza algo y dónde está liberado. Después de todo, no solo GC no es determinista, free() es tan poco determinista como malloc(). Nadie dice que una llamada libre() solo tiene que marcar la memoria como libre. También podría intentar combinar bloques de memoria libres más pequeños que rodean el de libre a uno grande y este comportamiento no es determinista, ni el tiempo de ejecución para él (a veces gratis no hará eso y malloc lo hará en cambio el próximo asignación, pero en ninguna parte está escrito que libre no debe hacer eso).

En un sistema crítico en tiempo real, incluso podría reemplazar el sistema estándar malloc()/free() con una implementación diferente, tal vez incluso escribir uno propio (¡no es tan difícil como parece! Lo he hecho antes solo por el gusto de hacerlo) que funciona de manera más determinista. Para mí, GC es una cosa fácil de usar, es para que los programadores se alejen del enfocado en el planeo sofisticado de malloc()/free() y en lugar de tener que lidiar con esto automáticamente. Ayuda a hacer un desarrollo de software rápido y ahorra horas de depuración al encontrar y solucionar fugas de memoria. Pero al igual que nunca usaría GC en un kernel de sistema operativo, tampoco lo usaría en una aplicación crítica en tiempo real.

Si necesito un manejo de memoria más sofisticado, quizás escriba mi propio malloc()/free() que funcione como desee (y el más determinista) y escriba mi propio modelo de recuento de referencias sobre él. El recuento de referencias sigue siendo la gestión de la memoria manual, pero mucho más cómodo que simplemente usar malloc()/free(). No es ultra rápido, sino determinista (al menos aumentar/disminuir el contador de referencia es determinista en velocidad) y, a menos que tenga referencias circulares, capturará toda la memoria muerta si sigue una estrategia de retención/liberación en toda la aplicación.La única parte no determinista es que no sabrás si la liberación de llamadas disminuirá el contador de referencia o realmente liberará el objeto (dependiendo de si el recuento de referencias va a cero o no), pero podrías retrasar la oferta real ofreciendo una función para decir "liberar sin liberar", lo que reduce el contador de referencia en uno, pero incluso si llega a cero, no liberará() el objeto todavía. Su implementación de malloc()/free() puede tener una función "findDeadObjects" que busca todos los objetos con un contador de retención de cero, que aún no se han liberado y liberarlos (en un momento posterior, cuando se encuentre en un estado menos crítico parte de tu código que tiene más tiempo para ese tipo de tareas). Como esto tampoco es determinista, puede limitar la cantidad de tiempo que puede usar para esto como "findDeadObjectsForUpTo (ms)", y ms es la cantidad de milisegundos que puede usar para encontrar y liberarlos, volviendo tan pronto como esta vez quantum se ha utilizado, por lo que no pasará demasiado tiempo en esta tarea.

Answer 6

No es GC, pero hay esquemas simples de atribución/asignación de bloques de tamaño fijo O (1) que puede usar para un uso simple. Por ejemplo, puede usar una lista gratuita de bloques de tamaño fijo.

struct Block { 
    Block *next; 
} 

Block *free_list = NULL; /* you will need to populate this at start, an 
          * easy way is to just call free on each block you 
          * want to add */ 

void release(void *p) { 
    if(p != NULL) { 
     struct Block *b_ptr = (struct Block *)p; 
     b_ptr->next = free_list; 
     free_list = b_ptr; 
    } 
} 

void *acquire() { 
    void *ret = (void *)free_list; 
    if(free_list != NULL) { 
     free_list = free_list->next; 
    } 
    return ret; 
} 

/* call this before you use acquire/free */ 
void init() { 
    /* example of an allocator supporting 100 blocks each 32-bytes big */ 
    static const int blocks = 100; 
    static const int size = 32; 
    static unsigned char mem[blocks * size]; 
    int i; 
    for(i = 0; i < blocks; ++i) { 
     free(&mem[i * size]); 
    } 
} 

Si usted planea en consecuencia, que podría limitar su diseño a sólo unos tamaños específicos para la asignación dinámica y tener una free_list para cada tamaño potencial. Si usa C++, puede implementar algo simple como scoped_ptr (para cada tamaño, usaría un param de plantilla) para obtener una administración de memoria O (1) más simple pero aún así.

La única salvedad real, es que tendrá no protección de doble libre o incluso accidentalmente pasando un ptr para liberar que no proviene de adquirir.

Answer 7

en tiempo real significa un límite superior garantizado en el tiempo de respuesta. Esto significa un límite superior en las instrucciones que puede ejecutar hasta que entregue el resultado. Esto también pone un límite superior en la cantidad de datos que puede tocar. Si no sabe cuánta memoria va a necesitar, es muy probable que tenga un cálculo para el cual no puede dar un límite superior de tiempo de ejecución. Otoh, si conoces el límite superior de tu cálculo, también sabes cuánta memoria toca (a menos que no sepas realmente qué hace tu software). Entonces, la cantidad de conocimiento que tiene sobre su código elimina la necesidad de un GC.

Existen características, como regiones en RT-Java, que permiten la expresividad más allá de variables locales y globales (estáticas). Pero no lo eximirán de su obligación de administrar la memoria que asigna, porque de lo contrario no puede garantizar que la próxima asignación próxima no fallará debido a la insuficiencia de recursos de memoria.

Lo admito: tengo algo de sospechoso sobre cosas que se llaman "recolectores de basura en tiempo real". Por supuesto, cualquier GC es en tiempo real si usted asume que cada asignación ejecuta una colección completa (lo que aún no garantiza que tendrá éxito después, porque se puede encontrar que todos los bloques de memoria son alcanzables). Pero para cualquier GC que promete un tiempo límite inferior en la asignación, tenga en cuenta su desempeño en el siguiente código de ejemplo:

// assume that on `Link` object needs k bytes: 
class Link { 
    Link next = null; 
    /* further fields */ 
    static Link head = null; 
} 

public static void main (String args) { 
    // assume we have N bytes free now 
    // set n := floor (N/k), assume that n > 1 

    for (int i = 0; i < n; i ++) { 
     Link tmp = new Link(); 
     tmp.next = Link.head; 
     Link.head = tmp; 
    } 
    // (1) 
    Link.head = Link.head.next; // (2) 
    Link tmp = new Link(); // (3) 
} 

• En el punto (1), tenemos menos de k bytes libres (asignación de otro Link objeto fallaría), y todos los objetos Link asignados hasta ahora son alcanzables desde el campo Link.static Link head.

• en el punto (2),

  • (a) lo que solía ser la primera entrada en la lista ya no es alcanzable, pero
  • (b) es todavía asignado, por lo que la parte de gestión de memoria se refiere.

• En punto (3), la asignación debe éxito debido (2a) - podemos utilizar lo que solía ser el primer eslabón - pero, a causa de (2b), hay que partir de la GC, que terminará atravesando objetos n-1 , por lo tanto tiene un tiempo de ejecución de O (N).

Así que, sí, es un ejemplo artificial. Pero un GC que dice tener un límite en la asignación debería ser capaz de dominar este ejemplo también.

Answer 8

Sun ha documentado extensamente su recolector de basura en tiempo real, y ha proporcionado los puntos de referencia que puede ejecutar here. Otros mencionaron Metronome, que es el otro algoritmo de RTGC de grado de producción más importante. Muchos otros proveedores de RT JVM tienen sus propias implementaciones: consulte mi lista de proveedores over here y la mayoría de ellos proporciona una amplia documentación.

Si le interesan especialmente los programas de aviónica/vuelo, le sugiero que consulte aicas, un proveedor de RTSJ que comercializa específicamente la industria de la aviónica. La página de inicio de Dr. Siebert (aicas CEO) enumera algunas publicaciones académicas que detallan detalladamente la implementación de GC de PERC.

Answer 9

Sucedió que estaba buscando a través de Stack Overflow y notó esta publicación bastante antigua.

Jon Anderson mencionó JamaicaVM. Dado que estas publicaciones han estado funcionando durante más de 4 años, , creo que es importante responder a parte de la información publicada aquí.

Trabajo para aicas, los desarrolladores y comercializadores de JamaicaVM, JamaicaCAR y Veriflux.

JamaicaVM tiene un recolector de basura en tiempo real. Es completamente preventivo. El exacto mismo comportamiento requerido en un sistema operativo en tiempo real. Aunque la latencia de prioridad es depende de la velocidad de la CPU, suponga que en un procesador de clase Ghz la preferencia del recolector de basura es inferior a 1 microsegundo. Hay una versión de 32 bits para un solo núcleo que admite hasta 3 GB de memoria por espacio de direcciones de proceso. Hay una versión multinúcleo de 32 bits que admite 3 GB de memoria por espacio de direcciones de proceso y múltiples núcleos. También hay versiones de 64 bits singlecore y multinúcleo que admiten hasta 128 GB de memoria por espacio de direcciones de proceso. El rendimiento del recolector de basura es independiente del tamaño de la memoria. En respuesta a una de las respuestas con respecto a ejecutar el GC completamente sin memoria, para un sistema en tiempo real no diseñaría su programa para que lo haga. Aunque, de hecho, puede utilizar un CG duradero en tiempo real en este escenario, tendría que considerar el peor tiempo de ejecución de caso que probablemente no sería aceptable para su aplicación.

En cambio, el enfoque correcto sería analizar su programa para la asignación máxima de memoria, y luego configurar el recolector de basura en tiempo real difícil de bloques libres durante todas las asignaciones anteriores, de modo que el escenario específico describen de forma incremental nunca ocurre. Esto se conoce como recolección de basura distribuida por subprocesos y basada en el trabajo.

El libro del Dr. Siebert sobre los recolectores de basura Hard Realtime describe cómo lograr esto y presenta una prueba formal de que el recolector de basura se mantendrá al día con la aplicación, sin convertirse en una operación O (N).

Es muy importante entender que la recogida en tiempo real de basura significa varias cosas:

1. El recolector de basura es de derecho preferente, al igual que cualquier otro servicio de sistema operativo
2. Se puede demostrar matemáticamente que el recolector de basura se mantendrá al día, de modo que la memoria no se agote porque aún no se ha recuperado memoria.
3. El recolector de elementos no utilizados no fragmenta la memoria, por lo que siempre que haya memoria disponible, se realizará una solicitud de memoria.
4. Además, necesitará esto para ser parte de un sistema con protección de inversión prioritaria, un planificador de hilos de prioridad fija y otras características. Consulte el RTSJ para obtener información sobre esto.

Aunque la recolección de basura en tiempo real es necesaria para aplicaciones de seguridad crítica, también se puede utilizar en aplicaciones de misión crítica y Java de propósito general. No hay limitaciones inherentes al uso de un recolector de basura en tiempo real. Para uso general, puede esperar una ejecución más fluida del programa ya que no hay largas pausas del recolector de basura.

Answer 10

Sé que esta publicación está un poco pasada de moda, pero he realizado algunas investigaciones interesantes y quiero asegurarme de que esto se actualice.

Deterministic GC puede ser ofrecido por Azul Systems "Zing JVM" y JRocket. Zing viene con algunas características adicionales muy interesantes y ahora está "100% basado en software" (puede funcionar en máquinas x86). Es sólo para Linux en este momento, aunque ...

Precio: Si usted está en Java 6 o antes de que Oracle está cargando una elevación del 300% y forzando el apoyo a esta capacidad ($ 15.000 por procesador & $ 3.300 soporte). Azul, por lo que he oído, ronda los $ 10,000 - $ 12,000, pero se cobra por máquina física, no por procesador central. Además, el proceso se gradúa por volumen, por lo que cuantos más servidores utilice, más profundo será el descuento. Mis conversaciones con ellos mostraron que eran bastante flexibles. Oracle es una licencia perpetua y Zing se basa en suscripciones ... pero si hace los cálculos y agrega otras características que tiene Zing (vea las diferencias a continuación).

Puede reducir los costos pasando a Java 7, pero luego incurre en costos de desarrollo. Teniendo en cuenta la hoja de ruta de Oracle (una nueva versión cada 18 meses más o menos), y el hecho de que históricamente solo ofrecen las últimas versiones más antiguas de Java SE de forma gratuita, se espera que el horizonte "libre" sea de 3 años desde la GA inicial liberar si hay alguna versión principal. Dado que las versiones iniciales de GA generalmente no se adoptan en producción durante 12-18 meses, y que mover los sistemas de producción a nuevas versiones principales de Java normalmente conlleva costos importantes, esto significa que las facturas de soporte de Java SE comenzarán a aparecer entre 6 y 24 meses después de la implementación inicial. .

Diferencias notables: JRocket todavía tiene algunas limitaciones de escalabilidad en términos de RAM (aunque mejorado desde hace días). Puede mejorar sus resultados con un poco de ajuste. Zing ha diseñado su algoritmo para permitir la compactación continua y concurrente (no se detienen las pausas mundiales y no se requiere "ajuste"). Esto permite a Zing escalar sin un techo de memoria teórico (están haciendo montones de más de 300 GB sin sufrir detener el mundo o estrellarse). Hable sobre un cambio de paradigma (piense en las implicaciones para los grandes datos).Zing tiene algunas mejoras realmente interesantes para el bloqueo, lo que le proporciona un rendimiento increíble con un poco de trabajo (si está sintonizado, puede alcanzar un promedio de menos de milisegundos). Finalmente, tienen visibilidad de clases, métodos y comportamiento de subprocesos en la producción (sin gastos generales). Estamos considerando esto como un gran ahorro de tiempo al considerar las actualizaciones, los parches y las correcciones de errores (por ejemplo, filtra & bloqueos). Esto prácticamente puede eliminar la necesidad de recrear muchos de los problemas en Dev/Test.

Enlaces a JVM datos que encontraron:

JRocket Deterministic GC

Azul Presentation - Java without Jitter

Azul/MyChannels Test