Pregunta ¿El uso de memoria de pila (malloc / nuevo) crea un programa no determinista?


Comencé a desarrollar software para sistemas en tiempo real hace unos meses en C para aplicaciones espaciales, y también para microcontroladores con C ++. Hay una regla empírica en tales sistemas que uno nunca debe crear objetos de montón (Así que no malloc / nuevo), porque hace que el programa no determinista. No pude verificar la exactitud de esta afirmación cuando la gente me dice eso. Asi que, ¿Es esta una declaración correcta?

La confusión para mí es que, hasta donde yo sé, el determinismo significa que ejecutar un programa dos veces conducirá a la misma ruta de ejecución exacta. Según tengo entendido, este es un problema con los sistemas multiproceso, ya que ejecutar el mismo programa varias veces podría tener diferentes subprocesos ejecutándose en diferente orden cada vez.


73
2017-09-19 10:36


origen


Respuestas:


En el contexto de los sistemas en tiempo real, hay más en el determinismo que un "camino de ejecución" repetible. Otra propiedad requerida es que el tiempo de los eventos clave está limitado. En los sistemas duros en tiempo real, un evento que ocurre fuera de su intervalo de tiempo permitido (ya sea antes del inicio de ese intervalo o después del final) representa una falla del sistema.

En este contexto, el uso de la asignación de memoria dinámica puede causar no determinismo, particularmente si el programa tiene un patrón variable de asignación, desasignación y reasignación. El momento de las asignaciones, la desasignación y la reasignación pueden variar con el tiempo y, por lo tanto, hacer que los tiempos del sistema en conjunto sean impredecibles.


71
2017-09-19 11:03



El comentario, como se dijo, es incorrecto.

Usando un administrador de montón con no determinista comportamiento crea un programa con comportamiento no determinista. Pero eso es obvio.

Un poco menos obvio es la existencia de administradores de montón con comportamiento determinista. Quizás el ejemplo más conocido es el asignador de grupo. Tiene una matriz de N * M bytes, y una available[] máscara de N bits. Para asignar, verifica la primera entrada disponible (prueba de bit, O (N), límite superior determinista). Para desasignar, establece el bit disponible (O (1)). malloc(X) redondeará X al siguiente valor más grande de M para elegir el grupo correcto.

Esto puede no ser muy eficiente, especialmente si sus opciones de N y M son demasiado altas. Y si elige demasiado bajo, su programa puede fallar. Pero los límites para N y M pueden ser menores que para un programa equivalente sin asignación de memoria dinámica.


39
2017-09-19 12:28



Nada en el C11 estándar o en n1570 dice que malloc es determinista (o no lo es); y ninguna otra documentación como Malloc (3) en Linux. Por cierto, muchos malloc implementaciones son software libre.

Pero malloc puede (y lo hace) fallar, y se desconoce su rendimiento (una llamada típica a malloc en mi escritorio haría prácticamente tomar menos de un microsegundo, pero podría imaginar situaciones extrañas donde podría tomar mucho más, tal vez muchos milisegundos en una computadora muy cargada; leer acerca de paliza) Y mi escritorio de Linux tiene ASLR (aleatorización de diseño de espacio de direcciones) por lo que ejecutar el mismo programa dos veces da diferente malloc-ed direcciones (en el espacio de direcciones virtuales del proceso). Por cierto aquí es un determinista (bajo suposiciones específicas que debes elaborar) pero prácticamente inútil malloc implementación.

determinismo significa que ejecutar un programa dos veces conducirá a la misma ruta de ejecución exacta

Esto es prácticamente incorrecto en la mayoría de los sistemas integrados, porque el entorno físico está cambiando; por ejemplo, el software que maneja un motor de cohete no puede esperar que el empuje, la resistencia, la velocidad del viento, etc. exactamente lo mismo desde un lanzamiento hasta el siguiente.

(Así que estoy sorprendido de que crea o desee que los sistemas en tiempo real sean deterministas, ¡nunca lo son! WCET, que es cada vez más difícil de predecir debido a cachés)

