2.7.标记-清除
最终那间凌乱的房间充斥着垃圾，再不能岁⽉静好了。在Ruby程序运⾏了⼀阵⼦以后，可⽤列表最终被⽤光光了:
此刻所有Ruby预创建对象都被程序⽤过了(它们都变灰了)，可⽤列表⾥空空如也（没有⽩格⼦了）。
此刻Ruby祭出另⼀McCarthy发明的算法，名⽈：标记-清除。⾸先Ruby把程 序停下来，Ruby⽤"地球停转垃圾回收⼤法"。之后Ruby轮询所有指针，变量 和代码产⽣别的引⽤对象和其他值。同时Ruby通过⾃身的虚拟机便利内部指针。标记出这些指针引⽤的每个对象。我在图中使⽤M表示。
上图中那三个被标M的对象是程序还在使⽤的。在内部，Ruby实际上使⽤⼀串位值，被称为:可⽤位图(译注：还记得《编程珠玑》⾥的为突发排序吗，这 对离散度不⾼的有限整数集合具有很强的压缩效果，⽤以节约机器的资源)，来跟踪对象是否被标记了。
如果说被标记的对象是存活的，剩下的未被标记的对象只能是垃圾，这意味 着我们的代码不再会使⽤它了。我会在下图中⽤⽩格⼦表示垃圾对象：
接下来Ruby清除这些⽆⽤的垃圾对象，把它们送回到可⽤列表中：
在内部这⼀切发⽣得迅雷不及掩⽿，因为Ruby实际上不会吧对象从这拷⻉到 那。⽽是通过调整内部指针，将其指向⼀个新链表的⽅式，来将垃圾对象归位到可⽤列表中的。
现在等到下回再创建对象的时候Ruby⼜可以把这些垃圾对象分给我们使⽤了。在Ruby⾥，对象们六道轮回，转世投胎，享受多次⼈⽣。
2.8.标记-删除 vs. 引⽤计数
乍⼀看，Python的GC算法貌似远胜于Ruby的：宁舍洁宇⽽居秽室乎？为什么Ruby宁愿定期强制程序停⽌运⾏，也不使⽤Python的算法呢？
然⽽，引⽤计数并不像第⼀眼看上去那样简单。有许多原因使得不许多语⾔ 不像Python这样使⽤引⽤计数GC算法：
⾸先，它不好实现。Python不得不在每个对象内部留⼀些空间来处理引⽤数。这样付出了⼀⼩点⼉空间上的代价。但更糟糕的是，每个简单的操作(像修改变量或引⽤)都会变成⼀个更复杂的操作，因为Python需要增加⼀ 个计数，减少另⼀个，还可能释放对象。
第⼆点，它相对较慢。虽然Python随着程序执⾏GC很稳健（⼀把脏碟⼦放在 洗碗盆⾥就开始洗啦），但这并不⼀定更快。Python不停地更新着众多引⽤ 数值。特别是当你不再使⽤⼀个⼤数据结构的时候，⽐如⼀个包含很多元素的列表，Python可能必须⼀次性释放⼤量对象。减少引⽤数就成了⼀项复杂的递归过程了。
最后，它不是总奏效的。引⽤计数不能处理环形数据结构--也就是含有循环引⽤的数据结构。
3.Python中的循环数据结构以及引⽤计数
3.1.循环引⽤
通过上篇，我们知道在Python中，每个对象都保存了⼀个称为引⽤计数的整数值，来追踪到底有多少引⽤指向了这个对象。⽆论何时，如果我们程序中的⼀个变量或其他对象引⽤了⽬标对象，Python将会增加这个计数值，⽽当 程序停⽌使⽤这个对象，则Python会减少这个计数值。⼀旦计数值被减到 零，Python将会释放这个对象以及回收相关内存空间。
从六⼗年代开始，计算机科学界就⾯临了⼀个严重的理论问题，那就是针对 引⽤计数这种算法来说，如果⼀个数据结构引⽤了它⾃身，即如果这个数据 结构是⼀个循环数据结构，那么某些引⽤计数值是肯定⽆法变成零的。为了更好地理解这个问题，让我们举个例⼦。下⾯的代码展示了⼀些上周我们所⽤到的节点类：
我们有⼀个"构造器"(在Python中叫做 __init__ )，在⼀个实例变量中存储⼀个单独的属性。在类定义之后我们创建两个节点，ABC以及DEF，在图中为左边的矩形框。两个节点的引⽤计数都被初始化为1，因为各有两个引⽤指向各个节点(n1和n2)。
现在，让我们在节点中定义两个附加的属性，next以及prev：
跟Ruby不同的是，Python中你可以在代码运⾏的时候动态定义实例变量或对象属性。这看起来似乎有点像Ruby缺失了某些有趣的魔法。(声明下我不是 ⼀个Python程序员，所以可能会存在⼀些命名⽅⾯的错误)。我们设置 n1.next 指向 n2，同时设置 n2.prev 指回 n1。现在，我们的两个节点使⽤循 环引⽤的⽅式构成了⼀个 双向链表 。同时请注意到 ABC 以及 DEF 的引⽤计 数值已经增加到了2。这⾥有两个指针指向了每个节点：⾸先是 n1 以及 n2， 其次就是 next 以及 prev。
现在，假定我们的程序不再使⽤这两个节点了，我们将 n1 和 n2 都设置为 null(Python中是None)。
好了，Python会像往常⼀样将每个节点的引⽤计数减少到1。
3.2.在Python中的零代(Generation Zero)
请注意在以上刚刚说到的例⼦中，我们以⼀个不是很常⻅的情况结尾：我们 有⼀个“孤岛”或是⼀组未使⽤的、互相指向的对象，但是谁都没有外部引 ⽤。换句话说，我们的程序不再使⽤这些节点对象了，所以我们希望Python 的垃圾回收机制能够⾜够智能去释放这些对象并回收它们占⽤的内存空间。 但是这不可能，因为所有的引⽤计数都是1⽽不是0。Python的引⽤计数算法 不能够处理互相指向⾃⼰的对象。
这就是为什么Python要引⼊ Generational GC 算法的原因！正如Ruby使⽤ ⼀个链表(free list)来持续追踪未使⽤的、⾃由的对象⼀样，Python使⽤⼀种 不同的链表来持续追踪活跃的对象。⽽不将其称之为“活跃列表”，Python的 内部C代码将其称为零代(Generation Zero)。每次当你创建⼀个对象或其他什么值的时候，Python会将其加⼊零代链表：
从上边可以看到当我们创建ABC节点的时候，Python将其加⼊零代链表。请 注意到这并不是⼀个真正的列表，并不能直接在你的代码中访问，事实上这个链表是⼀个完全内部的Python运⾏时。 相似的，当我们创建DEF节点的时候，Python将其加⼊同样的链表：
现在零代包含了两个节点对象。(他还将包含Python创建的每个其他值，与⼀些Python⾃⼰使⽤的内部值)
3.3.检测循环引⽤
随后，Python会循环遍历零代列表上的每个对象，检查列表中每个互相引⽤的对象，根据规则减掉其引⽤计数。在这个过程中，Python会⼀个接⼀个的 统计内部引⽤的数量以防过早地释放对象。
为了便于理解，来看⼀个例⼦：
从上⾯可以看到 ABC 和 DEF 节点包含的引⽤数为1.有三个其他的对象同时 存在于零代链表中，蓝⾊的箭头指示了有⼀些对象正在被零代链表之外的其他对象所引⽤。(接下来我们会看到，Python中同时存在另外两个分别被称为 ⼀代和⼆代的链表)。这些对象有着更⾼的引⽤计数因为它们正在被其他指针所指向着。
接下来你会看到Python的GC是如何处理零代链表的。
通过识别内部引⽤，Python能够减少许多零代链表对象的引⽤计数。在上图 的第⼀⾏中你能够看⻅ABC和DEF的引⽤计数已经变为零了，这意味着收集器可以释放它们并回收内存空间了。剩下的活跃的对象则被移动到⼀个新的 链表：⼀代链表。
从某种意义上说，Python的GC算法类似于Ruby所⽤的标记回收算法。周期性地从⼀个对象到另⼀个对象追踪引⽤以确定对象是否还是活跃的，正在被程序所使⽤的，这正类似于Ruby的标记过程。
4.Python中的GC阈值
Python什么时候会进⾏这个标记过程？随着你的程序运⾏，Python解释器保 持对新创建的对象，以及因为引⽤计数为零⽽被释放掉的对象的追踪。从理论上说，这两个值应该保持⼀致，因为程序新建的每个对象都应该最终被释放掉。
当然，事实并⾮如此。因为循环引⽤的原因，并且因为你的程序使⽤了⼀些 ⽐其他对象存在时间更⻓的对象，从⽽被分配对象的计数值与被释放对象的计数值之间的差异在逐渐增⻓。⼀旦这个差异累计超过某个阈值，则Python的收集机制就启动了，并且触发上边所说到的零代算法，释放“浮动的垃圾”，并且将剩下的对象移动到⼀代列表。
随着时间的推移，程序所使⽤的对象逐渐从零代列表移动到⼀代列表。⽽ Python对于⼀代列表中对象的处理遵循同样的⽅法，⼀旦被分配计数值与被 释放计数值累计到达⼀定阈值，Python会将剩下的活跃对象移动到⼆代列表。
通过这种⽅法，你的代码所⻓期使⽤的对象，那些你的代码持续访问的活跃 对象，会从零代链表转移到⼀代再转移到⼆代。通过不同的阈值设置， Python可以在不同的时间间隔处理这些对象。Python处理零代最为频繁，其 次是⼀代然后才是⼆代。
弱代假说
来看看代垃圾回收算法的核⼼⾏为：垃圾回收器会更频繁的处理新对象。⼀个新的对象即是你的程序刚刚创建的，⽽⼀个来的对象则是经过了⼏个时间 周期之后仍然存在的对象。Python会在当⼀个对象从零代移动到⼀代，或是 从⼀代移动到⼆代的过程中提升(promote)这个对象。
为什么要这么做？这种算法的根源来⾃于弱代假说(weak generational hypothesis)。这个假说由两个观点构成：⾸先是年亲的对象通常死得也快， ⽽⽼对象则很有可能存活更⻓的时间。
假定现在我⽤Python或是Ruby创建⼀个新对象：
根据假说，我的代码很可能仅仅会使⽤ABC很短的时间。这个对象也许仅仅 只是⼀个⽅法中的中间结果，并且随着⽅法的返回这个对象就将变成垃圾了。⼤部分的新对象都是如此般地很快变成垃圾。然⽽，偶尔程序会创建⼀ 些很重要的，存活时间⽐较⻓的对象-例如web应⽤中的session变量或是配置项。
通过频繁的处理零代链表中的新对象，Python的垃圾收集器将把时间花在更 有意义的地⽅：它处理那些很快就可能变成垃圾的新对象。同时只在很少的 时候，当满⾜阈值的条件，收集器才回去处理那些⽼变量。
