تعادل بار در جمعآوری زبالهی موازی (Load Balancing in Parallel GC)
"تعادل بار" یعنی مطمئن شویم که همهی پردازندهها تقریباً مقدار برابری از کار را انجام میدهند، بدون اینکه به همدیگر وابسته باشند و زیاد هماهنگسازی لازم داشته باشند. ولی مشکل اینجاست که "تعادل بار" و "حداقل کردن هماهنگی بین پردازندهها" معمولاً باهم در تضاد هستند!
مشکل تعادل بار در GC موازی
اگر پردازندهها بار کاری متعادلی نداشته باشند، بعضیها تمام میکنند و منتظر میمانند، در حالیکه بقیه هنوز مشغول هستند! بدون تعادل بار خوب، GC موازی عملاً مثل GC تکپردازندهای کار میکند!
راهحل کلی:
باید کارها را طوری تقسیم کنیم که همه پردازندهها بهطور مساوی درگیر شوند.
روشهای تقسیم بار استاتیک (Static) و داینامیک (Dynamic) داریم!
روشهای تعادل بار در GC موازی
روشهای استاتیک (Static Load Balancing)
در این روش، قبل از شروع چرخهی GC، کار را به پردازندهها تقسیم میکنیم. سپس هر پردازنده روی بخش خودش کار میکند، بدون نیاز به هماهنگی زیاد با بقیه.
مثال:
در الگوریتم Mark-Compact، میتوانیم حافظه را به N قسمت مساوی تقسیم کنیم و هر پردازنده فقط روی بخش خودش "Compaction" انجام بدهد.
مشکل اصلی:
این روش همیشه خوب جواب نمیدهد، چون تعداد اشیای زنده در هر بخش ممکن است متفاوت باشد! ممکن است یک پردازنده زودتر کارش تمام شود، درحالیکه بقیه هنوز مشغول باشند!
روشهای دینامیک (Dynamic Load Balancing)
تقسیم کار حین اجرا!
بهجای اینکه از قبل همه چیز را تقسیم کنیم، هر پردازنده میتواند از یک استخر کار (Work Pool) بردارد و کار جدید به آن اضافه شود.
چرا این روش بهتر است؟
باعث میشود که پردازندههایی که زودتر کارشان تمام میشود، بتوانند از کارهای جدید استفاده کنند. اگر تعداد پردازندهها تغییر کند (مثلاً سیستم تحت فشار باشد)، هنوز کار بهینه اجرا میشود!
On-the-Fly Marking در GC همزمان
On-the-Fly Marking دقیقاً برای این طراحی شده است که GC بتواند بدون توقف کامل برنامه، اشیای زنده را علامتگذاری (Mark) کند.
در روشهای سنتی مثل Stop-the-World (STW)، تمام نخهای برنامه باید متوقف شوند تا GC بتواند کل استک (Stack) را اسکن کند.
اما در On-the-Fly، این اتفاق نمیافتد. بلکه:
هر نخ (Mutator) به صورت جداگانه و مستقل بررسی میشود.
GC با هر نخ، یک "Soft Handshake" انجام میدهد، نه یک توقف سراسری.
GC فقط بخش فعال Stack هر نخ را بررسی میکند، نه کل Stack.
برخی موانع نوشتن (Write Barriers) بهکار میروند تا از مشکلات همزمانی جلوگیری شود.
فرآیند On-the-Fly Marking
۱. Soft Handshake: مکالمه نرم بین GC و هر نخ
- GC از هر نخ درخواست میکند که در یک نقطهی امن (Safepoint) بایستد.
- این توقف کوتاه و مستقل برای هر نخ انجام میشود.
- هنگام توقف، GC فقط بالاترین فریم Stack نخ را بررسی میکند.
- بعد از بررسی، نخ آزاد میشود و نخ بعدی بررسی میشود.
۲. استفاده از Write Barriers برای همزمانی
- در GCهای معمولی، یک Write Barrier (مانع نوشتن) برای جلوگیری از مشکلات همزمانی وجود دارد.
- اما در On-the-Fly Marking، علاوه بر Write Barrier، یک Insertion Barrier هم استفاده میشود.
- این موانع تضمین میکنند که اشیای جدید که هنوز اسکن نشده اند، گم نشوند.
چرا Write Barrier کافی نیست؟
چون در On-the-Fly، برخی نخها هنوز اسکن نشدهاند، ولی ممکن است حافظهی Heap حاوی اشیای سیاه (Black) باشد!
۳. انتقال از فاز Sync1 به Sync2 برای جلوگیری از مشکلات همزمانی
مشکل همزمانی در GC:
در حین اجرای GC، ممکن است یک نخ هنوز در فاز قبلی (قبل از شروع GC) باشد، ولی نخ دیگری وارد فاز جدید شده باشد! این تفاوت زمانی میتواند باعث شود برخی اشیاء به اشتباه از بین بروند یا درست علامتگذاری نشوند!
مانع ارجاعی بروکس (Brooks’s Indirection Barrier)
یکی از چالشهای اصلی در جمعآوری زباله (Garbage Collection) به روش کپیسازی همزمان (Concurrent Copying) این است که چطور کاری کنیم تا mutator (کدی که برنامه را اجرا میکند و اشیا را تغییر میدهد) بدون نگرانی از این که کدام شیء کپی شده یا نه، به کارش ادامه بدهد.
بروکس (Brooks, 1984) یک راهحل جالب پیشنهاد داد. اگه هر شیء، چه در from-space (فضایی که اشیاء از آن کپی میشوند) و چه در to-space (فضایی که اشیاء به آن کپی میشوند)، یک اشارهگر ارجاعی (Forwarding Pointer) داشته باشد، دیگر لازم نیست mutator برای هر دسترسی بررسی کند که آیا شیء به to-space کپی شده یا نه.
اگر یک شیء هنوز کپی نشده باشد، اشارهگر ارجاعیاش به خودش اشاره میکند. اما به محض این که شیء به to-space کپی شود، این اشارهگر ارجاعی به نسخهی جدید در to-space تغییر میکند.
یعنی:
اگر شیء هنوز کپی نشده باشد، اشارهگر آن به خودش اشاره میکند.
اگر کپی شده باشد، اشارهگر آن به نسخهی جدید در to-space اشاره میکند.
فایدهی اصلیاش این است که mutator دیگر نیازی ندارد وضعیت شیء را چک کند و همیشه یک اشارهگر قابلاعتماد دارد. به عبارت دیگر، مانع خواندن (Read Barrier) سادهتر میشود و نیازی نیست برای هر خواندن چک کنیم که آیا شیء هنوز در from-space است یا به to-space منتقل شدهاست.
اما یک مشکل هم داریم! چون mutator بدون توجه به موججلو (Wavefront) عمل میکند، ممکن است یک شیء در from-space باقی بماند درحالیکه اشارهگرهای mutator به آن اشاره میکنند. بنابراین، برای اطمینان از این که همه چیز درست کار کند، بروکس از مانع نوشتن سبک دایکسترا (Dijkstra-style Write Barrier) استفاده کرد.