硬实时系统中的动态内存

对于一类实时应用程序，很难静态地预测运行时对内存分配的需求。此类包括例如某些通信协议堆栈的嵌入式实现，其中资源的行为和分配部分由网络上其他代理的活动确定。在这种情况下，经典的方法是使用分配固定大小的片段的块内存管理器（例如，在LwIP中这样做）。这种方法对实施施加了不希望的功能和质量约束。在本文中，我提出了这样一种观点，即传统的（非块状）分配器理所应当被剥夺了实时系统开发人员的注意力，我分享了有关相关问题的想法，抱怨生活，我建议改善这种情况。

（KDPV-参见最后的图注释）

动态内存分配算法的属性的非显而易见性已在一些RTOS的文档中创造了一种对现实的轻微失​​真的令人不安的趋势，而不是最后的结果。例如，FreeRTOS内存管理部分绕过了具有恒定计算复杂度O（1）的分配器类，从而迫使没有经验的同事接受O（n）是理论上的上限。类似的工件是用于ChibiOS（文档中1，2）当然，我们不会怀疑这种出色产品的开发者对材料的无知；相反，我们将其写成典型的人们的平庸监督。实时应用程序很少在运行时依赖动态分配，因此受影响的很多很小。

熟悉实时系统细节的读者无需解释不是平均值而是最坏情况的特性对它们而言至关重要，这从根本上将它们与通用系统区分开来（后者的一个示例是您现在正在阅读本书的通用系统）。对于其他读者，我举一个例子：如果某种算法在大多数情况下具有渐近复杂度O（log n），但一千年一次 O(n), .

. , , , . , . NuttX, (best fit), . .

, , , , , .

. , , API , . , , :

//     :
struct FragmentedBuffer
{
    struct FragmentedBuffer* next;
    uint8_t data[];
};

// ... :
uint8_t* data;

, Buddy Allocator, Half-Fit, Two-Level Segregated Fit (TLSF). O(1) ( Buddy Allocator , , ). J. Herter J. Robson – , – “Timing-Predictable Memory Allocation In Hard Real-Time Systems” “Worst case fragmentation of first fit and best fit storage allocation strategies”, .

. . , , ( - ) . 26–33 , , H, , :

$$

$$H = 2 M (1 + \lceil{}\log_2 n\rceil{})$$

M – , n – .

. , , . , H = M (n — 2), .

, , () , . , StackOverflow, , . (500 C99/C11), , .

: https://github.com/pavel-kirienko/o1heap.

, . , , , . ; , :

• : H [KiB] M [KiB] n [KiB] 16 .
• : , MiB.

H , , . . H, , , . H , . , . (Embox?), .

. NuttX , , : "I considered porting TLSF at one point, but overall it's low on my list of NuttX improvements I'd explore if I actually had time". .