Memori dinamis dalam sistem waktu nyata yang sulit

Ada kelas aplikasi real-time yang sulit untuk memprediksi kebutuhan alokasi memori pada saat dijalankan secara statis. Kelas ini mencakup, misalnya, implementasi tertanam dari tumpukan beberapa protokol komunikasi, di mana perilaku dan distribusi sumber daya ditentukan sebagian oleh aktivitas agen lain di jaringan. Pendekatan klasik dalam kasus tersebut adalah dengan menggunakan manajer memori blok yang mengalokasikan fragmen dari ukuran tetap (seperti yang dilakukan, misalnya, di LwIP). Pendekatan ini memberikan batasan fungsional dan kualitas yang tidak diinginkan pada implementasi. Dalam artikel ini, saya mengusulkan sudut pandang bahwa pengalokasi tradisional (non-blok) secara tidak layak kehilangan perhatian pengembang sistem waktu-nyata, saya berbagi pemikiran saya tentang masalah yang relevan, saya mengeluh tentang kehidupan,dan saya mengusulkan untuk memperbaiki situasi.

(KDPV - lihat penjelasan diagram di akhir)

Ketidakjelasan sifat-sifat algoritma alokasi memori dinamis telah menciptakan kecenderungan yang mengganggu terhadap sedikit distorsi realitas dalam dokumentasi beberapa RTOS, dan bukan pukulan terakhir. Sebagai contoh, bagian manajemen memori FreeRTOS memotong kelas pengalokasi kompleksitas komputasi konstan O (1) , memaksa kolega yang tidak berpengalaman untuk menerima bahwa O (n) adalah langit-langit teoretis. Artefak serupa ada dalam dokumentasi untuk 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". .