تتبع عملية جمع القمامة

📅 آخر تحديث: ٤ أغسطس ٢٠٢٦
✍️ نُشر في: ٤ أغسطس ٢٠٢٦
📷 يحتوي على 6 صور
الموسوعة الحرة

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

إمكانية الوصول إلى جسم ما

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

  1. مجموعة مميزة من الجذور: كائنات يُفترض أنها قابلة للوصول. عادةً، تشمل هذه جميع الكائنات المشار إليها من أي مكان في مكدس الاستدعاءات (أي جميع المتغيرات المحلية والمعاملات في الدوال التي يتم استدعاؤها حاليًا)، وأي متغيرات عامة .
  2. أي شيء يُشار إليه من كائن قابل للوصول إليه يكون قابلاً للوصول إليه أيضاً؛ وبشكل أكثر رسمية، فإن إمكانية الوصول هي إغلاق متعدٍ .

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

Object x = new Foo (); Object y = new Bar (); x = new Quux (); /* في هذه المرحلة، نعلم أن كائن Foo * الذي تم تعيينه أصلاً إلى x لن يتم الوصول إليه أبدًا *: إنه مجرد بيانات غير ضرورية. *//* في الكتلة التالية، قد يكون y قيمة غير ذات دلالة؛ *لكننا لن نعرف ذلك حتى تُرجع x.check_something() * قيمة ما -- إن أعادت قيمة أصلاً. */ if ( x . check_something ()) { x . do_something ( y ); } System . exit ( 0 );

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

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

المراجع القوية والضعيفة

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

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

في بعض التطبيقات، تُقسّم المراجع الضعيفة إلى فئات فرعية. على سبيل المثال، توفر آلة جافا الافتراضية ثلاثة أنواع من المراجع الضعيفة، وهي المراجع الناعمة [ 2 ] ، والمراجع الوهمية [ 3 ] ، والمراجع الضعيفة العادية [ 4 ] . لا يكون الكائن المُشار إليه بشكل ناعم مؤهلاً للاستعادة إلا إذا قرر جامع البيانات المهملة أن البرنامج يعاني من نقص في الذاكرة. على عكس المرجع الناعم أو المرجع الضعيف العادي، لا يوفر المرجع الوهمي إمكانية الوصول إلى الكائن الذي يُشير إليه. بدلاً من ذلك، يُعد المرجع الوهمي آلية تسمح لجامع البيانات المهملة بإخطار البرنامج عندما يصبح الكائن المُشار إليه قابلاً للوصول الوهمي . يكون الكائن قابلاً للوصول الوهمي إذا كان لا يزال موجودًا في الذاكرة ويُشار إليه بواسطة مرجع وهمي، ولكن مُنهيه قد تم تنفيذه بالفعل. وبالمثل، توفر .NET فئتين فرعيتين من المراجع الضعيفة [ 5 ] ، وهما المراجع الضعيفة الطويلة (التي تتعقب الإحياء) والمراجع الضعيفة القصيرة.

مجموعات ضعيفة

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

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

إن استخدام جدول تجزئة عادي لمثل هذا الغرض قد يؤدي إلى "تسرب الذاكرة المنطقي": تراكم البيانات التي يمكن الوصول إليها والتي لا يحتاجها البرنامج ولن يستخدمها.

الخوارزمية الأساسية

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

تحديد ومسح ساذج

تطبيق بسيط لعملية التحديد والمسح على كومة تحتوي على ثمانية عناصر . تمثل الأسهم مراجع العناصر ، بينما تمثل الدوائر العناصر نفسها. العناصر رقم 1، 2، 3، 4، و6 مرتبطة ارتباطًا وثيقًا بمجموعة الجذر. أما العناصر رقم 5، 7، و8، فلا ترتبط ارتباطًا وثيقًا، لا بشكل مباشر ولا غير مباشر، بمجموعة الجذر؛ لذا فهي عناصر مهملة.

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

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

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

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

علامة ثلاثية الألوان

مثال على وضع علامات ثلاثية الألوان على كومة تحتوي على 8 عناصر. يتم تمثيل العناصر البيضاء والرمادية والسوداء باللون الرمادي الفاتح والأصفر والأزرق على التوالي.

بسبب مشاكل الأداء هذه، تُطبّق معظم خوارزميات جمع البيانات المهملة الحديثة نوعًا من تجريد التحديد ثلاثي الألوان ، لكن الخوارزميات البسيطة (مثل خوارزمية التحديد والمسح ) غالبًا لا تُوضّح هذا التجريد. يعمل التحديد ثلاثي الألوان كما هو موضح أدناه.

تم إنشاء ثلاث مجموعات - الأبيض والأسود والرمادي : 

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

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

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

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

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

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

استراتيجيات التنفيذ

الحركة مقابل عدم الحركة

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

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

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

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

النسخ مقابل التحديد والمسح مقابل التحديد وعدم المسح

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

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

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

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

