logo
搜索
我的图书馆

发文章

发文工具

其他工具

留言交流
搜索
分享

内存垃圾回收 GC

 scholes_goal 2011-11-09

最近在公司内部做了一次关于垃圾回收的讲座，我打算用几篇文章把讲座的内容整理出来，供大家参考。在开始之前，我们有必要稍微复习一下内存分配的主要方式，大多数主流语言都支持三种内存分配方式：

1. 静态分配：静态变量和全局变量的分配形式 
2. 自动分配：在栈中为局部变量分配内存的方法 
3. 动态分配：在堆中动态分配内存空间以存储数据的方式

如何管理堆对象的生命周期，正是我们要探讨的话题。从面向对象的角度来看，每个对象的生命周期应该由自己管理，也就是说，作为一个对象，它知道自己什么时候被创建，什么时候被销毁。然而事实上却不是这样，因为对象之间有相互引用关系，所以对象往往不知道自己什么时候可以宣告死亡，如果对象释放太早，会造成“悬空引用”问题；如果释放的太晚或者不释放，又会造成内存泄露问题。

在C/C++中提供了显式的内存管理方案，可以用malloc/new来显式分配一段内存，而当这段内存不再需要的时候，使用free/delete把它返回给系统，看下面这段代码：

view plain
  1. int main()  
  2. {  
  3.     string *ptr = new string;  
  4.     // do something  
  5.     delete ptr;  
  6. }  

这个过程非常的自然清晰，不是吗？在使用之前用new分配一段内存，使用完毕后再用delete销毁。可惜的是，现实世界中的代码不都是这么简单，开发人员会由于各种各样的原因，而忘记释放内存，或者释放内存不正确，从而导致内存泄露。下面是一个典型的内存泄露示例：

view plain
  1. void service(int n, char** names)  
  2. {  
  3.     for(int i=0; i< n; i++)  
  4.     {  
  5.         char* buf = (char*) malloc(strlen(names[i]));  
  6.         strncpy(buf,names[i], strlen(names[i]));  
  7.     }      
  8. }  

显然这里释放内存的工作应该由开发人员完成，但开发人员却忘记了调用free()。

view plain
  1. void service()  
  2. {  
  3.     Node* x = new Node("mid-autumn");  
  4.     Node* ptr = x;  
  5.     delete x;  
  6.     cout << ptr->data << endl;       
  7. }  

 

这段代码的问题在于不正确的调用了delete，提前释放了x的内存而导致最后一句ptr->data出错。麻烦的事情远不止这些，继续看下面这段代码：

view plain
  1. int main()  
  2. {  
  3.     string *ptr = new string[100];  
  4.     // do something  
  5.       
  6.     delete ptr;  
  7. }  

这段代码中看起来很美，使用new来为100个string对象分配内存，最后也使用了delete来销毁，但不幸的是这段代码仍然不正确，这里为100个string对象分配的对象，最后可能有99个string未必删除，原因在于没有使用相同形式的new和delete，正确的应该为

view plain
  1. int main()  
  2. {  
  3.     string *ptr = new string[100];  
  4.     // do something  
  5.       
  6.     delete [] ptr;  
  7. }  

注意到最后那个[]了吗？简单的说，在调用new时使用了[]，在调用delete时也要使用[]。但这条规则又不像我们说的这么简单，有了typedef，在调用new时可能没有使用[]，但是在调用delete时却要使用[]，如下面这段代码：

view plain
  1. typedef string address[4];  
  2. int main()  
  3. {  
  4.     string *ptr = new address;  
  5.     // do something  
  6.       
  7.     delete [] ptr;  
  8. }  

噩梦还没有到此结束，如果我们有两个类型Array和NamedArray，其中NamedArray公有继承于Array，如下面的代码所示：

