Garbage Collection: Mark-Sweep
Hawtian WangContents
1 Automatic dynamic memory management
原则上，回收器最终都会将所有不可达对象回收。
- 追踪式回收 引入 垃圾 这一具有明确判定标准的概念，但它不一定包含所有不再使用的对象。
- 出于效率原因，某些对象可能不会被回收。
2 Comparing garbage collection algorithms
用什么来衡量各种垃圾回收算法的好坏呢：
- 安全性。在任何时候都不能回收活的对象。
- 吞吐量。**标记 / 构造率（mark / cons ratio）**来衡量，它表示回收器（对存活对象进行标记）与赋值器（创建或者构造新的链表单元）活跃度的比值。
- 完整性和及时性。完整性即所有的垃圾被回收的情况，及时性就是垃圾产生之后多久被回收。
- 停顿时间。在进行垃圾回收的时候中断赋值器线程的时间。【最小赋值器使用率（MMU）和界限赋值器使用率（BMU）的概念，去衡量停顿时间的分布。】
- 空间开销。
- 针对结构的特别优化。
- 可扩展性和可移植性。
3 The mark-sweep algorithm
- 如果将标记位白存在对象中，那么
mark方法处理的将是那些刚刚被标记的对象，因此这些对象可能还在缓存中。那么回收过程的高速缓存相关行文会影响到回收器的性能。 - 标记-清扫回收器要求堆布局满足一定的条件：
- 标记-清扫回收器不会移动对象，因此内存管理器必须能够控制堆内存碎片，过多的内存碎片可能会导致分配器无法满足新分配请求，从而增加垃圾回收的频率，甚至于根本无法分配。
- 清扫器必须能够遍历堆中的每一个对象，不管是否存在一定用于对齐的字节，
sweep方法必能够准确的找到下一个对象。
New():
ref <- allocate()
if ref == null:
collect()
ref <- allocate()
if ref == null:
error "Out of memory."
return ref
atomic collect():
markFromRoots()
sweep(HeapStart, HeapEnd)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)sweep(start, end):
scan <- start
while scan < end:
if isMarked(scan):
unsetMarked(scan)
else:
free(scan)
scan <- nextObject(scan)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)5 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)5.0.0.1 2.6 Cache misses in the marking loop
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():
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)