Por cierto, algunos sistemas "en tiempo real" o "incrustados" están implementando su propio malloc (o alguna variante de esto). Los programas C ++ pueden tener su asignador-s, utilizable por estándar envases. Ver también esta y ese, etcétera etcétera.....

Y capas de alto nivel de software integrado (piense en un automóvil autónomo y su planificación software) están usando la asignación de montón y quizás incluso recolección de basura técnicas (algunas de las cuales son "en tiempo real"), pero generalmente no se consideran críticas para la seguridad.


21
2017-09-19 10:59



tl; dr: No es que la asignación de memoria dinámica es intrínsecamente no determinista (como lo definió en términos de rutas de ejecución idénticas); es que generalmente hace que tu programa impredecible. Específicamente, no puede predecir si el asignador puede fallar ante una secuencia arbitraria de entradas.

Podría tener un asignador no determinista. Esto es realmente común fuera de su mundo en tiempo real, donde los sistemas operativos usan cosas como aleatorización de diseño de direcciones. Por supuesto, eso haría que tu programa no sea determinista.

Pero ese no es un caso interesante, así que supongamos un asignador perfectamente determinista: la misma secuencia de asignaciones y desasignaciones siempre dará como resultado los mismos bloques en las mismas ubicaciones y esas asignaciones y desasignaciones siempre tendrán un tiempo de ejecución limitado.

Ahora su programa puede ser determinista: el mismo conjunto de entradas conducirá exactamente a la misma ruta de ejecución.

El problema es que si asigna y libera memoria en respuesta a entradas, no puede predecir si alguna asignación fallará alguna vez (y la falla no es una opción).

Primero, su programa podría perder memoria. Entonces, si necesita ejecutarse indefinidamente, eventualmente una asignación fallará.

Pero incluso si puede demostrar que no hay fugas, deberá saber que nunca hay una secuencia de entrada que pueda demandar más memoria de la disponible.

Pero incluso si puede probar que el programa nunca necesitará más memoria que la disponible, el asignador podría, dependiendo de la secuencia de asignaciones y liberaciones, fragmentar la memoria y, por lo tanto, no podrá encontrar un bloque contiguo para satisfacer una asignación, aunque hay suficiente memoria libre en general.

Es muy difícil probar que no hay una secuencia de entradas que conduzca a la fragmentación patológica.

Puede diseñar asignadores para garantizar que no habrá fragmentación (por ejemplo, asignando bloques de un solo tamaño), pero eso impone una restricción sustancial a la persona que llama y posiblemente aumenta la cantidad de memoria requerida debido al desperdicio. Y la persona que llama aún debe demostrar que no hay fugas y que hay un límite superior satiable en la memoria total requerida, independientemente de la secuencia de entradas. Esta carga es tan alta que en realidad es más simple diseñar el sistema para que no utilice la asignación de memoria dinámica.


12
2017-09-19 23:49



El trato con los sistemas en tiempo real es que el programa debe cumplir estrictamente con ciertas restricciones de computación y memoria, independientemente de la ruta de ejecución tomada (que aún puede variar considerablemente según la entrada). Entonces, ¿qué significa el uso de la asignación de memoria dinámica genérica (como malloc / new) en este contexto? Significa que el desarrollador en algún momento no puede determinar el consumo exacto de memoria y sería imposible determinar si el programa resultante podrá cumplir con los requisitos, tanto para la memoria como para la potencia de cálculo.


10
2017-09-19 10:46



Si es correcto. Para el tipo de aplicaciones que menciona, todo lo que puede ocurrir debe especificarse en detalle. El programa debe manejar el peor de los escenarios según las especificaciones y reservar exactamente tanta memoria, ni más ni menos. La situación donde "no sabemos cuántas entradas obtenemos" no existe. El peor de los escenarios se especifica con números fijos.

Su programa debe ser determinista en el sentido de que puede manejar todo hasta el peor de los casos.

