Memoria dinámica en sistemas duros en tiempo real

Hay una clase de aplicaciones en tiempo real para las que es difícil predecir la necesidad de asignación de memoria en tiempo de ejecución estáticamente. Esta clase incluye, por ejemplo, implementaciones integradas de las pilas de algunos protocolos de comunicación, donde el comportamiento y la distribución de recursos están determinados en parte por la actividad de otros agentes en la red. El enfoque clásico en tales casos es usar administradores de memoria de bloque que asignen fragmentos de un tamaño fijo (como se hizo, por ejemplo, en LwIP). Este enfoque impone restricciones funcionales y de calidad indeseables en la implementación. En este artículo, propongo el punto de vista de que los asignadores tradicionales (sin bloques) se ven privados de la atención de los desarrolladores de sistemas en tiempo real, comparto mis pensamientos sobre temas relevantes, me quejo de la vida,y propongo mejorar la situación.

(KDPV - ver la anotación del diagrama al final)

La no evidencia de las propiedades de los algoritmos de asignación dinámica de memoria ha creado una tendencia inquietante hacia una ligera distorsión de la realidad en la documentación de algunos RTOS, y no el último golpe. Por ejemplo, la sección de administración de memoria FreeRTOS omite la clase de asignadores de complejidad computacional constante O (1) , obligando a un colega inexperto a aceptar que O (n) es un techo teórico. Artefactos similares están en la documentación para 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". .