垃圾回收的算法和实现

「垃圾回收的算法和实现」 第三章-引用计数法

Posted by Dawn-K's Blog on January 21, 2022

引用计数法

思路

引用计数法的思路也是比较简单。既然当空间不足时再从头找垃圾，不如就不使用标记，在每次指针的赋值过程中就把引用的数量给维护了。一个对象，当有一个新的指针指向它的时候，计数器加 1，如果一个指针不再指向它，计数器减 1. 当计数器减为 0 的瞬间，执行回收。回收的时候还要考虑到它所有发射出的指针指向的儿子对象都要计数减 1。

这种思路看起来似乎正确，但是有一个致命的问题：循环引用。

根指向 A，A 指向 B，B 指向 A。然后根的指针指向别处，然后 A 和 B 的计数器都不为 1，所以就导致了内存泄漏。

实现方法

在讲述优化方法之前先讲这个算法的实现。

核心的算法有两个，一个是 NewPoj()，一个是 UpdatePtr()

$freeList 是全局变量，是空闲链表 reclaim(obj) 表示把对象所在的空间串入空闲链表。 pickupChunk(size,$freeList) 表示在空闲链表中寻找合适的块（已在标记清扫法中讲过） allocationFail() 表示分配失败，可以理解为抛出异常，自动终止程序流程

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
29
30
31
32
33
34
35
36
37
38
39
40

// 将 oldPtr 指向 obj 这个引用
// 根据后文的分析，这里的 obj 就当做是对象的引用来使用
UpdatePtr(oldPtr,obj){
    // 注意必须先增加再减少，如果反过来可能会造成对象减计数之后直接被回收了
    incObj(obj);
    // 这里也要看做传递的引用
    decObj(*oldPtr);
    oldPtr = &obj;
}

incObj(obj){
    obj.cnt++;
}

// 这里的 obj 是引用
decObj(obj){
    obj.cnt--;
    if(!obj.cnt){ // 为零的时候进行释放操作
        // 这里可以理解为都是指针
        for(child : children(obj)){
            decObj(child);
        }
        reclaim(obj);
    }
}

// 分配对象
NewObj(size){
    // 从空闲链表中尝试寻找合适大小的块
    obj  = pickupChunk(size,$freeList);
    if(obj == NULL){
        allocationFail();
    }

    obj.cnt = 1;
    // 这里可以理解为返回的是指针，也可以理解为就是返回的 longlong，不过这个 ll 和内存的值相同
    // 但是就不要再想这个指针对对象的引用了，这个对象就是个临时对象，朝生暮死，不考虑它对对象的影响，它的使命就是把值传给外面
    return obj; 
}

优点

  1. 随时整理，每次都能及时回收垃圾。最大暂停时间短
  2. 沿着指针查找次数少。仅在一个对象被回收了之后才会查找子对象。相比标记清扫法极大减少了沿对象指针的遍历次数

缺点

  1. 每次指针的移动都要进行标记，减缓了速度
  2. 无法解决循环引用
  3. 计数器的大小问题，如果小了容易溢出，大了就浪费空间
  4. UpdatePtr 这种方式过于笨重，让指针的赋值变得繁琐

优化

zct 优化

zct 优化的方向是试图减少因根中的指针频繁变动而造成的计数的消耗。将根指针的引用还是用普通的方法来赋值 oldPtr = newPtr , 对于堆中的还是采用上文提到的 UpdatePtr 。

然后由于缺少了对根指针引用的记录，必然导致有些计数为 0 的对象本来不是垃圾。所以不能直接清除计数为 0 的对象。我们这里采用了一个表 ZCT(Zero Count Table) 来作为一个缓冲，收留这些计数为 0 的对象。

根据这个思路，刚被根创建的对象的引用数是 0。

在 decObj 中，如果一个对象的计数被减为 0，不要直接回收，而是把它放到 ZCT 里面。