El objetivo del montón es permitir que varias aplicaciones no relacionadas compartan memoria RAM, como en una PC, donde la cantidad de programas / procesos / subprocesos en ejecución no es determinista. Este escenario no existe en un sistema en tiempo real.

Además, el montón no es determinista en su naturaleza, ya que los segmentos se agregan o eliminan a lo largo del tiempo.

Más información aquí: https://electronics.stackexchange.com/a/171581/6102


7
2017-09-19 11:03



Incluso si su asignador de montón tiene un comportamiento repetible (la misma secuencia de asignación y llamadas gratuitas producen la misma secuencia de bloques, por lo tanto (con suerte) el mismo estado de montón interno), el estado del montón puede variar drásticamente si se cambia la secuencia de llamadas , lo que puede conducir a la fragmentación que causará fallas de asignación de memoria de una manera impredecible.

La razón por la cual la asignación del montón está mal vista de lo que está francamente prohibido en los sistemas integrados, esp. Los sistemas de misión crítica como la guía de aeronaves o naves espaciales o los sistemas de soporte vital no permiten analizar todas las posibles variaciones en la secuencia de llamadas malloc / libres que pueden ocurrir en respuesta a eventos intrínsecamente asincrónicos.

La solución es que cada manejador tenga su única memoria reservada para su propósito y ya no importa (al menos en lo que respecta al uso de la memoria) en qué orden se invocan estos manejadores.


5
2017-09-19 21:41



El problema con el uso de Heap en el software duro en tiempo real es que las asignaciones de Heap pueden fallar. ¿Qué haces cuando te quedas sin montón?

Estás hablando de aplicaciones espaciales. Usted tiene requisitos muy difíciles de no falla. No debe tener la posibilidad de filtrar la memoria, por lo que no es suficiente para ejecutar al menos el código del modo seguro. No debes caerte. No debe lanzar excepciones que no tengan bloque catch. Probablemente no tengas un sistema operativo con memoria protegida, por lo que una aplicación bloqueada puede, en teoría, sacar todo.

Probablemente no quieras usar heap en absoluto. Los beneficios no superan los costos totales del programa.

Normalmente, no determinista significa algo más, pero en este caso la mejor lectura es que quieren que todo el comportamiento del programa sea completamente predecible.


3
2017-09-19 21:13



Presentar Integrity RTOS desde GHS:

https://www.ghs.com/products/rtos/integrity.html

y LynxOS:

http://www.lynx.com/products/real-time-operating-systems/lynxos-178-rtos-for-do-178b-software-certification/

LynxOS e Integrity RTOS se encuentran entre el software utilizado en aplicaciones espaciales, misiles, aviones, etc., ya que muchos otros no están aprobados o certificados por las autoridades (por ejemplo, FAA).

https://www.ghs.com/news/230210r.html

Para cumplir con los estrictos criterios de las aplicaciones espaciales, Integrity RTOS realmente proporciona verificación formal, es decir, lógica matemáticamente probada, de que su software se comporta de acuerdo con las especificaciones.

Entre estos criterios, para citar desde aquí:

https://en.wikipedia.org/wiki/Integrity_(operating_system)

y aquí:

Green Hills Integrity Asignación de memoria dinámica

Es esto:

enter image description here

No soy un especialista en métodos formales, pero tal vez uno de los requisitos para esta verificación es eliminar las incertidumbres en el tiempo requerido para la asignación de memoria. En RTOS, todos los eventos se planean con precisión milisegundos lejos el uno del otro. Y la asignación de memoria dinámica siempre tiene un problema con el tiempo requerido.

Matemáticamente, realmente necesita demostrar que todo funcionó a partir de las suposiciones más fundamentales sobre el tiempo y la cantidad de memoria.

Y si piensas en las alternativas para acumular memoria: memoria estática. La dirección es fija, el tamaño asignado es fijo. La posición en la memoria es fija. Por lo tanto, es muy fácil razonar sobre la suficiencia de la memoria, la confiabilidad, la disponibilidad, etc.


