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

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


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

معرفی الگوریتم‌های فشرده‌سازی


فشرده‌سازی چندریسمانی (Threaded Compaction)
روش Threaded Compaction یک تکنیک هوشمندانه برای فشرده‌سازی حافظه‌است که بر اساس Threading کار می‌کند. تفاوت اصلی آن در این است که بدون نیاز به فضای اضافی در هدر اشیاء، آدرس‌های جدید را ذخیره می‌کند. در مقابل، روش Lisp 2 به یک فیلد اضافه در هدر هر شیء نیاز دارد و روش Two-Finger Compaction اشیاء را به‌صورت تصادفی جابه‌جا می‌کند.

compact():
    updateForwardReferences()
    updateBackwardReferences()

thread(ref):
    if *ref ≠ null
        *ref, **ref ← **ref, ref  /* thread a reference */

update(ref, addr):
    tmp ← *ref
    while isReference(tmp)
        *tmp, tmp ← addr, *tmp
    *ref ← tmp  /* unthread all references, replacing with addr */

updateForwardReferences():
    for each fld in Roots
        thread(*fld)

    free ← HeapStart
    scan ← HeapStart
    while scan ≤ HeapEnd
        if isMarked(scan)
            update(scan, free)  /* forward refs to scan set to free */
            for each fld in Pointers(scan)
                thread(fld)
            free ← free + size(scan)
        scan ← scan + size(scan)

updateBackwardReferences():
    free ← HeapStart
    scan ← HeapStart
    while scan ≤ HeapEnd
        if isMarked(scan)
            update(scan, free)  /* backward refs to scan set to free */
            move(scan, free)  /* slide scan back to free */
            free ← free + size(scan)
        scan ← scan + size(scan)

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

ایده‌ی اصلی نخ‌گذاری (Threading)

مرحله‌ی اول:
اشاره‌گرهای رو به جلو (Forward Pointers) را نخ‌گذاری (Thread) می‌کند. مقدار اصلی فیلد اشاره‌گر را در شیء مقصد ذخیره می‌کند و آدرس جدید را در مکان اصلی قرار می‌دهد. این کار باعث می‌شود که بتوانیم همه‌ی اشاره‌گرهای یک شیء را بعداً پیدا کنیم.

مرحله دوم:
اشاره‌گرهای رو به عقب (Backward Pointers) را به‌روزرسانی می‌کند. اشیای زنده، به محل جدید خودشان منتقل می‌شوند. در نهایت، مقدار اصلی فیلد اشاره‌گر بازگردانی می‌شود.

مثال:
فرض کنید که سه شیء A، B و C در هیپ هستند، و B به C اشاره دارد:
قبل از فشرده‌سازی:
A → B → C
بعد از مرحله اول (نخ‌گذاری):
مقدار اشاره‌گر B که به C اشاره دارد، در C ذخیره می‌شود. مقدار جدیدی در B قرار می‌گیرد که به مکان جدید C اشاره میکند.

بعد از مرحله دوم (انتقال اشیاء):
C به محل جدید منتقل می‌شود و مقدار اصلی اشاره‌گر بازگردانی می‌شود. در نهایت، همه‌ی اشاره‌گرها به آدرس‌های جدید به‌روزرسانی شده‌اند.


مزایا و معایب روش Threaded Compaction
مزایا:
  1. بدون نیاز به فضای اضافی در هدر شیء: برخلاف روش Lisp 2 که به فیلد forwardingAddress نیاز دارد، این روش از خود اشاره‌گرهای اشیاء استفاده می‌کند.
  2. فشرده‌سازی پیوسته (Sliding Compaction): اشیاء به‌طور مرتب و بدون شکستگی حافظه (Fragmentation) مرتب می‌شوند.
  3. بدون نیاز به سه مرحله پردازش: فقط دو مرحله دارد، درحالی‌که Lisp 2 سه مرحله‌ای ست.
  4. قابل اجرا برای اشیایی با اندازه‌ی متغیر: مثل Lisp 2، این روش هم از اشیای متغیر در اندازه پشتیبانی می‌کند.

معایب:
  1. نیاز به بازنویسی دوباره‌ی تمام اشاره‌گرها: هر اشاره‌گر باید دو بار تغییر کند (یک بار برای نخ‌گذاری، یک بار برای به‌روزرسانی).
  2. کاهش کارآیی به دلیل دنبال‌کردن اشاره‌گرها (Pointer Chasing): چون اشاره‌گرها سه بار دنبال می‌شوند (در مرحله Marking، Threading و Unthreading)، این روش می‌تواند از نظر عملکردی ضعیف باشد.
  3. مناسب نبودن برای پردازش‌های هم‌زمان (Concurrent GC): چون در یک لحظه فقط یک پردازش می‌تواند نخ‌گذاری و بازنویسی اشاره‌گرها را انجام دهد، قابل اجرا برای محیط‌های چندنخی (Multithreading) نیست.