view plain
  1. template<class T>  
  2. class Array  
  3.  {  
  4.     public:  
  5.         Array(int lowBound, int highBound);  
  6.         ~Array();  
  7.     private:  
  8.         vector<T> data;  
  9.         size_t size;  
  10.         int lBound, int hBound;  
  11. };  
  12. template<class T>  
  13. class NamedArray : public Array<T>   
  14. {  
  15.     public:  
  16.         NamedArray(int lowBound, int highBound, const string& name);  
  17.     private:  
  18.         string* aName;     
  19. };  

 

开发人员在使用上面两个类型时，写了这样一段代码：

 

view plain
  1. int main()  
  2. {  
  3.    NamedArray<int> *pna = new NamedArray<int>(10,20,"Users");  
  4.    Array<int> *pa;  
  5.    pa = pna;  
  6.    // do something  
  7.    delete pa;  
  8. }  

看出问题所在了吗？最后一行调用delete并不能释放aname所占用的内存，原因在于Array类型的析构函数~Array()并没有被声明为virtual！所以父类的析构函数并没有表现出多态的特性。

通过上面的几个例子，想必大家已经体会到了显式管理内存的困难，于是在C++里出现了智能指针的概念，来减少开发人员手工管理内存出错的可能性，最常见的如STL中的std::auto_ptr，本质上它也是个普通的指针，只不过std::auto_ptr会在析构的时候调用 delete 操作符来自动释放所包含的对象。

view plain
  1. int main()  
  2. {  
  3.    auto_ptr<int> ptr(new int(42));  
  4.      
  5.    cout << *ptr << endl;  
  6.    // 不再需要delete了  
  7. }  

在大名鼎鼎的Boost C++库中更是包含了很多的智能指针，可用于各种情况，如作用域指针boost::scoped_ptr，共享指针boost::shared_ptr等等，如下代码所示：

view plain
  1. #include <boost/shared_ptr.hpp>   
  2. #include <vector>   
  3. int main()   
  4. {   
  5.   std::vector<boost::shared_ptr<int> > v;   
  6.   v.push_back(boost::shared_ptr<int>(new int(1)));   
  7.   v.push_back(boost::shared_ptr<int>(new int(2)));   
  8. }   

 

对象生命周期管理，除了使用显式管理方案之后，还有一种机制就是隐式管理，即垃圾回收（Garbage Collection，简称为GC），最早出现于世界第二元老语言Lisp中，Jean E. Sammet曾经说过，Lisp语言最长久的贡献之一是一个非语言特征，即代表了系统自动处理内存的方法的术语极其技术——垃圾回收（GC，Garbage Collection）。而现在很多平台和语言都支持垃圾回收机制，如JVM、CLR、Python等。

 

本文主要关注垃圾回收算法。垃圾回收机制，最早出现于世界上第二元老语言Lisp，Jean E. Sammet曾经说过，Lisp语言最长久的共享之一是一个非语言特征，即代表了系统自动处理内存的方法的术语极其技术——垃圾收集（GC，Garbage Collection）。接下来我们介绍几种经典的垃圾回收算法，这些算法尽管出现于60、70年代，但是现在的CLR、JVM等上面的垃圾回收器，仍然使用了它们。

 

引用计数算法

引用计数（Reference Counting）算法是每个对象计算指向它的指针的数量，当有一个指针指向自己时计数值加1；当删除一个指向自己的指针时，计数值减1，如果计数值减为0，说明已经不存在指向该对象的指针了，所以它可以被安全的销毁了。可以很直观的用下面的图表示：

引用计数算法的优点在于内存管理的开销分布于整个应用程序运行期间，非常的“平滑”，无需挂起应用程序的运行来做垃圾回收；而它的另外一个优势在于空间上的引用局部性比较好，当某个对象的引用计数值变为0时，系统无需访问位于堆中其他页面的单元，而后面我们将要看到的几种垃圾回收算法在回收前都回遍历所有的存活单元，这可能会引起换页（Paging）操作；最后引用计数算法提供了一种类似于栈分配的方式，废弃即回收，后面我们将要看到的几种垃圾回收算法在对象废弃后，都会存活一段时间，才会被回收。

