C Academy · درس

قوائم الذاكرة الحرة وإعادة الاستخدام

تتبّع الكتل وأعد استخدامها

قوائم الذاكرة الحرة وإعادة الاستخدام درس مجاني في C Academy على CoddyKit. هذا هو الدرس 3 من أصل 4. يمكنك قراءة الدرس كاملاً أدناه مجاناً — ثم تمرن عليه مباشرة في المتصفح باستخدام محرر أكواد مدمج ومدرس ذكاء اصطناعي متاح 24/7. هذا الدرس جزء من مسار التعلم في C Academy، وتقدمك يتزامن عبر الويب وتطبيق CoddyKit. تتضمن دورة C Academy 4 دروس في المجموع.

ما بعد مخصّص الزيادة التدريجية

لتحرير الكتل الفردية وإعادة استخدامها، نحتاج إلى حفظ معلومات إدارية. والقائمة الحرة هي قائمة مترابطة من الكتل المتاحة، يبحث فيها المخصّص قبل الحصول على ذاكرة جديدة.

تحمل كل كتلة ترويسةً تتيح للمخصّص معرفة حجمها وربطها بالكتلة التالية في السلسلة.

ترويسة كتلة مع رابط

نوسّع الترويسة بإضافة مؤشر next وراية free. ويحوّل هذان العنصران المجمّعَ إلى قائمة كتل يمكن التنقّل فيها.

وتأتي الحمولة مباشرةً بعد الترويسة في الذاكرة.

typedef struct block {
    size_t size;          /* payload bytes */
    int free;             /* 1 if reusable */
    struct block *next;   /* next block in pool */
} block_t;

تهيئة كتلة حرة واحدة كبيرة

عند بدء التشغيل، يكون المجمّع بأكمله كتلة حرة ضخمة واحدة. ومع حدوث عمليات التخصيص نقسمها، ومع حدوث عمليات التحرير نضع علامة على الكتل لتصبح قابلة لإعادة الاستخدام.

ورأس القائمة هو هذه الكتلة الأولية التي تغطي الساحة بأكملها.

static unsigned char pool[4096];
static block_t *head;

void heap_init(void) {
    head = (block_t *)pool;
    head->size = sizeof(pool) - sizeof(block_t);
    head->free = 1;
    head->next = NULL;
}

بحث الملاءمة الأولى

أبسط استراتيجية لإعادة الاستخدام هي الملاءمة الأولى: نسير عبر القائمة ونعيد أول كتلة حرة كبيرة بما يكفي. وتتميز هذه الطريقة بالسرعة، وتميل إلى إبقاء الكتل الصغيرة قرب المقدمة.

ومن البدائل الملاءمة الأفضل (أصغر كتلة كافية) والملاءمة الأسوأ، مع المفاضلة بين السرعة وسلوك التجزئة.

block_t *first_fit(size_t size) {
    for (block_t *b = head; b; b = b->next)
        if (b->free && b->size >= size)
            return b;
    return NULL;
}

التخصيص من كتلة حرة

بعد العثور على كتلة مناسبة، نضع علامة على أنها مستخدمة ونعيد المؤشر الواقع مباشرةً بعد ترويسـتها. وفي الوقت الحالي نسلّم الكتلة بأكملها؛ أما التقسيم فسنتناوله في الدرس التالي.

المؤشر المُرجع هو block + 1، مما يخفي الترويسة عن الجهة المستدعية.

void *my_alloc(size_t size) {
    block_t *b = first_fit(size);
    if (!b) return NULL;
    b->free = 0;
    return (void *)(b + 1);
}

تحرير كتلة

للتحرير، نرجع خطوة من مؤشر المستخدم إلى ترويسـة الكتلة ونبدّل راية التحرير. وبذلك تصبح الكتلة مؤهلة لإعادة الاستخدام في البحث التالي.

واستعادة الترويسة من الحمولة هي حيلة المؤشر ذات الخطوة الواحدة التي رأيناها سابقًا.

void my_free(void *p) {
    if (!p) return;
    block_t *b = (block_t *)p - 1;
    b->free = 1;
}

دمج الكتل الحرة المتجاورة

يترك التحرير وحده المجمّع ممتلئًا بكتل حرة صغيرة. يدمج الدمج الكتلة المحررة مع الكتلة التالية إذا كانت حرة أيضًا، فيعيد بناء مناطق متجاورة أكبر.

ويكافح ذلك التجزئة الخارجية، بحيث تظل الطلبات الكبيرة المستقبلية قابلة للتلبية.

void coalesce(block_t *b) {
    if (b->next && b->next->free) {
        b->size += sizeof(block_t) + b->next->size;
        b->next = b->next->next;
    }
}

عرض توضيحي قابل للتشغيل لقائمة الكتل الحرة

يهيّئ هذا البرنامج الكامل مجمّعًا، ويخصّص كتلتين، ويحرر الأولى، ثم يعيد استخدامها لطلب أصغر، مما يثبت عمل القائمة الحرة.

#include <stdio.h>
#include <stddef.h>

typedef struct block { size_t size; int free; struct block *next; } block_t;
static unsigned char pool[1024];
static block_t *head;

