Ruby的GC机制源码分析（1）

本文来自作者的日文书

GC 可以做的事

<!-- [if !mso]> <mce:style><!-- v\:* {behavior:url(#default#VML);} o\:* {behavior:url(#default#VML);} w\:* {behavior:url(#default#VML);} .shape {behavior:url(#default#VML);} --> <!-- [endif]--><!-- [if gte mso 9]><xml> <w:WordDocument> <w:View>Normal</w:View> <w:Zoom>0</w:Zoom> <w:PunctuationKerning/> <w:DrawingGridVerticalSpacing>7.8 磅</w:DrawingGridVerticalSpacing> <w:DisplayHorizontalDrawingGridEvery>0</w:DisplayHorizontalDrawingGridEvery> <w:DisplayVerticalDrawingGridEvery>2</w:DisplayVerticalDrawingGridEvery> <w:ValidateAgainstSchemas/> <w:SaveIfXMLInvalid>false</w:SaveIfXMLInvalid> <w:IgnoreMixedContent>false</w:IgnoreMixedContent> <w:AlwaysShowPlaceholderText>false</w:AlwaysShowPlaceholderText> <w:Compatibility> <w:SpaceForUL/> <w:BalanceSingleByteDoubleByteWidth/> <w:DoNotLeaveBackslashAlone/> <w:ULTrailSpace/> <w:DoNotExpandShiftReturn/> <w:AdjustLineHeightInTable/> <w:BreakWrappedTables/> <w:SnapToGridInCell/> <w:WrapTextWithPunct/> <w:UseAsianBreakRules/> <w:DontGrowAutofit/> <w:UseFELayout/> </w:Compatibility> <w:BrowserLevel>MicrosoftInternetExplorer4</w:BrowserLevel> </w:WordDocument> </xml><![endif]--><!-- [if gte mso 9]><xml> <w:LatentStyles DefLockedState="false" LatentStyleCount="156"> </w:LatentStyles> </xml><![endif]--><!-- [if gte mso 10]> <mce:style><!-- /* Style Definitions */ table.MsoNormalTable {mso-style-name:普通表格; mso-tstyle-rowband-size:0; mso-tstyle-colband-size:0; mso-style-noshow:yes; mso-style-parent:""; mso-padding-alt:0cm 5.4pt 0cm 5.4pt; mso-para-margin:0cm; mso-para-margin-bottom:.0001pt; mso-pagination:widow-orphan; font-size:10.0pt; font-family:"Times New Roman"; mso-ansi-language:#0400; mso-fareast-language:#0400; mso-bidi-language:#0400;} --> <!-- [endif]-->

<!-- [if !mso]> <mce:style><!-- v\:* {behavior:url(#default#VML);} o\:* {behavior:url(#default#VML);} w\:* {behavior:url(#default#VML);} .shape {behavior:url(#default#VML);} --> <!-- [endif]--><!-- [if gte mso 9]><xml> <w:WordDocument> <w:View>Normal</w:View> <w:Zoom>0</w:Zoom> <w:PunctuationKerning/> <w:DrawingGridVerticalSpacing>7.8 磅</w:DrawingGridVerticalSpacing> <w:DisplayHorizontalDrawingGridEvery>0</w:DisplayHorizontalDrawingGridEvery> <w:DisplayVerticalDrawingGridEvery>2</w:DisplayVerticalDrawingGridEvery> <w:ValidateAgainstSchemas/> <w:SaveIfXMLInvalid>false</w:SaveIfXMLInvalid> <w:IgnoreMixedContent>false</w:IgnoreMixedContent> <w:AlwaysShowPlaceholderText>false</w:AlwaysShowPlaceholderText> <w:Compatibility> <w:SpaceForUL/> <w:BalanceSingleByteDoubleByteWidth/> <w:DoNotLeaveBackslashAlone/> <w:ULTrailSpace/> <w:DoNotExpandShiftReturn/> <w:AdjustLineHeightInTable/> <w:BreakWrappedTables/> <w:SnapToGridInCell/> <w:WrapTextWithPunct/> <w:UseAsianBreakRules/> <w:DontGrowAutofit/> <w:UseFELayout/> </w:Compatibility> <w:BrowserLevel>MicrosoftInternetExplorer4</w:BrowserLevel> </w:WordDocument> </xml><![endif]--><!-- [if gte mso 9]><xml> <w:LatentStyles DefLockedState="false" LatentStyleCount="156"> </w:LatentStyles> </xml><![endif]--><!-- [if gte mso 10]> <mce:style><!-- /* Style Definitions */ table.MsoNormalTable {mso-style-name:普通表格; mso-tstyle-rowband-size:0; mso-tstyle-colband-size:0; mso-style-noshow:yes; mso-style-parent:""; mso-padding-alt:0cm 5.4pt 0cm 5.4pt; mso-para-margin:0cm; mso-para-margin-bottom:.0001pt; mso-pagination:widow-orphan; font-size:10.0pt; font-family:"Times New Roman"; mso-ansi-language:#0400; mso-fareast-language:#0400; mso-bidi-language:#0400;} --> <!-- [endif]-->

讨论GC 算法之前，需要解释一下“GC 是什么” 。也就是说，“ 无用的内存” 处于一种怎样的状态。

为了让讨论更加具体，将对象间的链接结构简化。也就是图3 所示的状态。

图3: 对象

首先，全局变量所指的而且在语言堆栈上的对象“ 确实必要” 。对象实例变量所指的对象也是必要的。从这些对象出发，顺着链接前进可以到达的对象，都是必要的。

稍微理论点说，以“ 确实必要” 的对象为起点，递归的沿链接前进可以到达的所有对象都是必要的。图4 表现了这种情况。线左侧是“ 确实必要” 的对象，从那开始能够到达的都涂成了黑色。涂黑的对象都是必要的。其余的可以释放。

图4: 必要的对象和不必要的对象

术语将“ 确实必要的对象” 称为“GC 的根” 。追踪必要对象的结果可以视为一个树型结构，而它就是树的根（root ）。

标记与清除（mark & sweep ）

GC 最初由Lisp 实现，Lisp 最初的GC 实现就是世界上最早的GC ，称为标记与清除（mark & sweep ）型GC 。 ruby 的GC 也是这一种。

标记与清除型GC 的印象接近于“ 必要对象” 的定义。首先给根对象加上“ 记号” 。以此为出发点，给找到的对象都加上“ 标记” 。这个全过程就是“ 标记” 阶段。

所以，除此之外，其它的对象都是无法找到的，检查全部的对象集合，释放掉那些没有“ 标记” 的对象（清除）。这就是扫雷（minesweeper ）中的sweep （清除）。

这种方法有两个优点。

· GC 实现之外的地方不必（太多）考虑GC 。

· 有环也可以释放（关于环，可以参考引用计数一节）。

缺点也是两个。

· 为实现清除，至少要将所有的对象遍历一次。

· GC 的负荷会集中于一点

使用Emacs 编辑器的时候，时常会出现“Garbage collecting...” ，完全失去响应，这时就是在进行GC 。这就是第二个缺点一个直接的例子。不过，这点可以通过改变算法（增量GC ）进行改进。