分代垃圾回收
背景
分代垃圾回收基于这样一个事实：
- 很多对象出生不久就会死亡
- 已经存在了很久的对象在未来一段时间内大概率还是存活
分代垃圾回收并没有创造新的算法，而是根据代的不同而采用不同的算法。对象刚创建是新生代，然后存活一段时间后就 晋升 老年代。
JVM 中就是这个算法。
Ungar 的分代垃圾回收
堆空间总的分为两个，一个是新生代空间，一个是老年代空间。其中新生代空间有分为生成空间和幸存者空间 from 和幸存者空间 to.
除了堆之外，我们还需要一个数组，称之为记录集，它用来记录老年代对新生代的引用。
在新生代空间中，对象产生于生成空间，在生成空间满的时候进行 gc，生成空间和 from 都向 to 进行 gc 复制算法。然后切换 from 和 to 的名字。记录集的作用就是用来记录老年代对象对新对象的引用。
当新生代通过晋升将老年代塞满的时候执行老年代 gc，是标记清扫法。
记录集
记录集往往设置为指向对新生代对象有引用的老年代对象。这是为了能够修复引用。
书中提到了一个 写屏障 的概念，这个我存在一些疑惑，和搜到的不一样。
一个对象头中有三个信息
- age 只对新生代对象有效
- remembered , 老年代对象只看这个
- forwarded 只对新生代对象有效，是一个布尔值，用于 gc 复制，表示是否复制完成了。
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
// 在这里的意思基本和之前 UpdatePtr 是一个使用时机
// obj 对象的 field 域指向了 newObj 对象
writeBarrier(obj,field,newObj){
// 如果 obj 是一个没有在记录集的老年代对象
// 指向的 newObj 是新生代对象
if(obj >= $oldStart && newObj< $oldStart && obj.remembered == False){
// 加入记录集
$rs[$rsIdx++] = obj;
obj.remembered = True;
}
// 真正的指向
*field = newObj;
}
newObj(size){
// 生成空间如果不足就 gc，对象只能生成在生成空间（不能生成在幸存空间）
if($newFree + size >= $surviveStart){
minorGC();
if($newFree + size >= $surviveStart){
allocationFail();
}
}
obj = $newFree;
obj.size = size;
obj.age = 0;
obj.forwarded = False;
obj.remembered = False;
$newFree += size;
return obj;
}
// 这里不去考虑如果生存空间和 from 活动对象超过了 to 空间大小的情况
这里比较复杂，先语言描述一下。
minorGC
首先向 to 空间执行 gc 复制算法，如果对象的 age 还没到上限，那么就正常复制，否则就晋升到老年代。我们不讨论 to 空间不足的情况。
然后遍历新对象的 children 对象，如果子对象不在老年代，就使用前文的 writeBarrier 进行记录集的增添。
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
minorGC(){
for(r : $roots){
// 只处理新生代的对象
if(r < $oldStart){
r = copy(r);
}
}
i = 0;
// 遍历记录集，从记录集中找到活动对象
while(i < $rsIndex){
for(child : children($rs[i])){
if(child < $oldStart){
child = copy(child);
if(child < $oldStart){
hasMinorObj = True;
}
}
}
// （经历过 gc 复制算法后）没有指向新生代的子对象 就从记录集中删掉它
if(!hasMinorObj){
$rs[i].emembered = False;
$rsIndex--;
swap($rs[i],$rs[$rsIndex]);
}else{
++i;
}
}
swap($fromStart,$toStart);
}
copy(obj){
// 已经复制完毕的
if(obj.forwarded){
return obj.forwarding;
}
if(obj.age < AGEMAX){
// 复制到 to
newObj = copyData(obj,$toFree);
$toFree += obj.size;
obj.forward = newObj;
obj.forwarded = True;
newObj.age ++;
for(chlid : children(child)){
child = copy(child);
}
}else{
promote(obj);
}
return obj.forward;
}
promote
对象的 forwarded 标签用于表示它有没有已经被赋值。
晋升到老年代的操作 promote ：如果老年代空间不足，就进行老年代 gc，再不足就报错。复制到老年代之后，让原来的对象的 forwarded 为 True，forwarding 指向刚才的新对象。
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
promote(obj){
newObj = allocateInOld(obj);
// 如果老生代没有空间，就尝试清理
if(newObj == NULL){
// 老年代 gc 就是标记清扫算法
majorGC();
newObj = allocateInOld(obj);
if(newObj == NULL){
allocationFail();
}
}
obj.forward = newObj;
obj.forwarded = True;
obj.remembered = False;
// 检查是否需要加入记录集
for(chlid : children(child)){
if(child < $oldStart){
$rs[$rsIndex] = child;
#rsIndex++;
obj.remembered = True;
return
}
}
}
评价
这个算法的优化完全建立在”刚产生的对象比产生很久的对象更容易变成垃圾“这个经验上。
在一般情况下能够起到比较好的效果，但是并不符合这个规律的效果甚至不如普通 gc 算法。
