Garbage Collection: Mark-Sweep

1.2 Automatic dynamic memory management

原则上,回收器最终都会将所有不可达对象回收。

  1. 追踪式回收 引入 垃圾 这一具有明确判定标准的概念,但它不一定包含所有不再使用的对象。
  2. 出于效率原因,某些对象可能不会被回收。

1.3 Comparing garbage collection algorithms

用什么来衡量各种垃圾回收算法的好坏呢:

  1. 安全性。在任何时候都不能回收活的对象。
  2. 吞吐量。标记 / 构造率(mark / cons ratio)来衡量,它表示回收器(对存活对象进行标记)与赋值器(创建或者构造新的链表单元)活跃度的比值。
  3. 完整性和及时性。完整性即所有的垃圾被回收的情况,及时性就是垃圾产生之后多久被回收。
  4. 停顿时间。在进行垃圾回收的时候中断赋值器线程的时间。【最小赋值器使用率(MMU)和界限赋值器使用率(BMU)的概念,去衡量停顿时间的分布。】
  5. 空间开销。
  6. 针对结构的特别优化。
  7. 可扩展性和可移植性。

2.1 The mark-sweep algorithm

  • 如果将标记位白存在对象中,那么mark方法处理的将是那些刚刚被标记的对象,因此这些对象可能还在缓存中。那么回收过程的高速缓存相关行文会影响到回收器的性能。
  • 标记-清扫回收器要求堆布局满足一定的条件:
  • 标记-清扫回收器不会移动对象,因此内存管理器必须能够控制堆内存碎片,过多的内存碎片可能会导致分配器无法满足新分配请求,从而增加垃圾回收的频率,甚至于根本无法分配。
  • 清扫器必须能够遍历堆中的每一个对象,不管是否存在一定用于对齐的字节,sweep方法必能够准确的找到下一个对象。

Mark-Sweep: Allocate

New():
    ref <- allocate()
    if ref == null:
        collect()
        ref <- allocate()
        if ref == null:
            error "Out of memory."
    return ref
atomic collect():
    markFromRoots()
    sweep(HeapStart, HeapEnd)

Mark-Sweep: Mark

markFromRoots():
    initialise(work_list)
    for each fld in Roots:
        ref <- *fld
        if ref != null and not isMarked(ref):
            setMarked(ref)
            add(work_list, ref)
            mark()

initialise(work_list):
    work_list <- empty

mark():
    while not isEmpty(work_list):
        ref <- remove(work_list)
        for each fld in Pointers(ref):
            child <- *fld
            if child != null and not isMarked(child):
                setMarked(child)
                add(work_list, child)

Mark-Sweep: Sweep

sweep(start, end):
    scan <- start
    while scan < end:
        if isMarked(scan):
            unsetMarked(scan)
        else:
            free(scan)
        scan <- nextObject(scan)

2.4 Bitmap marking

  • 可以应用于保守式回收器(conservative collector)。
  • 减少回收过程中的换页次数。
mark():
    cur <- nextInBitmap()
    while cur < HeapEnd:
        add(work_list, cur)
        markStep(cur)
        cur <- nextBitmap()

markStep(start):
    while not isEmpty(work_list):
        ref <- remove(work_list)
        for each fld in Pointers(ref):
            child <- *fld
            if child != null and not isMarked(child):
                setMarked(child)
                if child < start:
                    add(work_list, child)

2.5 Lazy sweeping

  • 优化清扫阶段高速缓存行为的一种方案是使用对象预取。回收器可以按照固定步幅对大小相同的对象进行清扫。
  • 对象及其标志位存在两个特征:
    1. 一旦某个对象成为垃圾,它将一直都是垃圾,不可能再被赋值器访问或者复活。
    2. 赋值器永远不会访问对象的标记位。

Block structure heep: lazy sweeping

atomic collect():
    markFromRoots()
    for each block in Blocks:
        if not isMarked(block):
            add(blockAllocator, block)
        else:
            add(reclaimList, block)
atomic allocate(sz):
    result <- remove(sz)
    if result == null:
        lazySweep(sz)
        result <- remove(sz)
    return result

lazySweep(sz):
    repeat
        block <- nextBlock(reclainmList, sz)
        if block != null:
            sweep(start(block), end(block))
            if spaceFound(block):
                return
    until block == null
    allocSlow(sz)

allocSlow(sz):
    block <- allocateBlock()
    if block != null:
        initialise(block, sz)

2.6 Cache misses in the marking loop

mark procedure base on FIFO prefetch buffer

add(work_list, item):
    markStack <- getStack(work_list)
    push(markStack, item)

remove(work_list):
    markStack <- getStack(work_list)
    addr <- pop(markStack)
    prefetch(addr)
    fifo <- getFifo(work_list)
    prepend(fifo, addr)
    return remove(fifo)

Mark edge not node in object graph

mark():
    while not isEmpty(work_list):
        obj <- remove(work_list)
        if not isMarked(obj):
            setMarked(obj)
            for each fld in Pointers(obj):
                child <- *fld
                if child != null:
                    add(work_list, child)
Comments
Write a Comment