خوارزمية مارك-كومباكت
في علوم الحاسوب ، تُعدّ خوارزمية الوسم والضغط نوعًا من خوارزميات جمع البيانات المهملة ، وتُستخدم لاستعادة الذاكرة غير القابلة للوصول . يمكن اعتبار خوارزميات الوسم والضغط مزيجًا من خوارزمية الوسم والمسح وخوارزمية نسخ تشيني . في البداية، تُوسَم الكائنات القابلة للوصول، ثم تُنقل هذه الكائنات (الموسومة) إلى بداية منطقة الكومة في خطوة ضغط. يُستخدم ضغط جمع البيانات المهملة في آلات جافا الافتراضية الحديثة ، وبيئة تشغيل اللغة المشتركة من مايكروسوفت ، ومترجم غلاسكو هاسكل .
الخوارزميات
بعد وضع علامات على الكائنات النشطة في الذاكرة الديناميكية (heap) بنفس طريقة خوارزمية الوسم والمسح ، غالبًا ما تُجزأ الذاكرة الديناميكية . يهدف خوارزميات الوسم والضغط إلى نقل الكائنات النشطة في الذاكرة معًا للتخلص من التجزئة. يكمن التحدي في تحديث جميع المؤشرات إلى الكائنات المنقولة بشكل صحيح، حيث سيحصل معظمها على عناوين ذاكرة جديدة بعد الضغط. تُعالج مسألة تحديث المؤشرات بطرق مختلفة.
الضغط القائم على الجداول
تم وصف خوارزمية تعتمد على الجداول لأول مرة بواسطة هادون ووايت في عام 1967. [ 1 ] وهي تحافظ على الوضع النسبي للكائنات الحية في الكومة، ولا تتطلب سوى مقدار ثابت من النفقات العامة.
تتم عملية الضغط من أسفل الكومة (العناوين المنخفضة) إلى أعلاها (العناوين العالية). عند مصادفة كائنات نشطة (أي مُعلَّمة)، تُنقل إلى أول عنوان منخفض متاح، ويُضاف سجل إلى جدول معلومات النقل. لكل كائن نشط، يتكون سجل في جدول النقل من عنوان الكائن الأصلي قبل الضغط والفرق بين العنوان الأصلي والعنوان الجديد بعد الضغط. يُخزَّن جدول النقل في الكومة التي يتم ضغطها، ولكن في منطقة مُعلَّمة بأنها غير مستخدمة. لضمان نجاح الضغط دائمًا، يجب أن يكون الحد الأدنى لحجم الكائن في الكومة أكبر من أو مساويًا لحجم سجل جدول النقل.
مع تقدم عملية الضغط، تُنسخ الكائنات المُعاد توجيهها نحو أسفل الكومة. وفي النهاية، سيحتاج أحد الكائنات إلى النسخ إلى المساحة التي يشغلها جدول التوزيع، والذي يجب نقله الآن إلى مكان آخر. تُسبب هذه التحركات لجدول التوزيع (والتي يُطلق عليها المؤلفون اسم " تدوير الجدول ") اضطرابًا في سجلات إعادة التوجيه، مما يستلزم فرز جدول التوزيع بعد اكتمال عملية الضغط. تبلغ تكلفة فرز جدول التوزيع O ( n log n )، حيث n هو عدد الكائنات النشطة التي تم العثور عليها في مرحلة الوسم من الخوارزمية.
أخيرًا، تُستخدم سجلات إعادة توجيه جدول الفواصل لتعديل حقول المؤشرات داخل الكائنات المُعاد توجيهها. تُفحص الكائنات النشطة بحثًا عن المؤشرات، والتي يمكن البحث عنها في جدول الفواصل المُرتب بحجم n في زمن قدره O(log n ) إذا كان جدول الفواصل مُرتبًا، ليصبح إجمالي زمن التشغيل O ( n log n ). ثم تُعدّل المؤشرات بالمقدار المُحدد في جدول إعادة التوجيه.
خوارزمية LISP 2
لتجنب التعقيد الزمني O ( n log n )، تستخدم خوارزمية LISP 2 ثلاث عمليات مسح مختلفة للذاكرة الديناميكية. إضافةً إلى ذلك، يجب أن تحتوي كائنات الذاكرة الديناميكية على خانة مؤشر توجيه منفصلة لا تُستخدم إلا في عملية جمع البيانات المهملة.
بعد وضع العلامات القياسية، تستمر الخوارزمية في المراحل الثلاث التالية:
- احسب موقع إعادة التوجيه للعناصر النشطة.
- احتفظ بمؤشر حر ومؤشر حي وقم بتهيئة كليهما إلى بداية الكومة.
- إذا كان المؤشر الحي يشير إلى كائن حي، فقم بتحديث مؤشر إعادة التوجيه الخاص بهذا الكائن إلى المؤشر الحر الحالي وقم بزيادة المؤشر الحر وفقًا لحجم الكائن.
- انقل المؤشر المباشر إلى الكائن التالي
- ينتهي الأمر عندما يصل المؤشر الحي إلى نهاية الذاكرة المخصصة.
- قم بتحديث جميع المؤشرات
- لكل كائن حي، قم بتحديث مؤشراته وفقًا لمؤشرات إعادة التوجيه للكائنات التي تشير إليها.
- تحريك العناصر
- لكل كائن نشط، انقل بياناته إلى موقع إعادة التوجيه الخاص به.
تتميز هذه الخوارزمية بتعقيد زمني قدره O ( n ) بالنسبة لحجم الكومة؛ فهي أقل تعقيدًا من الطريقة القائمة على الجداول، ولكن قيمة n في الطريقة القائمة على الجداول تمثل حجم المساحة المستخدمة فقط، وليس حجم مساحة الكومة بأكملها كما في خوارزمية LISP2. مع ذلك، تُعد خوارزمية LISP2 أسهل في التنفيذ.
الضاغط
تتميز خوارزمية ضغط الذاكرة Compressor [ 2 ] بأقل تعقيد بين خوارزميات الضغط المعروفة حاليًا. وهي امتداد لخوارزمية جمع البيانات المهملة من IBM للغة Java. [ 3 ] يحتفظ الإصدار التسلسلي من Compressor بخريطة نقل تربط العنوان القديم لكل كائن بعنوانه الجديد (أي، يتم ربط عنوانه قبل الضغط بعنوانه بعده). في المرحلة الأولى، تُحسب هذه الخريطة لجميع الكائنات في الذاكرة الديناميكية. وفي المرحلة الثانية، يُنقل كل كائن إلى موقعه الجديد (يُضغط إلى بداية الذاكرة الديناميكية)، وتُعدَّل جميع المؤشرات داخله وفقًا لخريطة النقل.
يمكن تبسيط حساب خريطة إعادة التوطين في المرحلة الأولى بشكل كبير باستخدام جداول صغيرة لا تتطلب المرور على كامل الذاكرة الرئيسية. هذا يُبقي تعقيد الضاغط منخفضًا، حيث يتضمن مرورًا واحدًا على الجداول الصغيرة ومرارًا واحدًا على الذاكرة الرئيسية بأكملها. وهذا يُمثل أفضل تعقيد معروف لخوارزميات الضغط.
يحتوي برنامج الضغط أيضًا على إصدار متوازٍ، حيث يمكن لعدة خيوط ضغط العمل معًا لضغط جميع الكائنات بالتوازي. كما يحتوي على إصدار متزامن، حيث يمكن لخيوط الضغط العمل بالتزامن مع البرنامج، مما يسمح للبرنامج بالوصول إلى الكائنات أثناء نقلها نحو بداية الذاكرة الديناميكية. يستخدم الإصداران المتوازٍ والمتزامن من برنامج الضغط عناصر الذاكرة الافتراضية.
انظر أيضاً
مراجع
- ↑ BK Haddon; WM Waite (أغسطس 1967). "إجراء ضغط لعناصر التخزين ذات الطول المتغير" (ملف PDF) . مجلة الكمبيوتر . 10 (2): 162-165 . doi : 10.1093/comjnl/10.2.162 .
- ↑ كيرماني، حاييم؛ بيترانك ، إيريز (يونيو 2006). الضاغط: الضغط المتزامن والتزايدي والمتوازي. وقائع المؤتمر السابع والعشرين لجمعية ACM SIGPLAN حول تصميم وتنفيذ لغات البرمجة . الصفحات 354-363 . doi : 10.1145/1133255.1134023 .
- ↑ أبو عياض، دياب؛ أوسيا، يوآف؛ بيترانك، إيريز؛ سيلبرشتاين، أوري (أكتوبر 2004). خوارزمية ضغط كومة متوازية فعالة . مؤتمر ACM حول البرمجة الكائنية التوجه، والأنظمة، واللغات، والتطبيقات. الصفحات 224-236 . doi : 10.1145/1028976.1028995 .
- إدارة الذاكرة التلقائية
- خوارزميات إدارة الذاكرة