c++ - pilas - ¿Usar memoria de almacenamiento dinámico(malloc/new) crea un programa no determinista?

pilas en c++ ejercicios resueltos

Question

Hace unos meses comencé a desarrollar software para sistemas en tiempo real en C para aplicaciones espaciales, y también para microcontroladores con C ++. Hay una regla general en tales sistemas que uno nunca debería crear objetos de montón (por lo que no hay malloc / new), porque hace que el programa no sea determinista . No pude verificar la exactitud de esta declaración cuando la gente me dice eso. Entonces, ¿es esta una afirmació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. 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 un orden diferente cada vez.

Answer 1

Respuesta corta

Hay algunos efectos sobre los valores de los datos o sus distribuciones de incertidumbre estadística de, por ejemplo, un dispositivo de centelleo desencadenante de primer o segundo nivel que puede derivarse de la cantidad de tiempo no reproducible que puede tener que esperar para malloc/free .

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

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 los errores. No siempre esta iteración convergerá en una solución estable; no se dice que será el correcto; sus datos ya no son independientes ... Corre el riesgo de un cortocircuito lógico ...

Respuesta más larga

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

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

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

  1. Mantendrá el contraataque arriesgando el desbordamiento (el segundo nivel tratará de contar correctamente el tiempo de los paquetes de datos) pero en este caso, ¿ subestimará los recuentos para ese período?
  2. vas a detener el contador introduciendo un agujero en la serie de tiempo ?

  Tenga en cuenta que:

  • Esperando la asignación, perderá el transitorio (o al menos su comienzo).
  • Lo que sea que haga depende del estado de su memoria y no es reproducible.

• Ahora, en cambio, la señal es variable alrededor del maxbincount a la tasa de adquisición máxima permitida desde su hardware, y el evento es más largo de lo habitual.
  Termina el espacio y pide más ... mientras tanto, incurre en el mismo problema anterior.
  ¿El desbordamiento y los picos sistemáticos cuentan la subestimación o los agujeros en las series de tiempo?

Permítanos mover un segundo nivel (también puede estar en el gatillo del primer nivel).

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

La incertidumbre del problema anterior puede afectar la distribución del error .
Hay una configuración CCD para la que tiene los píxeles del borde con recuentos cercanos al maxbincount (depende de "dónde" desea ver mejor).
Ahora puede ducharse en su CCD o en un solo lugar 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, cuando espera un perfil lorentziano, puede obtener su convolución con uno gaussiano (un Voigt), o si el segundo es realmente dominante con un gaussiano sucio ...

Answer 2

El comentario, como se dijo, es incorrecto.

El uso de un administrador de montón con comportamiento no determinista 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 piscinas. Tiene una matriz de N * M bytes y una máscara available[] 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 podría 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 más bajos que para un programa equivalente sin asignación de memoria dinámica.

Answer 3

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

Estás hablando de aplicaciones espaciales. Tiene requisitos bastante estrictos sin fallas. No debe tener ninguna posibilidad de pérdida de memoria, por lo que no hay suficiente para que se ejecute al menos el código de modo seguro. No debes caerte. No debe lanzar excepciones que no tengan bloque de captura. Probablemente no tenga un sistema operativo con memoria protegida, por lo que, en teoría, una aplicación que falla puede eliminar todo.

Probablemente no quieras usar el montón en absoluto. Los beneficios no superan los costos de todo el programa.

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

Answer 4

El trato con los sistemas en tiempo real es que el programa debe cumplir estrictamente ciertas restricciones de cálculo y memoria, independientemente de la ruta de ejecución tomada (que aún puede variar considerablemente dependiendo de 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 saber si el programa resultante podrá cumplir los requisitos, tanto de memoria como de potencia de cálculo.

Answer 5

En el contexto de los sistemas en tiempo real, hay más en el determinismo que una "ruta de ejecución" repetible. Otra propiedad requerida es que el tiempo de los eventos clave está limitado. En sistemas de tiempo real difíciles, un evento que ocurre fuera de su intervalo de tiempo permitido (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, desasignación y reasignación puede variar con el tiempo y, por lo tanto, hacer que los tiempos para el sistema en general sean impredecibles.

Answer 6

Hay una compensación siempre. Es el entorno de ejecución del programa y las tareas que realiza lo que debe ser la base para decidir si se debe usar HEAP o no.

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

Si la memoria de almacenamiento dinámico no se libera después de que se realiza 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.

Answer 7

Incluso si su asignador de montón tiene un comportamiento repetible (la misma secuencia de asignación y las 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 una fragmentación que provocará fallas en la asignación de memoria de una manera impredecible.

La razón por la que la asignación del montón está mal vista es totalmente prohibida en los sistemas integrados, especialmente. Los sistemas de misión crítica como la orientación de aeronaves o naves espaciales o los sistemas de soporte vital no hay forma de probar todas las variaciones posibles en la secuencia de llamadas malloc / gratuitas que pueden ocurrir en respuesta a eventos intrínsecamente asíncronos.

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

Answer 8

Introducir Integrity RTOS de 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 dinámica de memoria

Es esto:

No soy especialista en métodos formales, pero quizás 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 planifican con precisión a milisegundos de distancia. Y la asignación dinámica de memoria siempre tiene un problema con el tiempo requerido.

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

Y si piensa en las alternativas a la memoria de almacenamiento dinámico: 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.

Answer 9

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

Pero malloc puede fallar (y lo hace), y su rendimiento no se conoce (una llamada típica a malloc en mi escritorio prácticamente tomaría menos de un microsegundo, pero podría imaginar situaciones extrañas en las que podría tomar mucho más, tal vez muchos milisegundos en un computadora muy cargada; lea sobre la thrashing ). Y mi escritorio Linux tiene ASLR (aleatorización del diseño del espacio de direcciones), por lo que ejecutar el mismo programa dos veces da diferentes direcciones malloc (en el espacio de direcciones virtuales del proceso). Por cierto, here hay una implementación malloc determinista (bajo supuestos específicos que necesita elaborar) pero prácticamente inútil.

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 o la velocidad del viento, etc. sean exactamente iguales de un lanzamiento al siguiente.

^{(así que me sorprende que creas o desees que los sistemas en tiempo real sean deterministas; ¡nunca lo son! Tal vez te preocupes por WCET , que es cada vez más difícil de predecir debido a los caches )}

Por cierto, algunos sistemas "en tiempo real" o "integrados" están implementando su propio malloc (o alguna variante del mismo). Los programas C ++ pueden tener sus allocator -s, utilizables por container estándar. Ver también this y that , etc., etc.

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

Answer 10

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 casos según las especificaciones y reservar exactamente esa cantidad de memoria, ni más, ni menos. La situación en la que "no sabemos cuántas entradas obtenemos" no existe. El peor de los casos 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 propósito 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 es de naturaleza no determinista, ya que los segmentos se agregan o eliminan con el tiempo.

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

Answer 11

tl; dr: No es que la asignación dinámica de memoria sea inherentemente no determinista (como la definió en términos de rutas de ejecución idénticas); es que generalmente hace que su programa sea impredecible . Específicamente, no puede predecir si el asignador podría 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 la aleatorización del diseño de direcciones. Por supuesto, eso haría que su 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 está asignando y liberando memoria en respuesta a las entradas, no puede predecir si una 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, necesitará saber que nunca hay una secuencia de entrada que pueda exigir más memoria de la que está disponible.

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

Es muy difícil demostrar 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, al asignar 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 se requiere un límite superior saturable en la memoria total, 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 use la asignación dinámica de memoria.