void heap_init(void){ head=(block_t*)pool; head->size=sizeof(pool)-sizeof(block_t); head->free=1; head->next=NULL; }
block_t *first_fit(size_t s){ for(block_t *b=head;b;b=b->next) if(b->free&&b->size>=s) return b; return NULL; }
void *my_alloc(size_t s){ block_t *b=first_fit(s); if(!b) return NULL; b->free=0; return (void*)(b+1); }
void my_free(void *p){ if(!p) return; ((block_t*)p-1)->free=1; }

int main(void){
    heap_init();
    int *a = my_alloc(sizeof(int));
    *a = 7;
    printf("a=%d free=%d\n", *a, head->free);
    my_free(a);
    printf("after free: free=%d\n", head->free);
    return 0;
}

كلفة البحث

تعني القائمة الحرة المترابطة ذات الاتجاه الواحد أن التخصيص يعمل بتعقيد O(n) بالنسبة إلى عدد الكتل. ومع كثرة عمليات التخصيص، يصبح ذلك بطيئًا.

تستخدم المخصّصات الفعلية قوائم حرة منفصلة (حاويات حسب الحجم) أو أشجارًا لجعل البحث قريبًا من O(1). ويظل مبدأ إعادة الاستخدام نفسه.

/* Segregated lists: one bucket per size class */
static block_t *bins[NUM_SIZE_CLASSES];
/* lookup goes straight to the right bucket */

التحرير المزدوج والتلف

إن وضع علامة التحرير على كتلة مرتين، أو الكتابة بعد حجم الكتلة، يؤدي إلى إتلاف الترويسات المجاورة. وعندئذ يتبع البحث التالي مؤشر next تالفًا ويتسبب في انهيار البرنامج.

ولهذا تكون أخطاء الذاكرة في C خطيرة جدًا: فبيانات المخصّص الوصفية نفسها توجد بمحاذاة بياناتكم مباشرةً.

جمع عناصر إعادة الاستخدام

يحتاج مخصّص القائمة الحرة العامل إلى التهيئة، واستراتيجية ملاءمة، وعمليات التخصيص والتحرير والدمج. وبفضل هذه العناصر، تدور الذاكرة عبر المجمّع بدلًا من أن تنمو بلا نهاية.

والتحسين المتبقي هو تقسيم الكتل الأكبر من المطلوب واحترام المحاذاة، وهو موضوع الدرس الأخير.

تحقّق سريع

فكّروا في ما يمنع القائمة الحرة من التجزؤ بشكل سيئ.

مراجعة

تربط القائمة الحرة الكتلَ عبر ترويسات، بحيث يمكن تحرير التخصيصات الفردية وإعادة استخدامها. يعثر بحث الملاءمة الأولى على كتلة، ويبدّل التحرير رايةً، ويدمج الدمج الكتل المتجاورة لمكافحة التجزئة.

يعمل البحث الخطي بتعقيد O(n)، أما المخصّصات الإنتاجية فتقسم الكتل إلى حاويات حسب الحجم لتحقيق السرعة. وسنضيف لاحقًا التقسيم والمحاذاة.

الأسئلة الشائعة

هل درس «قوائم الذاكرة الحرة وإعادة الاستخدام» مجاني؟

نعم — نص درس «قوائم الذاكرة الحرة وإعادة الاستخدام» كامل متاح مجاناً هنا على الويب. لتمرينه بشكل تفاعلي (محرر أكواد مدمج ومدرس ذكاء اصطناعي متاح 24/7) وفتح باقي دورة C Academy، انتقل إلى CoddyKit PRO. تتضمن دورة C Academy 4 دروس في المجموع.

ماذا ستتعلم في «قوائم الذاكرة الحرة وإعادة الاستخدام»؟

تتبّع الكتل وأعد استخدامها تتمرن على C Academy مع أكواد عملية تشغلها مباشرة في المتصفح، ومدرس ذكاء اصطناعي متاح 24/7 يجيب على أسئلتك أثناء عملك.

هل أحتاج إلى خبرة سابقة لأبدأ C Academy؟

لا تُشترط خبرة سابقة. C Academy على CoddyKit منظم للمبتدئين حتى المتقدمين، لذا يمكنك البدء من هنا أو من البداية والتقدم بسرعتك الخاصة. هذا هو الدرس 3 من أصل 4.

كم من الوقت يستغرق درس «قوائم الذاكرة الحرة وإعادة الاستخدام»؟

معظم دروس CoddyKit تستغرق حوالي 5–10 دقائق. كل منها موجز وتفاعلي، لذا تحرز تقدماً مستمراً وتستأنف من حيث توقفت عبر الويب والتطبيق.

هل يمكنني كتابة وتشغيل أكواد في درس C Academy هذا؟

نعم. كل درس في C Academy يتضمن محرر أكواد مدمج، لذا تكتب وتشغل أكواداً حقيقية مباشرة في متصفحك وتحصل على تعليقات فورية من الذكاء الاصطناعي — بدون إعداد محلي.

جميع الدروس في هذه الدورة

كيف تعمل malloc
مخصّص Bump بسيط
قوائم الذاكرة الحرة وإعادة الاستخدام
المحاذاة والتقسيم

← العودة إلى C Academy