جمع النفايات (علوم الحاسوب)

يُعفي جامع البيانات المهملة المبرمج من تحرير الذاكرة يدويًا. وهذا يساعد على تجنب بعض أنواع الأخطاء : ^{[ 8 ]}

• تحدث مشكلة المؤشرات المعلقة عندما يتم تحرير جزء من الذاكرة بينما لا تزال هناك مؤشرات تشير إليه، ويتم إلغاء مرجعية أحد هذه المؤشرات . بحلول ذلك الوقت، قد تكون الذاكرة قد أعيد تخصيصها لاستخدام آخر، مما يؤدي إلى نتائج غير متوقعة. ^{[ 9 ]}
• أخطاء التحرير المزدوج ، والتي تحدث عندما يحاول البرنامج تحرير منطقة من الذاكرة تم تحريرها بالفعل، وربما تم تخصيصها مرة أخرى.
• قد تؤدي بعض أنواع تسرب الذاكرة ، التي يفشل فيها البرنامج في تحرير الذاكرة التي تشغلها كائنات أصبحت غير قابلة للوصول ، إلى استنفاد الذاكرة. ^{[ 10 ]}

تستخدم عملية جمع البيانات المهملة (GC) موارد الحوسبة لتحديد الذاكرة التي يجب تحريرها. ولذلك، فإن ثمن سهولة عدم تحديد دورة حياة الكائنات يدويًا في شفرة المصدر هو زيادة في الحمل ، مما قد يؤثر سلبًا على أداء البرنامج. ^{[ 11 ]} خلصت ورقة بحثية محكمة نُشرت عام 2005 إلى أن عملية جمع البيانات المهملة تحتاج إلى خمسة أضعاف الذاكرة للتعويض عن هذا الحمل وللعمل بنفس سرعة البرنامج نفسه باستخدام إدارة ذاكرة صريحة مثالية. ومع ذلك، تتم المقارنة مع برنامج تم إنشاؤه عن طريق إدخال استدعاءات إلغاء تخصيص الذاكرة باستخدام وسيط ، ويتم تنفيذه من خلال جمع آثار من برامج تعمل تحت مُحلل أداء ، ويكون البرنامج صحيحًا فقط لتنفيذ واحد محدد. ^{[ 12 ]} يمكن أن يؤدي التفاعل مع تأثيرات التسلسل الهرمي للذاكرة إلى جعل هذا الحمل غير مقبول في ظروف يصعب التنبؤ بها أو اكتشافها في الاختبارات الروتينية. وقد ذكرت شركة آبل تأثير ذلك على الأداء كسبب لعدم اعتمادها لجمع البيانات المهملة في نظام iOS ، على الرغم من كونه الميزة الأكثر طلبًا. ^{[ 13 ]}

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

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

تعتمد عملية جمع البيانات المهملة باستخدام عدّ المراجع على عدّ كل كائن، حيث يُحسب عدد المراجع التي تشير إليه. وتُعرف البيانات المهملة بأنها تلك التي يكون عدد مراجعها صفرًا. يُزاد عدد مراجع الكائن عند إنشاء مرجع إليه، ويُنقص عند حذفه. وعندما يصل العدد إلى الصفر، تُستعاد ذاكرة الكائن. ^{[ 15 ]}

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

هناك عدد من عيوب عدّ المراجع؛ ويمكن عموماً حل هذه المشكلة أو التخفيف من حدتها باستخدام خوارزميات أكثر تطوراً:

دورات

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

المساحة الإضافية (عدد المراجع)

