مدیریت اشارهگرهای بین نسلی در GC
وقتی GC فقط یک نسل را جمعآوری میکند، باید مطمئن شود که هیچ شیء زندهای که از نسلهای دیگر به این نسل اشاره میکند، نادیده گرفته نشدهاست. برای این کار، از "مجموعههای یادآوری" (Remembered Sets) و "مانع نوشتن" (Write Barrier) استفاده میشود. این روشها به GC کمک میکنند که فقط تغییرات مهم را ردیابی کند و لازم نباشد کل حافظه را اسکن کند.
مشکل اصلی: کشف ریشههای نسل
ریشههای یک نسل فقط شامل متغیرهای سراسری و مقادیر موجود در پشته نیستند. بلکه شامل هر اشارهگری از نسلهای قدیمی به نسل جوان هم میشوند. حتی اشیائی که خارج از هیپ معمولی ذخیره شدند، مثل اشیاء بوت (Boot Image)، ممکن است به نسلهای جدید اشاره کنند! GC باید این اشارهگرها را شناسایی و در نظر بگیرد، وگرنه ممکن است اشیاء زندهای را به اشتباه حذف کند.
راهحل اول: مجموعههای یادآوری (Remembered Sets)
بهجای اسکن کل حافظه، GC فقط آدرسهای اشیائی را که ممکن است شامل اشارهگرهای بین نسلی باشند ذخیره میکند. بهجای ثبت مقصد اشارهگرها، فقط مبدا آنها ذخیره میشود. چون اگر شیء مقصد جابهجا شود، GC باید آدرس مبدا را بهروزرسانی کند!
چگونه کار میکند:
وقتی یک شیء در نسل قدیمی به یک شیء در نسل جوان اشاره کند، این آدرس در مجموعهی یادآوری ثبت میشود. وقتی GC نسل جوان را اجرا میکند، بهجای اسکن کل هیپ، فقط این آدرسها را بررسی میکند. این باعث افزایش کارایی میشود، چون نیاز نیست کل حافظه را اسکن کنیم!
مزایا:
- حذف نیاز به اسکن کل حافظه
- افزایش سرعت GC در جمعآوری نسلهای جوان
معایب:
- ممکن است شامل اشارهگرهای قدیمی و غیرضروری هم شود.
- نیاز به مکانیزمی برای حذف ورودیهای نامعتبر دارد.
راهحل دوم: مانع نوشتن (Write Barrier)
هر تغییری در اشارهگرها را در لحظهی وقوع ثبت میکند، نه در زمان اجرای GC. یک قطعه کد که در لحظهی نوشتن یک اشارهگر جدید اجرا میشود و بررسی میکند که آیا باید این اشارهگر را ثبت کنیم یا نه. اگر اشارهگر از یک نسل قدیمی به یک نسل جدید اشاره کند، باید در مجموعهی یادآوری ثبت شود.
چگونه کار میکند:
در هر نوشتن جدید در حافظه، بررسی میشود که آیا اشارهگر بین نسلها حرکت کرده یا نه. اگر بله، این اشارهگر در مجموعهی یادآوری ذخیره میشود.
مزایا:
- GC فقط روی تغییرات جدید تمرکز میکند، نه روی کل هیپ.
- مقدار دادههایی که GC باید بررسی کند کاهش پیدا میکند.
معایب:
- اجرای این مانع نوشتن، باعث افزایش بار روی پردازنده میشود.
- برای بعضی زبانهای برنامهنویسی که پشتیبانی سختافزاری ندارند، ممکن است مشکلساز شود.
بررسی جهت اشارهگرها (Pointer Direction)
چرا مهم است:
همهی اشارهگرها نیازی به ثبت ندارند. اگر یک شیء در نسل جدید به یک شیء در نسل قدیمی اشاره کند، نیازی به ثبت آن اشارهگر نداریم. اما اگر یک شیء قدیمی به یک شیء جدید اشاره کند، آن اشارهگر مهم است و باید ذخیره شود!
چگونه کار میکند:
وقتی GC اجرا میشود، فقط اشارهگرهای "قدیمی → جدید" را بررسی میکند. این کار باعث کاهش شدید تعداد اشارهگرهای ذخیرهشده میشود.
مثال:
اگر یک شیء در نسل جدید به یک شیء در نسل قدیمی اشاره کند، GC نیازی به بررسی آن ندارد. اما اگر یک شیء در نسل قدیمی به یک شیء در نسل جدید اشاره کند، این اشارهگر باید ثبت شود.
مدیریت فضای حافظه در GC نسلگرا
تا اینجا فهمیدیم که در GC نسلگرا، نسلهای جوان معمولاً با کپی کردن اشیاء زنده به یک فضای جدید مدیریت میشوند. اما نسلهای قدیمی چطور مدیریت میشوند؟
نسلهای جوان خیلی سریع و با نرخ بالا، جمعآوری میشوند چون بیشتر اشیاء جوان زود از بین میروند. اما نسلهای قدیمی باید کمتر و به روشهای متفاوتی مدیریت شوند؛ چون بیشتر دادههای آنها زنده میمانند. مدیریت ضعیف نسل قدیمی میتواند باعث تکهتکه شدن حافظه و کاهش عملکرد سیستم شود!
چرا مدیریت نسل قدیمی سختتر است
- حجم بالای اشیاء زنده: برخلاف نسل جوان، که بیشتر اشیاء آن زود حذف میشوند، در نسل قدیمی، حجم زیادی از اشیاء زنده باقی میماند.
- تکهتکه شدن حافظه (Fragmentation): در روش Mark-Sweep، اشیاء حذفشده حفرههایی در حافظه ایجاد میکنند که باعث کاهش بهرهوری میشود.
- هزینه بالای جابهجایی: روش Copying Collection در نسلهای جوان خیلی سریع و کارآمد است، ولی برای نسلهای قدیمی باعث اتلاف حافظه و افزایش هزینه میشود.
- نیاز به فشردهسازی (Compaction): برای جلوگیری از تکهتکه شدن، گاهی باید دادههای زنده را فشردهسازی کرد که هزینه دارد.
روشهای مدیریت نسل قدیمی
روش 1: Semispace Copying (کپیبرداری دونیمهای)
در این روش، حافظهی نسل قدیمی به دو نیمهی مساوی تقسیم میشود. در هر اجرای GC، تمام اشیاء زنده به نیمهی دیگر کپی میشوند و نیمهی قبلی کاملاً پاک میشود.
مشکل: نصف فضای هیپ همیشه خالی میماند، پس حافظهی زیادی هدر میرود!
این روش معمولاً برای نسلهای جوان که نرخ مرگومیر بالایی دارند مناسبتر است.
روش 2: Mark-Sweep (نشانهگذاری و جاروب)
GC تمام اشیاء زنده را نشانهگذاری (Mark) میکند و بعد اشیاء غیرزنده را حذف (Sweep) میکند.
برتری: نیازی به جابهجایی اشیاء زنده نیست، پس اتلاف حافظهی کمتری نسبت به روش Copying دارد.
مشکل: این روش به مرور زمان باعث تکهتکه شدن حافظه میشود چون فضای خالی بین اشیاء زنده باقی میماند.
روش 3: Mark-Compact (نشانهگذاری و فشردهسازی)
نسخهی بهبودیافتهی Mark-Sweep که در آن، پس از حذف اشیاء غیرزنده، اشیاء زنده به هم فشرده میشوند.
برتری: از تکهتکه شدن حافظه جلوگیری میکند.
مشکل: این کار هزینهی بالایی دارد، چون باید کل حافظه را دوباره مرتب کرد.
بهینهسازیهای مدیریت فضا
چطور میتوانیم کارایی GC را در نسلهای قدیمی افزایش بدهیم:
1. ترکیب روشهای مختلف
بعضی GCها از ترکیب روشهای Copying و Mark-Sweep استفاده میکنند!
مثلاً: در ابتدا از Mark-Sweep استفاده میشود، ولی اگر حافظه خیلی تکهتکه شود، یک مرحله فشردهسازی (Compaction) هم انجام میشود.
2. تغییر دینامیک بین کپیبرداری و نشانهگذاری
اگر فضای کپیبرداری کافی نباشد، GC بهجای کپی، نشانهگذاری و فشردهسازی انجام میدهد. این باعث میشود که کمبود حافظه مشکلی ایجاد نکند و GC انعطافپذیرتر شود.
3. فشردهسازی دادههای بسیار قدیمی
اشیائی که خیلی وقت زنده ماندن را در پایین حافظه فشرده کنیم، تا همیشه در جای ثابتی بمانند.
الگوریتم "Beltway" در جمعآوری زباله (Garbage Collection)
Beltway یک چارچوب (Framework) انعطافپذیر برای مدیریت حافظه است که میتواند مثل انواع مختلف جمعآوری زباله رفتار کند! در این روش، حافظه به چندین "کمربند" (Belt) و "افزودهها" (Increment) تقسیم میشود. هر کمربند شامل تعدادی "افزوده" (Increment) هست، که مثل سینیهایی روی کمربند حرکت میکنند. افزودهها اول-ورود، اول-خروج (FIFO) پردازش میشوند، یعنی اول قدیمیترین بخش پردازش میشود. جمعآوری در هر کمربند مستقل انجام میشود، اما معمولاً اول از کمربندهای جوانتر شروع میکنیم. اشیاء زنده (Survivors) میتوانند درهمان کمربند یا کمربند بعدی قرار بگیرند.
Beltway چطور کار میکند
در Beltway GC، واحد پردازش "افزوده" (Increment) نام دارد و افزودهها در صفهایی به نام "کمربند" (Belt) گروهبندی میشوند.
1. حافظه به چند "کمربند" تقسیم میشود (Belt 0, Belt 1, ...)
2. هر کمربند شامل چندین "افزوده" هست که در دادهها نگهداری میشوند.
3. هنگام اجرای GC، اول قدیمیترین افزوده روی کمربند جوانتر پردازش میشود.
4. اشیاء زنده میتوانند یا در همان کمربند بمانند یا به کمربند بعدی منتقل شوند(Promotion).
تفاوت با GC نسلگرا:
در GC نسلگرا (Generational GC)، هر نسل بهطور کامل پردازش میشود.ولی در Beltway، هر افزوده بهصورت مستقل پردازش میشود!
مدلهای مختلف Beltway GC
1. نیمفضایی (Semispace Collector)
فقط یک کمربند دارد. دو افزوده در این کمربند هست (یک برای تخصیص، یکی برای جمعآوری). تمام اشیاء زنده به افزودهی دوم منتقل میشوند. روش سنتی جمعآوری کپیکننده (Copying Collector).
2. جمعآوری نسلگرا (Generational GC)
هر نسل یک کمربند جداگانه دارد! Belt 0 برای نسل جوان (Young Generation) Belt 1 برای نسل قدیمی (Old Generation) مشابه GC نسلگرا، ولی افزودهها بهصورت مستقل پردازش میشوند.
3. الگوریتم Appel
Belt 0 فضای جوانترین اشیاء ر نگه میدارد. کمربندهای بعدی برای اشیاء طولانیعمر هستند. افزودهها تا جایی که حافظه اجازه بدهد، رشد میکنند.
4. Renewal-Older-First و Deferred-Older-First
میتوانیم از Beltway برای مدلهای جمعآوری قدیمیتر-اول (Older-First GC) هم استفاده کنیم.
Renewal-Older-First: هر بار قدیمیترین بخش از کمربند پردازش میشود و اشیاء زنده به ابتدای حافظه منتقل میشوند.
Deferred-Older-First: "پنجرهی سنی" روی کمربند حرکت میکند تا کمترین اشیاء زنده را پیدا کند.
چالشهای پیادهسازی Beltway
1. نیاز به "Write Barrier" پیشرفته
چون Beltway افزودهها را جداگانه پردازش میکند، باید تمام اشارهگرهای بین افزودهها را نگه دارد! برای این کار از یک "Write Barrier" که اشارهگرهای مهم را ذخیره کند، استفاده میکنند. اشارهگرهای بین کمربندهای مختلف و بین افزودههای یک کمربند باید بهدرستی مانیتور شوند.
2. مدیریت پیچیدهی محل ذخیرهی اشیاء زنده
Beltway باید تصمیم بگیرد که اشیاء زنده را درهمان کمربند نگه دارد یا به کمربند بعدی بفرستد. این تصمیم تأثیر زیادی روی عملکرد GC دارد.
3. حساسیت به تنظیمات
انتخاب اندازهی مناسب افزودهها و کمربندها تأثیر مستقیمی روی عملکرد دارد. Beltway باید تعادل بین فضا و زمان پردازش را حفظ کند.