يُشبه جامع البيانات المهملة " التمييز وعدم المسح" جامع البيانات المهملة "التمييز والمسح"، حيث يحتفظ بت مع كل كائن لتسجيل ما إذا كان أبيض أم أسود؛ وتُحفظ المجموعة الرمادية كقائمة منفصلة أو باستخدام بت آخر. ثمة فرقان رئيسيان هنا. أولًا، يختلف معنى الأسود والأبيض عما هو عليه في جامع البيانات المهملة "التمييز والمسح". ففي جامع البيانات المهملة "التمييز وعدم المسح"، تكون جميع الكائنات التي يمكن الوصول إليها سوداء دائمًا. يُعلّم الكائن باللون الأسود عند تخصيصه، ويبقى كذلك حتى لو أصبح غير قابل للوصول. أما الكائن الأبيض فهو ذاكرة غير مستخدمة ويمكن تخصيصها. ثانيًا، يمكن أن يتغير تفسير بت الأسود/الأبيض. في البداية، قد يكون معنى بت الأسود/الأبيض (0=أبيض، 1=أسود). إذا فشلت عملية التخصيص في العثور على أي ذاكرة متاحة (بيضاء)، فهذا يعني أن جميع الكائنات تُعلّم بأنها مستخدمة (سوداء). عندئذٍ ينعكس معنى بت الأسود/الأبيض (على سبيل المثال، 0=أسود، 1=أبيض). يصبح كل شيء أبيض. يؤدي هذا مؤقتًا إلى كسر القاعدة الثابتة المتمثلة في أن الكائنات التي يمكن الوصول إليها سوداء، ولكن تتبع ذلك مباشرةً مرحلة تعليم كاملة لإعادة تعليمها باللون الأسود. بمجرد الانتهاء من ذلك، تصبح جميع الذاكرة التي لا يمكن الوصول إليها بيضاء. لا حاجة لمرحلة "مسح".

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

وبالتالي يمكن اعتبار استراتيجية "التحديد وعدم المسح" بمثابة حل وسط بين إيجابيات وسلبيات استراتيجيتي "التحديد والمسح" و"التوقف والنسخ".

الجيل GC (الجيل GC الزائل)

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

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

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

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

إيقاف العالم مقابل التدريج مقابل التزامن

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

يُعاب على هذا الأسلوب أنه لا يستطيع البرنامج القيام بأي عمل مفيد أثناء دورة جمع البيانات المهملة (والتي تُسمى أحيانًا "التوقف المُحرج" [ 7 ] ). لذا، يُعدّ جمع البيانات المهملة الذي يُوقف جميع العمليات مناسبًا بشكل أساسي للبرامج غير التفاعلية. وتكمن ميزته في سهولة تنفيذه وسرعته مقارنةً بجمع البيانات المهملة التزايدي.

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

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

دقيق مقابل متحفظ ومؤشرات داخلية

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

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

أداء

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

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

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

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

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

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

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

الحتمية

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

جمع القمامة في الوقت الفعلي

على الرغم من أن عملية جمع البيانات المهملة غير حتمية عمومًا، إلا أنه من الممكن استخدامها في الأنظمة ذات الوقت الحقيقي الصارم . يجب أن يضمن جامع البيانات المهملة في الوقت الحقيقي تخصيص عدد معين من موارد الحوسبة لخيوط التعديل حتى في أسوأ الحالات. عادةً ما تكون القيود المفروضة على جامع البيانات المهملة في الوقت الحقيقي إما قيودًا على العمل أو قيودًا زمنية. يبدو القيد الزمني كما يلي: ضمن كل نافذة زمنية مدتهاتي{\displaystyle T}ينبغي السماح لخيوط التعديل بالعمل لمدة لا تقل عنتيم{\displaystyle T_{m}}الوقت. بالنسبة للتحليل القائم على العمل، يتم استخدام MMU (الاستخدام الأدنى للمعدل) [ 10 ] عادةً كقيد زمني حقيقي لخوارزمية جمع البيانات المهملة.

كانت إحدى أولى تطبيقات جمع البيانات المهملة في الوقت الحقيقي الصارم لآلة جافا الافتراضية (JVM) تعتمد على خوارزمية ميترونوم ، [ 11 ] والتي يتوفر تطبيقها التجاري كجزء من IBM WebSphere Real Time . [ 12 ] وهناك خوارزمية أخرى لجمع البيانات المهملة في الوقت الحقيقي الصارم وهي ستاكاتو، المتوفرة في J9 JVM من IBM ، والتي توفر أيضًا قابلية التوسع لبنى المعالجات المتعددة الكبيرة، مع مزايا عديدة مقارنةً بخوارزمية ميترونوم وغيرها من الخوارزميات التي تتطلب، على النقيض من ذلك، أجهزة متخصصة. [ 13 ]