يتطلب عدّ المراجع تخصيص مساحة لكل كائن لتخزين عدد المراجع الخاصة به. يمكن تخزين هذا العدد بجوار ذاكرة الكائن أو في جدول جانبي في مكان آخر، ولكن في كلتا الحالتين، يحتاج كل كائن يتم عدّ مراجعه إلى مساحة تخزين إضافية. تُستخدم عادةً مساحة ذاكرة بحجم مؤشر غير مُوقّع لهذه المهمة، مما يعني أنه يجب تخصيص 32 أو 64 بتًا لتخزين عدد المراجع لكل كائن. في بعض الأنظمة، قد يكون من الممكن تخفيف هذا العبء باستخدام مؤشر مُعلّم لتخزين عدد المراجع في المناطق غير المستخدمة من ذاكرة الكائن. غالبًا، لا تسمح بنية النظام للبرامج بالوصول إلى النطاق الكامل لعناوين الذاكرة التي يمكن تخزينها بحجم المؤشر الأصلي؛ حيث يتم تجاهل عدد معين من البتات العليا في العنوان أو يُشترط أن تكون أصفارًا. إذا كان للكائن مؤشر موثوق في موقع معين، فيمكن تخزين عدد المراجع في البتات غير المستخدمة من المؤشر. على سبيل المثال، يحتوي كل كائن في لغة Objective-C على مؤشر إلى فئته في بداية ذاكرته. في بنية ARM64 باستخدام نظام التشغيل iOS 7 ، تُستخدم 19 بتة غير مستخدمة من مؤشر هذه الفئة لتخزين عدد مراجع الكائن. ^{[ 17 ] [ 18 ]}

زيادة/نقصان السرعة

في التطبيقات البسيطة، يتطلب كل تعيين لمرجع، وكل مرجع يخرج عن نطاق التعريف، تعديل عداد مرجع واحد أو أكثر. مع ذلك، في الحالة الشائعة عند نسخ مرجع من متغير نطاق خارجي إلى متغير نطاق داخلي، بحيث يكون عمر المتغير الداخلي محدودًا بعمر المتغير الخارجي، يمكن الاستغناء عن زيادة المرجع. يصبح المتغير الخارجي هو "مالك" المرجع. في لغة البرمجة C++، تُنفذ هذه التقنية بسهولة وتُوضح باستخدام المراجع const. عادةً ما يُنفذ عد المراجع في C++ باستخدام " المؤشرات الذكية " ^{[ 19 ]} التي تُدير دوالها البانية والمدمرة ومعاملات التعيين المراجع. يمكن تمرير المؤشر الذكي كمرجع إلى دالة، مما يُغني عن الحاجة إلى إنشاء مؤشر ذكي جديد (مما يزيد عدد المراجع عند الدخول إلى الدالة وينقصه عند الخروج منها). بدلًا من ذلك، تتلقى الدالة مرجعًا إلى المؤشر الذكي الذي يتم إنشاؤه بتكلفة منخفضة. تعتمد طريقة دويتش-بوبرو لحساب المراجع على حقيقة أن معظم تحديثات عداد المراجع تُنشأ في الواقع من مراجع مخزنة في متغيرات محلية. تتجاهل هذه الطريقة هذه المراجع، وتحسب فقط المراجع الموجودة في الذاكرة الديناميكية (heap). ولكن قبل حذف كائن ذي عداد مراجع يساوي صفرًا، يجب على النظام التحقق، من خلال مسح المكدس وتسجيله، من عدم وجود أي مرجع آخر إليه. ويمكن تحقيق انخفاض كبير إضافي في الحمل الزائد لتحديثات العداد من خلال دمج التحديثات الذي قدمه ليفانوني وبيترانك . [ ^{20 ] [ 21 ] لنفترض} مؤشرًا يتم تحديثه عدة مرات خلال فترة زمنية محددة من التنفيذ. يشير أولًا إلى كائن O1، ثم إلى كائن آخر O2، وهكذا حتى يشير في نهاية الفترة إلى كائن ما On. عادةً ما تُنفذ خوارزمية حساب المراجع التحديثات التالية rc(O1)--: rc(O2)++، ، rc(O2)--، rc(O3)++، rc(O3)--، ...، rc(On)++. لكن معظم هذه التحديثات زائدة عن الحاجة. ولتقييم عداد المراجع بشكل صحيح في نهاية الفترة، يكفي تنفيذ التحديثين rc(O1)--و rc(On)++. قام ليفانوني وبيترانك بقياس إزالة أكثر من 99٪ من تحديثات العداد في معايير جافا النموذجية.

يتطلب الذرية

