¿El uso de memoria de montón (malloc/new) crea un programa no determinista?

El comentario, como se ha dicho, es incorrecto.

Usando un gestor de montones con comportamiento no determinista crea un programa con comportamiento no determinista. Pero eso es obvio.

Un poco menos obvia es la existencia de gestores de pilas con comportamiento determinista. Quizás el ejemplo más conocido es el asignador de grupos. Tiene una matriz de N * M bytes, y una máscara available[] de N bits. Para asignar, comprueba la primera entrada disponible (bit test, O (N), deterministic upper obligado). 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.

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

Pero malloc puede (y falla), 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 donde podría tomar mucho más, tal vez muchos milisegundos en una computadora muy cargada; lea acerca de thrashing). Y mi escritorio Linux tiene ASLR (distribución aleatoria del espacio de direcciones) por lo que ejecutar el mismo programa dos veces da diferentes direcciones malloc-ed (en el espacio de direcciones virtuales del proceso). BTW aquí es una implementación determinista (bajo supuestos específicos que necesita elaborar) pero prácticamente inútil malloc.

Determinismo significa que ejecutar un programa twice llevará a la misma ruta de ejecución

Esto es prácticamente incorrecto en la mayoría de los sistemas embebidos, porque el entorno físico está cambiando; por ejemplo, el software que conduce un motor de cohete no puede esperar que el empuje, o la resistencia, o la velocidad del viento, etc... es exactamente el mismo 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 importe WCET , que es cada vez más difícil de predecir debido a cachés)}

POR cierto, algunos sistemas "en tiempo real" o "embebidos" están implementando su propio malloc (o alguna variante del mismo). Los programas de C++ pueden tener su asignador-s, utilizable por estándar contenedors. Ver también este y que, etc, etc.....

Y las capas de alto nivel de software embebido (piense en un automóvil autónomo y su software de planificación) son ciertamente usando asignación de montones 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.

Tl;dr: No es que la asignación de memoria dinámica sea inherentemente no determinista (como lo 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 frente a 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 distribución aleatoria de direcciones. Por supuesto, eso haría que su programa no determinista.

Pero ese no es un caso interesante, así que asumamos 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 ejecución camino.

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 el fallo no es una opción).

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

Pero incluso si puede probar que no hay fugas, debería 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 que está 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, a pesar de que 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 haya fragmentación (por ejemplo, asignando bloques de un solo tamaño), pero eso pone una restricción sustancial en el llamante 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 saciable 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.

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 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? Esto significa que el desarrollador en algún momento no es capaz de determinar el consumo de memoria exacta y sería imposible decir si el programa resultante será capaz de cumplir con los requisitos, tanto para la memoria como para la potencia de cálculo.

Sí es correcto. Para el tipo de aplicaciones que mencionas, todo lo que puede ocurrir debe especificarse en detalle. El programa debe manejar el peor de los casos de acuerdo con las especificaciones y dejar de lado exactamente esa cantidad de memoria, ni más, ni menos. La situación en la que "no sabemos cuántos insumos recibimos" no existe. El peor de los casos se especifica con números fijos.

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

El propósito mismo del montón es permitir que varias aplicaciones no relacionadas compartan memoria RAM, como en un PC, donde la cantidad de programas/procesos/subprocesos que se ejecutan 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 con el tiempo.

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

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 potencialmente conduce a la fragmentación que causará fallas en la asignación de memoria de una manera impredecible.

La asignación del montón de la razón está mal visto de francamente prohibido en sistemas embebidos, esp. misión crítica sistemas como la guía de aeronaves o naves espaciales o los sistemas de soporte vital no hay manera de probar todas las variaciones posibles en la secuencia de llamadas malloc/gratuitas que pueden ocurrir en respuesta a eventos intrínsecamente asincrónicos.

La solución es que cada manejador tenga su 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 manejadores.

El problema con el uso de heap en 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. Tienes requisitos muy difíciles de no fallar. No debe tener ninguna posibilidad de pérdida de memoria, por lo que no hay suficiente para que al menos el código de modo seguro se ejecute. No debes caerte. No debe lanzar excepciones que no tengan bloque catch. Probablemente no tenga un sistema operativo con memoria protegida, por lo que una aplicación que se bloquea puede en teoría, saca todo.

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

No determinsítico normalmente significa otra cosa, pero en este caso lo mejor es que quieren que todo el comportamiento del programa sea completamente predecible.

Introducir RTOS de integridad desde GHS:

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

Y LincES:

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, aeronaves, 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, los RTO de Integridad realmente proporcionan una verificación formal, es decir, una lógica matemáticamente probada, de que su software se comporta de acuerdo con las especificaciones.

Entre estos criterios, para citar de aquí:

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

Y aquí:

Memoria dinámica de Integridad de Green Hills asignación

Es esto:

No soy un 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 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ó desde lo más fundamental suposiciones sobre el tiempo y la cantidad de memoria.

Y si piensas en las alternativas a la memoria de montón: 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 memoria, confiabilidad, disponibilidad, etc.

Respuesta corta

Hay algunos efectos sobre los valores de datos o sus distribuciones de incertidumbre estadística de, por ejemplo, un dispositivo de centelleo de disparo de primer o segundo nivel que pueden derivarse 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 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 errores. No siempre esta iteración convergerá en una solución estable; no se dice que será la correcta; sus datos no son más independientes... Se corre el riesgo de un cortocircuito lógico ...

Respuesta más larga

Usted declaró " No fui capaz de verificar la exactitud de esta declaración cuando la gente me dice eso " .
Voy a tratar de darle una situación puramente hipotética/ estudio de caso.

Imaginemos que tratas con un CCD o con algunos disparadores de centelleo de 1er y 2do nivel en un sistema que tienen que economizar recursos (estás en el espacio).
La tasa de adquisición se establecerá de manera que el fondo esté en x% del MAXBINCOUNT.

• Hay una ráfaga, tienes un pico en los recuentos y un desbordamiento en el contador de la papelera.
  Lo quiero todo: cambias al máximo tasa de adquisición y terminas tu buffer.
  Vas a liberar / asignar más memoria mientras terminas el búfer extra.
  ¿Qué harás?

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

  Tenga en cuenta que:

  • A la espera de la asignación perderá el transitorio (o al menos su comienzo).
  • Cualquier cosa que hagas depende del estado de tu memoria y no es reproducible.

• Ahora, en cambio, la señal es variable alrededor de maxbincount a la tasa de adquisición máxima permitida desde su hardware, y el evento es más largo de lo habitual.
  Terminas el espacio y pides más... mientras tanto, usted incurre en el mismo problema anterior.
  Desbordamiento y picos sistemáticos cuenta subestimación o agujeros en la serie temporal?

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

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

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

Así que, por ejemplo, cuando se espera un perfil lorentziano, se puede obtener su convolución con un Uno gaussiano (un Voigt), o si el segundo es realmente dominante con un sucio Gaussiano...

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

El objeto Heap es eficiente cuando desea compartir los datos entre varias llamadas a funciones. Solo necesita pasar el puntero ya que heap es accesible globalmente. También hay desventajas. Alguna función podría liberar esta memoria, pero aún así pueden existir algunas referencias en otros lugares también.

Si el la memoria del montón no se libera después de que se realiza su trabajo y el programa sigue asignando más memoria, en algún momento EL MONTÓN se quedará sin memoria y afecta el carácter determinista del programa.