The*_*ist 74 c c++ deterministic real-time non-deterministic
几个月前,我开始在C中开发用于空间应用的实时系统软件,以及用于C++的微控制器.在这样的系统中有一个经验法则,即永远不应该创建堆对象(因此没有malloc/new),因为它使程序不确定.当人们告诉我时,我无法验证此声明的正确性.那么,这是正确的陈述吗？
对我来说困惑的是,据我所知,确定性意味着两次运行程序将导致完全相同的执行路径.根据我的理解,这是多线程系统的一个问题,因为多次运行相同的程序可能每次都以不同的顺序运行不同的线程.
Pet*_*ter 72
在实时系统的背景下,确定性比可重复的"执行路径"更多.另一个必需的属性是关键事件的时间有限.在硬实时系统中,在其允许的时间间隔之外(在该间隔开始之前或在结束之后)发生的事件表示系统故障.
在这种情况下,动态内存分配的使用可能导致非确定性,特别是如果程序具有分配,解除分配和重新分配的变化模式.分配,解除分配和重新分配的时间可能会随着时间的推移而变化 - 因此整个系统的时间安排是不可预测的.
MSa*_*ers 39
如上所述,评论不正确.
使用具有非确定性行为的堆管理器会创建具有非确定性行为的程序.但这很明显.
具有确定性行为的堆管理器的存在稍微不那么明显.也许最着名的例子是池分配器.它有一个N*M字节的数组和一个available[]N位的掩码.要分配,它会检查第一个可用条目(位测试,O(N),确定性上限).要解除分配,它会设置可用位(O(1)).malloc(X)将X舍入到M的下一个最大值,以选择合适的池.
这可能效率不高,特别是如果你选择的N和M太高了.如果选择太低,您的程序可能会失败.但是N和M的限制可能低于没有动态内存分配的等效程序.
Bas*_*tch 21
C11标准或n1570中没有任何内容表明它malloc是确定性的(或不是); 在Linux上也没有像malloc(3)这样的其他文档.顺便说一下,许多malloc实现都是免费软件.
但是malloc可以(并且确实)失败,并且其性能未知(malloc在我的桌面上的典型调用实际上将花费不到一微秒,但我可以想象它可能需要更多的奇怪情况,也许在非常负载的情况下可能需要几毫秒计算机;阅读有关颠簸的内容.我的Linux桌面具有ASLR(地址空间布局随机化),因此运行相同的程序两次会产生不同的malloc地址(在进程的虚拟地址空间中).BTW 在这里是一个确定性的(在具体的假设下你需要详细说明)但实际上是无用的malloc实现.
确定性意味着两次运行程序将导致完全相同的执行路径
这在大多数嵌入式系统中实际上是错误的,因为物理环境正在发生变化; 例如,驱动火箭发动机的软件不能指望从一次发射到下一次发射的推力,阻力或风速等完全相同.
(所以我很惊讶你相信或希望实时系统是确定性的;它们永远不会!也许你关心WCET,因为缓存越来越难以预测)
BTW一些"实时"或"嵌入式"系统正在实现自己的malloc(或其某些变体).C++程序可以有自己的分配器,可以由标准容器使用.另见这个和那个,等等.....
嵌入式软件的高级层次(想想自动汽车及其规划软件)当然使用堆分配甚至垃圾收集技术(其中一些是"实时"),但通常不被认为是安全关键.
Adr*_*thy 12
tl; dr:动态内存分配本质上不是非确定性的(正如你根据相同的执行路径定义的那样); 它通常会使您的程序无法预测.具体来说,您无法预测分配器是否可能在任意输入序列面前失败.
你可能有一个非确定性的分配器.这实际上是在您的实时世界之外,操作系统使用地址布局随机化等内容.当然,这会使你的程序不确定.
但是,这不是一个有趣的例子,让我们假设一个完美确定性分配:分配和释放相同的顺序将总是导致在相同的位置和那些分配和释放相同的块将永远有一个限定的运行时间.
现在你的程序可以是确定性的:同一组输入将导致完全相同的执行路径.
问题是,如果您为响应输入分配和释放内存,则无法预测分配是否会失败(并且失败不是一种选择).
首先,您的程序可能会泄漏内存.因此,如果它需要无限期运行,最终分配将失败.
但即使你可以证明没有泄漏,你也需要知道从来没有一个输入序列可能需要更多的内存.
但即使您可以证明程序永远不会需要比可用内存更多的内存,分配器可能会根据分配和释放的顺序,分段内存,从而最终无法找到一个连续的块来满足分配,即使整体上有足够的可用内存.
很难证明没有任何输入序列会导致病理性碎片化.
您可以设计分配器以保证不会出现碎片(例如,通过分配仅一个大小的块),但这会给调用者带来很大的限制,并可能因浪费而增加所需的内存量.并且调用者必须仍然证明没有泄漏,并且无论输入顺序如何,都需要总存储器的上限.这种负担是如此之高,以至于设计系统实际上更简单,因此它不使用动态内存分配.
use*_*670 10
与实时系统的交易是程序必须严格满足某些计算和内存限制,而不管所采用的执行路径(根据输入可能仍然有很大差异).那么在这种情况下使用通用动态内存分配(例如malloc/new)意味着什么呢？这意味着开发人员在某些时候无法确定确切的内存消耗,并且无法确定生成的程序是否能够满足内存和计算能力的要求.
是的,这是对的.对于您提到的应用程序类型,必须详细说明可能发生的所有事情.该程序必须根据规范处理最坏情况,并准确地留出那么多内存,不多也不少."我们不知道我们得到多少输入"的情况不存在.最坏情况是用固定数字指定的.
从某种意义上说,你的程序必须是确定性的,它可以处理所有情况,直到最坏的情况.
堆的目的是允许几个不相关的应用程序共享RAM内存,例如在PC中,其中运行的程序/进程/线程的数量不确定.实时系统中不存在此方案.
此外,堆的性质是非确定性的,因为段随着时间的推移会被添加或删除.
更多信息:https://electronics.stackexchange.com/a/171581/6102
即使您的堆分配器具有可重复的行为(相同的分配序列和空闲调用产生相同的块序列,因此(希望)具有相同的内部堆状态),如果调用序列发生更改,堆的状态可能会发生很大变化,可能导致碎片,以不可预测的方式导致内存分配失败.
堆积分配在嵌入式系统中被禁止使用的原因,尤其是 飞行器或航天器引导或生命支持系统等关键任务系统无法测试malloc/free调用序列中可能发生的所有可能的变化,以响应本质异步事件.
解决方案是让每个处理程序为其目的留出一个内存,并且不再重要(至少就内存使用而言)这些处理程序的调用顺序.