عند استخدامها في بيئة متعددة الخيوط ، قد تتطلب هذه التعديلات (الزيادة والنقصان) عمليات ذرية مثل المقارنة والتبديل ، على الأقل بالنسبة للكائنات المشتركة، أو التي يُحتمل مشاركتها بين خيوط متعددة. تُعدّ العمليات الذرية مكلفة على المعالجات المتعددة، وتزداد تكلفتها عند محاكاتها باستخدام خوارزميات برمجية. يمكن تجنب هذه المشكلة بإضافة عدادات مرجعية لكل خيط أو لكل وحدة معالجة مركزية، والوصول إلى العداد المرجعي العام فقط عندما تصبح العدادات المرجعية المحلية صفرًا أو تتجاوز الصفر (أو، بدلاً من ذلك، استخدام شجرة ثنائية للعدادات المرجعية، أو حتى التخلي عن التدمير الحتمي مقابل عدم وجود عداد مرجعي عام على الإطلاق)، ولكن هذا يُضيف عبئًا كبيرًا على الذاكرة، وبالتالي يميل إلى أن يكون مفيدًا فقط في حالات خاصة (يُستخدم، على سبيل المثال، في عدّ المراجع لوحدات نواة لينكس). يمكن استخدام دمج التحديثات بواسطة ليفانوني وبيترانك ^{[ 20 ] [ 21 ]} لإزالة جميع العمليات الذرية من حاجز الكتابة. لا يتم تحديث العدادات بواسطة خيوط البرنامج أثناء تنفيذه، بل يتم تعديلها فقط بواسطة جامع البيانات الذي يعمل كخيط إضافي مستقل دون تزامن. يمكن استخدام هذه الطريقة كآلية لإيقاف جميع العمليات في البرامج المتوازية، وكذلك مع جامع عدادات مرجعية متزامن.

ليس في الوقت الفعلي

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

تحليل الهروب هو أسلوب يُستخدم أثناء الترجمة لتحويل تخصيصات الذاكرة في الكومة إلى تخصيصات في المكدس ، مما يقلل من حجم عملية جمع البيانات المهملة. يحدد هذا التحليل ما إذا كان الكائن المُخصص داخل دالة ما قابلاً للوصول إليه من خارجها. إذا وُجد أن تخصيصًا محليًا للدالة قابل للوصول إليه من دالة أخرى أو خيط معالجة آخر، يُقال إن التخصيص "هرب" ولا يمكن إجراؤه على المكدس. وإلا، فقد يُخصص الكائن مباشرةً على المكدس ويُحرر عند انتهاء الدالة، متجاوزًا بذلك الكومة وما يرتبط بها من تكاليف إدارة الذاكرة. ^{[ 22 ]}

كثيراً ما استخدمت لغتا BASIC و Logo خاصية جمع البيانات المهملة لأنواع البيانات ذات الأطوال المتغيرة، مثل السلاسل النصية والقوائم، وذلك لتجنب إثقال كاهل المبرمجين بتفاصيل إدارة الذاكرة. في جهاز Altair 8800 ، قد تتسبب البرامج التي تحتوي على العديد من متغيرات السلاسل النصية ومساحة تخزين محدودة في حدوث فترات توقف طويلة بسبب عملية جمع البيانات المهملة. ^{[ 25 ]} وبالمثل، تقوم خوارزمية جمع البيانات المهملة في مترجم لغة Applesoft BASIC بفحص واصفات السلاسل النصية بشكل متكرر بحثاً عن السلسلة النصية ذات العنوان الأعلى لضغطها في الذاكرة الرئيسية، مما ينتج عنه${\displaystyle O(n^{2})}$^{[ 26 ]} ويتوقف البرنامج لفترات تتراوح بين بضع ثوانٍ وبضع دقائق. ^{[ 27 ]} يقوم جامع البيانات المهملة البديل للغة Applesoft BASIC، الذي طوره راندي ويغينتون، بتحديد مجموعة من السلاسل النصية في كل دورة على الذاكرة، مما يقلل وقت التجميع بشكل كبير. ^{[ 28 ]} يوفر BASIC.SYSTEM، الذي صدر مع ProDOS عام 1983، جامع بيانات مهملة يعمل بنظام النوافذ للغة BASIC وهو أسرع بكثير. ^{[ 29 ]}

لم تُقدّم لغة C دعمًا رسميًا لجمع البيانات المهملة. أضافت لغة C++ دعمًا لجمع البيانات المهملة في الإصدار C++11 إلى المكتبة القياسية، إلا أنه أُزيل في الإصدار C++23 لعدم وجود مُترجمات تدعم هذه الميزة. ^{[ 30 ]} وكانت الميزات التي كانت جزءًا من ذلك متعلقة بأمان المؤشرات. ^{[ 31 ]}

