使用堆内存(malloc/new)是否会创建非确定性程序?

在实时系统的上下文中,确定性不仅仅是可重复的“执行路径”。另一个必需的特性是关键事件的时间是有界的。在硬实时系统中,发生在允许时间间隔之外的事件(在该时间间隔开始之前或结束之后)表示系统故障。

在这种情况下,使用动态内存分配可能会导致不确定性,特别是当程序具有不同的分配、取消分配和重新分配模式时。分配、取消分配和重新分配的时间可能随时间而变化,因此使整个系统的时间不可预测。

将堆管理器与 非确定性 行为创建具有不确定性行为的程序。但这是显而易见的。

available[] N位掩码。为了分配,它检查第一个可用条目(位测试,O(N),确定性上限)。要取消分配,它设置可用位(O(1))。 malloc(X) 将X取整到M的下一个最大值,以选择正确的池。

这可能不是很有效,尤其是当您选择的N和M太高时。如果你选择太低,你的程序可能会失败。但是,N和M的限制可能低于没有动态内存分配的等效程序的限制。

C11 标准或英寸 n1570 他说 malloc 确定性(或非确定性);也没有其他类似的文档 malloc(3) 在Linux上。顺便说一句,很多 free software .

但是 可以(并且确实)失败,并且其性能未知(典型的调用 马洛克 在我的桌面上 几乎 不到一微秒,但我可以想象奇怪的情况,在一台负载非常大的计算机上可能需要更多的时间,可能需要很多毫秒;了解 thrashing ASLR (地址空间布局随机化)因此运行同一程序两次会产生不同的 马洛克 here 几乎 无用的

决定论意味着两次运行一个程序将得到完全相同的执行路径

这在大多数嵌入式系统中实际上是错误的,因为物理环境正在变化;例如,驱动火箭发动机的软件不能期望推力、阻力或风速等。。。是 从一次发射到下一次发射都是一样的。

^{(所以我很惊讶你相信或希望实时系统是确定性的;它们从来都不是!也许你关心 WCET caches}

马洛克 (或其变体)。C++程序可以 allocator container s、 另请参见 this 和 that

以及嵌入式软件的高层(想想自动驾驶汽车及其 planning 软件)肯定在使用堆分配,甚至可能 garbage collection 技术(其中一些是“实时的”),但通常不被视为安全关键技术。

tl;dr:动态内存分配并不是天生的 (正如您根据相同的执行路径定义的);它通常会让你的程序 不可预知的 . 具体来说,您无法预测分配器在面对任意输入序列时是否会失败。

但这不是一个有趣的情况,所以让我们假设一个完全确定的分配器:相同的分配和释放序列总是会在相同的位置产生相同的块,这些分配和释放总是有一个有限的运行时间。

现在,您的程序可以是确定性的:相同的输入集将导致完全相同的执行路径。

问题是,如果您根据输入分配和释放内存,您无法预测分配是否会失败(失败不是一种选择)。

但是,即使你能证明没有泄漏,你也需要知道,从来没有一个输入序列需要比可用内存更多的内存。

但是,即使您可以证明程序永远不会需要比可用内存更多的内存,根据分配和释放的顺序,分配器可能会分割内存,因此最终无法找到满足分配的连续块,即使总体上有足够的可用内存。

很难证明不存在会导致病理碎片的输入序列。

处理实时系统的方法是,无论执行路径如何(根据输入,执行路径可能仍有很大差异),程序都必须严格满足某些计算和内存限制。那么,在这种情况下,通用动态内存分配(如malloc/new)的使用意味着什么呢?这意味着开发人员在某些时候无法确定确切的内存消耗,并且不可能判断生成的程序是否能够满足内存和计算能力的要求。

是的,它是正确的。对于您提到的应用程序,必须详细说明可能发生的一切。程序必须根据规范处理最坏的情况,并留出足够的内存,不多也不少。“我们不知道我们得到了多少输入”的情况并不存在。最坏情况是用固定数字指定的。

您的程序在某种意义上必须是确定性的,它可以处理最坏情况下的所有事情。

堆的真正目的是允许几个不相关的应用程序共享RAM内存,例如在PC中,运行的程序/进程/线程的数量是不确定的。实时系统中不存在这种情况。

更多信息请点击此处: https://electronics.stackexchange.com/a/171581/6102

在嵌入式系统中,尤其是在任务关键型系统(如飞机或航天器制导或生命支持系统)中,堆分配被严格禁止的原因是,无法测试响应本质异步事件时可能发生的malloc/free调用序列中的所有可能变化。

解决方案是为每个处理程序留出一个内存用于其目的,并且这些处理程序的调用顺序不再重要(至少就内存使用而言)。

你说的是太空应用。你有非常严格的不失败要求。您必须没有内存泄漏的可能性,因此至少安全模式代码无法运行。你不能摔倒。您不能抛出没有catch块的异常。你可能没有一个内存受保护的操作系统,所以一个崩溃的应用程序理论上可以毁掉一切。

非确定性通常意味着其他东西,但在这种情况下,最好的解读是他们希望整个程序行为完全可预测。

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

和LynxOS:

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

LynxOS和Integrity RTOS是用于空间应用、导弹、飞机等的软件之一,因为许多其他软件未经当局(如FAA)批准或认证。

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

为了满足严格的空间应用标准,完整性实时操作系统实际上提供了形式验证,即数学证明的逻辑,以证明其软件的行为符合规范。

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

这里:

Green Hills Integrity Dynamic memory allocation

从数学上来说,你真的需要证明一切都是从关于时间和内存量的最基本假设开始的。

静态存储器 . 地址是固定的,分配的大小是固定的。内存中的位置是固定的。因此,很容易对内存充足性、可靠性、可用性等进行推理。

简短的回答

对数据值或其统计不确定度分布有一些影响,例如,一级或二级触发闪烁体设备,其可能来自您可能必须等待的不可再现时间量 malloc/free

最糟糕的方面是,它们与硬件的物理现象无关,但在某种程度上与内存的状态(及其历史)有关。

短路 ...

你说过 “当人们告诉我这一点时,我无法验证这一说法的正确性。”
我将尝试给你一个纯粹的假设情况/案例研究。

让我们想象一下,你在一个系统上处理CCD或一些一级和二级闪烁体触发器,它们必须节约资源(你在太空中)。
采集速率将设置为使背景处于 x% 的 MAXBINCOUNT .

• 
  
  您可以在完成额外缓冲区的同时释放/分配更多内存。
  你会怎么做?

  1. 你将保持反作用的风险 (第二级将尝试正确计算数据包的计时),但在这种情况下,您将转到 那一时期的统计数字是多少?
  2. 您将阻止柜台引入 ?
  • 等待分配您将失去 转瞬即逝的 (或者至少是它的开始)。
  • 无论你做什么,这取决于你的记忆状态,它是不可复制的。

• 现在,信号在 maxbincount
  你完成了空间并要求更多。。。同时,你也遇到了同样的问题。
  溢出和系统峰值统计时间序列中的低估或漏洞?

让我们移动第二级(也可以在第一级触发器上)。

从硬件接收的数据超过了存储或传输的数据量。
您必须在时间或空间上对数据进行聚类(2x2、4x4、…16x16…256x256…像素缩放…)。

前一个问题的不确定性可能会影响
maxbincount (这取决于 “其中”
现在你可以在你的CCD上有一个淋浴或一个大的点,具有相同的计数总数,但具有不同的统计不确定性(由等待时间引入的部分)。。。

例如,当你期望一个洛伦兹轮廓时,你可以得到它与高斯轮廓的卷积(Voigt),或者如果第二个轮廓真的是占主导地位的 肮脏的 高斯。。。

如果堆内存在其工作完成后没有释放,并且程序继续分配更多内存,那么在某个时候堆将耗尽内存,并影响程序的确定性特征。