2
2017-09-20 13:10



Respuesta corta

Existen algunos efectos sobre los valores de datos o sus distribuciones de incertidumbre estadística de, por ejemplo, un dispositivo centelleador de activación de primer o segundo nivel que puede derivar de la cantidad de tiempo no reproducible que puede tener que esperar. malloc/free.

El peor aspecto es que no están relacionados con el fenómeno físico, ya sea con el hardware, sino de alguna manera con el estado de la memoria (y su historial).

Su objetivo, en ese caso, es reconstruir la secuencia original de eventos a partir de los datos afectados por esos errores. La secuencia reconstruida / adivinada también se verá afectada por errores. No siempre esta iteración convergerá en una solución estable; no se dice que será el correcto; tus datos no son más independientes ... arriesgas una lógica cortocircuito...

Respuesta más larga

Usted declaró "No pude verificar la exactitud de esta afirmación cuando la gente me dice eso".
Trataré de darte una situación / estudio de caso puramente hipotético.

Imaginemos que maneja un CCD o con algunos disparadores de centelleo de primer y segundo nivel en un sistema que tiene que economizar recursos (está en el espacio).
La velocidad de adquisición se establecerá de modo que el fondo esté en x% del MAXBINCOUNT.

  • Hay una explosión, tienes un pico en los conteos y un desbordamiento en el contador de basura.
    Lo quiero todo: cambias a la tasa máxima de adquisición y terminas tu buffer.
    Vas a liberar / asignar más memoria mientras terminas el búfer adicional.
    ¿Qué harás?

    1. Mantendrás el contraataque arriesgando el rebosar (el segundo nivel intentará contar correctamente el tiempo de los paquetes de datos) pero en este caso, irás a subestimar los conteos para ese período?
    2. usted detendrá el contador presentando un agujero en la serie de tiempo?

    Tenga en cuenta que:

    • En espera de la asignación, perderá la transitorio (o al menos su comienzo).
    • Hagas lo que hagas depende del estado de tu memoria y no es reproducible.
  • Ahora, en cambio, la señal es variable alrededor del maxbincount a la velocidad máxima de adquisición permitida desde su hardware, y el evento es más largo de lo habitual.
    Terminas el espacio y pides más ... mientras tanto, incurres en el mismo problema anterior.
    ¿El desbordamiento y los picos sistemáticos cuentan la subestimación o los agujeros en las series temporales?

Vamos a mover un segundo nivel (también puede estar en el disparador de primer nivel).

Desde su hardware, recibe más datos de los que puede almacenar o transmitir.
Debe agrupar los datos en tiempo o espacio (escalado de 2x2, 4x4, ... 16x16 ... 256x256 ... píxeles ...).

La incertidumbre del problema anterior puede afectar el distribución de error.
Hay una configuración de CCD para la que tiene los píxeles del borde con recuentos cercanos al maxbincount (depende de "dónde" quieres ver mejor).
Ahora puede darse una ducha en su CCD o un solo punto grande con el mismo número total de conteos pero con una incertidumbre estadística diferente (la parte que se introduce por el tiempo de espera) ...

Entonces, por ejemplo, donde está esperando un perfil de Lorentz, puede obtener su convolución con un gaussiano (un Voigt), o si el segundo es realmente dominante con un sucio Gaussiano ...


2
2017-09-20 12:14



Siempre hay una compensación. Es el entorno de ejecución del programa y las tareas que realiza que debería ser la base para decidir si HEAP se debe utilizar o no.

El objeto Heap es eficiente cuando desea compartir los datos entre múltiples llamadas a funciones. Solo necesita pasar el puntero ya que Heap es accesible globalmente. También hay desventajas. Algunas funciones pueden liberar esta memoria, pero aún algunas referencias pueden existir en otros lugares también.

Si la memoria del montón no se libera después de que se ha terminado el trabajo y el programa sigue asignando más memoria, en algún momento HEAP se quedará sin memoria y afectará el carácter determinista del programa.


-3
2017-09-19 11:05