使用堆内存（malloc/new）会创建一个不确定性程序吗？

Question

使用堆内存（malloc/new）会创建一个不确定性程序吗？

c++creal-timedeterministicnon-deterministic

79

我几个月前开始使用C语言为空间应用程序和使用C++语言的微控制器开发实时系统软件。在这类系统中，有一个经验法则，就是永远不要创建堆对象(因此没有malloc/new)，因为这会使程序不确定性。当别人告诉我这个经验法则时，我无法验证其正确性。那么，这是一个正确的说法吗？

对我来说纠结的地方在于，据我所知，确定性意味着再次运行程序将导致完全相同的执行路径。就我的理解而言，在多线程系统中会出现这个问题，因为每次运行相同的程序可能会按不同的顺序运行不同的线程。

- The Quantum Physicist

12

动态内存分配和释放存在内存碎片问题，在实时应用程序中这是不可接受的。 - Gaurav Pathak

24

基本上是这样的：PC程序员学习使用malloc/new。然后他们来到嵌入式系统，但由于嵌入式系统具有完全不同的架构和思维方式，堆栈在这里就不再有任何意义了。PC程序员感到沮丧，因为学校没有教他们如何在嵌入式系统中使用堆栈！而且他们已经在PC上使用堆栈很长时间了！PC程序员无视其他人并继续使用堆栈分配内存。结果程序变得糟糕，充满错误和性能问题。PC程序员被解雇。嵌入式系统程序员接手处理混乱。程序被重新从头编写。 - Lundin

11

作为一名获得过粒子物理学和原子物理学博士学位的物理学家，我已经发现很难区分计算机中的确定性和非确定性，因为我们生活在一个非确定性的宇宙中。我知道我的问题很容易引起循环论证，即在某些假设下是否存在确定性，才能将其称为确定性。但这里的确定性语言使用仅限于计算机科学家的用法，与自然界中的真实随机性没有实际关联。 - The Quantum Physicist

9

在现代几乎所有的计算机上做非确定性的事情都是微不足道的。其中一种简单的方法是在等待磁盘读取完成的例程中注意处理器指令计数器的最低有效位。它受到磁盘旋转速度的剪切湍流的影响。你可以通过类似的方式处理网络数据包，这受到石英晶体微观区域温度变化的影响，进而影响网络接口时钟和CPU时钟之间的偏差。你还可以从音频输入中提取热噪声。还有许多其他的方法。 - David Schwartz

6

现在大多数x86 CPU（自IvyBridge时代Intel开始）都内置了一个名为rdrand的指令，您可以从一个普通的用户空间进程中执行它。它从热噪声发生器提供真正的硬件随机性，并使用AES进行条件处理（除非NSA削弱了设计…）。当然，正如David指出的那样，rdtsc也是不确定的，特别是考虑到仅一个进程，但他提出了不同时钟域之间的同步给出了一些真正的不确定性。 - Peter Cordes

显示剩余15条评论

12个回答

40

如所述，该评论是不正确的。

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

稍微不那么明显的是具有确定性行为的堆管理器的存在。可能最著名的示例是池分配器。它具有N * M字节的数组和N位的available[]掩码。要进行分配，它会检查第一个可用条目（位测试，O(N)，确定性上限）。要进行释放，它设置可用位（O(1)）。 malloc(X)将X舍入到下一个最大的M值以选择正确的池。

这可能不是很有效率，特别是如果您选择的N和M值过高。如果您选择得太低，程序可能会失败。但是，与没有动态内存分配的等效程序相比，N和M的限制可以更低。

- MSalters

循环缓冲区是这种分配器的一种变体，甚至可以在执行开始时使用单个malloc进行分配，然后根据上下文进行其他变异-如果您事先知道需要N个不同的缓冲区大小，则可以构建更高效的分配器。 - Rsf

1

使用链表作为池收集器的另一种方法，可以避免使用位掩码，具有O(1)的分配和释放。只要代码不尝试分配超过池中存在的某个大小的更多缓冲区，时间就是完全确定的，除了缓存问题。 - supercat

1

更一般的情况是在需要确定性行为之前提前进行分配。就像这个池分配器所需的内存一样 :) - Hans Passant

我在这里的使命是打破嵌入式工程师中普遍存在的一个误解，即任意大小的内存分配（如malloc()而不是固定大小的块）本质上是非时间确定性的或可能导致无限制的碎片化。正如“Timing-Predictable Memory Allocation In Hard Real-Time Systems” [Herter 2014]所示，可预测和高效的算法存在，但它们很少被提及。我在这里实现了一个约500行的实时嵌入式系统的算法：https://github.com/pavel-kirienko/o1heap - Pavel Kirienko

21

