www.dntips.ir
مطالب ۳۶۹۴
نویسندگان ۲۷۶
گروه‌های مطالب ۱۰۲۴
نقشه‌های راه ۱۱۹
دوره‌ها ۱۴
اشتراک‌ها ۱۷۹۱۴
عنوان:

‫مدیریت حافظه و جمع‌آوری زباله (Garbage Collection) - قسمت یازدهم


نویسنده: امیر مکارچی
تاریخ: ۱۴۰۳/۱۱/۲۷ ۱۰:۱۰
آدرس: www.dntips.ir
ترتیب پیمایش اشیاء در حافظه

وقتی جمع‌آوری زباله انجام می‌شود، اشیای زنده از fromspace به tospace منتقل می‌شوند. حالا، دو روش اصلی برای این پیمایش وجود دارد:
پیمایش عرضی (Breadth-First Traversal): که توسط الگوریتم Cheney استفاده می‌شود.
پیمایش عمقی (Depth-First Traversal): که توسط روش‌های دیگری مثل Fenichel-Yochelson استفاده می‌شود.

در روش عرضی (BFS)، اشیاء بر اساس سطحی که در گراف اشیاء قرار دارند پردازش می‌شوند. یعنی اول ریشه‌ها پردازش می‌شوند، بعد اشیای فرزندان آن‌ها، بعد نوه‌ها و ...
در روش عمقی (DFS)، ابتدا یک مسیر از ریشه تا پایین‌ترین سطح طی می‌شود، سپس برمی‌گردد و مسیر بعدی را پردازش می‌کند.
BFS باعث می‌شود که اشیای غیرمرتبط (مثلاً "فامیل دور" یا distant cousins) نزدیک هم در حافظه قرار بگیرند که برای دسترسی متوالی پردازنده (mutator) می‌تواند بد باشد!
DFS باعث می‌شود که والدین و فرزندان نزدیک هم در حافظه قرار بگیرند، که باعث بهبود locality و کاهش Cache Miss می‌شود.

چرا Locality مهم است؟
در پردازنده‌های مدرن، زمانیکه داده‌ای از Cache Level 1 (L1) خوانده شود، فقط ۳ تا ۴ سیکل طول می‌کشد.
اما اگه داده‌ای از حافظه‌ی اصلی (RAM) خوانده شود، ممکن است صدها سیکل طول بکشد!
پس هر چقدر اشیاء به هم نزدیک‌تر باشند، دسترسی به آن‌ها سریع‌تر است.

مشکل پیمایش عرضی (BFS) چیست؟
اشیاء در صفحات (Pages) مختلف حافظه پراکنده می‌شوند.
باعث می‌شود Cache Miss زیاد شود که یعنی پردازنده مدام باید داده‌ها را از حافظه‌ی اصلی بخواند.
در نتیجه، عملکرد برنامه افت می‌کند.

تحقیقات نشان داده که در حافظه‌های کوچک، Mark-Sweep عملکرد بهتری دارد، اما در حافظه‌های بزرگ‌تر، Copying Collection با پیمایش صحیح (Depth-First) بهتر است.

الگوریتم Moon’s Approximate Depth-First
Moon در سال ۱۹۸۴ یک الگوریتم بهبود یافته را برای Cheney طراحی کرد. در این روش، به‌جای یک scan pointer، از دو pointer به نام‌های scan و partialScan استفاده می‌شود که باعث می‌شود والدین و فرزندان نزدیک هم قرار بگیرند، در حالیکه هنوز به سبک Cheney (BFS) کار می‌کند. مشکل این روش این است که اشیاء ممکن است دوباره اسکن شوند که باعث کاهش سرعت می‌شود.

initialise(worklist):
    scan ← free
    partialScan ← free

isEmpty(worklist): /* as per Cheney */
    return scan = free

remove(worklist):
    if (partialScan < free)
      ref ← partialScan /* prefer secondary scan */
      partialScan ← partialScan + size(partialScan)
    else
      ref ← scan /* primary scan */
      scan ← scan + size(scan)
      return ref

add(worklist, ref): /* secondary scan on the most recently allocated page */
    partialScan ← max(partialScan, startOfPage(ref))

Copying Collection یکی از روش‌های محبوب برای مدیریت حافظه خودکار (Garbage Collection) است، اما مثل هر تکنیکی، مزایا و معایب خودش را دارد. بیائیم به چند جنبه‌ی کلیدی نگاه کنیم:

