<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
<html lang="en-US">
<head>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
<meta http-equiv="Content-Language" content="zh-CH">
<link rel="stylesheet" type="text/css" href="rhg.css">
<title>第五章 垃圾回收</title>
</head>
<body>
<h1>第五章 垃圾回收</h1>
<h2>程序执行映像</h2>
<p>有些突然，在本章开始的部分，准备复习一下程序执行时内存空间的状态。
本章会涉及到计算机底层的部分，如果不事先储备一些知识的话，恐怕会无法应对。
这些知识在随后的章节中迟早也会用到。在这里弄懂了，后面就轻松了。</p>
<h3>段（segment）</h3>
<p>一般C程序在内存空间中会有如下几个部分。</p>
<ol>
<li>文本段</li>
<li>存放静态变量和全局变量的地方</li>
<li>机器栈（stack）</li>
<li>堆（heap）</li>
</ol>
<p>文本段是代码存放的地方。第二点一看便知。函数参数和局部变量压在机器栈中。
堆由<code>malloc</code>负责分配。</p>
<p>再稍微说一下第三点。因为是机器“栈”，自然使用的是栈的数据结构。
也就是说，可以不断在上面堆加新东西。实际上，栈中的值是以<code>int</code>这样细小的单位堆放的，
不过，可以看到，还有一个逻辑上更大的单位。称之为堆帧（stack frame）。</p>
<p>栈帧对应着一次函数调用。也就是说，每次函数调用都会推进去一个栈帧。
函数返回时，弹出一个栈帧。尽可能简化一下，机器栈的情况就如图1所示。</p>
<p style="text-align:center;"><img src="images/ch_gc_macstack.png" title="机器栈" alt="机器栈" /><br>图1: 机器栈</p>
<p>图中，栈的上面写了“上”，但是， 机器栈未必是从低地址向高地址延伸。
比如，x86的机器栈就是向低地址延伸。</p>
<h3><code>alloca()</code></h3>
<p>使用<code>malloc()</code>可以在堆上分配任意大小的内存区域。<code>alloca()</code>是它的机器栈版。
不同于<code>malloc()</code>，用<code>alloca()</code>分配的内存无需释放。
也许说函数<code>return</code>时，释放就“完成”了更好一些。
因此，分配的值是不能当作函数返回值的。“不能返回指向局部变量的指针”也是一样的。</p>
<p>到这里就好了。可以在局部分配运行时可改变长度的数组，理解到这种程度就可以了。</p>
<p>但是世上还存在没有native版本的<code>alloca()</code>的环境。即便如此，还有很多人想用<code>alloca()</code>，
所以，可以用C写一个完成同样功能的函数。在这种情况下，只要实现“无需释放”这一特征，
无需在机器栈中分配。通常不会这么做。如果可能，都会先实现native版本的<code>alloca()</code>。</p>
<p><code>alloca()</code>用C怎样实现呢？最简单的实现是，先使用<code>malloc()</code>分配内存。
让<code>alloca()</code>将调用函数和分配的地址作为一组记录到一个全局列表中。
下一次调用<code>alloca()</code>的时候，检查这个列表，
那些分配给已经结束的函数的内存使用<code>free()</code>释放就可以了（图2）。</p>
<p style="text-align:center;"><img src="images/ch_gc_calloca.png" title="C实现alloca的动作" alt="C实现alloca的动作" /><br>图2: C实现alloca的动作</p>
<p><code>ruby</code>的<code>missing/alloca.c</code>是一个模拟版<code>alloca()</code>实现的例子。</p>
<h2>概要</h2>
<p>从这里开始就进入本章的主题，一个关于垃圾回收的话题。</p>
<h3>何为GC</h3>
<p>对象通常存在于内存之中。如果生成了大量的对象，势必要占用大量的内存。
如果有无限的内存可以使用当然没什么问题，但现实中，内存容量必然是有限的。
因此，用过的内存必须回收再利用。具体点说，
通过<code>malloc()</code>得到的内存必须用<code>free()</code>归还。</p>
<p>不过，把<code>malloc()</code>与<code>free()</code>全部交给程序员管理会很麻烦。特别是在面向对象程序中，
对象之间相互引用，很难知道哪个对象的内存应该释放。</p>
<p>这时候就轮到垃圾回收登场了。所谓垃圾回收（garbage collection，以下简称GC），
是“自动检测和释放不再需要的内存”的功能。有了GC，就不必再为“何时<code>free()</code>内存”而烦恼了。
是否使用它会让程序编写的难易程度有很大差异。</p>
<p>顺便说一下，过去有一些书，在其中可以看到，“整理可用内存碎片就是GC”。
这是“压缩（compaction）”的工作。压缩会让内存变得紧凑。
压缩完成后，可以轻松提高内存缓存的命中率，起到加速的效果，然而，这不是GC的主要目的。
GC的目的在于内存回收。实际上，许多GC在内存回收时并不做压缩。<code>ruby</code>的GC也不做压缩。</p>
<p>那么，具体有什么样的GC系统可以使用呢？<a href="http://www.hpl.hp.com/personal/Hans_Boehm/gc">Boehm GC</a>
可以作为C或C++的add-on使用。此外，在Java和Perl、Python、C#、Eiffel等最近的语言中，
GC已经成为的标准配置。本章就来详细讨论<code>ruby</code>的GC。目标文件是<code>gc.c</code>。</p>
<h3>GC可以做的事</h3>
<p>讨论GC算法之前，需要解释一下“GC是什么”。也就是说，“无用的内存”处于一种怎样的状态。</p>
<p>为了让讨论更加具体，将对象间的链接结构简化。也就是图3所示的状态。</p>
<p style="text-align:center;"><img src="images/ch_gc_objects.png" title="对象" alt="对象" /><br>图3: 对象</p>
<p>首先，全局变量所指的而且在语言堆栈上的对象“确实必要”。
对象实例变量所指的对象也是必要的。从这些对象出发，顺着链接前进可以到达的对象，都是必要的。</p>
<p>稍微理论点说，以“确实必要”的对象为起点，递归的沿链接前进可以到达的所有对象都是必要的。
图4表现了这种情况。线左侧是“确实必要”的对象，从那开始能够到达的都涂成了黑色。
涂黑的对象都是必要的。其余的可以释放。</p>
<p style="text-align:center;"><img src="images/ch_gc_gcimage.png" title="必要的对象和不必要的对象" alt="必要的对象和不必要的对象" /><br>图4: 必要的对象和不必要的对象</p>
<p>术语将“确实必要的对象”称为“GC的根”。追踪必要对象的结果可以视为一个树型结构，而它就是树的根（root）。</p>
<h3>标记与清除（mark & sweep）</h3>
<p>GC最初由Lisp实现，Lisp最初的GC实现就是世界上最早的GC，称为标记与清除（mark & sweep）型GC。
<code>ruby</code>的GC也是这一种。</p>
<p>标记与清除型GC的印象接近于“必要对象”的定义。
首先给根对象加上“记号”。以此为出发点，给找到的对象都加上“标记”。
这个全过程就是“标记”阶段。</p>
<p>所以，除此之外，其它的对象都是无法找到的，检查全部的对象集合，释放掉那些没有“标记”的对象（清除）。
这就是扫雷（minesweeper）中的sweep（清除）。</p>
<p>这种方法有两个优点。</p>
<ul>
<li>GC实现之外的地方不必（太多）考虑GC。</li>
<li>有环也可以释放（关于环，可以参考引用计数一节）。</li>
</ul>
<p>缺点也是两个。</p>
<ul>
<li>为实现清除，至少要将所有的对象遍历一次。</li>
<li>GC的负荷会集中于一点</li>
</ul>
<p>使用Emacs编辑器的时候，时常会出现“<code>Garbage collecting...</code>”，完全失去响应，这时就是在进行GC。
这就是第二个缺点一个直接
rhgchs-20070924
需积分: 0 27 浏览量
2009-09-21
23:35:03
上传
评论
收藏 1.21MB ZIP 举报
rhgchs-20070924.zip （69个子文件） 
rhg.css 2KB
chapter05.html 65KB chapter07.html 9KB chapter01.html 43KB chapter02.html 46KB chapter06.html 22KB chapter04.html 57KB chapter03.html 23KB
images 
ch_minimum_supersub.png 8KB ch_abstract_syntree.png 25KB ch_minimum_constref.png 19KB ch_class_reqlink.png 17KB ch_gc_cycle.png 7KB ch_name_chain.png 15KB ch_gc_stop3.png 9KB ch_minimum_multiinherit.png 20KB ch_minimum_ccc.png 18KB ch_abstract_ci.png 17KB ch_class_simulate.png 48KB ch_object_value.png 7KB ch_object_string.png 7KB ch_name_aset.png 9KB ch_gc_heapitems.png 16KB ch_gc_calloca.png 25KB ch_gc_macstack.png 15KB ch_minimum_objimage.png 13KB ch_minimum_Kernel.png 13KB ch_object_rbasic.png 30KB ch_gc_heaps.png 34KB ch_class_mmm.png 36KB ch_object_classtree.png 40KB ch_variable_gaccess.png 24KB ch_gc_mostcopy.png 28KB ch_minimum_modclass.png 6KB ch_object_flags.png 41KB ch_object_givtable.png 26KB ch_class_infloop.png 10KB ch_object_rdata.png 18KB ch_class_real.png 10KB ch_minimum_classclass.png 7KB ch_class_metaclass.png 15KB ch_class_boot1.png 32KB ch_minimum_const.png 9KB ch_gc_gcimage.png 21KB ch_gc_objid.png 16KB ch_minimum_modclass2.png 15KB ch_name_nexti.png 15KB ch_gc_stop2.png 10KB ch_minimum_reference.png 10KB ch_abstract_build.png 11KB ch_class_metaobj.png 29KB ch_gc_objects.png 13KB ch_name_sttable.png 24KB ch_name_array.png 7KB ch_minimum_classtree.png 63KB ch_minimum_metaobjects.png 14KB ch_gc_gengc.png 19KB ch_class_multi.png 17KB ch_class_include.png 13KB ch_class_addsclass.png 30KB ch_gc_refcnt.png 17KB ch_abstract_repo.png 26KB ch_minimum_modinherit.png 8KB ch_class_symbolic.png 43KB ch_object_class.png 23KB ch_variable_gvar.png 24KB introduction.html 57KB index.html 5KB preface.html 9KB资源评论
