内存垃圾回收(Garbage Collection)是一个很古老的技术了，最开始在Lisp上出现。如今几乎所有高级语言都有GC，大部分程序员不再需要绞尽脑汁通宵达旦去查找内存泄露的原因了。我以前也不怎么关心垃圾回收这个问题，可是面试时老是被问到智能指针，而我又不会写，因为我对C++不熟。所以决定研究并且总结一下这个问题。
其实智能指针都不能称为GC，就是编译器给你加了delete或free，基于的原理是引用计数(Reference Counting)。GC一般基于一下两个原理
Reference Counting(引用计数): 每个对象都设置一个参数，就是引用它的变量，引用少一个就减1，多一个就加1，为0时回收
Reachability(可达性):有一组基本的对象或变量是可达的，称为root set，这些变量或对象指向的对象也是可达的，同理，一个可达对象指向的对象是可达的。
本文简单的介绍了常用的几种内存回收算法，包括Reference Counting，Mark and Sweep，Semispace, Generation。
Reference Counting
一般没有真正的GC使用Reference Counting。智能指针使用了Reference Counting，在指针析构的时候，将引用数减1，为0时顺便把指向的对象回收了。
一个简单的智能指针的实现(用于应付面试)
|
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
|
template
<
class
T>
class
SmartPointer {
protected
:
T* ref;
unsigned
int
* ref_count;
public
:
SmartPointer(T *ptr)
{
ref = ptr;
ref_count = (unsigned
int
*)
malloc
(
sizeof
(unsigned
int
));
*ref_count = 1;
}
SmartPointer(SmartPointer<T> & sptr)
{
ref = sptr.ref;
ref_count = sptr.ref_count;
++*ref_count;
}
SmartPointer<T> & operator= (SmartPointer<T> &sptr)
{
if
(
this
!= &sptr)
{
ref = sptr.ref;
ref_count = sptr.ref_count;
++*ref_count;
}
return
*
this
;
}
~SmartPointer()
{
--*ref_count;
if
(*ref_count == 0)
{
delete
ref;
free
(ref_count);
ref = NULL;
ref_count = NULL;
}
}
T getValue() {
return
*ref;}
}
|
智能指针是最简单的一种gc方法。甚至，这算不上一种gc，实际上是编译器帮你写了free或者delete，基于的原理就是：对象的作用域结束时都会自动调用析构函数，这个析构函数是编译器在编译时加上的。gc都会有一个触发事件，对于智能指针来说，就是作用域结束。对于其他的，可能是内存不够了，然后会启动gc进行回收。
Mark and Sweep
Mark and Sweep使用的是可达性。在一个程序中，所有的全局变量，静态变量，局部变量都是可达的，这些称为root set。从root出发，找到所有可达的，然后回收不可达的。
基本的过程如下：
每个object都有一个singlebit的标志位，一开始都是0
要回收的时候，扫两遍
第一遍，从root变量开始进行DFS扫描，可达的都将它们的标志位置1
第二遍，搜索所有的object，如果是1，置为0，如果是0，reclaim
这就有一个问题，这个root怎么找呢？比如C语言，怎么确定找出栈上哪些是变量？更不用说要确定哪些是指针了。对于高级的动态语言，虚拟机或者解释器都会维护一个所有符号的表，这样找起来是很容易的。gc可以分为Precise gc和Conservative gc。前者明确知道内存的哪个地方是变量，哪个地方是指针，因此可以精确的进行回收，这种一般适用于高级语言，例如lisp,python,Java等。但是对于C语言，只能假设栈上任何32bit(或者64bit)都是指针，在此基础上可能会有一些检测方法，然后把这些指针当作root，进行扫描。C/C++还有一个问题就是internal pointer。因为在高级语言里，一般所有的地址都指向对象的开头，但是C/C++指针可以指向对象的任何地方，这也导致了扫描的困难。所以C/C++一般不会使用gc。This is the nature of C! 但是也有一些比较好的C/C++的gc，例如Boehm GC，它是一种Conservative GC。
Boehm挺好用的，下面是一个例子。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
#include <stdio.h>
#include <gc/gc.h>
int
main()
{
int
i;
GC_INIT();
int
*p;
for
(i = 0; i < 1000000; i++)
{
p = (
int
*)GC_MALLOC(20*1024*1024);
p[i/400] = 5;
if
(i % 10000 == 0)
printf
(
"Heap size = %d\n"
,GC_get_heap_size());
}
}
|
这段代码不会发生内存溢出，如果使用malloc但是不free，很快内存就不够了。
但是如果我把大小从20*1024*1024增加到1024*1024*1024，就有问题了。
内存不够用了。说明它的回收做的不够好。而使用malloc加free，可以一直运行下去。我的内存有2G，是够用的。Boehm GC是最有名的C/C++ GC，而且不少项目也在用它。但是，C语言的本性决定了它不需要GC。
Semispace
在进行内存回收时，内存整理也是必须的。否则内存中充满了碎片。Semispace的方法也是基于可达性，从名字也可以看出，它是要把内存分成两半，只有一半可用，一个FromSpace，一个ToSpace(或者叫Old,New,whatever)。
基本工作过程是：
从root开始扫描，找到可达的，就从FromSpace复制到ToSpace，一直这样找下去，最后可达的都被移到了ToSpace，而且不存在碎片。
这个过程牵涉到一个很严重的问题：指针重定向，称为pointer forward。这是semispace需要解决的最主要问题。这个问题最简单的方法就是查表。
|
1
2
3
4
5
6
7
8
9
10
|
copy(p):
if
(content of p is already copy to ToSpace)
p = forwarding_address(p)
ret
if
(content of p is not copied to ToSpace)
copy content of p to ToSpace
forwarding_address(p) = ToSpacePtr;
ToSpacePtr +=
sizeof
(p)
foreach pointer x in content of p:
copy(x)
|
如果回收的时候堆里大部分都是garbage，那么semispace的方法特别好，如果大部分都是可达的，那么效率就很低了。
Generation Garbage Collection
如果你在程序里读入了一些静态的数据，很大，而且需要常驻内存，而且里面确定没有指针。你肯定不希望GC一直去扫描它或者一直移来移去。Java和.Net采用的方法称为Generation Garbage Collection，将对象分成几个generation，新创建的对象在 Generation 0(Java使用Young,Old,Permenant,Eden,Survior,Tenured,.Net使用0,1,2)，逃过第一次扫荡(Sweep)的被挪到Generation 1，逃过两次的被挪到Generation 2，.Net就到2，就是你逃过回收的次数越多，就越年老，GC就越不管你。
基本的过程如下：
|
1
2
3
4
5
6
7
8
9
10
11
12
|
if
(G0 is almost full)
{
scan and reclaim G0
if
(G1 is almost full)
{
scan and reclaim G1
if
(G2 is almost full)
scan and reclaim G2
move survivors to G2
}
move survivors to G1
}
|
这张图是Java使用的方法，先分了Young,Old,Permanent，然后里面又细分，挺复杂的，但是思想就是上面所叙述的。
总结
本文只是简单的介绍了垃圾回收的一些基本思想方法，实际上GC特别复杂。自动回收的代价就是性能的下降，在有些情况下自动回收可能会比手动释放性能更好。即使性能差点，能摆脱内存泄露这样的问题，还是非常值得的。
本文转自nxlhero 51CTO博客，原文链接：http://blog.51cto.com/nxlhero/1293433，如需转载请自行联系原作者
