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