نظرة على إدارة الذاكرة وآلية عمل جامع القمامة

كتبه بركات يوم الجمعـة, 25 أيلول 2015

عندما ننشئ كائن أو نحجز جزء من الذاكرة، هناك مكون يسمى مخصص الذاكرة memory allocator، مخصص الذاكرة يحجز جزء كبير من الذاكرة التخيلية سواءً عند بداية تشغيل البرنامج، أو عند أول طلب حجز للذاكرة، وذلك باستخدام API إدارة الذاكرة التخيلية التي يوفرها نظام التشغيل، في أنظمة ويندوز من عائلة NT هذه الدالة VirtualAlloc وكذلك VirtualAllocEx1، وفي الأنظمة المتوافقة مع POSIX، مثل لينكس، هذه الدالة mmap، عندما تطلب حجز جزء من الذاكرة التخليلة، فالنظام يحجز لك بمضاعفات وحدة تسمى الصفحة page، حجم الصفحة يعتمد على معمارية معالجك، غالباً 4KB في معماريات أنتل x86، فحتى لو طلبت حجز بايت واحد، فالنظام سيحجز لك 4KB، لأنها أقل قيمة يمكنه حجزها، مخصص الذاكرة يعمل على تقسيم تلك الصفحات لوحدات أصغر والإستفادة من تلك المساحة قدر مايستطيع، يمكننا تشبيه مخصص الذاكرة التخيلية الذي يوفرها نظام التشغيل بمحلات البيع بالجملة، ومخصص الذاكرة تستطيع تشبيهه بمحلات البيع بالتجزئة.

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

كتابة مخصص ذاكرة عملية ممتعة، وتساعدك في فهم كيف تعمل مخصصات الذاكرة مثل malloc في لغة C، وكيف تكتب واحد بنفسك، وكذلك فهم بعض مشاكل إدارة الذاكرة مثل مشكلة تقطع الذاكرة memory fragmentation، لكننا سنتحدث هنا عن جامع القمامة، وتفاصيل عمل مخصص الذاكرة سأدعها لوقت لاحق.

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

عداد الإشارة أبسط آليات إدارة حياة الكائنات، آلية عمله أن مع كل كائن هناك عداد يرتبط به ويمثل برقم موجب، قيمة هذا العداد تشير لعدد الإشارات لهذا الكائن، عند إنشاء الكائن لأول مرة والإشارة إليه، فقيمة العداد تساوي 1، إذا أشار كائن آخر لهذا الكائن فيزداد العداد بواحد وعند إلغاء الإشارة كعند طلب تحرير الكائن أو استدعاء هدام الكائن، فينقص العداد بواحد، عندما يطلب آخر كائن تحرير الكائن المحجوز، فينقص العداد ليصبح صفر، فور وصول العداد للصفر فيحرر الكائن، مثال هنا (تشير A.ref لقيمة عداد الكائن بعد تنفيذ الجملة):

Node A = new Node();  // A.ref = 1
Node B = new Node();  // B.ref = 1

A.next = B;           // A.ref = 1, B.ref = 2
B.next = null;

A = null;             // A.ref = 0, B.ref = 1 (A يحذف)
B = null;             // B.ref = 0            (B يحذف)

لايشترط أن تستخدم A = null، حيث استخدمتها فقط للتوضيح، فبمجرد انتهاء الدالة سيتم انقاص عدادات جميع الكائنات الحية في تلك الدالة، هذا كما قلت أبسط أنواع جوامع القمامة، إلا أنه لايستطيع حل مشكلة الإشارة الدائرية reference cycles وذلك عندما يشير كائنان لبعض سواءً مباشرة مثل A → B → A أو بإشارة غير مباشرة مثل A → B → C → A، انظر لهذا المثال2:

Node A = new Node();  // A.ref = 1
Node B = new Node();  // B.ref = 1

A.next = B;           // A.ref = 1, B.ref = 2
B.prev = A;           // A.ref = 2, B.ref = 2

A = null;             // A.ref = 1, B.ref = 2
B = null;             // A.ref = 1, B.ref = 1

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

