حلقه علامتگذاری (Marking Loop) یکی از مراحل اصلی است که طی آن اشیای قابلدسترسی، علامتگذاری میشوند تا مشخص شود کدام اشیاء هنوز مورد استفاده هستند و کدامها قابل جمعآوریاند. زمانی که Garbage Collector در مرحله Marking اجرا میشود، معمولاً یک worklist (لیستی از اشیایی که باید پردازش شوند) را طی میکند و هر شیء را بررسی و علامتگذاری میکند. این فرآیند میتواند منجر به Cache Misses شود، زیرا:
- دسترسی تصادفی به حافظه: اشیای Heap معمولاً بهصورت پراکنده در حافظه قرار دارند. در نتیجه، هنگام پیمایش، پردازنده نمیتواند دادههای موردنیاز را بهطور مؤثر، در کش نگه دارد و مجبور میشود مکرراً از حافظهی اصلی بارگذاری کند.
- حجم بالای دادهها: در برنامههایی که دارای یک Heap بزرگ با تعداد زیادی اشیاء هستند، مقدار دادهای که باید پردازش شود، فراتر از ظرفیت کش پردازنده است و این باعث افزایش Cache Miss میشود.
- عدم محلیّت داده (Poor Locality): پردازندهها برای افزایش عملکرد، دادههای موردنیاز را بهصورت بلوکی در کش نگه میدارند (Spatial Locality). اما اگر اشیاء بهطور پراکنده در حافظه باشند، این مزیت از بین میرود.
در حلقه علامتگذاری، برای بررسی و علامتگذاری هر شیء باید به دادههای حافظه اصلی دسترسی پیدا کنیم. اگه شیء، بدون اشارهگر (Pointer-Free) باشد، نیازی به بارگذاری فیلدهاش نیست. اما وقتی شیء، دارای اشارهگر باشد، دسترسی به فیلدها منجر به کش میس (Cache Miss) میشود. یعنی وقتی پردازنده به دادهای نیاز دارد و آن داده در کش موجود نیست، باید از حافظهی اصلی بازیابی شود که میتواند صدها چرخهی پردازنده طول بکشد.
بهبود الگوریتم علامتگذاری
مشکل اصلی این است که حلقهی علامتگذاری به صورت عمقاول (Depth-First) کار میکند؛ در حالیکه کش لاینها به صورت عرضاول (Breadth-First) بارگذاری میشوند. برای حل این مشکل، میتوانیم از یک صف FIFO در کنار پشته علامتگذاری استفاده کنیم.
روش کار صف FIFO
وقتی شیءای به پشتهی علامتگذاری اضافه میشود، به صف FIFO هم اضافه میشود. وقتی قرار است شیءای برای پردازش برداشته شود، ابتدا از FIFO گرفته میشود. این ترتیب باعث میشود که دادهها قبل از استفاده، در کش بارگذاری شده باشند.
افزودن آیتم (add):
اشارهگرهای جدید (فرزندان گره فعلی) به لیست کاری (worklist) اضافه میشوند. این کار از طریق mark stack انجام میشود (پوش کردن آیتم جدید روی استک).
حذف آیتم (remove):
آیتمی از بالای mark stack برداشته میشود. قبل از پردازش، آدرس آن prefetch میشود تا احتمال cache miss کاهش یابد. این آدرس در یک FIFO buffer قرار داده میشود. سپس، قدیمیترین آیتم از FIFO حذف و پردازش میشود.
add(worklist, item):
markStack ← getStack(worklist)
push(markStack, item)
remove(worklist):
markStack ← getStack(worklist)
addr ← pop(markStack)
prefetch(addr)
fifo ← getFifo(worklist)
prepend(fifo, addr)
return remove(fifo)
الگوریتم Mark-Sweep با اینکه اولین الگوریتم جمعآوری زباله (Garbage Collection) است که در سال 1960 توسط مککارتی معرفی شد، ولی ویژگیهایی دارد که همچنان آنرا برای توسعهدهندهها جذاب میکند. الگوریتم Mark-Sweep به تنهایی سرباری برای عملیات خواندن و نوشتن (Read و Write) روی Mutator ندارد.
اما وقتی به شکل پایه برای سایر الگوریتمهای پیشرفته مثل Generational Collectors یا Concurrent Collectors استفاده شود، نیاز به هماهنگی بین Mutator و Collector پیش میاید. وقتی Mutator، اشارهگرها را تغییر میدهد، باید این تغییرات را به Collector اطلاع بدهد. البته این سربار، خیلی کم است و معمولاً فقط چند درصد از زمان کل اجرا را میگیرد.
وقتی از Lazy Sweeping استفاده شود، این الگوریتم توان عملیاتی خوبی دارد. در فاز علامتگذاری (Mark Phase)، فقط نیاز داریم که یک بیت یا بایت را برای هر شیء زنده تنظیم کنیم، که نسبت به روشهایی مثل Semispace Copying یا Mark-Compact بسیار ارزانتر است. ولی متأسفانه تمام Mutatorها باید متوقف شوند تا Collector اجرا شود که این توقف میتواند در سیستمهای بزرگ، به چند ثانیه یا حتی بیشتر برسد.
Mark-Sweep در استفادهی از فضا، بسیار بهینهتر از Semispace Copying عمل میکند، چون نیاز به تقسیم حافظه به دو بخش برابر ندارد. اگر Mark Bits در هدر اشیاء ذخیره شوند، تقریباً هیچ هزینهای برای فضا ندارد. در صورتیکه از جدول Bitmap جانبی استفاده شود، سربار فضا، بستگی به تنظیمات همترازی (Alignment) دارد. الگوریتمهای غیر فشردهسازی (Non-Compacting) مثل Mark-Sweep یا Reference Counting با مسئله تکهتکه شدن حافظه (Fragmentation) مواجه میشوند. اگه تعداد زیادی شیء زنده نسبت به فضای کل داشته باشیم، Collector مجبور میشود خیلی زود به زود، اجرا شود که باعث میشود برنامه دچار Thrashing شود.
جمعبندی نهایی از Mark-Sweep
این الگوریتم هنوز هم گزینهی خوبی است، بهشرط اینکه محدودیتهایش را در نظر بگیریم. مزیت اصلی این الگوریتم این است که:
- ساده و موثر است.
- سربار کمی روی Mutator دارد.
- فضای حافظه را بهتر از روشهای Copying استفاده میکند.