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

1. Marking (علامت‌گذاری): مثل Mark-Sweep، تمام اشیای زنده را پیدا می‌کند و علامت‌گذاری می‌کند.
2. Compacting (فشرده‌سازی): اشیای زنده را به سمت ابتدای حافظه حرکت می‌دهد تا فضای خالی یک‌جا جمع شود.
3. Updating Pointers (به‌روزرسانی اشاره‌گرها): تمام اشاره‌گرها را تنظیم می‌کند تا به مکان جدید اشیاء اشاره کند.

1. Arbitrary (ترتیب تصادفی): بدون در نظر گرفتن ترتیب اصلی، اشیاء به مکان‌های جدید منتقل می‌شوند.
2. Linearising (مرتب‌سازی رابطه‌ای): اشیای مرتبط، کنار هم قرار می‌گیرند (مثلاً اشیایی که به یکدیگر اشاره دارند یا در یک ساختار داده‌ای قرار دارند).
3. Sliding (لغزشی): اشیاء در همان ترتیب قبلی‌شان، ولی بدون فاصله‌های خالی، قرار می‌گیرند.

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

compact():
    relocate(HeapStart, HeapEnd, slotSize)
    updateReferences(HeapStart, free, slotSize)

relocate(start, end, slotSize):
    free ← start
    scan ← end

    while free < scan
        while isMarked(free)
            unsetMarked(free)
            free ← free + slotSize    /* find next hole */

        while not isMarked(scan) && scan > free
            scan ← scan - slotSize    /* find previous live object */

        if scan > free
            unsetMarked(scan)
            move(scan, free)
            *scan ← free              /* leave forwarding address (destructively) */
            free ← free + slotSize
            scan ← scan - slotSize

updateReferences(start, end, slotSize):
    for each fld in Roots        /* update roots that pointed to moved objects */
        ref ← *fld
        if ref ≥ end
            *fld ← *ref          /* use the forwarding address left in first pass */

    scan ← start
    while scan < end             /* update fields in live region */
        for each fld in Pointers(scan)
            ref ← *fld
            if ref ≥ end
                *fld ← *ref      /* use the forwarding address left in first pass */
        scan ← scan + slotSize   /* next object */

1. سرعت بالا و سادگی: الگوریتم، فقط یک بار کل هیپ را اسکن می‌کند و نیاز به متادیتای اضافی ندارد.
2. عدم نیاز به حافظه اضافی: چون آدرس‌های جایگزین فقط در مکان‌های قدیمی (که دیگر استفاده نمی‌شوند) ذخیره می‌شوند.
3. پشتیبانی از اشاره‌گرهای داخلی (Interior Pointers): یعنی اگر اشاره‌گری به داخل یک شیء وجود داشته باشد، این روش می‌تواند آن را مدیریت کند.
4. الگوی دسترسی به حافظه‌ی قابل پیش‌بینی: به دلیل حرکت یکنواخت scan، سخت‌افزار می‌تواند از Prefetching برای بهبود سرعت استفاده کند.

1. وابسته به اشیای هم‌اندازه: اگر اشیاء اندازه‌های مختلفی داشته باشند، ممکن است فضای خالی مناسبی پیدا نشود و فرآیند فشرده‌سازی مؤثر نباشد.
2. تغییر ترتیب اشیاء: این الگوریتم چینش اصلی اشیا را تغییر می‌دهد که ممکن است باعث کاهش locality و افت عملکرد برنامه گردد.
3. عدم بهینه‌سازی locality: چون اشیای مرتبط ممکن است در نقاط مختلف هیپ قرار بگیرند، دسترسی به آن‌ها کندتر می‌شود.

• محاسبه مکان جدید هر شیء (Compute Locations)

• به‌روزرسانی اشاره‌گرها (Update References)

compact():
    computeLocations(HeapStart, HeapEnd, HeapStart)
    updateReferences(HeapStart, HeapEnd)
    relocate(HeapStart, HeapEnd)

computeLocations(start, end, toRegion):
    scan ← start
    free ← toRegion
    while scan < end
        if isMarked(scan)
            forwardingAddress(scan) ← free
            free ← align(free + size(scan))
        scan ← nextObject(scan)

updateReferences(start, end):
    for each fld in Roots        /* update roots */
        ref ← *fld
        if ref ≠ null
            *fld ← forwardingAddress(ref)

    scan ← start
    while scan < end             /* update fields */
        if isMarked(scan)
            for each fld in Pointers(scan)
                if *fld ≠ null
                    *fld ← forwardingAddress(*fld)
        scan ← nextObject(scan)

relocate(start, end):
    scan ← start
    while scan < end
        if isMarked(scan)
            dest ← forwardingAddress(scan)
            move(scan, dest)
            unsetMarked(dest)
        scan ← nextObject(scan)

1. حفظ ترتیب اشیاء: در مقایسه با Two-Finger Compaction، این روش ترتیب اصلی اشیا را حفظ می‌کند.
2. کاهش پراکندگی حافظه (Fragmentation): چون اشیا به یک سمت فشرده می‌شوند، هیچ فضای خالی باقی نمی‌ماند.
3. پشتیبانی از اشیای متغیر در اندازه: برخلاف Two-Finger Compaction که فقط برای اشیای هم‌اندازه خوب بود، این روش برای همه نوع اشیاء کاربرد دارد.

1. نیاز به یک فیلد اضافی در هدر هر شیء: این فیلد برای ذخیره‌ی forwardingAddress استفاده می‌شود که در برخی سیستم‌ها می‌تواند فضای زیادی را اشغال کند.
2. اجرای سه مرحله‌ای: نسبت به روش‌هایی مثل Two-Finger Compaction، که فقط دو مرحله دارد، این روش یک مرحله بیشتر دارد و می‌تواند کمی کندتر باشد.
3. متکی به پردازش‌های متوالی: این الگوریتم حافظه نهان (Cache) را بهینه استفاده نمی‌کند، مگر اینکه پیش‌بارگذاری داده‌ها (Prefetching) انجام شود.