引用计数算法有着诸多的优点，但它的缺点也是很明显的。首先能看到的一点是时间上的开销，每次在对象创建或者释放时，都要计算引用计数值，这会引起一些额外的开销；第二是空间上的开销，由于每个对象要保持自己被引用的数量，必须付出额外的空间来存放引用计数值；引用计数算法最大的缺点就在于它无法处理环形引用，如下图所示：

此处蓝色的这两个对象既不可达也无法回收，因为彼此之间互相引用，它们各自的计数值都不为0，这种情况对引用计数算法来说是无能为力的，而其他的垃圾回收算法却能很好的处理环形引用。

引用计数算法最著名的运用，莫过于微软的COM技术，大名鼎鼎的IUnknown接口：

view plain
  1. interface IUnknown  
  2. {  
  3.     virtual HRESULT _stdcall QueryInterface  
  4.         (const IID& iid, void* * ppv) = 0;  
  5.     virtual ULONG _stdcall AddRef() = 0;  
  6.     virtual ULONG _stdcall Release() = 0;  
  7. }  

 

其中的AddRef和Release就是用来让组件自己管理其生命周期，而客户程序只关心接口，而无须再去关心组件的生命周期，一个简单的使用示例如下：

view plain
  1. int main()  
  2. {  
  3.     IUnknown* pi = CreateInstance();  
  4.     IX* pix = NULL;  
  5.     HRESULT hr = pi->QueryInterface(IID_IX, (void*)&pix);  
  6.     if(SUCCEEDED(hr))  
  7.     {  
  8.         pix->DoSomething();  
  9.         pix->Release();  
  10.     }  
  11.     pi->Release();  
  12. }  

 

上面的客户程序在CreateInstance中已经调用过AddRef，所以无需再次调用，而在使用完接口后调用Release，这样组件自己维护的计数值将会改变。下面代码给出一个简单的实现AddRef和Release示例：

view plain
  1. ULONG _stdcall AddRef()  
  2. {  
  3.     return ++ m_cRef;  
  4. }  
  5. ULONG _stdcall Release()  
  6. {  
  7.     if(--m_cRef == 0)  
  8.     {  
  9.         delete this;  
  10.         return 0;  
  11.     }  
  12.     return m_cRef;  
  13. }  

在编程语言Python中，使用也是引用计数算法，当对象的引用计数值为0时，将会调用__del__函数，至于为什么Python要选用引用计数算法，据我看过的一篇文章里面说，由于Python作为脚本语言，经常要与C/C++这些语言交互，而使用引用计数算法可以避免改变对象在内存中的位置，而Python为了解决环形引用问题，也引入gc模块，所以本质上Python的GC的方案是混合引用计数和跟踪（后面要讲的三个算法）两种垃圾回收机制。

 

标记-清除算法

标记-清除（Mark-Sweep）算法依赖于对所有存活对象进行一次全局遍历来确定哪些对象可以回收，遍历的过程从根出发，找到所有可达对象，除此之外，其它不可达的对象就是垃圾对象，可被回收。整个过程分为两个阶段：标记阶段找到所有存活对象；清除阶段清除所有垃圾对象。

标记阶段：

 

 

清除阶段：

 

 

相比较引用计数算法，标记-清除算法可以非常自然的处理环形引用问题，另外在创建对象和销毁对象时时少了操作引用计数值的开销。它的缺点在于标记-清除算法是一种“停止-启动”算法，在垃圾回收器运行过程中，应用程序必须暂时停止，所以对于标记-清除算法的研究如何减少它的停顿时间，而分代式垃圾收集器就是为了减少它的停顿时间，后面会说到。另外，标记-清除算法在标记阶段需要遍历所有的存活对象，会造成一定的开销，在清除阶段，清除垃圾对象后会造成大量的内存碎片。

 

 

标记-缩并算法

标记-缩并算法是为了解决内存碎片问题而产生的一种算法。 它的整个过程可以描述为：标记所有的存活对象；通过重新调整存活对象位置来缩并对象图；更新指向被移动了位置的对象的指针。

 

标记阶段：

 

清除阶段：

 

