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

در روش‌های Tracing GC که قبلاً دیدیم، باید کل گراف اشیاM را از ریشه‌های زنده (Roots) دنبال می‌کردیم تا بفهمیم چه اشیایی هنوز استفاده می‌شوند و چه اشیایی Garbage هستند. ولی در روش Reference Counting، هر شیء یک شمارنده‌ی مرجع (Reference Count) دارد که نشان می‌دهد چند اشاره‌گر (Pointer) به آن شیء اشاره می‌کنند. اگر این مقدار به صفر برسد، یعنی هیچ‌کس به این شیء نیاز ندارد و می‌توانیم آن را آزاد کنیم (Free).

برخلاف Tracing GC که معمولاً باید یک مرحله Stop-the-World اجرا شود، در Reference Counting هر وقت یک شیء غیرقابل دسترسی شد، بلافاصله آزاد می‌شود. این ویژگی باعث می‌شود که سیستم در حافظه‌های تقریباً پر، بهتر عمل کند، چون نیازی نیست که تا لحظه‌ی بحرانی صبر کند.

مثال:

فرض کنید یک برنامه‌ی مالتی‌تسکینگ داریم که می‌خواهد در یک محیط با حافظه‌ی کم اجرا شود. اگر از Mark-Sweep GC استفاده کنیم، باید کلی حافظه مصرف شود تا بعداً آزاد گردد. اما Reference Counting می‌تواند به محض اینکه اشیایی بی‌استفاده شدند، آنها را بلافاصله حذف کند.

در روش Tracing GC باید بدانیم ریشه‌ها (Roots) چه هستند تا بتوانیم اشیای زنده را پیدا کنیم. ولی در Reference Counting، هر شیء خودش می‌داند که زنده هست یا خیر، چون با شمارش مرجع کنترل می‌شود.

در زبان‌هایی مثل ++C و Rust که Garbage Collector ندارند، از Reference Counting برای مدیریت حافظه استفاده می‌شود.

اگر برنامه‌ای داشته باشیم که در هر لحظه فقط تعداد کمی شیء زنده دارد و باقی حافظه به سرعت آزاد می‌شود، روش Reference Counting می‌تواند کارایی بالاتری داشته باشد. در برخی سناریوها، Mark-Sweep GC ممکن است اشیاء را دیرتر از حد نیاز حذف کند، ولی Reference Counting بلافاصله این کار را انجام می‌دهد.

در این روش، هر تغییری در اشاره‌گرها باید شمارنده‌ی مرجع را به‌روز کند، که این یعنی:

این عملیات، حتی در دسترسی‌های خواندنی ساده هم رخ می‌دهد، که باعث افزایش تعداد Memory Writeها و کاهش کارایی کش (Cache Performance) می‌شود.

نتیجه:

