گاربج کالکشن و الگوریتم mark-sweep

مقدمه:

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

برای فهم بهتر به برسی چند مفهوم پایه ایی زیر نیاز داریم:

۱. حافظه:
به هر وسیله که توانایی نگهداری اطلاعات را داشته باشد، حافظه می‌گویند. کلیه دستورالعمل‌ها و داده‌ها، برای این که مورد اجرا و پردازش قرار گیرند، نخست باید به حافظه اصلی منتقل گردند و نتایج پردازش نیز به آنجا فرستاده شود. حافظه اصلی از جنس نیمه رسانا (الکترونیکی) است و در نتیجه، سرعت دسترسی به اطلاعات موجود در آن‌ها در مقایسه با انواع حافظه جانبی که به صورت مکانیکی کار می‌کنند بالاست و قیمت آن نیز گران‌تر است اما در مقابل حافظه‌هایی، که به پردازنده نزدیک‌تر هستند و از ظرفیت کمتری برخوردارند مانند ثبات (Register) و Cache گران‌تر و از سرعت دسترسی بالاتری بهره می‌برند.
در RAM پردازنده می‌تواند هم بنویسد و هم از آن‌ بخواند. به‌طور کلی، برنامه‌ها، دستورالعمل‌ها، و داده‌هایی در این حافظه قرار می‌گیرند که پردازشگر بخواهد بر روی آن‌ها کاری انجام دهد.

۲.چرخه زندگی حافظه:
این تعریف در حالت کلی به نوع زبان مورد استفاده وابستگی ندارد و عموما به شکل زیر برسی می‌شود:

1. تخصیص حافظه:
   حافظه توسط سیستم عامل برای استفاده در برنامه ها رزرو می‌شود که در زبان های سطح پایین این روند به صورت دستی توسط دولوپر انجام شده و در زبان های سطح بالا کنترل روند به صورت اتوماتیک است.
   
2. استفاده از حافظه:
   استفاده برنامه در حال توسعه از حافظه رزرو شده توسط سیستم عامل.
   
3. آزادسازی حافظه:
   آزاد کردن و در دسترس قرار دادن حافظه مورد استفاده.
   

استفاده از الگوریتم Mark-Sweep:

این الگوریتم خود شامل ۲ قسمت زیر است:
۱. mark phase
وقتی که یک شی ایجاد می‌شود، فلگ آن صفر می‌شود.
در مرحله علامت‌گذاری، مقدار علامت‌گذاری شده برای تمام اشیا قابل‌ دسترس را یک می‌کند.
حالا برای انجام این مرحله نیاز است که پیمایش گراف را انجام دهیم آن هم به صورت عمق اول جستجو (DFS).
می‌توانیم هر شی را به صورت یک نود در نظر بگیریم و بعد تمامی گره‌ها (اشیا) که از این نود قابل‌ دسترسی هستند (شی) تا زمانی که تمامی نود های قابل‌ دسترسی را بازدید نماییم.
یک ریشه داریم که خود متغیری است که به یک شی اشاره می‌کند و مستقیما توسط متغیر محلی در دسترس قرار دارد.

Mark(root)
    If markedBit(root) = false then
        markedBit(root) = true
        For each v referenced by root
             Mark(v)

ر
۲. sweep phase:
تمام آن اشیایی که مقدار مشخص آن‌ها صفر است، از حافظه هیپ و برای باقی اشیا در دسترس که بیت مشخص‌ شده یک است، پاک می‌شود.
حالا مقدار برای تمام اشیا قابل‌ دسترس صفر می‌شود، و اگر لازم باشد دوباره از مرحله mark شروع می‌کنیم تا تمام اشیا قابل‌ دسترس را علامت‌گذاری کنیم.

Sweep()
For each object p in heap
    If markedBit(p) = true then
        markedBit(p) = false
    else
        heap.release(p)

معایب الگوریتم: برنامه در حین اجرای الگوریتم GC از حالت اجرای نرمال در می آید و پس از تکرار فاز های متعدد Mark & Sweep در انتها اشیاء قابل دسترسی توسط بخش های کوچک استفاده نشده از حافظه
از هم دیگر جدا می شوند و در نتیجه موجب پراکندگی می‌شود.<br/>

خطا ها و ایرادات احتمالی گاربج کالکتور:

۱. عملکرد غیرقابل‌پیش‌بینی:
GC باید کل برنامه را در بعضی موارد متوقف کند و همچنین زمان مشخصی برای جمع کردن حافظه و تخصیص آن ندارد.

۲. مقیاس پذیری:
GC بر خلاف قانون مور است و هنگام بزرگ‌تر شدن کامپیوتر ها به مشکل می‌خورد.

۳. استفاده از منابع:
زبان‌های دارای GC اتوماتیک از ۱۰ برابر مقدار RAM برای حل مشکلات استفاده می‌کنند.

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

۵. عملکرد تخریبی:
نه تنها از منابع CPU استفاده می‌کند، بلکه چندین لایه از حافظه نهان را محدود می‌کند و آن را تحت‌تاثیر قرار می‌دهد.