标记-压缩算法最大的难点在于如何选择所使用的压缩算法，如果压缩算法选择不好，将会导致极大的程序性能问题，如导致Cache命中率低等。一般来说，根据压缩后对象的位置不同，压缩算法可以分为以下三种：

1. 任意：移动对象时不考虑它们原来的次序，也不考虑它们之间是否有互相引用的关系。 
2. 线性：尽可能的将原来的对象和它所指向的对象放在相邻位置上，这样可以达到更好的空间局部性。 
3. 滑动：将对象“滑动”到堆的一端，把存活对象之间的自由单元“挤出去”，从而维持了分配时的原始次序。

 

 

节点拷贝算法

节点拷贝算法是把整个堆分成两个半区（From，To）， GC的过程其实就是把存活对象从一个半区From拷贝到另外一个半区To的过程，而在下一次回收时，两个半区再互换角色。在移动结束后，再更新对象的指针引用，GC开始前的情形：

GC结束后的情形：

节点拷贝算法由于在拷贝过程中，就可以进行内存整理，所以不会再有内存碎片的问题，同时也不需要再专门做一次内存压缩。，而它最大的缺点在于需要双倍的空间。

总结

本文总共介绍了四种经典的垃圾回收算法，其中后三种经常称之为跟踪垃圾回收，因为引用计数算法能够平滑的进行垃圾回收，而不会出现“停止”现象，经常出现于一些实时系统中，但它无法解决环形问题；而基于跟踪的垃圾回收机制，在每一次垃圾回收过程中，要遍历或者复制所有的存活对象，这是一个非常耗时的工作，一种好的解决方案就是对堆上的对象进行分区，对不同区域的对象使用不同的垃圾回收算法，分代式垃圾回收器正是其中一种，CLR和JVM中都采用了分代式垃圾回收机制，但它们在处理上又有些不同，后面的文章再详细介绍这两种垃圾回收器的区别。

 

 

本文我们主要关注微软的CLR与JVM垃圾回收器方面的比较。我们知道CLR和JVM都采用了分代式垃圾回收器，而分代式垃圾回收器则基于以下几点假设：

1. 对象越新，其生存期就越短 
2. 对象越老，其生存期就越长 
3. 对堆的一部分执行GC比对整个堆执行GC要快

CLR和JVM尽管都采用了分代式垃圾回收器，但是它们在很多处理方面都有些不同：分代机制，大对象堆，回收模式，回收算法，寻找存活对象效率等。

分代机制

在CLR中，对象按年龄可以分为三代：第0代、第1代、第2代，如下图所示：

 

在这三代之间，对象代的提升过程，大家可以参考《CLR via C# 》，里面有比较详细的介绍。

JVM中对于对象的分代式新生代和旧生代：

 

回收模式

在CLR4.0之前，提供三种不同的垃圾回收模式：工作站并发GC、工作站非并发GC以及服务器GC，如下图所示：

 

 

工作站非并发GC模式，没有专门的GC线程，而是由工作线程负责回收，在回收过程中，需要暂时挂起应用程序，回收结束后应用程序继续运行，所以在回收过程中会有应用程序暂停现象：

工作站并发GC模式，为了解决在执行垃圾回收时引起的应用程序暂停问题，会有一个专门的GC线程负责垃圾回收，大多数时间垃圾回收都可以应用程序并发执行，但是仅仅是针对Full GC，而对于第0代、第1代对象，仍然会使用非并发模式执行，并发垃圾回收本质上牺牲了更多的CPU时间和内存来换取应用程序暂停时间的减小：

服务器GC模式运行在多CPU服务器上，如果在单CPU机器上配置了使用服务器GC，不会起任何作用，垃圾回收仍然会使用工作站非并发模式执行。服务器GC模式为每个CPU分配一个专用的垃圾回收线程和一个托管堆，并且该垃圾回收线程具有较高的优先级，在执行垃圾回收期间，应用程序工作线程会暂时挂起：

 

CLR 4.0中提供了后台垃圾回收机制，用于取代并发GC。

 

