استفاده از چندین نسل در Garbage Collection
اگر فقط دو نسل داشته باشیم، وقتی نسل جوان پر میشود، اشیای زنده باید به نسل قدیمی منتقل شوند. اما بعضی از این اشیاء هنوز خیلی جوان هستند و ممکن است زودتر از موعد بمیرند! مشکل چیست؟ ما داریم اشیاء را به نسل قدیمی منتقل میکنیم، ولی خیلیاز آنها زود میمیرند و فضای نسل قدیمی را بیهوده اشغال میکنند. این باعث میشود Full GC زودتر اجرا گردد و باعث توقف طولانیتر شود.
راهحل: استفاده از نسلهای بیشتر! یک یا چند نسل میانی (Intermediate Generations) ایجاد میکنیم تا قبل از اینکه اشیاء به نسل قدیمی منتقل شوند، فیلتری روی آنها انجام شود!
مزایای استفاده از چندین نسل
- کاهش فشار روی نسل قدیمی: چون اشیای موقتی قبل از رسیدن به نسل قدیمی حذف میشوند.
- بهینهسازی توقفهای GC (Pause Time): تعداد دفعات اجرای Full GC کاهش پیدا میکند.
- کاهش مشکل nepotism: چون اشیایی که خیلی زود میمیرند، قبل از انتقال به نسل قدیمی، در نسلهای میانی حذف میشوند.
چالشها و مشکلات استفاده از چندین نسل
با اینکه چندین نسل، مفید است، اما مشکلاتی هم ایجاد میکند:
افزایش پیچیدگی پیادهسازی:
- حالا GC باید بین چندین نسل مدیریت انجام بدهد، نه فقط دو نسل.
- نوشتن الگوریتمهای GC سختتر و پردازش کندتر میشود.
افزایش حجم ردیابی اشارهگرها (Inter-Generational Pointers):
- حالا باید اشارهگرها را بین چندین نسل مختلف مدیریت کنیم، نه فقط بین دو نسل.
- این باعث افزایش بار روی Write Barrier و کاهش عملکرد میشود.
افزایش اندازهی Root Set در نسلهای جوانتر:
- بعضی اشیاء که در نسلهای میانی هستند، میتوانستند درنسل جوان حذف شوند اما بهجای آن ارتقا داده شدند.
- این باعث میشود نسل جوان زودتر پر شود و Minor GCها بیشتر اجرا شوند.
چرا امروزه اکثر GCها فقط دو نسل دارن؟
با این که سیستمهایی مثل Smalltalk و Lisp در گذشته از چندین نسل استفاده میکردند، اما بیشتر GCهای امروزی فقط دو نسل دارند.
دلیل این موضوع:
- مدیریت چندین نسل پیچیده و پرهزینه است.
- تکنیکهای بهینهسازی داخل خود نسلها (مثل مدیریت ارتقای اشیاء در نسل جوان) میتوانند مشکل را حل کنند.
- افزایش تعداد نسلها باعث افزایش هزینهی Write Barrier و کاهش عملکرد کلی برنامه میشود.
چند روش هوشمندانه وجود دارد که بدون اضافه کردن نسلهای جدید، همان مزایای نسلهای میانی را بهدست آوریم:
۱. مدیریت نرخ ارتقاء (Promotion Rate Management)
بهجای اینکه تمام اشیاء زندهی نسل جوان را به صورت مستقیم به نسل قدیمی بفرستیم، از چندین "Bucket" برای کنترل نرخ ارتقاء استفاده میکنیم. مثلاً یک شیء باید حداقل 2-3 بار Minor GC را زنده بماند تا به نسل قدیمی منتقل شود.
۲. بهینهسازی اندازهی نسل جوان (Adaptive Nursery Sizing)
اندازهی نسل جوان باید بهینه تنظیم شود تا قبل از ارتقا، اکثر اشیاء حذف شوند. اندازهی نسل جوان را میشود بسته به میزان اشیای زنده، پویا تنظیم کرد!
۳. استفاده از Write Barrier هوشمند (Intelligent Write Barrier)
Write Barrier نباید همهی اشارهگرهای بین نسلها را ثبت کند، بلکه فقط موارد بحرانی را پیگیری کند. این باعث کاهش بار Write Barrier و بهبود کارایی میشود.
GC باید یک روشی برای "اندازهگیری سن" اشیاء داشته باشد تا بتواند تصمیم بگیرد که آیا این شیء باید ارتقا پیدا کند یا خیر. چند روش مختلف برای این کار وجود دارد که هرکدام مزایا و معایب خود را دارند.
روش ساده: ارتقای دستهجمعی (En Masse Promotion)
هر بار که یک Minor GC اجرا میشود، همهی اشیاء زنده به نسل بعدی ارتقا پیدا میکنند!
مشکل:
- خیلی از اشیاء زنده که تازه ایجاد شدند، زودتر از موعد ارتقاء پیدا میکنند.
- این باعث افزایش نرخ ارتقاء (Promotion Rate) و کاهش فضای مفید نسل قدیمی میشود.
- ممکن است 50% تا 100% اشیاء بیشتری ارتقاء پیدا کنند، نسبت به روشهای بهینهتر!
جمعبندی:
خیلی ساده و بهینه از نظر پردازشی، اما بهینه از نظر استفاده از حافظه نیست!
روش نیمهفضاهای سنی (Aging Semispaces)
نسل جوان به دو یا چند نیمهفضا (Semispace) تقسیم میشود. اشیاء قبل از اینکه ارتقاء پیدا کنند، چند بار بین این نیمهفضاها جابجا میشوند.به این دلیل خوب است که اشیایی که زود میمیرند، قبل از رسیدن به نسل قدیمی حذف میشوند. این روش از ارتقای زودهنگام جلوگیری میکند!
مشکل:
- نیاز به محاسبهی سن اشیاء دارد، که سربار پردازشی اضافه میکند.
- هر بار که GC اجرا میشود، اشیاء باید بین نیمهفضاها جابجا شوند.
استفاده:
ExactVM در Sun Microsystems این روش را با استفاده از 5 بیت در Header شیء برای ذخیرهی سن اجرا کرده بود!
روش Bucket Brigade و Step Systems
نسل جوان به چند بخش کوچکتر تقسیم میشود، به اسم "Buckets" یا "Steps". اشیاء به مرور از یک Step به Step بعدی منتقل میشوند تا زمانی که به حد کافی زنده بمانند و ارتقاء پیدا کنند.
مزایا:
- دقیقتر از نیمهفضاها عمل میکند.
- بدون نیاز به ذخیرهی سن برای هر شی، میتوانیم ارتقاء را بهتر کنترل کنیم.
- با هر اجرای Minor GC، فقط اشیای واقعاً پایدار ارتقا پیدا میکنند.
استفاده:
- Glasgow Haskell Compiler و UMass GC Toolkit این روش را پیادهسازی کردند.
- Shaw’s Bucket Brigade بهینهسازی خاصی داشت که باعث میشد ارتقاء بدون نیاز به جابجایی دادهها انجام شود!
روش Survivor Spaces (فضاهای بازمانده)
یک بخش خاص از نسل جوان به اسم "Eden" داریم که همهی اشیاء جدید درآن ساخته میشوند. دو فضای بازمانده (Survivor Spaces) داریم که اشیاء زنده از Eden به آنها منتقل میشوند. اگر یک شیء چند بار در Survivor Space زنده بماند، به نسل قدیمی ارتقا پیدا میکند.
مزایا:
- بهینهترین روش برای استفاده از حافظه، چون Eden خیلی بزرگ است و فقط 6.25% فضا برای کپی رزرو میشود!
- اشیای زودمرگ از بین میرود قبل از اینکه به نسل قدیمی برسند.
- مدیریت ساده و موثر
روش High Water Mark
در هر اجرای Minor GC، یک "High Water Mark" تعیین میکنیم. اگر یک شیء پایینتر از این مارک باشد، به Survivor Space منتقل میشود. اگر بالاتر از مارک باشد، به نسل قدیمی ارتقا پیدا میکند.
مزایا:
- ارتقای اشیاء دقیقتر انجام میشود، چون فقط اشیاء واقعاً پایدار منتقل میشوند.
- نیاز به ذخیرهی سن اشیاء نداریم، فقط از مقایسهی آدرسها استفاده میکنیم!
استفاده:
Scheme-48 و Standard ML از این روش استفاده کردند.