algorithm - que - ¿Qué algoritmos deterministas de recolección de basura existen?

operacion no determinista

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 imponga restricciones sobre cómo se usan.

Answer 1

Para mí, Java 100% 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 . Él es el arquitecto de Azul, ha codificado prácticamente todas las clases simultáneas 1.5 de Java simultáneas, etc. ... FYI, Azul está diseñado para sistemas que requieren tamaños de pila muy grandes, en lugar de solo los requisitos RT estándar.

Answer 2

Puede tener algo de suerte con la siguiente tesis doctoral CMU-CS-01-174 - Colección de basura paralela escalable en tiempo real para multiprocesadores simétricos .

Answer 3

Sé que Azul Systems tiene 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.

Sin embargo, no estoy seguro de lo determinista que es.

Answer 4

Metronome GC y BEA JRockit son dos implementaciones de GC deterministas de las que soy consciente (tanto para Java).

Answer 5

Sé que podría obtener muchos votos negativos para esta respuesta, pero si ya está tratando de evitar la memoria dinámica, 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 puede reemplazar el sistema estándar malloc () / free () con una implementación diferente, tal vez incluso escribiendo uno propio (¡no es tan difícil como parece! Lo he hecho antes solo por diversión de ella) que funciona 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, podría escribir mi propio malloc () / free () que funcione como desee (y el más determinista) y escribir mi propio modelo de recuento de referencias encima. 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 asignaciones / 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 planifica en consecuencia, podría limitar su diseño a solo unos pocos tamaños específicos para la asignación dinámica y tener una lista_fría para cada tamaño potencial. Si está utilizando 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 advertencia real, es que no tendrás protección contra dobles liberaciones 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.

Hay características, como las regiones en RT-Java, que permiten la expresividad más allá de las 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.

Es cierto: 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 prometa un límite inferior de tiempo en la asignación, considere su rendimiento 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 (la asignación de otro objeto de Link fallaría), y todos los objetos de Link asignados hasta ahora son accesibles comenzando desde el campo de Link.static Link head .

• En el punto (2),

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

• En el punto (3), la asignación debería tener éxito debido a (2a) - podemos usar lo que solía ser el primer enlace - pero, debido a (2b), debemos iniciar el GC, que terminará atravesando objetos n-1 , por lo tanto, tienen un tiempo de ejecución de O (N).

Entonces, 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

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

Jon Anderson mencionó JamaicaVM. Como estos mensajes 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 mismo comportamiento exacto requerido en un sistema operativo en tiempo real. Aunque la latencia de preferencia 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 difícil no diseñaría su programa para hacerlo. 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 su lugar, el enfoque correcto sería analizar su programa para la máxima asignación de memoria, y luego configurar el recolector de basura en tiempo real para liberar bloques incrementalmente durante todas las asignaciones previas para que el escenario específico descrito nunca ocurra. Esto se conoce como recolección de basura distribuida por subprocesos y basada en el trabajo.

El libro del Dr. Siebert sobre recolectores de basura duraderos en tiempo real 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 recolección de basura en tiempo real significa varias cosas:

1. El recolector de basura es preemptible, al igual que cualquier otro servicio del sistema operativo
2. Se puede demostrar, matemáticamente, que el recolector de basura se mantendrá al día, de manera que la memoria no se agote porque aún no se ha reclamado 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á que esto sea 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 críticas de seguridad, también se puede usar aplicaciones Java de misión crítica y 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 9

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

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). Aunque solo es para Linux en este momento ...

Precio: si tiene Java 6 o antes, Oracle ahora está cargando un 300% de subida y forzando el soporte para esta capacidad ($ 15,000 por procesador y $ 3,300 de 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 el costo moviéndose a Java 7, pero luego incurrir 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 en algún momento entre 6 y 24 meses después del despliegue inicial. .

Diferencias notables: JRocket todavía tiene algunas limitaciones de escalabilidad en términos de RAM (aunque mejorada 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 actualizaciones, parches y correcciones de errores (por ejemplo, fugas y bloqueos). Esto prácticamente puede eliminar la necesidad de recrear muchos de los problemas en Dev / Test.

Enlaces a JVM Data que encontré:

JRocket Deterministic GC

Presentación Azul - Java sin fluctuación

Prueba Azul / MyChannels

Answer 10

Sun ha documentado exhaustivamente su recolector de basura en tiempo real y proporcionó puntos de referencia que puede ejecutar aquí . 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 aquí y la mayoría de ellos proporciona una amplia documentación.

Si su interés es particularmente en el software de aviónica / vuelo, le sugiero que eche un vistazo a aicas , un proveedor de RTSJ que comercializa específicamente a la industria de la aviónica. La página de inicio del Dr. Siebert (CEO de Aicas) enumera algunas publicaciones académicas que detallan detalladamente la implementación de GC de PERC.