请教：确定性 vs. 动态堆内存管理

bluelucky

我在研究了几种堆管理机制后，除了块池之外(一次只允许拿一个块，因此用双向链表来分配），字节池（一次可分配任意连续字节）和页池（类似字节池，一次可分配任意个连续页），都不可避免地存在“遍历数据结构”的操作，这无疑会是确定性的天敌。因为在被遍历的数据结构中，元素的数量可以在巨大的范围内变化，如1-100是很正常的事。
    后来我又想了想，觉得在多数情况下，当响应高确定性要求的任务时，也就是在响应死线很紧的硬实时任务时，不会进行内存的动态申请与回收操作，这些操作通常都是在准备工作中完成，此时即使有硬实时要求，也都很宽松。因此，在构建堆管理系统时，可以把平均性能放在首位，而不必过分地拿确定性说事儿。
    大家觉得这种看法有道理吗？
    PS: 我正在研究在CM3中优化页池分配算法的可能性

yyccaa

原本高实时要求下，就不该运行中动态分配，因为除了时间不确定，还会面对分配失败的处理。
至于说到遍历链表的时间，这其实取决于处理链表或树的算法的复杂度（数学问题了），比如linux同时使用了链表和红黑树管理内存,以便于按需要使用不同的遍历算法，而红黑树算法很大程度上缩短了查找特定内存块的时间。

stdio

在非通用系统，也即嵌入式系统中，一般只有有限的几种业务在运行，针对这几中特定的业务，量身定制内存管理模式，达到效率最高。
在简单应用中，固定块大小的内存管理方式就足够了，一个单链表，申请和释放都只有几个动作。在多数应用中，设定几个固定块尺寸的单链表，一般也能应付下来。
LINUX的方法已经很复杂了，那是因为LINUX是通用操作系统。

watercat

在确定要求的真实时系统中，根本不应该使用动态内存分配，因为原则上，并不应该有什么情况是编程时无法想到的

不过，如果是伪实时系统或者基于时间片的分时系统，就另当别论了

bluelucky

很多实时应用程序，会在开启调度前就把所有需要的资源创建好，它们应该不需要动态内存管理了。这类应用我想是比较简洁的：功能不复杂，且针对性极强。这种系统的最大内存需要量也不会超过物理内存，因此只使用块池（一次只允许拿一个块），就足够了。块池的分配与回收直接对应链表的头删与尾插操作，都是确定执行时间。

    关键就是页池与字节池，我能想到的可能需要此类动态内存管理的，主要是一些大型点的应用程序。比如，具有网络服务器性质的系统；有n种功能但最多有m个同时打开（n>m），且不同场合下打开的功能不同的系统；需要从文件系统扫描并建立树型结构的系统；需要图形界面以进行人机交互的系统，系统中的非实时任务等。当它们需求的内存最大值超过物理内存，但极少达到最大值时，就需要页池或字节池的管理。比如一个系统最多可能需要256KB内存，但平均只需要20KB，而系统的物理内存是64KB，就需要动态内存管理。

rainyss

不同于嵌入式系统,在单片机上根本就不应该使用纯粹的动态内存分配.你可以使用多个进程共用一个内存块的方式,但随机地分配内存而非有预计性的分配,是做梦.如果能实现,不说明你赢了我,只能说明你又浪费了一回硬件.当然,这个问题仁者见仁.但我始终坚持"单片机,成本第一".咦,好压韵．．．．．．

watercat

【4楼】 bluelucky

        很多实时应用程序，会在开启调度前就把所有需要的资源创建好，它们应该不需要动态内存管理了。这类应用我想是比较简洁的：功能不复杂，且针对性极强。这种系统的最大内存需要量也不会超过物理内存，因此只使用块池（一次只允许拿一个块），就足够了。块池的分配与回收直接对应链表的头删与尾插操作，都是确定执行时间。

    关键就是页池与字节池，我能想到的可能需要此类动态内存管理的，主要是一些大型点的应用程序。比如，具有网络服务器性质的系统；有n种功能但最多有m个同时打开（n>m），且不同场合下打开的功能不同的系统；需要从文件系统扫描并建立树型结构的系统；需要图形界面以进行人机交互的系统，系统中的非实时任务等。当它们需求的内存最大值超过物理内存，但极少达到最大值时，就需要页池或字节池的管理。比如一个系统最多可能需要256KB内存，但平均只需要20KB，而系统的物理内存是64KB，就需要动态内存管理。

======================================

那么就用定长分配或页面分配机制好了

纯粹意义上的动态内存分配，只有和虚拟内存技术结合在一起才有最优化的效率，但那样子你还用什么RTOS？？

bluelucky

我只是在研究过若干流行的rtos后，发现它们几乎都支持这些池，才会想这些动态分配到底有什么用。总之我想正如大家和前辈所见，这种东西应该只是个可以尘封在角落里（除了块池外），偶尔用时再拿出来，或者准备扩展支持虚拟内存的子系统时再用吧（据我所知，VxWorks和T-Kernel都是把虚拟内存当作一个子系统来扩充的，内核本身不支持，但提供强大的子系统扩展接口）。

lllaaa

实时操作系统+VM子系统这个组合相当尴尬啊。

vm一上实时性肯定就得打折扣。需要内存的时候还要产生缺页中断去调页，频繁起来性能就下来了。

既然要确定性就得预先确定好。要么给足内存预先分配好各个业务的内存，要么业务之间互斥。自由度多起来，确定性从何谈起。

bluelucky

在实时系统中，如果大多数任务是非实时的，可以在保证实时任务的基础上，对非实时任务以平均性能优先的原则处理，就可以上很多现代操作系统的特性了。即使上VM，也可以不要启用交换区，只做逻辑地址到物理地址的转换，就不会有缺页的概念了