自从java把垃圾回收的概念发扬光大,现在介绍垃圾回收算法的文章已经很多了,这篇文章的目的是想结合python源码分析python实现的GC算法.

简单得说,垃圾回收就是两个步骤:找出垃圾,回收垃圾.回收比较简单,直接free掉就可以.关键在于怎么找到垃圾.

找垃圾的算法有两种,一个是引用计数法,这是python使用的,引用计数法比较好理解,接触过com的人肯定记得他,用一个整数保存当前对内存块引用的数目,找垃圾就只需要找那些引用计数为0的就可以,唯一的缺陷就是著名的引用循环问题,不过大家放心,python2.0以后解决了这个问题;另一种就是tracing算法了,.net和java使用的都是这个,该算法要求维护固定数目的几个"根","根"保存着对其他内存块的引用,当然普通内存块也可以保存其他内存块的引用,比如容器.这样内存块和之间的引用就构成了一棵树,所有分配的内存块都在这棵树中,删除一个内存块删除对他的引都是有用的,用就可以.找垃圾的时候不是很方便,每次从"根"开始遍历这棵树,能遍历到的剩下的都是垃圾,这个时候如何清除垃圾又有两种选择,详细情况见... 另外generation算法和adaptive算法都是通用的,详细情况也不一一赘述了.

上面说了.net和java都选择tracing算法,为什么python却选择引用计数法呢.我不知道.

python是如何解决引用循环的呢.python在收集的时候给,每一块内存指定一个gc_refs属性,其值初始化为引用计数的值,然后对每一块内存块,讲所有该内存块直接引用的内存块的gc_refs--,完成后gc_refs的值就是外部引用的个数了,不过这个时候还有个问题

..............................................