💕 👨‍🎤 🙅🏿 Memória dinâmica em sistemas rígidos em tempo real ✳️ 🏇🏿 👋🏻

Há uma classe de aplicativos em tempo real para os quais é difícil prever a necessidade de alocação de memória em tempo de execução estaticamente. Essa classe inclui, por exemplo, implementações incorporadas das pilhas de alguns protocolos de comunicação, em que o comportamento e a distribuição de recursos são determinados em parte pela atividade de outros agentes na rede. A abordagem clássica nesses casos é usar gerenciadores de memória de bloco que alocam fragmentos de tamanho fixo (como foi feito, por exemplo, no LwIP). Essa abordagem impõe restrições funcionais e de qualidade indesejáveis à implementação. Neste artigo, proponho o ponto de vista de que os alocadores tradicionais (sem blocos) são imerecidamente privados da atenção dos desenvolvedores de sistemas em tempo real, compartilho meus pensamentos sobre questões relevantes, queixo-me da vida,e proponho melhorar a situação.

Tamanho do heap (H) em função do pico de demanda do aplicativo na memória dinâmica (M) e do tamanho máximo do fragmento alocado (n)
(KDPV - veja a anotação no diagrama no final)

A não-obviedade das propriedades dos algoritmos de alocação de memória dinâmica criou uma tendência perturbadora para uma ligeira distorção da realidade na documentação de alguns RTOS, e não o último golpe. Por exemplo, a seção de gerenciamento de memória do FreeRTOS ignora a classe de alocadores de complexidade computacional constante O (1) , forçando um colega inexperiente a aceitar que O (n) é um teto teórico. Artefatos semelhantes estão na documentação do 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". .

Memória dinâmica em sistemas rígidos em tempo real

More articles: