الذاكرة الديناميكية في أنظمة الوقت الحقيقي الصعبة

هناك فئة من التطبيقات في الوقت الفعلي يصعب عليها التنبؤ بالحاجة إلى تخصيص الذاكرة في وقت التشغيل بشكل ثابت. تتضمن هذه الفئة ، على سبيل المثال ، تطبيقات مدمجة لمكدسات بعض بروتوكولات الاتصال ، حيث يتم تحديد سلوك وتوزيع الموارد جزئيًا من خلال نشاط وكلاء آخرين على الشبكة. النهج الكلاسيكي في مثل هذه الحالات هو استخدام مديري ذاكرة كتلة تخصيص أجزاء من حجم ثابت (كما تم ، على سبيل المثال ، في LwIP). يفرض هذا النهج قيود وظيفية وجودة غير مرغوب فيها على التنفيذ. في هذه المقالة ، أقترح وجهة نظر مفادها أن الموزعين التقليديين (غير المحظورين) محرومون بشكل غير مستحق من انتباه مطوري الأنظمة في الوقت الفعلي ، وأشارك أفكاري في القضايا ذات الصلة ، وأشكو من الحياة ،وأقترح تحسين الوضع.

(KDPV - انظر التعليق على الرسم التخطيطي في النهاية)

خلقت عدم وضوح خصائص خوارزميات تخصيص الذاكرة الديناميكية نزعة مثيرة للقلق تجاه تشويه طفيف للواقع في توثيق بعض RTOS ، وليس الضربة الأخيرة. على سبيل المثال ، يتجاوز قسم إدارة الذاكرة FreeRTOS فئة الموزعين ذوي التعقيد الحسابي المستمر O (1) ، مما يجبر زميلًا عديم الخبرة على قبول أن O (n) هو سقف نظري. التحف مماثلة في وثائق 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". .