在 NewObj() 中，如果一个对象能够在空闲链表中找到合适的空间，就直接分配。仅仅在空闲列表中没有内存的时候，调用 scanZct() 来操作 zct 中的对象，看看能不能释放它们。

新方法 scanZct() ，首先把所有根指向的对象的引用值+1（这些对象可能不在 zct 中），然后遍历 zct，回收其中所有的引用为 0 的对象。遍历之后再把跟指向的对象的引用值-1.

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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60

UpdatePtr(oldPtr,obj){
    incObj(obj);
    decObj(*oldPtr);
    oldPtr = &obj;
}

incObj(obj){
    obj.cnt++;
}

decObj(obj){
    // 这里仍是对象引用
    obj.cnt--;
    if(!obj.cnt){
        // 满了就整理一下
        if(isFull($zct)){
            scanZct();
        }
        // 放到 zct 表中，为了程序简洁，这里就不再写如果表满了会怎样
        push($zct,obj);
    }
}

// 分配对象
NewObj(size){
    obj  = pickupChunk(size,$freeList);
    if(obj == NULL){
        // 整理之后重试
        scanZct();
        obj  = pickupChunk(size,$freeList);
        if(obj == NULL){
            allocationFail();
        }
    }

    obj.cnt = 1;
    return obj; 
}

// 清除无用对象
// 实际上如果这个函数运行时一个垃圾也没回收，可以直接报错了
// 因为都是没空间的时候才会去调用它
scanZct(){
    for (root : $roots){
        root.cnt++;
    }

    for(obj : $zct){
        if(!obj.cnt){
            for(child : children(obj)){
                decObj(child);
            }
            reclaim(obj);
        }
    }

    for (root : $roots){
        root.cnt--;
    }
}

总结

这个方法的原理就是，我不去记录每次的根指针导致的对象引用计数变化。我只是在即将清除对象的时候再去检查它会不会被根节点引用了，如果没有的话就回收，有的话就让它继续在 zct 里待着。

虽然书中没有说，但是我感觉到，书中对 指针的转移，语焉不详。这里写的是根指针的引用不需要计数，比如根引用对象 A，然后根又指向对象 B 了，也就是放弃了对 A 的引用，那么岂不是 A 的计数器永远不会少了？然后也不会被加入到 zct 中。同样的道理，一旦加入了 zct 中，就再也没有出来的机会了。

这种方法减少了部分对计数器的操作。但是在 zct 满的时候会进行一次扫描，这个操作是费时的，也就消除了引用计数法的一大优势，也就是 STW 短。

而且这个算法的效率也受 zct 的大小制约。如果 zct 过小，则清理的次数多，如果 zct 过大，则单次清理的时间长。

Sticky 引用计数法

这个算法的思路是针对于计数器占用空间的大小进行优化。这个算法基于两个经验：

  1. 引用计数不会很大，大部分对象都是出生之后不久就会死亡，不会有太多计数
  2. 被大量引用的对象在未来的一段时间内大概率不是垃圾

这个可以了理解为，大部分对象不会有太多引用，而有大量引用的对象很难成为垃圾，也就是有很长的寿命。

基于这个，我们就可以把计数器设置的小一点，比如 5 位，也就是最多 31 个对象引用它。

而面对溢出这个计数器的对象，也有两种思路。第一种是直接不管了，反正这样的对象很少很少。第二种思路是采用标记清扫法来作为备份。我们主要讨论第二种。

书中对此处的标记清扫法进行了魔改。我理解的是这里的操作是为了兼容计数器而不是之前说的标记。在标记前将所有对象的计数器全部清零。然后在标记完之后，每个对象的计数器也达到了正确的数量。然后清扫计数器为 0 的。

这样就解决了溢出的对象，然后也减少了计数器的空间占用，并且还能回收循环引用。唯一的缺点就是让 STW 变大了。

一位引用计数

此外还有更激进的改法，就是直接把计数器改成 1 位，只有 0 和 1.