الگوریتم‌های یک‌مرحله‌ای (One-Pass Algorithms)
بیشتر الگوریتم‌های فشرده‌سازی مثل Lisp 2 و Threaded Compaction معمولاً چندین مرحله را بر روی هیپ اجرا می‌کنند. اما روش‌های جدیدتر، مثل Compressor [Kermany & Petrank, 2006] و الگوریتم Abuaiadh et al. [2004] از جداول جانبی (Side Tables) برای ذخیره‌ی آدرس‌های جدید استفاده می‌کنند. این باعث می‌شود که دیگر نیازی به چندین بار پیمایش کل هیپ نباشد، بلکه فقط در یک مرحله‌ی اصلی (Single Pass) هم اشیاء جابه‌جا شوند و هم اشاره‌گرها به‌روزرسانی شوند.

ایده‌ی اصلی الگوریتم‌های یک‌مرحله‌ای
روش‌های سنتی مثل Lisp 2:
ابتدا مکان جدید هر شیء را محاسبه میکند. اشاره‌گرهای مربوط به آن شیء را به‌روزرسانی میکند. شیء را به مکان جدید منتقل میکند.

روش One-Pass:
علامت‌گذاری (Marking) انجام می‌شود. فقط یکبار هیپ را مرور می‌کنیم، همزمان هم اشیاء را منتقل می‌کنیم و هم اشاره‌گرها را به‌روزرسانی می‌کنیم.

compact();
  computeLocations(HeapStart, HeapEnd, HeapStart);
  updateReferencesRelocate(HeapStart, HeapEnd);

computeLocations(start, end, toRegion):
    loc ← toRegion
    block ← getBlockNum(start)
    for b ← 0 to numBits(start, end) - 1
        if b % BITS_IN_BLOCK = 0 /* crossed block boundary? */
            offset[block] ← loc /* first object will be moved to loc */
            block ← block + 1
        if bitmap[b] = MARKED
            loc ← loc + BYTES_PER_BIT /* advance by size of live objects */

newAddress(old):
    block ← getBlockNum(old)
    return offset[block] + offsetInBlock(old)

updateReferencesRelocate(start, end):
    foreach fld in Roots
        ref ← *fld
        if ref ≠ null
            *fld ← newAddress(ref)
    scan ← start
    while scan < end
        scan ← nextMarkedObject(scan) /* use the bitmap */
        for each fld in Pointers(scan) /* update references */
            ref ← *fld
            if ref ≠ null
                *fld ← newAddress(ref)
        dest ← newAddress(scan)
        move(scan, dest)

چطور بدون ذخیره‌ی آدرس‌های جدید، شیءای را جابه‌جا کنیم؟
اینجا از دو بردار (Vector) جانبی استفاده می‌شود:
بردار علامت‌گذاری (Mark Bit Vector)
یک آرایه‌ی بیت که مشخص می‌کند کدام گرانول‌ها (Granules) زنده هستند. یعنی مشخص می‌کند که کدام بخش‌های حافظه، اشیای زنده دارند و باید منتقل شوند.
بردار جابجایی (Offset Vector)
یک آرایه‌ی عددی که مشخص می‌کند اولین شیء زنده در هر بلوک، کجا منتقل شود. ما نمی‌خواهیم برای هر شیء یک آدرس ذخیره کنیم، پس فقط آدرس اولین شی زنده را در هر بلوک حافظه ذخیره میکنیم. بقیه‌ی اشیاء در همان بلوک، از روی بیت‌های علامت‌گذاری‌شده، مکان جدید خودشان را پیدا می‌کنند.


مثال:
قبل از فشرده‌سازی:
(اشیای زنده و مرده‌ی درون هیپ)
[ X ][ A ][ B ][ ][ C ][ ][ D ][ ]
(اینجا X، A، B، C و D اشیای زنده هستن و [ ] بخش‌های آزاد یا مرده)

بعد از علامت‌گذاری (Marking):
(بیت‌های مربوط به اشیای زنده ۱ و بقیه ۰ می‌شود.)
Mark Vector: [ 1 ][ 1 ][ 1 ][ 0 ][ 1 ][ 0 ][ 1 ][ 0 ]

بعد از تولید Offset Vector:
(مشخص می‌کند که اولین شیء زنده در هر بلوک کجا خواهد رفت.)
Offset Vector: [ 0 ][ 1 ][ 3 ][ 4 ]

