تقسیمبندی هیپ (Partitioning the Heap) در مدیریت حافظه
چرا هیپ را تقسیمبندی کنیم؟
- کاهش سربار حافظه
- افزایش سرعت جمعآوری زباله
- کاهش زمان توقف (Pause Time) برای جمعآوری زباله
- بهبود locality و عملکرد کش
- مدیریت بهتر اشیایی که نمیتوان آنها را جابهجا کرد
چطور انجام میشود؟
- تقسیم اشیاء بر اساس قابلیت جابجایی
- تقسیم اشیاء بر اساس اندازه
- تقسیم اشیاء بر اساس نوع (Type-based Segmentation)
- تقسیم اشیاء برای بهینهسازی عملکرد حافظه نهان (Cache Locality)
- تقسیم اشیاء بر اساس قابلیت تغییرپذیری (Mutability)
تقسیمبندی بر اساس قابلیت جابجایی (Mobility)
بعضی از اشیاء را نمیتوانیم جابهجا کنیم چون:
در کدهای بومی (Native Code) استفاده میشوند.
به سیستمعامل (مثل بافرهای I/O) داده شدهاند.
به کتابخانههایی که انتظار GC ندارند پاس داده شدهاند.
راهحل
جدا کردن این اشیاء در یک بخش غیرقابل جابهجایی از هیپ و برای بهروزرسانی رفرنسها، از هندلها (Handles) یا رفرنسهای غیرمستقیم استفاده کنیم.
تقسیمبندی بر اساس اندازهی اشیاء (Size-based Segmentation)
جابجا کردن اشیای بزرگ، هزینهی زیادی دارد.
راهحل
ایجاد یک Large Object Space (LOS) برای اشیاء بزرگ که با Mark-Sweep جمعآوری میشود. برای اشیاء کوچک، میتوانیم از Copying Collector استفاده کنیم که سریعتر است.
تقسیمبندی برای کاهش مصرف حافظه (Space Optimization)
جمعآوری زباله معمولاً نیاز به فضای رزرو شده دارد، مخصوصاً در جمعآوریهایی که از کپی کردن (Copying) استفاده میکنند.
راهحل
مدیریت جداگانهی اشیایی که احتمال زنده ماندنشان بالاست، تا نیاز به فضای رزرو شده کاهش پیدا کند. استفاده از Mark-Compact برای اشیاء پایدار، و Copying برای اشیاء کوتاهعمر.
تقسیمبندی بر اساس نوع اشیاء (Type-based Segmentation)
بعضی از اشیاء ویژگیهای متفاوتی دارند که اگر کنار هم باشند، میتوانند کارایی را کاهش بدهند.
راهحل
اشیای بدون اشارهگر (Pointer-free objects) را جداگانه ذخیره کنیم، چون نیازی به اسکن شدن ندارند! اشیای بزرگی که فقط شامل اشارهگر هستند را جدا کنیم، چون هزینهی بررسی این اشارهگرها بالاست. کدهای ماشین مجازی را جداگانه مدیریت کنیم، چون معمولاً بزرگ و پایدار هستند و نیاز به مدیریت خاص دارند.
تقسیمبندی برای بهینهسازی جمعآوری زباله (Partitioning for Yield)
طبق "فرضیهی نسلها" (Generational Hypothesis) اکثر اشیاء خیلی زود بیاستفاده میشوند، اما بعضی از اشیاء از اول تا آخر برنامه زنده میمانند.
راهحل
ساخت جمعکنندهی نسلمحور (Generational GC) که تمرکز را روی جمعآوری اشیای کوتاهعمر بگذارد. این باعث میشود هزینهی جمعآوری زباله به حداقل برسد، چون فقط بخش کوچکی از هیپ بررسی میگردد.
تقسیمبندی برای کاهش توقف برنامه (Partitioning for Responsiveness)
جمعآوری زبالههای بزرگ باعث متوقف شدن کل برنامه میشود!
راهحل
جمعآوری تدریجی (Incremental GC) که هر بار فقط یک بخش کوچک از هیپ را بررسی میکند. تعیین بخشهایی که میشود فوراً خالی کرد بدون نیاز به بررسی (Scoped Regions).
تقسیمبندی بر اساس locality برای بهبود عملکرد حافظه نهان (Cache Locality)
دسترسی به حافظه به مراتب کندتر از پردازنده است، مخصوصاً اگر دادهها پراکنده باشد.
راهحل
قراردادن اشیایی که اغلب با هم استفاده میشوند در کنار هم. بهینهسازی ترتیب جابجایی اشیاء در Copying Collector برای کاهش Cache Miss.
تقسیمبندی بر اساس نخها (Thread-based Partitioning)
در جمعآوری زباله، باید همهی نخها متوقف شوند که باعث کاهش کارایی میگردد.
راهحل
ایجاد Heap جدا برای هر نخ (Thread-local Heap) که نیاز به همگامسازی (Synchronization) را کاهش بدهد. شناخت و جدا کردن اشیایی که فقط توسط یک نخ استفاده میشوند تا نخها بتوانند مستقلتر حافظه را مدیریت کنند.
تقسیمبندی بر اساس تغییرپذیری (Mutability)
بعضی از اشیاء زیاد تغییر میکنند (مثل متغیرهای موقت)، در حالیکه بعضیها تقریباً ثابت هستند.
راهحل
جداسازی اشیای تغییر پذیر و ثابت. مدیریت اشیای ثابت با Reference Counting (چون کمتر تغییر میکنند) و استفاده از Tracing برای اشیای تغییرپذیر.
چگونه هیپ را تقسیمبندی کنیم؟
چند روش برای تقسیمبندی هیپ وجود دارد که هر کدام مزایا و معایب خاص خودشان را دارند.
روشهای اصلی تقسیمبندی هیپ
1. تقسیمبندی با محدودههای آدرسی جداگانه (Non-overlapping Address Ranges)
در این روش، هر فضای حافظه (Space) یک بخش پیوسته (Contiguous Chunk) از هیپ را اشغال میکند. این روش یکبهیک (One-to-One Mapping) است، یعنی هر فضا یک آدرس مجزا دارد.
مزایا:
سریع و ساده
میشود از مقایسهی سادهی آدرس برای تشخیص فضای شیء استفاده کرد.
معایب:
روی سیستمهای ۳۲ بیتی، ممکن است استفادهی بهینهای از فضای آدرس نداشته باشد.
نیاز به رزرو اولیهی آدرسها دارد که ممکن است فضای آدرس زودتر تموم شود.
مشکل امنیتی: بعضی از سیستمعاملها آدرسهای خاصی را به صورت تصادفی تخصیص میدهند که رزرو آدرسهای پیوسته را سخت میکند.
2. تقسیمبندی با فضاهای ناپیوسته (Discontiguous Spaces)
در این روش، فضاهای حافظه از چندین تکهی جدا از هم (Non-contiguous Chunks) تشکیل شدهاند. بهجای یک فضای پیوسته، این روش از لیستی از فریمهای ثابت اندازه (Fixed-size Frames) استفاده میکند.
مزایا:
انعطافپذیرتر از روش پیوسته
استفادهی بهینهتر از فضای آدرس در سیستمهای ۳۲ بیتی
بهینهتر برای سیستمهایی که از صفحهبندی (Paging) استفاده میکنند.
معایب:
برای پیدا کردن فضای هر شیء، نیاز به یک جدول جستجو (Lookup Table) است.
کمی پیچیدهتر از نظر پیادهسازی و زمان اجرای عملیات.
3. استفاده از بیتهای داخل هدر شیء (Encoding Space in Object Header)
در این روش، چند بیت در هدر شیء برای مشخص کردن فضای آن شیء رزرو میشود. این روش باعث میشود که نیازی به جستجوی آدرسهای حافظه نباشد؛ مثلاً، میتونیم تعیین کنیم که آیا یک شیء متعلق به نسل جوان است (Young Generation) یا متعلق به فضای بالغها (Mature Object Space).
مزایا:
انعطافپذیر
برای اشیائی که ویژگیهای متغیر در زمان اجرا دارند (مثل سن یا اشتراکگذاری بین نخها) عالی است!
معایب:
کمی سربار اضافه به دلیل وجود بیتهای اضافی در هدر شیء.
این روش نیاز دارد که هر بار مقدار این بیتها بررسی شود که ممکن است کمی سربار محاسباتی ایجاد کند.
چالشهای جمعآوری زباله در فضاهای جداگانه
جمعآوری زباله (GC) روی هیپ تقسیمبندیشده چه مشکلاتی دارد؟
1. ناقص بودن جمعآوری زباله
وقتی فقط یک بخش از هیپ جمعآوری شود، ممکن است بعضی از اشیاء غیرضروری در فضاهای دیگه بمانند و بازیافت نشوند.
راهحل: اجرای دورهای جمعآوری زبالهی کامل (Full GC).
2. مشکل حلقههای مرجع بین فضاها
اگه دو شیء در فضاهای مختلف به هم اشاره کنند، ممکن است حلقهی مرجع (Reference Cycle) ایجاد گردد که توسط GC شناسایی نشود!
راهحل: استفاده از مدیریت خاصی مثل Train Algorithm برای شناسایی و حذف حلقههای مرجع.
3. هزینهی انتقال اشیاء بین فضاها
بعضی وقتها لازم است که اشیاء از یک فضا به فضای دیگر منتقل شوند(مثل ارتقاء از نسل جوان به بالغ) که هزینهی پردازشی دارد.
راهحل: استفاده از جداول نگاشت سریع یا تکنیکهای کپی کارآمد (مثل Baker's Treadmill).
یک روش خاص: الگوریتم "قطار" برای مدیریت اشیاء بالغ (Train Algorithm)
در این روش، هیپ به چندین بخش کوچکتر به نام "واگن" تقسیم میشود. اشیای زنده به واگنهای جدید منتقل میشوند و اشیای قدیمیتر به تدریج حذف میشوند. این روش باعث میشود که جمعآوری زبالهی تدریجی (Incremental GC) ممکن شود و نیازی به توقف کل برنامه نباشد.
چه زمانی باید هیپ را تقسیمبندی کنیم؟
تقسیمبندی هیپ (Partitioning) بسته به نوع جمعآوری زباله (Garbage Collection) و نیازهای سیستم میتواند در زمانهای مختلفی انجام شود!
روشهای زمانی برای تقسیمبندی هیپ
1. تقسیمبندی ایستا (Static Partitioning)
در این روش، تقسیمبندی هیپ در زمان کامپایل انجام میشود. کامپایلر بر اساس نوع شیء (Object Type) تصمیم میگیرد که آن شیء در چه فضایی قرار بگیرد.
مثالها:
اگر یک شیء "جاودانه" (Immortal) باشد (مثلاً کانستنتهای برنامه)، کامپایلر میتواند مستقیماً آن را در یک بخش جدا از هیپ قرار بدهد.
اگر یک شیء "کد اجرایی" باشد، ممکن است در یک فضای مخصوص ذخیره شود چون نمیخواهیم آن را جابهجا کنیم.
مزایا:
- سریع
- بهینه برای اشیائی که نیاز به جابهجایی ندارند
- کاهش هزینهی مدیریت در زمان اجرا
معایب:
- انعطافپذیری پایین
- برای همهی اشیاء جواب نمیدهد
2. تقسیمبندی پویا در زمان جمعآوری زباله (Dynamic Partitioning at Collection Time)
جمعکننده زباله (GC) تصمیم میگیرد که چه زمانی یک شیء را از یک فضا به فضای دیگر منتقل کند. معمولاً در طی اجرای GC، اشیائی که بیشتر زنده ماندن، به نسلهای قدیمیتر منتقل میشوند (Promotion).
مثالها:
- جمعآوری زبالهی نسلگرا (Generational GC) که اشیاء را بر اساس سنشان تقسیمبندی میکند.
- مدیریت اشیائی که به دلیل وابستگی به کد بومی (Native Code) نباید جابهجا شوند.
مزایا:
- بهینه برای برنامههایی که عمر اشیاء در آنها متفاوت است
- کاهش سربار پردازشی GC با تمرکز روی اشیا کوتاهعمر
معایب:
- هزینهی اضافی هنگام انتقال اشیاء
- نیاز به الگوریتمهای پیچیده برای مدیریت فضا
3. تقسیمبندی در زمان تخصیص (Partitioning at Allocation Time)
در این روش، تخصیصدهنده حافظه (Allocator) تصمیم میگیرد که شی در چه فضایی قرار بگیرد. تخصیصدهنده میتواند بر اساس اندازهی شیء، نوع شیء، یا سایر فاکتورها این تصمیم را بگیرد.
مثالها:
- قرار دادن اشیاء بزرگ در فضای جداگانهی Large Object Space (LOS)
- مدیریت حافظه در سیستمهایی که از مناطق تخصیص صریح استفاده میکنند (Explicit Memory Regions)
- Thread-local allocation برای قرار دادن اشیاء یک نخ در یک هیپ محلی
مزایا:
- افزایش کارایی و کاهش تأخیر در تخصیص حافظه
- بهینه برای برنامههای چند نخی و سروری
معایب:
- نیاز به تنظیمات و پیکربندی مناسب
- ممکن است سربار مدیریت حافظه را افزایش بدهد
4. تقسیمبندی در زمان اجرا (Partitioning at Runtime)
در این روش، خود برنامه (Mutator) تصمیم میگیرد که چه زمانی و چگونه یک شی به فضای جدید منتقل شود. معمولاً در سیستمهای اجرای همزمان (Concurrent GC)، این فرآیند به وسیلهی موانع خواندن/نوشتن (Read/Write Barriers) انجام میشود.
مثالها:
- مدیریت اشیاء قابل اشتراکگذاری بین نخها (Thread-local vs Shared Objects)
- همکاری بین سیستمعامل و جمعکننده زباله برای تغییر تخصیص صفحات حافظه
مزایا:
- افزایش انعطافپذیری
- بهینه برای سیستمهای چند نخی و توزیعشده
معایب:
- پیچیدگی بیشتر در پیادهسازی
- نیاز به موانع اضافی برای هماهنگی دسترسیها