这个思路是这样的，我们在 decObj 的时候是先减后判断。其实我们完全可以先特判它是不是 1，也就是 0 这个状态是无用的。所以在这个算法中，0 表示 1, 1 表示大于等于 2. 书中称之为标签。0 是 Unique, 1 是 Multiple.

这里还使用了内存对齐的黑科技，来存储这个比特（因为没法直接申请 1 比特）。书中假定的都是 32 位系统，所有的对象都按照四字节对齐也就是对象占据的内存的首地址必须是 4 的倍数，也就是首地址末尾的两个 bit 一定是 0，所以指向这个对象的指针的值的最后两位也都是 0.

换言之，一个指针除了它指向的位置之外，还可以存储一个标签，用于指明这个指针指向的对象引用是 1 还是更多，这个标签是在指针上存储，所以不会占据对象的空间。

将 UpdatePtr 换成了 CopyPtr(oldPtr,newPtr) ，也就是直接针对两个指针进行复制操作。这个有点类似 c++中 shared_ptr 的复制操作。

可以分析出，

  1. oldPtr 如果是 Unique，则指向的对象就可以直接回收了。
  2. 如果 newPtr 指向的对象只有一个引用，也就是 newPtr 本身的标签是 Unique，那么在这次复制之后，必然变成 Multiple. 而 oldPtr 一定会变成 Multiple
1
2
3
4
5
6
7
8
9
10
11

// 将 UpdatePtr 改成这个，其他的都不用变
CopyPtr(oldPtr,newPtr){
    if(oldPtr.tag == UNIQUE){
        reclaim(oldPtr);
    }
    oldPtr = newPtr;
    if(newPtr.tag == UNIQUE){
        newPtr.tag == MULTIPLE;
    }
    oldPtr.tag == MULTIPLE;
}

这个优化思路是极大减少了对内存的占用，并且在指针操作的时候不用对对象本身有任何操作，甚至不用读取对象本身。对 cache 比较友好，而在对计数器溢出的对象则是采用完全不管的方式，只要一个对象被两个指针引用了，那么就再也不会被回收了。

部分标记清扫法

这个方法实际上比较冗长，效果也不好，相关资料也少。不过 PHP 里面就是这种方法，我们就简单说一下。这种染色的思想也被 go 语言吸纳了一部分，之后会通过 go 的 gc 算法来详细地讲述并行时候的实现（虽然书上没有）。

这个算法可以参考下面的资料，不过实际上论文实现的要复杂很多很多，论文还讲述了这个算法的并行形式。书中只是举了个非常简化版的说明。

PHP 官方文档 IBM 论文

核心思想是通过引入标记清扫法来解决循环引用问题。但是直接使用标记清扫法会带来很大的开销。既然为了消除循环引用，那么我们的标记清扫法也要针对这个问题进行魔改。我们只关注可能是循环引用的对象群。

规定四种颜色代表四种状态：

  1. 黑色，表示绝对不会是垃圾
  2. 白色，表示一定是垃圾
  3. 灰色，已经搜索完毕，但是还不能判定是黑白
  4. 阴影 (HATCH)，可能是循环垃圾，往往阴影对象都会放到阴影队列中 ($hatch_queue)

我们经过染色，将对象最终染成黑白两色，把白色的给回收即可。

至于颜色，用两个位来表示，就存储的对象的头上。

  1. 刚创建的对象一定是黑色，计数为 1
  2. 减少对象引用的时候，如果引用为 0，那就直接照上文进行回收以及对子对象的减计数即可，同时如果在队列中也记得删除。如果引用不为 0，那么就把它加到队列中并涂成阴影（如果已经是阴影就表示已经在队列，就不用添加）
  3. 当且仅当分配对象没有空间的时候，才会去选择调用scanHatchQueue()方法，然后尝试重新运行 newObj（注意这里不是重新到空闲链表去找，而是重新运行整个方法，这也就意味着可能要连着回收好几次阴影队列中的对象。这是一个新方法，也是我们的重头戏。