در یک مرحله، هم اشیاء جابه‌جا می‌شوند و هم اشاره‌گرها اصلاح می‌شوند:
[ A ][ B ][ C ][ D ][ ][ ][ ][ ]

مزایای این روش نسبت به روش‌های کلاسیک
نیاز به پیمایش چندباره‌ی هیپ ندارد. استفاده‌ی بهینه از کش پردازنده، چون هیپ کمتر لمس می‌شود. از حافظه‌ی جانبی فقط به مقدار کم استفاده می‌کند (یک بیت برای هر گرانول و یک ورودی برای هر بلوک). به‌خوبی با پردازش موازی سازگار است (Parallel GC). نیاز دارد که حافظه به بلوک‌های کوچکی تقسیم شود؛ ممکن است برای اشیای خیلی بزرگ بهینه نباشد، چون همه چیز در یک بلوک قرار نمی‌گیرد.

آیا فشرده‌سازی همیشه ضروری است؟
نه همیشه! روش Mark-Sweep به خودی خود از حافظه بهینه‌تر استفاده می‌کند؛ چون مثل Copying Collection کل فضای هیپ را به دو قسمت تقسیم نمی‌کند. همین باعث می‌شود که در سیستم‌هایی که حافظه کم است، انتخاب بهتری باشد.

مزایای Mark-Sweep بدون فشرده‌سازی:
نیاز به حافظه‌ی اضافی ندارد، برخلاف Copying Collection که نصف حافظه را خالی نگه می‌دارد. ریشه‌ها (Roots) نیازی به تغییر ندارند، چون اشیاء جابه‌جا نمی‌شوند. برای سیستم‌هایی که مدیریت نوع (Type-Accurate Identification) ندارند، انتخاب بهتری است.

معایب اصلی:
تکه‌تکه شدن حافظه (Fragmentation)، مخصوصا در برنامه‌هایی که اشیای بزرگ و اندازه‌های متنوع دارند. عملکرد کند در جستجوی فضای آزاد، چون ممکن است برای یافتن فضای مناسب، کلی وقت صرف شود. برای اجراهای طولانی‌مدت، Heap ممکن است بیش از حد پخش شود و بهره‌وری کاهش پیدا کند. پس در عمل، برنامه‌ها از جمع‌آوری زباله‌هایی استفاده می‌کنند که قابلیت فشرده‌سازی دارند تا از Fragmentation جلوگیری کنند.

هزینه‌ی پردازشی فشرده‌سازی
فشرده‌سازی باعث افزایش سربار پردازشی (Overhead) می‌شود. Mark-Compact به نسبت Mark-Sweep یا Copying Collection کندتر است؛ چون باید اشیاء را پیدا کند، منتقل کند و اشاره‌گرها را به‌روزرسانی کند.
چالش‌های پردازشی:
  1. تعداد زیاد پاس‌های پردازشی: بیشتر الگوریتم‌های Mark-Compact باید چندین بار کل هیپ را پردازش کنند.
  2. دسترسی زیاد به اطلاعات نوع (Type Information): فشرده‌سازی باید نوع و اندازه هر شیء را بداند تا درست منتقل شود.
  3. بار پردازشی بالای دنبال کردن اشاره‌گرها (Pointer Chasing): اشاره‌گرهای زیادی باید به‌روزرسانی شوند، که زمان‌بر است.

راه‌حل‌های بهینه‌سازی:
اجرای Mark-Sweep تا زمانیکه Fragmentation خیلی زیاد نشود؛ سپس سوئیچ به Mark-Compact. استفاده از Compressor GC که فقط یکبار روی هیپ حرکت می‌کند و هزینه‌ی کمتری دارد.

مشکل در جمع‌آوری زباله‌های قدیمی:
Copying Collectors عملکرد بدی در جمع‌آوری اشیای طولانی‌عمر (Long-Lived Objects) دارند؛ چون مدام این اشیاء را کپی می‌کنند. Generational Collectors این مشکل را حل می‌کنند با انتقال اشیای پایدار به یک فضای جداگانه که کمتر بررسی می‌شود. Mark-Compact می‌تواند تصمیم بگیرد که اشیای پایدار را جابه‌جا نکند و فقط بخش‌های پراکنده‌ی هیپ را فشرده‌سازی کند.

تأثیر فشرده‌سازی بر Locality
اگر اشیاء در هیپ به‌صورت نامرتب پخش شوند، باعث کاهش بهره‌وری پردازنده و افزایش Cache Miss می‌شود. Sliding Compacting GC به‌خوبی نظم اولیه را حفظ می‌کند و باعث بهبود Locality و عملکرد بهتر Cache می‌شود.
مطالب مشابه