Garbage Collection: Mark-Sweep

Hawtian Wang included in category Tech

2016-08-27 2023-09-18 1142 words 3 minutes comments

Contents

1 Automatic dynamic memory management

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

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

2 Comparing garbage collection algorithms

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

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

3 The mark-sweep algorithm

如果将标记位白存在对象中，那么mark方法处理的将是那些刚刚被标记的对象，因此这些对象可能还在缓存中。那么回收过程的高速缓存相关行文会影响到回收器的性能。
标记-清扫回收器要求堆布局满足一定的条件：

标记-清扫回收器不会移动对象，因此内存管理器必须能够控制堆内存碎片，过多的内存碎片可能会导致分配器无法满足新分配请求，从而增加垃圾回收的频率，甚至于根本无法分配。
清扫器必须能够遍历堆中的每一个对象，不管是否存在一定用于对齐的字节，sweep方法必能够准确的找到下一个对象。

Mark-Sweep: Allocate

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
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

1
2
3
4
5
6
7
8
sweep(start, end):
	scan <- start
	while scan < end:
		if isMarked(scan):
			unsetMarked(scan)
		else:
			free(scan)
		scan <- nextObject(scan)

4 Bitmap marking

可以应用于保守式回收器（conservative collector）。
减少回收过程中的换页次数。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
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

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

Block structure heep: lazy sweeping

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
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

mark procedure base on FIFO prefetch buffer

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
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

1
2
3
4
5
6
7
8
9
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)