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

عنوان:

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

نویسنده: امیر مکارچی
تاریخ: ۱۴۰۳/۱۱/۲۵ ۲۱:۵۰
آدرس: www.dntips.ir

جمع‌آوری زباله به روش کپی (Copying Garbage Collection)

این روش نیم‌فضایی (Semispace Copying) نام دارد که اولین بار توسط Fenichel و Yochelson در ۱۹۶۹ و بعد توسط Cheney در ۱۹۷۰ توسعه داده شد. در این روش، کل فضای هیپ به دو بخش مساوی تقسیم می‌شود:

Fromspace (فضای قدیمی)
Tospace (فضای جدید)

یعنی اشیای زنده از fromspace به tospace منتقل می‌شوند و در نهایت کل فضای fromspace دور انداخته می‌شود. این باعث می‌شود که هیچ تکه‌تکه شدن حافظه‌ای (Fragmentation) رخ ندهد و ما یک فضای پیوسته، برای تخصیص حافظه داشته باشیم.

مراحل کلی Semispace Copying Collection

initialise(worklist):
    scan ← free

isEmpty(worklist):
    return scan = free

remove(worklist):
    ref ← scan
    scan ← scan + size(scan)
    return ref

add(worklist, ref):
    /*nop*/

تخصیص اولیه:

همه‌ی اشیاء در tospace ذخیره می‌شوند تا فضای fromspace خالی بماند. تخصیص حافظه فقط با افزایش مقدار free pointer انجام می‌شود.

آغاز جمع‌آوری زباله:

فضای fromspace کهنه شده و حالا به عنوان منبع زباله‌ها در نظر گرفته می‌شود. فضای tospace جدیدی تخصیص داده می‌شود و آماده‌ی ذخیره‌ی اشیای زنده می‌شود.

کپی کردن اشیای زنده:

Root Objects (ریشه‌های حافظه مثل متغیرهای سراسری و استک‌ها) بررسی می‌شوند و اگر زنده باشند، به tospace کپی می‌شوند. هر شیء زنده‌ی جدیدی که کپی می‌شود، در لیست خاکستری (Grey List) قرار می‌گیرد.

اسکن کردن شی‌ءهای کپی‌شده:

برای هر شیء خاکستری، تمامی اشاره‌گرها بررسی می‌شوند. اگر اشاره‌گری هنوز به fromspace اشاره کند، شیء موردنظر به tospace منتقل می‌شود و اشاره‌گرها به‌روزرسانی می‌شوند. اگر قبلاً منتقل شده باشد، اشاره‌گر با آدرس جدید شیء در tospace جایگزین می‌شود.

پایان کار:

وقتی تمام اشیای زنده منتقل و اسکن شدند، فضای fromspace کاملاً کنار گذاشته می‌شود. tospace حالا به عنوان فضای جدید استفاده می‌شود.

مزایا و معایب Copying Collection

مزایا:

عدم تکه‌تکه شدن حافظه (No Fragmentation): تمام اشیای زنده به‌صورت متوالی (Contiguous) در حافظه چیده می‌شوند.
تخصیص حافظه‌ی سریع: چون همه‌ی اشیاء پشت‌سر هم قرار می‌گیرند، تخصیص حافظه فقط با افزایش pointer آزاد (Bump Pointer Allocation) انجام می‌شود.
پیاده‌سازی ساده: نیازی به Free List یا ساختارهای پیچیده‌ی تخصیص حافظه نیست.
عدم نیاز به اطلاعات اضافی در هدر اشیاء: برعکس Mark-Compact که یک Forwarding Address نیاز دارد، دراین روش این اطلاعات درون نسخه‌ی قدیمی شیء ذخیره می‌شود.

معایب:

کاهش نصف فضای در دسترس: از کل حافظه‌ی هیپ، فقط ۵۰٪ قابل استفاده است! چون همیشه باید دو فضا داشته باشیم.
افزایش بار پردازشی: تمام اشیای زنده باید هر بار کپی شوند، حتی اگه اصلاً نیازی به حرکت آن ها نباشد.
تأخیر بیشتر در دسترسی به حافظه: پردازش تمام بایت‌های اشیاء در مقایسه با Mark-Sweep که فقط اشاره‌گرها را پردازش می‌کند، سنگین‌تراست.

الگوریتم Cheney برای اجرای Copying Collection

این که هر دفعه لیستی از اشیای زنده بسازیم و همه را پردازش کنیم، خیلی کند به نظر میرسد برای حل این مشکل، Cheney در سال ۱۹۷۰ یه الگوریتم فوق‌العاده را طراحی کرد که نیازی به لیست اضافی ندارد!

روش کار الگوریتم Cheney:

از خود tospace به عنوان یک صف FIFO (First-In, First-Out Queue) استفاده می‌کند. به‌جای ذخیره‌ی لیست جداگانه، از دو Pointer به نام scan و free استفاده می‌کند. scan نشان می‌دهد که کدام شیء دارد پردازش می‌شود و free نشان می‌دهد کجا باید اشیای جدید کپی شوند. وقتی scan به free برسد، یعنی تمام اشیای زنده بررسی شده‌اند و جمع‌آوری زباله تمام شده‌است!

مزیت بزرگ این روش:

بدون نیاز به لیست اضافی، همه‌چیز در خود حافظه مدیریت می‌شود. سرعت پردازش بالاتر، چون فقط یک‌بار بر روی حافظه حرکت می‌کند. مناسب برای سیستم‌های نه‌چندان بزرگ، چون از حافظه‌ی اضافه استفاده نمی‌کند.

مثال: اجرای الگوریتم Cheney برای یک لیست پیوندی

فرض کنیم یک لیست L شامل اشیای A، B، C و E داریم:

قبل از اجرا:

اشیای A، B، C و E در fromspace هستند.

اشاره‌گرهای scan و free به ابتدای tospace اشاره می‌کنند.

کپی کردن ریشه‌ها (L) به tospace:

L منتقل می‌شود و یک آدرس هدایت‌کننده (Forwarding Address) درنسخه‌ی قدیمی ذخیره می‌شود.

scan به L' در tospace اشاره می‌کند.

بررسی اشاره‌گرهای L':

چون L' به A و E اشاره دارد، این دو شی هم کپی می‌شوند.

اشاره‌گرهای جدید جایگزین می‌شوند.

ادامه‌ی پردازش روی A' و E':