使用堆内存（malloc/new）是否会创建一个非确定性程序？
Does using heap memory (malloc/new) create a non-deterministic program?
几个月前，我开始使用 C 语言为 space 应用程序以及使用 C++ 的微控制器开发实时系统软件。在这样的系统中有一个经验法则，一个人永远不应该创建堆对象（所以没有malloc/new），因为它使程序非确定性。当人们告诉我时，我无法验证此声明的正确性。那么，这个说法正确吗？
令我困惑的是，据我所知，确定性意味着 运行 一个程序两次将导致完全相同的执行路径。根据我的理解，这是多线程系统的一个问题，因为 运行 同一个程序多次可能有不同的线程 运行 每次都以不同的顺序。
实时系统的处理是程序必须严格满足某些计算和内存限制，而不管采用的执行路径如何（可能仍会因输入而有很大差异）。那么在这种情况下使用通用动态内存分配（例如 malloc/new）意味着什么？这意味着开发人员在某些时候无法确定确切的内存消耗，并且无法判断生成的程序是否能够满足内存和计算能力的要求。
C11 standard or in n1570 says that malloc is deterministic (or is not); and neither some other documentation like malloc(3) on Linux. BTW, many malloc implementations are free software 中没有内容。
但是 malloc 可能（并且确实）失败，并且其性能未知（在我的桌面上对 malloc 的典型调用 实际上 不到一微秒，但我可以想象奇怪的情况，在负载很重的计算机上可能需要更多时间，也许需要几毫秒；阅读 thrashing). And my Linux desktop has ASLR (address space layout randomization) so runnning the same program twice gives different malloc-ed addresses (in the virtual address space of the process). BTW here 是确定性的（在您需要详细说明的特定假设下）但是 实际上无用malloc实现。
determinism means that running a program twice will lead to the exact, same execution path
这在大多数嵌入式系统中实际上是错误的，因为物理环境在变化；例如，驱动火箭发动机的软件不能期望从一次发射到下一次发射的推力、阻力或风速等...完全相同。
（所以我很惊讶你相信或希望实时系统是确定性的；它们从来不是！也许你关心WCET, which is increasingly difficult to predict because of caches）
顺便说一句，一些 "real-time" 或 "embedded" 系统正在实现自己的 malloc（或它的某些变体）。 C++程序可以有它们的allocator-s, usable by standard containers. See also this and that，等等，等等.....
和嵌入式软件的高层（想想自动驾驶汽车及其 planning software) are certainly using heap allocation and perhaps even garbage collection 技术（其中一些是 "real-time"），但通常不被视为安全关键。
是的，没错。对于您提到的那种应用程序，必须详细说明可能发生的一切。程序必须根据规范处理最坏的情况，并留出恰好那么多的内存，不多也不少。 "we don't know how many inputs we get"的情况是不存在的。最坏情况是用固定数字指定的。
从某种意义上说，您的程序必须是确定性的，它可以处理最坏情况下的所有事情。
堆的真正目的是允许多个不相关的应用程序共享 RAM 内存，例如在 PC 中，programs/processes/threads 运行 的数量是不确定的。这种场景在实时系统中是不存在的。
此外，堆在本质上是不确定的，因为随着时间的推移会添加或删除段。
在实时系统的上下文中，确定性不仅仅是可重复的"execution path"。另一个要求 属性 是关键事件的时间是有界的。在硬实时系统中，在其允许的时间间隔之外发生的事件（在该间隔开始之前或结束之后）表示系统故障。
在这种情况下，使用动态内存分配可能会导致不确定性，尤其是当程序具有不同的分配、取消分配和重新分配模式时。分配、解除分配和重新分配的时间会随时间变化 - 因此使整个系统的时间不可预测。
总是有取舍的。程序的 运行ning 环境和它执行的任务应该是决定是否应该使用 HEAP 的基础。
当你想在多个函数调用之间共享数据时，堆对象是有效的。您只需要传递指针，因为堆是全局可访问的。也有缺点。某些函数可能会释放此内存，但其他地方也可能存在一些引用。
如果堆内存在它的工作完成后没有被释放并且程序继续分配更多内存，在某些时候 HEAP 将 运行 内存不足并影响程序的确定性。
如前所述，评论不正确。
使用具有非确定性 行为的堆管理器创建具有非确定性行为的程序。但这是显而易见的。
不太明显的是具有确定性行为的堆管理器的存在。也许最著名的例子是池分配器。它有一个 N*M 字节的数组，和一个 N 位的 available[] 掩码。为了分配，它检查第一个可用条目（位测试，O(N)，确定性上限）。要解除分配，它会设置可用位 (O(1))。 malloc(X) 会将 X 舍入到 M 的下一个最大值以选择正确的池。
这可能不是很有效，尤其是当您选择的 N 和 M 太高时。如果您选择的太低，您的程序可能会失败。但是 N 和 M 的限制可能低于没有动态内存分配的等效程序。
在硬实时软件中使用堆的问题是堆分配可能会失败。当你 运行 堆满时你会做什么？
您正在谈论 space 个应用程序。您有非常严格的不失败要求。你必须没有内存泄漏的可能性，所以至少安全模式代码是不够的 运行。你不能摔倒。您不得抛出没有 catch 块的异常。您可能没有带受保护内存的 OS，因此理论上一个崩溃的应用程序可以清除所有内容。
您可能根本不想使用堆。收益不会超过整个计划的成本。
非确定性通常意味着其他含义，但在这种情况下，最好的解读是他们希望整个程序的行为完全可预测。
即使您的堆分配器具有可重复的行为（相同的分配序列和自由调用产生相同的块序列，因此（希望）相同的内部堆状态），如果调用顺序发生变化，可能导致碎片化，从而以不可预测的方式导致内存分配失败。
堆分配在嵌入式系统中被彻底禁止的原因是不受欢迎的，尤其是。飞机或航天器制导或生命支持系统等关键任务系统无法测试响应本质上异步事件而发生的 malloc/free 调用序列中的所有可能变化。
解决方案是为每个处理程序预留一个内存用于其用途，并且这些处理程序的调用顺序不再重要（至少就内存使用而言）。
tl;dr：并不是说动态内存分配本质上是 非确定性的 （正如您根据相同的执行路径定义的那样）；就是它通常会使您的程序不可预测。具体来说，您无法预测分配器是否会在面对任意输入序列时失败。
您可能有一个非确定性分配器。这实际上在您的实时世界之外很常见，在实时世界中，操作系统使用诸如地址布局随机化之类的东西。当然，这会使您的程序具有不确定性。
但这不是一个有趣的情况，所以让我们假设一个完全确定的分配器：相同的分配和释放序列总是会在相同的位置产生相同的块，并且这些分配和释放总是有一个有界的运行宁时间.
现在您的程序可以是确定性的：相同的输入集将导致完全相同的执行路径。
问题在于，如果您根据输入分配和释放内存，则无法预测分配是否会失败（失败不是一种选择）。
首先，您的程序可能会泄漏内存。因此，如果它需要无限期地运行，最终分配将失败。
但是即使您可以证明没有泄漏，您也需要知道永远不会有输入序列需要比可用内存更多的内存。
但即使您可以证明程序永远不会需要比可用内存更多的内存，分配器也可能根据分配和释放的顺序产生内存碎片，因此最终无法找到一个连续的块来满足分配，即使总体上有足够的可用内存。
很难证明不存在会导致病态碎片化的输入序列。
您可以设计分配器以保证不会出现碎片（例如，通过仅分配一种大小的块），但这对调用者施加了很大的限制，并且可能会由于浪费而增加所需的内存量.并且调用者仍然必须证明没有泄漏，并且无论输入顺序如何，所需的总内存都有一个可满足的上限。这个负担太重了，其实把系统设计成不使用动态内存分配更简单。
简答
对数据值或其统计不确定性分布有一些影响，例如，第一级或第二级触发闪烁器设备可能源自您可能必须等待的不可重现的时间量malloc/free.
最糟糕的方面是，它们与硬件的物理现象无关，但与内存状态（及其历史）有某种关系。
在这种情况下，您的目标是根据受这些错误影响的数据重建事件的原始序列。 reconstructed/guessed 序列也会受到错误的影响。这种迭代并不总是会收敛于一个稳定的解决方案；并不是说这将是正确的；您的数据不再独立...您冒着逻辑短路...
的风险
更长的答案
您说 "I wasn't able to verify the correctness of this statement when people tell me that"。
我会尽量给你一个纯假设的情况/案例研究。
让我们假设您在必须节约资源的系统上处理 CCD 或一些第一级和第二级闪烁体触发器（您在 space）。
将设置采集速率，使背景位于 MAXBINCOUNT 的 x%。
突然出现，计数出现尖峰，垃圾箱计数器溢出。
我想要这一切：你切换到最大采集率并完成你的缓冲区。
在完成额外缓冲区的同时，您使用了 free/allocate 更多内存。
你会怎么做？
- 你将保持反作用冒着溢出的风险（第二级将尝试正确计算数据包的时间）但在这种情况下，你将转到低估了那个时期的计数？
- 你会停止计数器在时间序列中引入一个漏洞？
注意：
- 等待分配，您将丢失 transient（或至少它的开头）。
- 无论你做什么，都取决于你的记忆状态，而且是不可重现的。
现在，信号在 maxbincount 附近以硬件允许的最大采集速率变化，并且事件比平时更长。
您完成了 space 并要求更多...同时，您遇到了上述相同的问题。
溢出和系统峰值计数低估或时间序列中的漏洞？
让我们移动第二层（它也可以在第一层触发）。
您从您的硬件接收到的数据多于您可以存储或传输的数据。
您必须及时对数据进行聚类或 space（2x2、4x4、... 16x16 ... 256x256... 像素缩放...）。
上一个问题的不确定性可能会影响误差分布。
有 CCD 设置，您的边框像素计数接近 maxbincount（这取决于 "where"，您希望看得更清楚）。
现在，您可以在 CCD 或单个大点上淋浴，总计数相同但统计不确定性不同（等待时间引入的部分）...
因此，例如，在您期望洛伦兹分布的地方，您可以获得其与高斯分布（Voigt）的卷积，或者如果第二个它确实占主导地位 脏 高斯分布...
从 GHS 引入 Integrity RTOS：
https://www.ghs.com/products/rtos/integrity.html
和 LynxOS：
LynxOS 和 Integrity RTOS 是 space 应用程序、导弹、飞机等使用的软件之一，因为许多其他软件未经当局（例如美国联邦航空局）批准或认证。
https://www.ghs.com/news/230210r.html
为了满足 space 应用程序的严格标准，Integrity RTOS 实际上提供形式验证，即数学证明逻辑，其软件的行为符合规范。
在这些标准中，引用自这里：
https://en.wikipedia.org/wiki/Integrity_(operating_system)
这里：
Green Hills Integrity Dynamic memory allocation
这是：
我不是形式化方法方面的专家，但也许这种验证的要求之一是消除内存分配所需时序的不确定性。在 RTOS 中，所有事件都精确地计划为彼此相距几毫秒。而且动态内存分配总是有时间要求的问题。
从数学上讲，您确实需要根据有关时序和内存量的最基本假设来证明一切正常。
如果您想到堆内存的替代方案：静态内存。地址是固定的，分配的大小也是固定的。在内存中的位置是固定的。因此很容易推断出内存充足性、可靠性、可用性等。
几个月前，我开始使用 C 语言为 space 应用程序以及使用 C++ 的微控制器开发实时系统软件。在这样的系统中有一个经验法则，一个人永远不应该创建堆对象（所以没有malloc/new），因为它使程序非确定性。当人们告诉我时，我无法验证此声明的正确性。那么，这个说法正确吗？
令我困惑的是，据我所知，确定性意味着 运行 一个程序两次将导致完全相同的执行路径。根据我的理解，这是多线程系统的一个问题，因为 运行 同一个程序多次可能有不同的线程 运行 每次都以不同的顺序。
实时系统的处理是程序必须严格满足某些计算和内存限制，而不管采用的执行路径如何（可能仍会因输入而有很大差异）。那么在这种情况下使用通用动态内存分配（例如 malloc/new）意味着什么？这意味着开发人员在某些时候无法确定确切的内存消耗，并且无法判断生成的程序是否能够满足内存和计算能力的要求。
C11 standard or in n1570 says that malloc is deterministic (or is not); and neither some other documentation like malloc(3) on Linux. BTW, many malloc implementations are free software 中没有内容。
但是 malloc 可能（并且确实）失败，并且其性能未知（在我的桌面上对 malloc 的典型调用 实际上 不到一微秒，但我可以想象奇怪的情况，在负载很重的计算机上可能需要更多时间，也许需要几毫秒；阅读 thrashing). And my Linux desktop has ASLR (address space layout randomization) so runnning the same program twice gives different malloc-ed addresses (in the virtual address space of the process). BTW here 是确定性的（在您需要详细说明的特定假设下）但是 实际上无用malloc实现。
determinism means that running a program twice will lead to the exact, same execution path
这在大多数嵌入式系统中实际上是错误的，因为物理环境在变化；例如，驱动火箭发动机的软件不能期望从一次发射到下一次发射的推力、阻力或风速等...完全相同。
（所以我很惊讶你相信或希望实时系统是确定性的；它们从来不是！也许你关心WCET, which is increasingly difficult to predict because of caches）
顺便说一句，一些 "real-time" 或 "embedded" 系统正在实现自己的 malloc（或它的某些变体）。 C++程序可以有它们的allocator-s, usable by standard containers. See also this and that，等等，等等.....
和嵌入式软件的高层（想想自动驾驶汽车及其 planning software) are certainly using heap allocation and perhaps even garbage collection 技术（其中一些是 "real-time"），但通常不被视为安全关键。
是的，没错。对于您提到的那种应用程序，必须详细说明可能发生的一切。程序必须根据规范处理最坏的情况，并留出恰好那么多的内存，不多也不少。 "we don't know how many inputs we get"的情况是不存在的。最坏情况是用固定数字指定的。
从某种意义上说，您的程序必须是确定性的，它可以处理最坏情况下的所有事情。
堆的真正目的是允许多个不相关的应用程序共享 RAM 内存，例如在 PC 中，programs/processes/threads 运行 的数量是不确定的。这种场景在实时系统中是不存在的。
此外，堆在本质上是不确定的，因为随着时间的推移会添加或删除段。
在实时系统的上下文中，确定性不仅仅是可重复的"execution path"。另一个要求 属性 是关键事件的时间是有界的。在硬实时系统中，在其允许的时间间隔之外发生的事件（在该间隔开始之前或结束之后）表示系统故障。
在这种情况下，使用动态内存分配可能会导致不确定性，尤其是当程序具有不同的分配、取消分配和重新分配模式时。分配、解除分配和重新分配的时间会随时间变化 - 因此使整个系统的时间不可预测。
总是有取舍的。程序的 运行ning 环境和它执行的任务应该是决定是否应该使用 HEAP 的基础。
当你想在多个函数调用之间共享数据时，堆对象是有效的。您只需要传递指针，因为堆是全局可访问的。也有缺点。某些函数可能会释放此内存，但其他地方也可能存在一些引用。
如果堆内存在它的工作完成后没有被释放并且程序继续分配更多内存，在某些时候 HEAP 将 运行 内存不足并影响程序的确定性。
如前所述，评论不正确。
使用具有非确定性 行为的堆管理器创建具有非确定性行为的程序。但这是显而易见的。
不太明显的是具有确定性行为的堆管理器的存在。也许最著名的例子是池分配器。它有一个 N*M 字节的数组，和一个 N 位的 available[] 掩码。为了分配，它检查第一个可用条目（位测试，O(N)，确定性上限）。要解除分配，它会设置可用位 (O(1))。 malloc(X) 会将 X 舍入到 M 的下一个最大值以选择正确的池。
这可能不是很有效，尤其是当您选择的 N 和 M 太高时。如果您选择的太低，您的程序可能会失败。但是 N 和 M 的限制可能低于没有动态内存分配的等效程序。
在硬实时软件中使用堆的问题是堆分配可能会失败。当你 运行 堆满时你会做什么？
您正在谈论 space 个应用程序。您有非常严格的不失败要求。你必须没有内存泄漏的可能性，所以至少安全模式代码是不够的 运行。你不能摔倒。您不得抛出没有 catch 块的异常。您可能没有带受保护内存的 OS，因此理论上一个崩溃的应用程序可以清除所有内容。
您可能根本不想使用堆。收益不会超过整个计划的成本。
非确定性通常意味着其他含义，但在这种情况下，最好的解读是他们希望整个程序的行为完全可预测。
即使您的堆分配器具有可重复的行为（相同的分配序列和自由调用产生相同的块序列，因此（希望）相同的内部堆状态），如果调用顺序发生变化，可能导致碎片化，从而以不可预测的方式导致内存分配失败。
堆分配在嵌入式系统中被彻底禁止的原因是不受欢迎的，尤其是。飞机或航天器制导或生命支持系统等关键任务系统无法测试响应本质上异步事件而发生的 malloc/free 调用序列中的所有可能变化。
解决方案是为每个处理程序预留一个内存用于其用途，并且这些处理程序的调用顺序不再重要（至少就内存使用而言）。
tl;dr：并不是说动态内存分配本质上是 非确定性的 （正如您根据相同的执行路径定义的那样）；就是它通常会使您的程序不可预测。具体来说，您无法预测分配器是否会在面对任意输入序列时失败。
您可能有一个非确定性分配器。这实际上在您的实时世界之外很常见，在实时世界中，操作系统使用诸如地址布局随机化之类的东西。当然，这会使您的程序具有不确定性。
但这不是一个有趣的情况，所以让我们假设一个完全确定的分配器：相同的分配和释放序列总是会在相同的位置产生相同的块，并且这些分配和释放总是有一个有界的运行宁时间.
现在您的程序可以是确定性的：相同的输入集将导致完全相同的执行路径。
问题在于，如果您根据输入分配和释放内存，则无法预测分配是否会失败（失败不是一种选择）。
首先，您的程序可能会泄漏内存。因此，如果它需要无限期地运行，最终分配将失败。
但是即使您可以证明没有泄漏，您也需要知道永远不会有输入序列需要比可用内存更多的内存。
但即使您可以证明程序永远不会需要比可用内存更多的内存，分配器也可能根据分配和释放的顺序产生内存碎片，因此最终无法找到一个连续的块来满足分配，即使总体上有足够的可用内存。
很难证明不存在会导致病态碎片化的输入序列。
您可以设计分配器以保证不会出现碎片（例如，通过仅分配一种大小的块），但这对调用者施加了很大的限制，并且可能会由于浪费而增加所需的内存量.并且调用者仍然必须证明没有泄漏，并且无论输入顺序如何，所需的总内存都有一个可满足的上限。这个负担太重了，其实把系统设计成不使用动态内存分配更简单。
简答
对数据值或其统计不确定性分布有一些影响，例如，第一级或第二级触发闪烁器设备可能源自您可能必须等待的不可重现的时间量malloc/free.
最糟糕的方面是，它们与硬件的物理现象无关，但与内存状态（及其历史）有某种关系。
在这种情况下，您的目标是根据受这些错误影响的数据重建事件的原始序列。 reconstructed/guessed 序列也会受到错误的影响。这种迭代并不总是会收敛于一个稳定的解决方案；并不是说这将是正确的；您的数据不再独立...您冒着逻辑短路...
的风险更长的答案
您说 "I wasn't able to verify the correctness of this statement when people tell me that"。
我会尽量给你一个纯假设的情况/案例研究。
让我们假设您在必须节约资源的系统上处理 CCD 或一些第一级和第二级闪烁体触发器（您在 space）。
将设置采集速率，使背景位于 MAXBINCOUNT 的 x%。
突然出现，计数出现尖峰，垃圾箱计数器溢出。
我想要这一切：你切换到最大采集率并完成你的缓冲区。
在完成额外缓冲区的同时，您使用了 free/allocate 更多内存。
你会怎么做？- 你将保持反作用冒着溢出的风险（第二级将尝试正确计算数据包的时间）但在这种情况下，你将转到低估了那个时期的计数？
- 你会停止计数器在时间序列中引入一个漏洞？
注意：
- 等待分配，您将丢失 transient（或至少它的开头）。
- 无论你做什么，都取决于你的记忆状态，而且是不可重现的。
现在，信号在
maxbincount附近以硬件允许的最大采集速率变化，并且事件比平时更长。
您完成了 space 并要求更多...同时，您遇到了上述相同的问题。
溢出和系统峰值计数低估或时间序列中的漏洞？
让我们移动第二层（它也可以在第一层触发）。
您从您的硬件接收到的数据多于您可以存储或传输的数据。
您必须及时对数据进行聚类或 space（2x2、4x4、... 16x16 ... 256x256... 像素缩放...）。
上一个问题的不确定性可能会影响误差分布。
有 CCD 设置，您的边框像素计数接近 maxbincount（这取决于 "where"，您希望看得更清楚）。
现在，您可以在 CCD 或单个大点上淋浴，总计数相同但统计不确定性不同（等待时间引入的部分）...
因此，例如，在您期望洛伦兹分布的地方，您可以获得其与高斯分布（Voigt）的卷积，或者如果第二个它确实占主导地位 脏 高斯分布...
从 GHS 引入 Integrity RTOS：
https://www.ghs.com/products/rtos/integrity.html
和 LynxOS：
LynxOS 和 Integrity RTOS 是 space 应用程序、导弹、飞机等使用的软件之一，因为许多其他软件未经当局（例如美国联邦航空局）批准或认证。
https://www.ghs.com/news/230210r.html
为了满足 space 应用程序的严格标准，Integrity RTOS 实际上提供形式验证，即数学证明逻辑，其软件的行为符合规范。
在这些标准中，引用自这里：
https://en.wikipedia.org/wiki/Integrity_(operating_system)
这里：
Green Hills Integrity Dynamic memory allocation
这是：
我不是形式化方法方面的专家，但也许这种验证的要求之一是消除内存分配所需时序的不确定性。在 RTOS 中，所有事件都精确地计划为彼此相距几毫秒。而且动态内存分配总是有时间要求的问题。
从数学上讲，您确实需要根据有关时序和内存量的最基本假设来证明一切正常。
如果您想到堆内存的替代方案：静态内存。地址是固定的，分配的大小也是固定的。在内存中的位置是固定的。因此很容易推断出内存充足性、可靠性、可用性等。