GC

发表于 | 更新于

1 引用计数

  • 当创建一个对象的时候，设置它的引用计数为0
  • 当在该对象上创建一个引用的时候，它的计数增加1
  • 当移除该对象上的一个引用的时候，它的计数减少1

1.1 回收

  • 当对象的引用计数为0的时候，回收该对象的内存
  • 同时移除所有该对象创建的引用

1.2 例子

1.2.1 good case

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
61
62
type LinkedList struct {
    next *LinkedList
	number int
}


func main () {

    head := &LinkedList{nil, 1}; 
    // head -> [ 1 | ]

    mid := &LinkedList{nil, 2};
    // head -> [ 1 | ] 
    // mid ->  [ 1 | ]

    tail := &LinkedList{nil, 3};
    // head -> [ 1 | ] 
    // mid ->  [ 1 | ]
    // tail -> [ 1 | ]


    head.next = mid;
    // head -> [ 1 | ] 
    //            |
    // mid ->  [ 1->2 | ]
    // tail -> [ 1 | ]

    mid.next = tail;

    // head -> [ 1 | ] 
    //            |
    // mid ->  [ 2 | ]
    //            |
    // tail -> [ 1->2 | ]

    tail = nil;
    // head ->[ 1 | ] 
    //            |
    // mid -> [ 2 | ]
    //            |
    // tail   [ 2->1 | ]

    mid = nil;
    // head ->[ 1 | ] 
    //            |
    // mid    [ 2->1 | ]
    //            |
    // tail   [ 1 | ] 
    head.next.next = nil;
    // head ->[ 1 | ] 
    //            |
    // mid    [ 1 | ]
    //            
    // tail   [ 1->0 | ] (回收)
    
	head = nil;
    // head   [ 1->0 | ] (回收)
    //                (该对象创建的引用同样回收)
    // mid    [ 1->0 | ] (回收)
    //            
    // tail   [ 0 | ] 
}

1.2.2 bad case

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
61
62
63
64
65
66
67
68
type LinkedList struct {
    next *LinkedList
	number int
}


func main () {

    head := &LinkedList{nil, 1}; 
    // head -> [ 1 | ]

    mid := &LinkedList{nil, 2};
    // head -> [ 1 | ] 
    // mid ->  [ 1 | ]

    tail := &LinkedList{nil, 3};
    // head -> [ 1 | ] 
    // mid ->  [ 1 | ]
    // tail -> [ 1 | ]


    head.next = mid;
    // head -> [ 1 | ] 
    //            |
    // mid ->  [ 1->2 | ]
    // tail -> [ 1 | ]

    mid.next = tail;

    // head -> [ 1 | ] 
    //            |
    // mid ->  [ 2 | ]
    //            |
    // tail -> [ 1->2 | ]
    tail.next = head;
    //            |
    // head -> [ 1->2 | ] 
    //            |
    // mid ->  [ 2 | ]
    //            |
    // tail -> [ 2 | ]

    head = nil;
    //            |
    // head   [ 2->1 | ] 
    //            |
    // mid -> [ 2 | ]
    //            |
    // tail ->[ 2->1 | ]

    mid = nil;
    //            |
    // head   [ 1 | ] 
    //            |
    // mid    [ 2->1 | ]
    //            |
    // tail ->[ 1 | ] 
    
    tail = nil;
    //            |
    // head   [ 1 | ] 
    //            |
    // mid    [ 1 | ]
    //            |
    // tail   [ 2->1| ]
    
	// 无东西可以回收
}

2 Mark-and-Sweep

从程序中已经知道的可以到达的内存地址(root set)出发，找到所有可以到达(reachable)的内存地址

2.1 mark阶段

  • 初始化: 维护一个workList里面，添加root到workList中
  • 迭代:
    • 从workList取一个元素
      • 如果尚未mark，则mark该元素，同时添加所有该元素引用的对象到workList中，然后移除
      • 如果已经mark，则直接移除
      • workList为空则退出迭代

2.2 sweep阶段

  • 遍历所有对象, 回收所有没有mark的对象的内存，同时将mark的对象重新变为没有mark以便下一次mark阶段迭代
    (遍历所有对象, 时间正比于对象的数目O(n))

3 Baker’s Algorithm

3.1 mark阶段

  • 初始化:
    • 维护enqueued/marked/unknown/deallocated4个双向链表(之前Mark-and-Sweep阶段只需要workList队列)
    • 所有分配的对象内存块初始都在unknow链表中，enqueued就代替了workList
  • 迭代:
    • 运行上一节的Mark算法，这次将从enqueued链表中移除的元素添加到marked
    • 如果enqueued为空则退出

3.2 sweep阶段

  • 释放所有unknow链表中的对象内存块，同时将内存块添加到deallocated中 (O(1))
  • 将所有marked的对象内存块移动到unknown中用于下一次迭代(O(1) 只需要链表头部的指针换一下)

3.3 实现细节

  • 不维护单独的链表
    可以猜测之前naive的做法
1
2
3
4
5
class LinkedList {
    Pointer* toTheMemoryLocation;
    LinkedList* next;
    LinkedList* prev;
}
  • 直接将指针嵌入到分配给对象的内存地址中(如果对象还能分配出来，那么链表就不会空间不足)
1
2
3
4
5
6
7
class SomeObject {
    // 编译器隐式的加入如下字段
    State s;
    LinkedList* next;
    LinkedList* prev;
    // 对象原有字段
}

3.4 优点与缺点

优点

  • 时间正比于可以到达(reachable)的对象数目
    缺点
  • Stop-the-world算法会引入巨大的停顿时间
  • 链表占用大量的空间