خوارزمية تشيني

الموسوعة الحرة

خوارزمية تشيني ، التي وُصفت لأول مرة في ورقة بحثية نُشرت عام 1970 في مجلة ACM بقلم سي جيه تشيني، هي طريقة إيقاف ونسخ لتتبع عملية جمع البيانات المهملة في أنظمة برمجيات الحاسوب. في هذه الطريقة، تُقسّم الذاكرة المخصصة (heap) إلى نصفين متساويين، يُستخدم أحدهما فقط في أي وقت. يتم جمع البيانات المهملة بنسخ الكائنات النشطة من نصف مساحة الذاكرة (مساحة المصدر) إلى النصف الآخر (مساحة الوجهة)، الذي يُصبح بدوره الذاكرة المخصصة الجديدة. ثم تُحذف الذاكرة المخصصة القديمة بالكامل دفعة واحدة. تُعد هذه الخوارزمية تحسينًا لتقنية الإيقاف والنسخ السابقة.

تستعيد خوارزمية تشيني العناصر على النحو التالي:

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

بمجرد فحص جميع مراجع الفضاء وتحديثها، تكتمل عملية جمع البيانات المهملة.

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

يتم استخدام مؤشر التوجيه (الذي يسمى أحيانًا "القلب المكسور") فقط أثناء عملية جمع البيانات المهملة؛ فعندما يتم العثور على مرجع لكائن موجود بالفعل في مساحة to (وبالتالي يحتوي على مؤشر توجيه في مساحة from)، يمكن تحديث المرجع بسرعة ببساطة عن طريق تحديث مؤشره ليطابق مؤشر التوجيه.

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

شبه الفضاء

استند تشيني في عمله على جامع القمامة شبه الفضائي ، الذي نشره قبل عام من قبل آر آر فينيشيل وجيه سي يوشيلسون.

مكافئ للتجريد ثلاثي الألوان

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

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

عندما يصل مؤشر المسح إلى مؤشر المساحة الحرة، تصبح المجموعة الرمادية فارغة، وتنتهي الخوارزمية.

مراجع