C11标准或n1570文件中都未对malloc的确定性（或非确定性）进行规定。而且，像Linux上的malloc(3)等一些其他文档也没有提及。顺便说一句，许多malloc实现都是免费软件。

但是malloc可能失败（确实有这种情况），而且其性能不确定（在我的台式计算机上，典型的malloc调用实际上只需要不到一微秒的时间，但我可以想象，在非常繁忙的计算机上可能需要更长时间，例如几毫秒；请阅读关于抖动的内容）。另外，我的Linux台式机具有ASLR（地址空间布局随机化），因此两次运行同一个程序会给出不同的malloc分配的地址（在进程的虚拟地址空间中）。顺便说一句，这里有一个确定性（在需要详细说明的特定假设下）但实际上没有什么用处的malloc实现。

确定性意味着两次运行程序将导致完全相同的执行路径

这在大多数嵌入式系统中实际上是错误的，因为物理环境正在发生变化；例如，驱动火箭引擎的软件不能期望从一次发射到下一次发射推力、阻力、风速等都是完全相同的。

^{所以我感到惊讶的是你相信或希望实时系统是确定性的; 它们从来不是！也许您关心 WCET，由于高速缓存的影响，这越来越难以预测)}

顺便提一下，一些“实时”或“嵌入式”系统正在实现自己的malloc（或其变体）。C ++程序可以使用其分配器，它可以被标准的容器使用。还可以参考这篇文章和那篇文章等等.....

嵌入式软件的高级层（例如自动驾驶汽车及其规划软件）肯定正在使用堆分配，甚至可能是垃圾收集技术（其中一些是“实时的”），但通常不被认为具有安全性关键性。

- Basile Starynkevitch

6

我认为OP的意思是运行程序两次 使用完全相同的输入 应该导致相同的执行路径，或者相同的可观察行为（或任何其他首选定义）。 - Toby Speight

但是，“可观察行为”是主观的（例如，使用malloc结果的％p调试printf），可能会引起激烈讨论。 - Basile Starynkevitch

一个自主车辆（或实际上任何其他关键安全汽车软件）的计划者将不使用堆分配或垃圾回收。动态内存分配被MISRA规则禁止使用。 - dasdingonesin

我在AI意义上使用了规划。所有的规划AI软件都使用堆分配（大多数使用垃圾回收并编写在非常高级的AI语言中，例如Lisp、Prolog等）。当然，它们不是这些系统的安全关键层。 - Basile Starynkevitch

12

tl;dr: 动态内存分配并不是本质上的“不确定性”（如您在执行路径相同的条件下定义的），而是使程序通常变得“不可预测”。具体来说，您无法预测分配器是否会在任意输入序列面前失败。

您可以有一个非确定性的分配器。这在您的实时世界之外实际上很常见，操作系统使用诸如地址布局随机化之类的东西。当然，这将使您的程序非确定性。

但这不是一个有趣的情况，因此让我们假设一个完全确定性的分配器：相同的分配和释放序列总是会导致相同位置的相同块，这些分配和释放具有有限的运行时间。

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

问题在于，如果您正在根据输入分配和释放内存，则无法预测分配是否会失败（并且失败不是一种选择）。

首先，您的程序可能会泄漏内存。因此，如果需要无限制地运行，最终会出现分配失败的情况。

但是即使您可以证明没有泄漏，您也需要知道是否存在能够要求更多内存的输入序列。

但即使您可以证明程序永远不会需要超过可用内存，分配器也可能会根据分配和释放序列的不同而使内存碎片化，从而最终无法找到连续的块来满足分配，即使整体上有足够的空闲内存。

很难证明没有输入序列会导致病态碎片化。

您可以设计分配器来保证没有内存碎片（例如，分配仅限于一个大小的块），但这会对调用者造成重大约束并可能增加由于浪费而需要的内存量。而且调用者仍然必须证明没有泄漏，并且无论输入序列如何，都存在可满足的总内存上限。这个负担非常重，实际上更简单的方法是设计系统不使用动态内存分配。

- Adrian McCarthy

OP提到了空间应用（高可靠性）和基于微控制器的应用程序。对于这些应用，真正的大问题是堆碎片化和可能发生的意外分配失败。由于微控制器可用内存空间较小，出现这种类型的错误的可能性很高。为了防止这种情况发生，所有内存都应该被静态分配，并且应仔细监测最大堆栈使用量。 - uɐɪ

10

实时系统的问题在于，程序必须严格符合特定的计算和内存限制，无论采取哪种执行路径（这可能仍然会因输入而有很大不同）。那么，在这种情况下使用通用动态内存分配（例如malloc / new）意味着什么？这意味着开发人员在某个时刻无法确定确切的内存消耗，并且不可能告诉是否结果程序将能够满足内存和计算能力要求。

- user7860670

4