Although garbage collection support in the standard library was removed, some garbage collectors such as Boehm garbage collector (for C and C++) can still be used. Boehm GC uses tracing garbage collection. It can also be used in leak detection mode, where memory management is still manual however leaks and double-free errors can be detected and reported. Its use can be called from the header <gc.h>.

One can still abstract away manual object destructions in C++ by using the "resource acquisition is initialization" (RAII) idiom and smart pointers. std::unique_ptr ties lifetimes to ownership, while std::shared_ptr uses reference counting to determine lifetime. std::weak_ptr can be used to obtain a pointer without increasing the reference count. Unlike garbage collection, RAII is deterministic.

While the Objective-C traditionally had no garbage collection, with the release of OS X 10.5 in 2007 Apple introduced garbage collection for Objective-C 2.0, using an in-house developed runtime collector.^[32] However, with the 2012 release of OS X 10.8, garbage collection was deprecated in favor of LLVM's automatic reference counter (ARC) that was introduced with OS X 10.7.^[33] Furthermore, since May 2015 Apple even forbade the usage of garbage collection for new OS X applications in the App Store.^[34][35] For iOS, garbage collection has never been introduced due to problems in application responsivity and performance;^[13][36] instead, iOS uses ARC.^[37][38]

Garbage collection is rarely used on embedded or real-time systems because of the usual need for very tight control over the use of limited resources. However, garbage collectors compatible with many limited environments have been developed.^[39] The Microsoft .NET Micro Framework, .NET nanoFramework^[40] and Java Platform, Micro Edition are embedded software platforms that, like their larger cousins, include garbage collection.

Garbage collectors available in JavaOpenJDKs virtual machine (JVM) include:

• Serial
• Parallel
• CMS (Concurrent Mark Sweep)
• G1 (التخلص من النفايات أولاً)
• ZGC (جامع القمامة Z)
• إبسيلون
• شيناندواه
• GenZGC (الجيل ZGC)
• جينشن (جيل شيناندواه)
• IBM Metronome (متوفر فقط في IBM OpenJDK)
• SAP (فقط في SAP OpenJDK)
• Azul C4 (جامع الضغط المتزامن المستمر) ^{[ 41 ]} (فقط في Azul Systems OpenJDK)

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

تمت دراسة هذا النوع من جمع البيانات المهملة في لغة برمجة ميركوري ، ^{[ 42 ]} وشهد استخدامًا أكبر مع إدخال عداد المراجع التلقائي (ARC) الخاص بـ LLVM في نظام أبل البيئي (iOS و OS X) في عام 2011. ^{[ 37 ] [ 38 ] [ 34 ]} 

تم تطوير خوارزميات جمع البيانات المهملة التزايدية والمتزامنة واللحظية، على سبيل المثال من قبل هنري بيكر وهنري ليبرمان . ^{[ 43 ] [ 44 ] [ 45 ]}

في خوارزمية بيكر، يتم تخصيص الذاكرة في أحد نصفي منطقة واحدة. عندما تمتلئ نصفها، تُجرى عملية جمع البيانات المهملة، حيث تُنقل الكائنات النشطة إلى النصف الآخر، بينما تُحرر الكائنات المتبقية ضمنيًا. يجب على البرنامج قيد التشغيل (المُعدِّل) التحقق من وجود أي كائن يشير إليه في النصف الصحيح، وإذا لم يكن كذلك، ينقله إلى النصف الآخر، بينما تقوم مهمة في الخلفية بالعثور على جميع الكائنات. ^{[ 46 ]}

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

تتضمن بعض بنى الحواسيب ذات اللغات عالية المستوى دعمًا للأجهزة لجمع البيانات المهملة في الوقت الفعلي.

تستخدم معظم تطبيقات جامعات البيانات المهملة في الوقت الحقيقي تقنية التتبع . وتلبي هذه الجامعات قيود الوقت الحقيقي الصارمة عند استخدامها مع نظام تشغيل يعمل في الوقت الحقيقي. ^{[ 47 ]}