يتمثل أحد التحديات الرئيسية لجمع البيانات المهملة في الوقت الحقيقي على معالجات متعددة النوى الحديثة في تصميم عملية جمع بيانات مهملة متزامنة غير محظورة، بحيث لا تتسبب الخيوط المتزامنة في حظر بعضها البعض، مما يؤدي إلى توقفات غير متوقعة. وقد نُشرت دراسة للخوارزميات التي تسمح بجمع البيانات المهملة المتزامنة في الوقت الحقيقي دون حظر في ورقة بحثية لبيزلو وآخرين في مايكروسوفت ريسيرش. [ 14 ]

انظر أيضاً

مراجع

  1. ↑ "نظرية موحدة لجمع النفايات" . www.cs.cornell.edu . 2019-11-08 . تاريخ الاسترجاع 2025-09-10 .
  2. 1 2 "Class SoftReference < T > " . Java™ Platform Standard Ed. 7 . Oracle . تم الاسترجاع في 25 مايو 2013 . 
  3. ↑ "Class PhantomReference < T > " . Java™ Platform Standard Edition. 7 . Oracle . تم الاسترجاع في 25 مايو 2013 . 
  4. ↑ "Class WeakReference < T > " . Java™ Platform Standard Ed. 7 . Oracle . تم الاسترجاع في 25 مايو 2013 . 
  5. ↑ "المراجع الضعيفة" . وثائق .NET . مايكروسوفت . تم الاطلاع عليه بتاريخ 31 يوليو 2026 .
  6. ↑ "النسخ والتثبيت" . مستندات مايكروسوفت . تم الاسترجاع في 25 أبريل 2022 .
  7. ↑ ستيل، جاي ل. (سبتمبر 1975). "المعالجة المتعددة وضغط جمع البيانات المهملة" . اتصالات رابطة مكائن ​​الحوسبة . 18 (9): 495-508 . doi : 10.1145/361002.361005 . S2CID 29412244 . 
  8. ↑ أبيل، أندرو و. (17 يونيو 1987). "جمع البيانات المهملة قد يكون أسرع من تخصيص الذاكرة في المكدس" (ملف PDF) . رسائل معالجة المعلومات . 25 (4): 275-279 . CiteSeerX 10.1.1.49.2537 . doi : 10.1016/0020-0190(87)90175-X . S2CID 2575400. تاريخ الاسترجاع: 25 أبريل 2022 .  
  9. ↑ هوبوود، ديفيد (1 يناير 2007). "تخصيص الذاكرة في الأنظمة المدمجة" . cap-talk (قائمة بريدية). EROS . مؤرشف من الأصل في 24 سبتمبر 2015.
  10. ↑ تشنغ، بيري؛ بليلوش، غاي إي. (22 يونيو 2001). "جامع قمامة متوازٍ في الوقت الحقيقي" (ملف PDF) . إشعارات ACM SIGPLAN . 36 (5): 125-136 . doi : 10.1145/381694.378823 .
  11. ↑ بيكون، ديفيد ف.؛ تشينغ، بيري؛ راجان، في تي (نوفمبر 2003). "المترونوم: منهج أبسط لجمع البيانات المهملة في الأنظمة الآنية" (ملف PDF) . في: كورسارو، أنجيلو؛ سيترون، رون؛ سانتورو، كورادو (محررون). ورشة عمل حول تقنيات جافا للأنظمة الآنية والمدمجة . JTRES'03. ورش عمل OTM 2003. نحو أنظمة إنترنت ذات معنى 2003. LNCS . المجلد 2889. الصفحات 466-478 . CiteSeerX 10.1.1.3.8544 . doi : 10.1007/978-3-540-39962-9_52 . ISBN    3-540-20494-6ISSN 0302-9743 . S2CID 14565934. مؤرشف من الأصل (PDF) بتاريخ 26-10-2006 .  
  12. ↑ بيرون، بنيامين؛ سيامباكون، رايان (2 مايو 2007). "جافا في الوقت الحقيقي، الجزء 4: جمع البيانات المهملة في الوقت الحقيقي" . IBM DeveloperWorks . مؤرشف من الأصل في 9 نوفمبر 2020.
  13. ↑ ماكلوسكي، بيل؛ بيكون، ديفيد ف.؛ تشينغ، بيري؛ غروف، ديفيد (22 فبراير 2008). ستاكاتو: جامع قمامة مضغوط متوازي ومتزامن في الوقت الحقيقي للمعالجات المتعددة (ملف PDF) (تقرير فني). قسم أبحاث IBM. RC24504 . تاريخ الاسترجاع: 25 أبريل 2022 .
  14. ↑ بيزلو، فيل؛ بيترانك، إيريز ؛ ستينسجارد، بيارن (يونيو 2008). وقائع المؤتمر التاسع والعشرين لجمعية ACM SIGPLAN حول تصميم لغات البرمجة وتنفيذها (ملف PDF) . مؤتمر PLDI 2008. الصفحات 33-44 . CiteSeerX 10.1.1.3.8544 . doi : 10.1145/1375581.1375587 . ISBN   9781595938602.