JVM（以Hotspot为例）中使用的垃圾回收更为复杂，针对新生代、旧生代在工作站和服务器上，分别使用不同的垃圾回收模式，如下图所示：

 

在Client端默认的方式为串行GC，而在服务端，对于新生代和旧生代默认的方式分别为：并行回收GC和并行GC：

 

下图体现了默认串行GC与并行GC之前的区别，并行GC会把堆分成多个区，分区进行标记和回收，但这两种方式都会引起应用程序的暂停：

 

下图体现了默认的标记缩并回收与并发GC，在并发GC中，标记的总共分为三个阶段，分别为：Initial Mark、Concurrent Marking和Remark，只有在Initial Mark和Remark阶段才会引起应用程序暂停，而在Concurrent Marking和清除阶段都是与应用程序并发执行，并不会引起暂停：

 

回收算法

在CLR中有专门的大对象堆（LOH），超过85000字节的对象将会分配在LOH上面，只有在进行第2代对象垃圾回收时才会同时对LOH进行回收，即一次Full GC。第0代、第1代、第2代对象所在的堆称之为小对象堆（SOH）。

在CLR中，对于小对象堆SOH，采用的回收算法为标记-缩并算法 ，由于移动大对象比较耗费时间，所以在LOH上，CLR采用了标记-清除算法 ，即只做对象的清除并不对大对象堆进行压缩。

在JVM中，对于新生代对象采用节点复制算法 进行回收，这也是为什么我们在上面的图中，新生代对象堆分为S0和S1的原因，有时也称之为为From和To；对于旧生代对象根据不同的回收模式，采用不同的回收算法：

串行GC：标记-缩并算法（滑动缩并） 
并行GC：标记-缩并算法 
并发GC：标记-清除算法

提高查找存活对象的效率

现在考虑这样一个问题，只对第0代（或者新生代）对象做回收，在查找存活对象过程中（不关是标记-缩并还是节点复制算法），从根集合开始，如果发现有一个根对象指向了第1代、第2代（或者旧生代），为了提高效率，垃圾回收器将会立即终止这条线上的查找：

 

这样带来的一个问题是:如果在第0代（或者新生代）分配的对象X，没有根对象指向它，但有一个第1代或者第2代（旧生代）的对象，指向了该新创建的对象：

此时虽然没有根对象可以到达新创建的对象X，但由于有其他代的对象指向它，所以它仍然不能当做垃圾回收，为了解决这个问题，人们提出了各种解决方案，常见的有：

1. 记忆集 
2. 硬件标记 
3. 虚拟页面标记 
4. 字标记 
5. 卡标记

由于硬件标记需要特定的硬件平台来支持，所以不具有可移植性，现在更多的垃圾回收器都使用了软件解决方案，在CLR和JVM上都使用了卡标记技术，即把托管堆分成一个一个的卡片，这个卡片代表一个抽象的概念（卡片的大小可以等于一个字，也可以等于一个虚拟页面）。如果有卡片上的对象发生了变化，则在Card Table中做一个标记，在查找存活对象时，除了要查找根对象之外，还有查找Card Table中标记的对象所引用的对象：

 

在CLR和JVM上所使用的卡片大小也不相同，CLR为128字节一个卡片，而JVM上为512字节一个卡片。在更新卡片过程中，它们都是按字节（Byte）进行更新而不是按位（Bit）进行更新。

总结

虽然CLR和JVM都采用了分代式垃圾回收器，但是它们在很多处理上都有区别，不管怎样，分代式垃圾回收器的一个原则就是把对象分成不同的区（按年龄也好、按对象大小也好），以便在不同的分区上采用不同的回收算法和模式。

    本站是提供个人知识管理的网络存储空间，所有内容均由用户发布，不代表本站观点。请注意甄别内容中的联系方式、诱导购买等信息，谨防诈骗。如发现有害或侵权内容，请点击一键举报。
    转藏 分享 献花（0）

    来自： scholes_goal > 《Cs》

    举报/认领

    0条评论

    发表

    请遵守用户 评论公约

    类似文章 更多