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

• دسترسی‌های مرحله Mark تصادفی هستند: Collector باید به صورت نامنظم در گراف اشیاء حرکت کند.
• مرحله Sweep الگوی دسترسی بهتری دارد: معمولاً اشیاء به صورت متوالی اسکن می‌شوند که باعث می‌شود کش و مکانیزم‌های سخت‌افزاری مثل Prefetching عملکرد بهتری داشته باشد.

1. بهبود locality: شکاف‌های حافظه بلافاصله بعد از جارو شدن، استفاده می‌شوند.
2. کاهش پیچیدگی زمانی: این روش، پیچیدگی زمانی را به O(L) کاهش می‌دهد؛ مشابه الگوریتم‌های کپی.
3. کاهش توقف Mutator: چون Sweep به صورت تنبل انجام می‌شود، زمان توقف برنامه کاهش پیدا می‌کند.

1. احتمال نشت حافظه (Memory Leak): اگر بلوک‌های استفاده‌نشده، جارو نشوند، ممکن است حافظه آزاد نشود.
2. مشکلات با بلوک‌های جداگانه: در سیستم‌هایی که حافظه به بلوک‌های مختلف برای اندازه‌های مختلف تقسیم می‌شود، ممکن است یک کلاس، اندازه حافظه‌اش تمام شود ولی بلوک‌های دیگر هنوز جارو نشده باشند.

1. علامت‌گذاری چرخه‌ای (Cyclic Marking): به‌جای استفاده از یک بیت برای علامت‌گذاری، از چند بیت استفاده می‌شود تا اشیایی که در چرخه‌های قبلی علامت‌گذاری شدند مشخص شوند.
2. جارو کردن بلوک‌های کامل: اگر هیچ شیء زنده‌ای در یک بلوک نباشد، کل بلوک می‌تواند به تخصیص‌دهنده برگردانده شود.
3. اولویت‌بندی بلوک‌ها: بلوک‌هایی که بیشتر احتمال جارو شدن دارند، اولویت بیشتری برای Sweep می‌گیرند.

atomic collect() {
    markFromRoots();
    for each block in Blocks {
        if not isMarked(block)
            add(blockAllocator, block);  /* no objects marked in this block? */
                                         /* return block to block allocator */
        else
            add(reclaimList, block);     /* queue block for lazy sweeping */
    }
}

atomic allocate(sz) {
    result ← remove(sz);                 /* allocate from size class for sz */
    if result = null {
        lazySweep(sz);                    /* if no free slots for this size.. */
        result ← remove(sz);               /* sweep a little */
    }
    return result;                        /* if still null, collect */
}

lazySweep(sz) {
    repeat {
        block ← nextBlock(reclaimList, sz);
        if block ≠ null {
            sweep(start(block), end(block));
            if spaceFound(block)
                return;
        }
    } until block = null;                 /* reclaim list for this size class empty */
    allocSlow(sz);                         /* get an empty block */
}

allocSlow(sz) {
    block ← allocateBlock();               /* allocation slow path */
    if block ≠ null
        initialise(block, sz);              /* from the block allocator */
}