ما هي القائمة الحرة؟

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

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

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

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

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

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