解压相同的压缩文件总是会得到相同的结果，但建议存储未压缩的结果有点忽略了文件压缩的意义。更严肃地说，路线规划器是一个众所周知的完全确定性程序的例子，其输入空间很小（起点和终点），但其结果矩阵太大而无法存储。 - MSalters

1

这似乎并没有回答被问出的问题，而是回答了其他问题。提醒一下，问题是“使用堆会使程序不确定吗？”这并没有回答那个问题。它可能回答了“在实时系统中使用堆是否有问题？”，但那是另一个问题。 - D.W.

8

是的，这是正确的。对于您提到的那种应用程序，必须详细说明可能发生的每种情况。根据规范，程序必须处理最坏情况，并准确地留出那么多内存，既不多也不少。不存在“我们不知道会得到多少输入”的情况。最坏情况是用固定数字指定的。

您的程序必须是确定性的，以便能够处理最坏情况。

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

此外，堆是非确定性的，因为随着时间的推移，段会被添加或删除。

更多信息请参见：https://electronics.stackexchange.com/a/171581/6102

- Lundin

2

“确定性”并不意味着它可以处理一切，直到最坏的情况。糟糕的工程并不代表非确定性。 - D.W.

1

@D.W. 如果您指定程序应该能够处理多达100个事物，那么您就要为此进行设计，并期望在100个情况下获得确定性行为。如果您超出了指定的限制，那么一切都是未知的结果。这实际上就是确定性的含义。另一种选择是不设置上限并进行堆分配。程序失控的点无法轻易确定。它取决于堆大小、堆碎片化和许多其他因素。同样，如果您允许“任意数量的输入”而不是确定性的最大值。 - Lundin

6

即使您的堆分配器具有可重复的行为（相同的分配和释放调用序列会产生相同的块序列，因此（希望）相同的内部堆状态），如果调用序列发生变化，则堆的状态可能会大幅变化，可能导致碎片化，从而以不可预测的方式导致内存分配失败。

堆分配在嵌入式系统中被反对或完全禁止的原因是，在内在异步事件的响应中，无法测试malloc/free调用可能发生的所有可能变化的序列，尤其是在关键任务系统中，例如飞机或宇宙飞船导航或生命支持系统。

解决方案是为每个处理程序保留其自己的内存，以便其目的得到满足，并且不再需要按任何顺序调用这些处理程序（至少就内存使用而言）。

- chqrlie

4

在硬实时软件中使用堆的问题在于，堆分配可能会失败。当您用完堆空间时该怎么办？

您正在谈论太空应用。您有相当严格的无故障要求。您不能有任何泄漏内存的可能性，以至少使安全模式代码可以运行。您不得倒下。您不得抛出没有catch块的异常。您可能没有带有受保护内存的操作系统，因此一个崩溃的应用程序理论上可以搞垮一切。

您可能根本不想使用堆。利弊不成比例。

非确定性通常指其他内容，但在这种情况下，最好理解为他们希望整个程序行为完全可预测。

- Joshua

2

简短回答

例如，第一或第二级触发闪烁器设备可能从不可重复的malloc/free等待时间中导致数据值或其统计不确定性分布的某些影响。

最糟糕的方面是，它们既不与物理现象相关，也不与硬件相关，而是与内存状态（及其历史）有关。

在这种情况下，您的目标是从受这些错误影响的数据中重构原始事件序列。重构/猜测的序列也将受到错误的影响。并不总是能够收敛到稳定的解决方案；这并不意味着它会是正确的；您的数据不再独立... 您面临逻辑短路的风险...

详细回答

您说："当人们告诉我时，我无法验证此声明的正确性"。
我将尝试给您一个纯粹的假设情况/案例研究。

让我们想象一下，您处理具有 CCD 或某些第一和第二级闪烁体触发器的系统，该系统必须节约资源（您位于太空中）。
采集率将设置为使背景处于MAXBINCOUNT的x%。

出现了一次突发，您的计数器出现了尖峰，并且bin计数器溢出。
我需要全部：您切换到最大采集速率并完成缓冲区。
同时，你去释放/分配更多内存，等待结束额外的缓冲区。
你会怎么做？
1. 你将保持对抗性，冒着溢出的风险（第二级将尝试正确计算数据包的时间），但在这种情况下，您将低估该时期的计数？
2. 你会停止计数，引入时间序列中的空洞吗？
请注意：
- 等待分配您将失去瞬态（或至少其开头）。
- 您所做的任何事情都取决于您内存的状态，而且它是无法重现的。
现在相反，信号在允许您硬件的最大采集速率下围绕maxbincount变化，并且事件比通常更长。
你用完空间并请求更多...同时，您遇到了上述相同的问题。
溢出和系统峰计数低估或时间序列中的空洞？