🛄 🎿 🎢 Dynamic memory in hard real-time systems 🔽 🖐️ 👩‍🚀

There is a class of real-time applications for which it is difficult to predict the need for memory allocation at run time statically. This class includes, for example, embedded implementations of the stacks of some communication protocols, where the behavior and distribution of resources is determined in part by the activity of other agents on the network. The classic approach in such cases is to use block memory managers that allocate fragments of a fixed size (as was done, for example, in LwIP). This approach imposes undesirable functional and quality constraints on implementation. In this article, I propose the point of view that traditional (non-blocky) allocators are undeservedly deprived of the attention of developers of real-time systems, I share my thoughts on relevant issues, I complain about life,and I propose to improve the situation.

Heap size (H) as a function of the peak demand of the application in dynamic memory (M) and the maximum size of the allocated fragment (n)
(KDPV - see the annotation to the diagram at the end)

The non-obviousness of the properties of dynamic memory allocation algorithms has created a troubling tendency toward a slight distortion of reality in the documentation of some RTOS, and not the last hit. For example, the FreeRTOS memory management section bypasses the class of allocators of constant computational complexity O (1) , forcing an inexperienced colleague to accept that O (n) is a theoretical ceiling. Similar artifacts are in the documentation for 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 + ⌈ \log_{2} n ⌉)

$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". .

Dynamic memory in hard real-time systems

More articles: