内存回收的一些基本方法

内存垃圾回收(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时顺便把指向的对象回收了。

一个简单的智能指针的实现(用于应付面试)

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挺好用的,下面是一个例子。

#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需要解决的最主要问题。这个问题最简单的方法就是查表。

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就越不管你。
基本的过程如下:

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特别复杂。自动回收的代价就是性能的下降,在有些情况下自动回收可能会比手动释放性能更好。即使性能差点,能摆脱内存泄露这样的问题,还是非常值得的。

参考

http://en.wikipedia.org/wiki/Garbage_collection_(computer_science)

http://www.memorymanagement.org/glossary/t.html

http://www.hpl.hp.com/personal/Hans_Boehm/gc/

http://xtzgzorex.wordpress.com/2012/10/11/demystifying-garbage-collectors/

本文出自 “牛哥的博客” 博客,请务必保留此出处http://nxlhero.blog.51cto.com/962631/1293433

更多相关文章
  • 他曾经在eBay上兜售Xbox Durango开发工具包,他声称知道下一代Xbox和PlayStation秘密,甚至拥有两台下一代Xbox原型,接触过下一代主机游戏<Homefront 2>和<Sleeping Dogs 2>,在<战争机器3>发售前就玩过了游戏, ...
  • ​​文/葛甲陈彤加盟小米是个没出太大意外的消息,但真正公布出来的时候,还是让很多人惊呼连连.从陈彤离职,到退还编辑们三年来的罚款,再到最终正式加盟小米,这怎么看都像是一起精心策划的营销大戏.一向善于占领关注焦点的小米,成了最大赢家.陈彤加盟小米的逻辑相当清晰,小米400亿美元估值,浪新不到30亿,谁 ...
  • 当地时间周三,微软在Windows 8开发者博客上展示了Windows 8触控屏幕的运行视频,细心的用户很快发现了Windows 8桌面版的最新版本号8165.fbl_fun_resp.111205-2000,而来自winunleaked.tk的消息显示,目前最新版本的Windows 8版本号为Bu ...
  •          JBOSS的版本从5.0升级到eap 6.2的版本,也算是突破了一下,为什么这样说呢?         现在JBOSS EAP 6.2版本这里面有一个模块的概念,所以如果是通用的jar包的话需要在模块里面配置,每有一个jar包都需要配置一下,很恶心.而5.0版本的直接把jar包放到 ...
  • 易网科技讯,五道口沙龙第41期于7月7日在北京举行.本次沙龙主题是"医生集团"专场.神州海德医疗集团常务副总裁丑东明在沙龙上发表了演讲.丑东明首先先介绍了一下神州海德集团,神州海德是中国顶尖的心血管专家团队共同建立的一个以心血管专家和技术专家为核心的专科医疗技术团队和投资管理机构 ...
  • 欢迎大家加入运维开发讨论交流群来交流,群号 365534424 关于扩展性的定义 可伸缩性(可扩展性)是一种对软件系统计算处理能力的设计指标,高可伸缩性代表一种弹性,在系统扩展成长过程中,软件能够保证旺盛的生命力,通过很少的改动甚至只是硬件设备的添置,就能实现整个系统处理能力的线性增长,实现高吞吐量 ...
一周排行
  • 前言 我们在手机上布局一般是这个样子的: 其中头部对整个mobile的设计至关重要,而且坑也很多: ① 一般来说整个header是以fixed布局,fixed这个产物在移动端来说本身坑就非常多 ② 在Hybrid应用 ...
  • -31 今天我已经优化了很多地方,让客户使用起来几乎是傻瓜式使用了,废话不多说,我们开始吧. 默认的我提供了一些图片,但是也只占用了8M多,2.0版本目前总共有45M左右大小,毕竟包含了fontaweso ...
  • 文中内容来源于stackoverflow上的一个问题 ,提问者想知道Mesos在实际的使用中都有哪些使用场景,来自Twitter的工程师从容器编排.资源利用率.优先级和资源抢占.以及服务运行等几个角度,对问题进行了回 ...
  • 据国外媒体报道,  虽然目前苹果公司打死也不会说出具体数字,但是华尔街的分析师们还是通过各种渠道(比如供应链)做出了自己的预测.这是目前华尔街最好奇的数字,蒂姆·库克有可能在周二的苹果第三财季财报中公布这一数字.不过 ...
  • 为了用Xdos进行攻击ac(无线交换机)的实验,在搭建攻击环境上下了好大的功夫,     由于小人愚钝,Xdos在xp下老报错send error 10004!所以我在虚拟机中装了个windows server200 ...
  • 2011年9月,杨永智回到母校华中科技大学给同学们做关于创业的演讲.易网科技讯 10月31日消息百纳信息CEO杨永智也许不希望你认为他的公司只是"开发出一款浏览器"--像<新闻联播>说 ...
  • 众所周知,苹果搞的一套框架NSContention发送请求与接收请求的方式十分繁琐.操作起来很不方便.不仅要做区分各种请求设置各种不同的参数,而且还要经常在多线程里操作,同时还要对请求与返回的数据做各种序列化的操作, ...
  • 我们知道在windows里面有远程桌面(著名的有pcanywhere,网络人等)对吧,在linux下我们同样有这个东西,其中最流行的一种就是VNC,其实VNC是一种协议,它的全称是virtual network co ...
  • IEEE802 局域网标准 IEEE 是英文 Institute of Electrical and Electronics Engineers 的简称,其中文译名是电气和电子工程师协会.该协会的总部设在美国,主要开 ...
  • 1.nil:一般赋值给空对象: 2.NULL:一般赋值给nil之外的其他空值.如SEL等: 举个栗子(好重啊~): [NSApp beginSheet:sheet              modalForWindo ...