कठिन वास्तविक समय प्रणालियों में गतिशील मेमोरी

वास्तविक समय के अनुप्रयोगों का एक वर्ग है, जिसके लिए रन समय पर स्मृति आवंटन की आवश्यकता का अनुमान लगाना मुश्किल है। इस वर्ग में, उदाहरण के लिए, कुछ संचार प्रोटोकॉल के ढेर के एम्बेडेड कार्यान्वयन शामिल हैं, जहां संसाधनों का व्यवहार और वितरण नेटवर्क पर अन्य एजेंटों की गतिविधि द्वारा भाग में निर्धारित किया जाता है। ऐसे मामलों में क्लासिक दृष्टिकोण ब्लॉक मेमोरी प्रबंधकों का उपयोग करना है जो एक निश्चित आकार के टुकड़े आवंटित करते हैं (जैसा कि किया गया था, उदाहरण के लिए, LwIP में)। यह दृष्टिकोण कार्यान्वयन पर अवांछनीय कार्यात्मक और गुणवत्ता संबंधी बाधाओं को लागू करता है। इस अनुच्छेद में, मैं इस दृष्टिकोण का प्रस्ताव करता हूं कि पारंपरिक (गैर-अवरोधक) आवंटनकर्ता वास्तविक समय प्रणालियों के डेवलपर्स के ध्यान से अवांछनीय रूप से वंचित हैं, मैं प्रासंगिक मुद्दों पर अपने विचार साझा करता हूं, मैं जीवन के बारे में शिकायत करता हूं,और मैं स्थिति को सुधारने का प्रस्ताव देता हूं।

(केडीपीवी - अंत में चित्र के लिए एनोटेशन देखें)

गतिशील मेमोरी आवंटन एल्गोरिदम के गुणों की गैर-स्पष्टता ने कुछ RTOS के दस्तावेज़ीकरण में वास्तविकता की थोड़ी विकृति की ओर एक परेशान प्रवृत्ति पैदा की है, न कि आखिरी हिट। उदाहरण के लिए, FreeRTOS मेमोरी प्रबंधन अनुभाग निरंतर कम्प्यूटेशनल जटिलता ओ (1) के आवंटनकर्ताओं के वर्ग को बायपास करता है , एक अनुभवहीन सहयोगी को यह स्वीकार करने के लिए मजबूर करता है कि O (n) एक सैद्धांतिक छत है। इसी तरह की कलाकृतियाँ चिबिओस ( 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". .