هناك أيضاً هناك مشكلة التعقيد الذي تضيفه هذه الطريقة على كتابة بيئة التشغيل أو كتابة إضافاتها، فعندما تشير لكائن فلا بد أن تزيد العداد، وتنقصه عندما تنتهي من الكائن، نسيان عمل هذا سيتسبب في أخطاء أو تسريب في الذاكرة، فإحتما كبير أن تنسى زيادة العداد أو انقاصه، انظر مثلاً هنا للملف unicodeobject.c، حيث يحتوي على الفئة المسؤولة عن النصوص في مترجم CPython الخاص بلغة Python 3، حيث كان في بداياته يعتمد على عداد الإشارة فقط ثم لاحقاً أضيف جامع قمامة يعتمد على طريقة ضع علامة ثم اكنس لحل مشكلة الإشارة الدائرية، يكفي أن تبحث عن الـmacros المسماة Py_INCREF و Py_DECREF، والمسؤولة عن زيادة وإنقاص عداد الإشارة للكائنات، لترى كمية التعقيد على التي تضيفه على الكود، لو عدل أحد الكود ونسي أن يزيد عداد أو ينقصه، سيحدث تسريب، تسريب بايت واحد سيكبر ويكبر إلى أن يستهلك معظم الذاكرة.

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

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

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

لننظر لهذا المثال:

  void func1() {
0     Integer A = 111;
1     Integer B = 222;
2 
3     B = null;
4 
5     func2()
6     return;
  }

  void func2() {
0     Integer C = 333;
1     func3();
2     return;
  }

  void func3() {
0     Integer D = 444;
1     gc();               // استدعاء جامع القمامة
2     return;
  }

حيث لدينا أربعة متغيرات، المتغير B أصبح قمامة بعد تنفيذ الجملة B = null، ولدينا ثلاثة دوال تستدعي بعض، func1 يستدعي func2، و func2 يستدعي func3، هذا الأخير استدعى جامع القمامة3، عند وصولنا للسطر gc() سيحتوي اطار المكدس stack frame على التالي:

مثال

نلاحظ في يسار الصورة اطار المكدس stack frame، وهو عبارة عن مكدس stack4، حيث يحتوي على عناوين قيم المتغيرات المحلية في الدوال، والمتغيرات الممررة للدوال arguments عند استدعاءها، حيث لم نمرر شيء للدوال، وعنوان العودة والذي نعود له بعد انتهاء تنفيذ الدالة الحالية، وفي يمين الصورة هناك الكومة heap، حيث تخزن الكائنات في الذاكرة.

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

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

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

هناك استراتيجيات كثيرة لم أذكرها، بعض بيئات التشغيل حتى تسمح لك بتغيير الاستراتيجية التي يستخدمها جامع القمامة لما يناسب برنامجك، انظر إلى الخيارات الخاصة بجامع القمامة التي توفرها Java HotSpot VM وهي آلة JVM للغة Java من Sun أو Oracle حالياً، لكن في بعض التطبيقات كبعض الألعاب وتطبيقات الـrealtime التي يهمها كل جزء من الثانية، الإيقاف الذي يسببه جامع القمامة قد يعتبر مرفوض، لذا تستخدم إما لغات أخرى مثل C/C++ أو تستخدم طرق مثل memory pool حيث تحجز كمية كبيرة من الكائنات في مصفوفة تدار يدوياً ويعاد استخدام الكائنات غير المستخدمة وذلك لتقليل عمل جامع القمامة.


  1. يوفر ويندوز أيضاً HeapAlloc، هو ولينكس يوفران أيضاً malloc، وهذه مخصصات ذاكرة عادية جاهزة، دوال تخصيص الذاكرة التخليلة VirtualAlloc و mmap متوفرة لمن يريد كتابة مخصص ذاكرة خاص، وكذلك لأغراض أخرى مثل الـmemory mapped files. 

  2. قد تخطئ وتقول لماذا لاننقص قيمة العداد لكل الكائنات التي يشير لها الكائن عندما ننقص قيمة عداده وهكذا سنحل المشكلة؟ السبب لأن الكائن لو كان يشير لكائن آخر وكانت قيمة الكائن الأب 2 وقيمة الإبن 1، ثم أنقصنا قيمة الأب بواحد، فالإبن يحذف رغم أن الأب لايزال يشير له. 

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

  4. يرسم إطار المكدس غالباً بالمقلوب، حيث أن قمته في الأسفل وذلك لأنه في كثير من المعماريات المكدس ينمو للأسفل.