这个方法就是遍历队列，遇到阴影对象就尝试探索它是不是在一个对象群中。如果是，就对这个群进行染色和回收，然后算法就结束了，也就是一次只回收一个对象群。否则就寻找队列中下一个对象。

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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50

decObj(obj){
    obj.cnt--;
    if(!obj.cnt){
        for(child : children(obj)){
            decObj(child);
        }
        reclaim(obj);
    }else if (obj.color != HATCH){
        // 标记为阴影并且加入队列
        obj.color = HATCH;
        push($hatch_queue,obj);
    }
}

NewObj(size){
    obj  = pickupChunk(size,$freeList);
    if(obj != NULL){
        return obj;
    }else if(!$hatch_queue.empty()){
        scanHatchQueue();
        // 一直重试到找到对象或者队列为空
        return newObj();
    }
    allocationFail();
}

// 尝试回收第一个对象群
scanHatchQueue(){
    obj = $hatch_queue.pop();
    if(obj.color == HATCH){
        paintGray(obj);
        scanGray(obj);
        collectWrite(obj);
    }else if(!$hatch_queue.empty()){
        scanHatchQueue();
    }
}

paintGray(obj){
    // 这里的意思是 灰色不用染色， 白色是垃圾，不能染色
    if(obj.color == (BLACK | HATCH))
        obj.color = GRAY;
        for(child : children(obj)){
            // 这里乍看比较突兀，似乎和染色没有关系
            // 实际上是为下文 scanGray 的判断循环引用设置条件
            child.cnt--;
            paintGray(child);
        }
    }
}

这里先暂停一下，我们探讨一个环的性质。如果一群对象构成了一个环（不一定是简单环，复杂的环也可以），那么从任何一个点出发，沿着有向边 dfs 去减另一个阴影对象的计数，那么必然最终会减到自己，把自己减为 0。

换言之，从垃圾环（也就是循环引用的垃圾群）中任意一个对象出发，沿着引用的指针减去其子对象的引用计数，并且将自身染成灰色，那么最终会得到一堆引用计数为 0 的灰色对象，而如果最终这个对象自身并没有被减到 0，那么说明他不存在于任何垃圾环中。

而且必须是要自己被循环回来的指针给减计数，否则假设根有两个指针指向 A，A 指向 B，B 指向 C，C 不向外指。那么根的一个指针不再指向 A 的时候，顺着过去这三个都会被识别成垃圾。

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
29
30
31
32
33
34
35
36
37
38
39
40

scanGray(obj){
    // 只扫描灰色的，别的颜色的不管
    if(obj.color == GRAY){
        if(obj.cnt == 0){
            obj.color = WRITE;
            for(child : children(obj)){
                scanGray(obj);
            }
        }else{
            paintBlack(obj);
        }
    }
}

// 执行到这个函数说明 obj 虽然是灰色，但是引用计数并不为 0
// 所以就需要撤销
paintBlack(obj){
    if (obj.color != BLACK){
        obj.color = BLACK
        for(child : children(obj)){
            if (child.color == GRAY){
                // 这里的逻辑和之前的一样，不是给自己加而是给儿子加
                child.cnt++;
                paintBlack(child);
            }
        }
    }
}

collectWrite(obj){
    if(obj.color == WRITE){
        // 避免无限递归
        obj.color = BLACKED;
        for(child : children(obj)){
            collectWrite(obj);
        }
        reclaim(obj);
    }
}

这个算法在垃圾回收的时候要扫描三次对象，效率比较低下。

CATALOG
    FEATURED TAGS
    CodeNote Web开发 软件工程 SpringBoot 互联网架构 垃圾回收的算法和实现 设计模式 android DAO 数据库 Python Vue Linux Unity VSCode学习 操作系统 版本控制 C++ View Java Kotlin Missing-Semester
    FRIENDS