问使用堆内存(malloc/new)会创建不确定的程序吗？

EN

在实时系统的上下文中，除了可重复的“执行路径”之外，还有更多的确定性。另一个必需的属性是关键事件的计时是有界的。在硬实时系统中，超出其允许的时间间隔(在该时间间隔开始之前或结束之后)发生的事件表示系统故障。

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

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

不太明显的是，存在具有确定性行为的堆管理器。也许最著名的例子是池分配器。它有一个N*M字节的数组和一个N位的available[]掩码。为了进行分配，它检查第一个可用条目(位测试，O(N)，确定性上限)。为了解除分配，它设置可用位(O(1))。malloc(X)会将X四舍五入到M的下一个最大值，以选择正确的池。

这可能效率不是很高，特别是在N和M的选择太高的情况下。如果你选择太低，你的程序可能会失败。但N和M的限制可以低于没有动态内存分配的等效程序。

dr:这并不是说动态内存分配本质上是non-deterministic的(就像您在相同的执行路径中定义的那样)；而是它通常使您的程序成为unpredictable.具体地说，您无法预测分配器在面对任意输入序列时是否会失败。

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

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

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

问题是，如果您正在分配和释放内存以响应输入，则无法预测分配是否会失败(并且失败不是一个选项)。

首先，你的程序可能会泄漏内存。因此，如果它需要无限期运行，最终分配将失败。

但是，即使您可以证明没有泄漏，您也需要知道输入序列永远不会需要超过可用内存的输入序列。

但是，即使您可以证明程序永远不会需要比可用内存更多的内存，分配器也可能会根据分配和释放的顺序，对内存进行分段，从而最终无法找到满足分配要求的连续块，即使总体上有足够的空闲内存。

很难证明没有导致病理性碎片化的输入序列。

你可以设计分配器来保证不会有碎片(例如，通过只分配一种大小的块)，但这会对调用者造成很大的约束，并可能由于浪费而增加所需的内存量。而且调用者仍然必须证明没有泄漏，并且无论输入的顺序如何，所需的总内存都有一个令人满意的上限。这个负担是如此之高，以至于它实际上更容易设计成不使用动态内存分配的系统。