تخصیص سریع (Fast Allocation)
در روش Copying Collection، تخصیص حافظه خیلی سریع انجام می‌شود؛ چون فقط کافی است یک pointer جلو برود و فضای جدید را رزرو کند. این به روش Bump Pointer Allocation معروف است که فقط دو عملیات ساده دارد:
  1. بررسی اینکه حافظه کافی هست یا خیر.
  2. افزایش مقدار free pointer به اندازه‌ی شیء جدید.
همچنین در سیستم‌های چند نخی (Multithreading)، هر Thread می‌تواند بافر اختصاصی خودش را برای تخصیص حافظه داشته باشد که نیاز به همگام‌سازی (Synchronization) بین نخ‌ها را کاهش می‌دهد.

استفاده‌ی بهینه از حافظه (Memory Usage)
یکی از بزرگ‌ترین نقاط ضعف Copying GC این است که برای عملکرد مناسب، نیاز به دو برابر حافظه نسبت به سایر الگوریتم‌ها دارد. این یعنی به‌جای استفاده از تمام فضای Heap، فقط نصف آن استفاده می‌شود، چون همیشه باید یک فضای رزرو (Copy Reserve) برای کپی کردن اشیاء داشته باشیم. مقدار حافظه‌ی هدررفته (Wasted Memory) بستگی به نسبت اشیای زنده به کل حافظه (L/M) دارد.
در سیستم‌هایی با حافظه‌ی زیاد، ممکن است مشکل‌ساز نباشد. اما در سیستم‌هایی با حافظه‌ی کم، این روش باعث می‌شود که Garbage Collection بیشتر اجرا گردد و در نتیجه عملکرد سیستم کاهش پیدا کند.

پیچیدگی محاسباتی و عملکرد (Computational Complexity & Performance)
اگه بخواهیم Copying Collection را با Mark-Sweep مقایسه کنیم، باید ببینیم کدام روش کارایی بهتری دارد.
به طور خلاصه:
Copying GC:
  • پیچیدگی زمانی: O(L) (فقط اشیای زنده بررسی و کپی می‌شوند)
  • فضای اضافی مورد نیاز: M/2 (نصف حافظه به عنوان Copy Reserve رزرو می‌شود)
  • تعداد دفعات Garbage Collection بیشتر از Mark-Sweep است، چون فضای کمتری برای تخصیص دارد.

Mark-Sweep GC:
  • پیچیدگی زمانی: O(L + M) (همه‌ی اشیای زنده علامت‌گذاری می‌شوند، سپس کل حافظه بررسی می‌شود)
  • فضای اضافی مورد نیاز: حداقل (Mark Bitmap)
  • Garbage Collection کمتر اجرا می‌شود، اما عملیات Sweep ممکن است طولانی شود.

اگه حافظه‌ی سیستم خیلی بزرگ باشد و حجم اشیای زنده کم، روش Copying GC می‌تواند عملکرد بهتری داشته باشد. اما در سیستم‌های کم‌حافظه، روش Mark-Sweep می‌تواند بهتر باشد، چون نیاز به دو برابر حافظه ندارد.

تاثیر روی Locality و Cache Miss
یکی از مزیت‌های Copying Collection این است که باعث بهبود locality می‌شود. چون اشیا در فضای متراکم و پشت سر هم (Compact Heap) ذخیره می‌شوند، دسترسی به داده‌ها سریع‌تر انجام می‌شود و Cache Miss کاهش پیدا می‌کند. این یعنی برنامه‌ها می‌توانند از بهینه‌سازی‌های Cache پردازنده بهره ببرند.

مشکل جابجایی اشیاء (Moving Objects)
در برخی از سیستم‌ها، جابجا کردن اشیا ممکن نیست.دلایل مختلفی برای این موضوع وجود دارد:
  1. عدم دقت در نوع داده‌ها (Type Accuracy): اگر سیستم نمی‌داند کدام مقدار واقعاً یک اشاره‌گر (Pointer) است، نمی‌تواند آن را به‌روز کند.
  2. کدهای Native یا Unmanaged: بعضی از برنامه‌ها، اشاره‌گرهای خودشان را مستقیماً به کد Native پاس می‌دهند. در این حالت اگر شیء، جابجا شود، اشاره‌گرهای Native خراب می‌شوند.
  3. پیچیدگی به‌روزرسانی اشاره‌گرها: در Garbage Collectorهای هم‌زمان (Concurrent GC)، باید مطمئن شد که همه‌ی اشاره‌گرها به‌طور اتمی آپدیت می‌شوند.
مطالب مشابه