读书笔记

垃圾回收的算法与实现(1)

标记-清除算法

标记阶段

深度优先搜索 or 广度优先搜索，从 stack 上利遍历有对象，标记为1.

1
2
3
4
5
def make(obj)
    if obj.mark is False:
        obj.mark = True
        for child in obj.childs:
            make(child)

清除阶段

里面堆内的所有对象，将标记为0的对象，全部回收到 freeList 中。

1
2
3
4
5
6
7
8
def clear():
    newHeap = []
    for obj in heap:
        if obj.mark is True
            newHeap.append(obj)
        else:
            freeList.append(obj)
    heap = newHeap

分配对象

优先遍历 freeList,知道找到 obj.size 满足所需分配的内存，则返回。

1
2
3
4
5
6
def malloc(size):
    for obj in freeList:
        if obj.size > size:
            freeList.remove(obj)
            return obj
    return newObj(size)

评价

  • 实现简单
  • 碎片化严重
  • 分配 O(n)
  • 与写时复制技术不兼容

优化

  1. 多个 freeList
    将回收的对象根据size回到不同的 freeList 中，分配内存对象时，则可直接找到对象的 freeList。
  2. BiBOP
    将内存切分为固定的大小，如2个字节的，3个字节。
    每次分配 足够满足 size 的 n 个连续块。
  3. 位图标记
    从 obj 中分离标记d，用其他数据结构管理。
    如：整数数组、树、散列表。
  4. 延迟清除法
    4.1 只是标记，需要分配时才从堆中清除。
    4.2 清除一轮后，重新标记清除。
    4.3 还是没能从清除的对象中找到合适的，那就重新系统分配吧。