در زبان‌هایی که عملکرد مهم است (مثل جاوا و #C)، روش Tracing GC معمولاً بهتر از Reference Counting عمل می‌کند؛ چون به‌جای هر تغییر، فقط در زمان GC پردازش انجام می‌شود.

بزرگ‌ترین مشکل این روش این است که نمی‌تواند چرخه‌های حافظه را آزاد کند. یعنی اگر دو یا چند شیء به صورت دایره‌ای به هم اشاره کنند، شمارنده‌ی آن‌ها هیچ‌وقت صفر نمی‌شود و حافظه نشت می‌کند (Memory Leak).

مثال:

فرض کنید یک لیست پیوندی دوطرفه (Doubly Linked List) داریم که هر گره به گره‌ی بعدی و قبلی اشاره می‌کند. اگر این لیست دیگر از هیچ جای کد در دسترس نباشد، شمارنده‌ها همچنان غیر صفر باقی می‌مانند و حافظه آزاد نمی‌شود!

برای حل این موضوع برخی پیاده‌سازی‌ها از Weak References (مراجع ضعیف) استفاده می‌کنند که در شمارش مرجع تأثیری ندارد.

اگر چندین Thread همزمان روی یک شیء، عملیات انجام بدهند، باید شمارنده‌ی مرجع، اتمی (Atomic) باشد. این یعنی در یک سیستم چند نخی (Multithreading)، ممکن است نیاز به قفل‌گذاری (Locking) یا عملیات اتمی (Atomic Operations) داشته باشیم که خودش هزینه‌ی بالایی دارد.

در این روش، هر شیء یک فیلد اضافی برای شمارنده‌ی مرجع دارد که باعث افزایش مصرف حافظه می‌شود. در سیستم‌هایی که اشیاء کوچک هستند، این سربار می‌تواند قابل توجه باشد.

مشکل اصلی Reference Counting این است که هر بار که یک اشاره‌گر (Pointer) تغییر می‌کند، شمارنده‌ی مرجع آن شیء باید به‌روز گردد. این کار نیاز به عملیات اتمی دارد که می‌تواند کش CPU را آلوده کند (Cache Pollution) و باعث کاهش کارایی گردد.

اما Deferred Reference Counting یک راه حل هوشمندانه دارد:

این روش بین دو نوع متغیر اشاره‌گر تفاوت قائل می‌شود:

وقتی که یک شیء ممکن است حذف گردد (یعنی شمارنده‌ی مرجعش صفر شود)، ما بلافاصله آن را حذف نمی‌کنیم! بلکه آن را در جدول شمارنده صفر (ZCT) ذخیره می‌کنیم تا در یک مرحله‌ی جمع‌آوری بررسی شود.

فرآیند Deferred Reference Counting در چند مرحله

1. زمانیکه یک شیء درون Heap ذخیره می‌شود:

شمارنده‌ی مرجع شیء جدید افزایش پیدا می‌کند. اگر شمارنده‌ی مرجع شیء قدیمی صفر باشد، به ZCT اضافه می‌شود اما هنوز حذف نمی‌شود.

2. وقتی‌که نیاز به جمع‌آوری زباله (Garbage Collection) داریم:

تمام اشیای موجود در ZCT بررسی می‌شوند تا ببینیم که آیا واقعاً باید حذف شوند یا خیر. اگر شیء هنوز یک اشاره‌گر از استک داشته باشد، یعنی هنوز زنده است و نباید حذف گردد. اگر هیچ اشاره‌گری به شیء نباشد، آن را حذف می‌کنیم.

3. در نهایت:

شمارنده‌ی مرجع تمام اشیایی که از استک پیدا کردیم، دوباره اصلاح می‌شود. اگر بعد از این مرحله، شیء‌ای باقی بماند که شمارنده‌ی مرجعش صفر است، حذف می‌گردد.

هنوز نیاز به یک مرحله‌ی توقف (Stop-the-world Pause) برای جمع‌آوری اشیای زباله داریم. نیاز به مدیریت یک جدول اضافه (Zero Count Table - ZCT) داریم که می‌تواند کمی هزینه‌بر باشد. جمع‌آوری زباله هنوز باید مطمئن شود که هیچ اشاره‌گر مخفی‌ای به شیء وجود ندارد. اما در کل، این روش هنوز هم از Reference Counting معمولی خیلی سریع‌تر است!

درست است که Deferred Reference Counting هزینه‌ی شمارش ارجاعات (Reference Counting) برای متغیرهای محلی (Stack/Registers) را کاهش می‌دهد، اما هنوز یک مشکل اساسی باقی می‌ماند:

وقتی یک شیء چندین بار تغییر می‌کند، باید شمارش ارجاع برای هر تغییر، به‌روزرسانی شود. Coalesced Reference Counting این مشکل را حل می‌کند!

به‌جای اینکه هر تغییر اشاره‌گر فوراً اعمال شود، فقط وضعیت اولیه و نهایی یک فیلد ذخیره می شود. یعنی تمام تغییرات وسط نادیده گرفته می‌شوند چون در نهایت، فقط آخرین مقدار اشاره‌گر مهم است. این روش باعث می‌شود که عملیات‌های غیرضروری روی شمارنده‌های مرجع حذف شوند.

1. زمانیکه یک شیء تغییر می‌کند:

2. در پایان یک Epoch (دوره‌ی اجرای برنامه):

مثال

فرض کنید یک شیء A داریم که یک اشاره‌گر به C دارد. در طی اجرای برنامه، این اشاره‌گر به D تغییر می‌کند.

در روش معمولی، باید برای هر تغییر دو عملیات انجام شود:

A → C (RC_C = +1)

A → D (RC_C = -1, RC_D = +1)

یعنی برای هر تغییر، شمارنده‌ی C کم و شمارنده‌ی D زیاد می‌شود.

اما در Coalesced Reference Counting، فقط مقدار اولیه و مقدار نهایی مهم هستند:

C به D تغییر می‌کند → فقط شمارنده‌ی C کاهش و شمارنده‌ی D افزایش پیدا می‌کند.

یعنی تمام مراحل میانی حذف می‌شوند و فقط تأثیر نهایی اعمال می‌شود!

کاهش تعداد عملیات‌ Reference Counting.

کاهش هزینه‌ی پردازشی و بهینه‌سازی عملکرد پردازنده.

افزایش بهره‌وری در پردازش موازی (Multi-threading)، چون نیاز به عملیات‌ اتمی کمتر می‌شود.

کاهش آلودگی کش (Cache Pollution)، چون نیاز به تغییرات مکرر در حافظه کم‌تر می‌شود.

کاهش بار روی Mutator و افزایش کارایی کلی سیستم.

نیاز به توقف‌های موقتی برنامه (Stop-the-world Pauses) برای پردازش Log ها.

افزایش فضای مصرفی برای ذخیره‌ی Log تغییرات.

ممکن است برخی از شمارنده‌ها به‌درستی کاهش نیابند، مگر اینکه به‌دقت مدیریت شوند.

اما در مجموع، این روش باز هم از روش‌های سنتی Reference Counting خیلی سریع‌تر است!

مشکل اصلی Reference Counting این است که اگر چند شیء به صورت حلقه‌ای به هم اشاره کنند، هیچ‌وقت شمارنده‌ی مرجع‌ صفر نمی‌شود، پس جمع‌آوری زباله (Garbage Collection) روی این چرخه‌ها کار نمی‌کند!

که این مشکل در نوع داده‌هایی زیر پیش می آید:

در این روش، Reference Counting زباله‌های معمولی را سریعاً پاک می‌کند، اما یک Tracing Garbage Collector هر از چند گاهی اجرا می‌شود تا چرخه‌ها را تشخیص بدهد و حذف کند.

این روش ترکیب دو مدل مختلف است:

بهینه‌تر از یک Garbage Collector کلی است، اما همچنان به توقف‌های مقطعی نیاز دارد.

ایده این است که اشاره‌گرهایی که باعث ایجاد چرخه می‌شوند، به‌جای Strong Reference، به Weak Reference تغییر کنند.

در این روش:

Strong References نمی‌توانند چرخه ایجاد کنند.

Weak References باعث حفظ شی نمی‌شود، و وقتی همه‌ی Strong Reference‌ها از بین رفتند، شیء می‌تواند جمع‌آوری گردد.

روش Trial Deletion بهترین روش برای مدیریت چرخه‌ها در Reference Counting است.

وقتی یک شیء مشکوک به چرخه وارد می‌شود، یک آزمایش انجام می‌دهیم تا ببینیم اگر همه‌ی اشاره‌گرهای داخلی حذف شوند، آیا شیء همچنان ارجاعی دارد یا خیر.

اگر بعد از حذف همه‌ی اشاره‌گرهای داخلی، هیچ ارجاعی از خارج، به آن شیء باقی نماند، یعنی شیء واقعاً زباله است و می‌توانیم پاکش کنیم!

اگر همچنان ارجاعی از بیرون به شیء باقی مانده بود، آن را به حالت قبل برمی‌گردانیم.

روش Trial Deletion به جای بررسی کل گراف، فقط روی زیرگراف‌های مشکوک به چرخه اجرا می‌شود.

الگوریتم‌های معروف این روش: