python垃圾回收机制

962148150

　　转载自： http://my.oschina.net/hebianxizao/blog/57367
　　现在的高级语言如java，c#等，都采用了垃圾收集机制，而不再是c，c++里用户自己管理维护内存的方式。自己管理内存极其自由，可以任意申请内存，但如同一把双刃剑，为大量内存泄露，悬空指针等bug埋下隐患。     

    对于一个字符串、列表、类甚至数值都是对象，且定位简单易用的语言，自然不会让用户去处理如何分配回收内存的问题。
    python里也同java一样采用了垃圾收集机制，不过不一样的是，python采用的是引用计数机制为主，标记-清除和分代收集两种机制为辅的策略。
    引用计数机制：
    python里每一个东西都是对象，它们的核心就是一个结构体：PyObject

1	typedef struct_object {

2	int ob_refcnt;

3	struct_typeobject *ob_type;

4	}PyObject;

    PyObject是每个对象必有的内容，其中ob_refcnt就是做为引用计数。当一个对象有新的引用时，它的ob_refcnt就会增加，当引用它的对象被删除，它的ob_refcnt就会减少

1	#define Py_INCREF(op)   ((op)->ob_refcnt++)          //增加计数

2	#define Py_DECREF(op)      \                         //减少计数

3	if (--(op)->ob_refcnt != 0)    \

4	;        \

5	else         \

6	__Py_Dealloc((PyObject *)(op))

引用计数为0时，该对象生命就结束了。
    引用计数机制的优点：
         1、简单
        2、实时性：一旦没有引用，内存就直接释放了。不用像其他机制等到特定时机。实时性还带来一个好处：处理回收内存的时间分摊到了平时。        
    引用计数机制的缺点：
        1、维护引用计数消耗资源
        2、循环引用

1	list1 = []

2	list2 = []

3	list1.append(list2)

4	list2.append(list1)

    list1与list2相互引用，如果不存在其他对象对它们的引用，list1与list2的引用计数也仍然为1，所占用的内存永远无法被回收，这将是致命的。
    对于如今的强大硬件，缺点1尚可接受，但是循环引用导致内存泄露，注定python还将引入新的回收机制。


　　上面说到python里回收机制是以引用计数为主，标记-清除和分代收集两种机制为辅。
　　1、标记-清除机制

　　标记-清除机制，顾名思义，首先标记对象（垃圾检测），然后清除垃圾（垃圾回收）。如图1：

　　图1
　　首先初始所有对象标记为白色，并确定根节点对象（这些对象是不会被删除），标记它们为黑色（表示对象有效）。将有效对象引用的对象标记为灰色（表示对象可达，
　　但它们所引用的对象还没检查），检查完灰色对象引用的对象后，将灰色标记为黑色。重复直到不存在灰色节点为止。最后白色结点都是需要清除的对象。
　　2、回收对象的组织

　　这里所采用的高级机制作为引用计数的辅助机制，用于解决产生的循环引用问题。而循环引用只会出现在“内部存在可以对其他对象引用的对象”，比如：list，class等。

　　为了要将这些回收对象组织起来，需要建立一个链表。自然，每个被收集的对象内就需要多提供一些信息，下面代码是回收对象里必然出现的。
　　一个对象的实际结构如图2：
　　
　　图2
　　通过PyGC_Head的指针将每个回收对象连接起来，形成了一个链表，也就是在1里提到的初始化的所有对象。
　　3、分代技术

　　分代技术是一种典型的以空间换时间的技术，这也正是java里的关键技术。这种思想简单点说就是：对象存在时间越长，越可能不是垃圾，应该越少去收集。

　　这样的思想，可以减少标记-清除机制所带来的额外操作。分代就是将回收对象分成数个代，每个代就是一个链表（集合），代进行标记-清除的时间与代内对象
　　存活时间成正比例关系。
　　从上面代码可以看出python里一共有三代，每个代的threshold值表示该代最多容纳对象的个数。默认情况下，当0代超过700,或1，2代超过10，垃圾回收机制将触发。
　　0代触发将清理所有三代，1代触发会清理1,2代，2代触发后只会清理自己。
　　
　　下面是一个完整的收集流程：链表建立，确定根节点，垃圾标记，垃圾回收~
1、链表建立
　　首先，中里在分代技术说过：0代触发将清理所有三代，1代触发会清理1,2代，2代触发后只会清理自己。在清理0代时，会将三个链表（代）链接起来，清理1代的时，会链接1,2两代。在后面三步，都是针对的这个建立之后的链表。
2、确定根节点
　　图1为一个例子。list1与list2循环引用，list3与list4循环引用。a是一个外部引用。

　　图1
　　对于这样一个链表，我们如何得出根节点呢。python里是在引用计数的基础上又提出一个有效引用计数的概念。顾名思义，有效引用计数就是去除循环引用后的计数。
　　下面是计算有效引用计数的相关代码：

01	/* Set all gc_refs = ob_refcnt.  After this, gc_refs is > 0 for all objects

02	* in containers, and is GC_REACHABLE for all tracked gc objects not in

03	* containers.

04

*/

05	static void

06	update_refs(PyGC_Head *containers)

07

{

08	PyGC_Head *gc = containers->gc.gc_next;

09	for (; gc != containers; gc = gc->gc.gc_next) {

10	assert(gc->gc.gc_refs == GC_REACHABLE);

11	gc->gc.gc_refs = Py_REFCNT(FROM_GC(gc));

12	assert(gc->gc.gc_refs != 0);

13

}

14

}

15

16	/* A traversal callback for subtract_refs. */

17	static int

18	visit_decref(PyObject *op, void *data)

19

{

20	assert(op != NULL);

21	if (PyObject_IS_GC(op)) {

22	PyGC_Head *gc = AS_GC(op);

23	/* We're only interested in gc_refs for objects in the

24	* generation being collected, which can be recognized

25	* because only they have positive gc_refs.

26

*/

27	assert(gc->gc.gc_refs != 0); /* else refcount was too small */

28	if (gc->gc.gc_refs > 0)

29	gc->gc.gc_refs--;

30

}

31

return 0;

32

}

33

34	/* Subtract internal references from gc_refs.  After this, gc_refs is >= 0

35	* for all objects in containers, and is GC_REACHABLE for all tracked gc

36	* objects not in containers.  The ones with gc_refs > 0 are directly

37	* reachable from outside containers, and so can't be collected.

38

*/

39	static void

40	subtract_refs(PyGC_Head *containers)

41

{

42	traverseproc traverse;

43	PyGC_Head *gc = containers->gc.gc_next;

44	for (; gc != containers; gc=gc->gc.gc_next) {

45	traverse = Py_TYPE(FROM_GC(gc))->tp_traverse;

46	(void) traverse(FROM_GC(gc),

47	(visitproc)visit_decref,

48

NULL);

49

}

50

}

　　update_refs函数里建立了一个引用的副本。
　　visit_decref函数对引用的副本减1，subtract_refs函数里traverse的作用是遍历对象里的每一个引用，执行visit_decref操作。
　　最后，链表内引用计数副本非0的对象，就是根节点了。
　　说明：
　　1、为什么要建立引用副本？
　　答：这个过程是寻找根节点的过程，在这个时候修改计数不合适。subtract_refs会对对象的引用对象执行visit_decref操作。如果链表内对象引用了链表外对象，那么链表外对象计数会减1，显然，很有可能这个对象会被回收，而回收机制里根本不应该对非回收对象处理。
　　2、traverse的疑问（未解决）？
　　答：一开始，有个疑问。上面例子里，subtract_refs函数中处理完list1结果应该如下：

　　然后gc指向list2，此时list2的副本（为0）不会减少，但是list2对list1还是存在实际上的引用，那么list1副本会减1吗？显然，如果减1就出问题了。
　　所以list1为0时，traverse根本不会再去处理list1这些引用（或者说，list2对list1名义上不存在引用了）。
　　此时，又有一个问题，如果存在一个外部对象b，对list2引用，subtract_refs函数中处理完list1后，如下图：

　　当subtract_refs函数中遍历到list2时，list2的副本还会减1吗？显然traverse的作用还是没有理解。
3、垃圾标记
　　接下来，python建立两条链表，一条存放根节点，以及根节点的引用对象。另外一条存放unreachable对象。
　　标记的方法就是中里的标记思路，代码如下：

001	/* A traversal callback for move_unreachable. */

002	static int

003	visit_reachable(PyObject *op, PyGC_Head *reachable)

004

{

005	if (PyObject_IS_GC(op)) {

006	PyGC_Head *gc = AS_GC(op);

007	const Py_ssize_t gc_refs = gc->gc.gc_refs;

008

009	if (gc_refs == 0) {

010	/* This is in move_unreachable's 'young' list, but

011	* the traversal hasn't yet gotten to it.  All

012	* we need to do is tell move_unreachable that it's

013	* reachable.

014

*/

015	gc->gc.gc_refs = 1;

016

}

017	else if (gc_refs == GC_TENTATIVELY_UNREACHABLE) {

018	/* This had gc_refs = 0 when move_unreachable got

019	* to it, but turns out it's reachable after all.

020	* Move it back to move_unreachable's 'young' list,

021	* and move_unreachable will eventually get to it

022

* again.

023

*/

024	gc_list_move(gc, reachable);

025	gc->gc.gc_refs = 1;

026

}

027	/* Else there's nothing to do.

028	* If gc_refs > 0, it must be in move_unreachable's 'young'

029	* list, and move_unreachable will eventually get to it.

030	* If gc_refs == GC_REACHABLE, it's either in some other

031	* generation so we don't care about it, or move_unreachable

032	* already dealt with it.

033	* If gc_refs == GC_UNTRACKED, it must be ignored.

034

*/

035

else {

036	assert(gc_refs > 0

037	|| gc_refs == GC_REACHABLE

038	|| gc_refs == GC_UNTRACKED);

039

}

040

}

041

return 0;

042

}

043

044	/* Move the unreachable objects from young to unreachable.  After this,

045	* all objects in young have gc_refs = GC_REACHABLE, and all objects in

046	* unreachable have gc_refs = GC_TENTATIVELY_UNREACHABLE.  All tracked

047	* gc objects not in young or unreachable still have gc_refs = GC_REACHABLE.

048	* All objects in young after this are directly or indirectly reachable

049	* from outside the original young; and all objects in unreachable are

050

* not.

051

*/

052	static void

053	move_unreachable(PyGC_Head *young, PyGC_Head *unreachable)

054

{

055	PyGC_Head *gc = young->gc.gc_next;

056

057	/* Invariants:  all objects "to the left" of us in young have gc_refs

058	* = GC_REACHABLE, and are indeed reachable (directly or indirectly)

059	* from outside the young list as it was at entry.  All other objects

060	* from the original young "to the left" of us are in unreachable now,

061	* and have gc_refs = GC_TENTATIVELY_UNREACHABLE.  All objects to the

062	* left of us in 'young' now have been scanned, and no objects here

063	* or to the right have been scanned yet.

064

*/

065

066	while (gc != young) {

067	PyGC_Head *next;

068

069	if (gc->gc.gc_refs) {

070	/* gc is definitely reachable from outside the

071	* original 'young'.  Mark it as such, and traverse

072	* its pointers to find any other objects that may

073	* be directly reachable from it.  Note that the

074	* call to tp_traverse may append objects to young,

075	* so we have to wait until it returns to determine

076	* the next object to visit.

077

*/

078	PyObject *op = FROM_GC(gc);

079	traverseproc traverse = Py_TYPE(op)->tp_traverse;

080	assert(gc->gc.gc_refs > 0);

081	gc->gc.gc_refs = GC_REACHABLE;

082	(void) traverse(op,

083	(visitproc)visit_reachable,

084	(void *)young);

085	next = gc->gc.gc_next;

086

}

087

else {

088	/* This *may* be unreachable.  To make progress,

089	* assume it is.  gc isn't directly reachable from

090	* any object we've already traversed, but may be

091	* reachable from an object we haven't gotten to yet.

092	* visit_reachable will eventually move gc back into

093	* young if that's so, and we'll see it again.

094

*/

095	next = gc->gc.gc_next;

096	gc_list_move(gc, unreachable);

097	gc->gc.gc_refs = GC_TENTATIVELY_UNREACHABLE;

098

}

099	gc = next;

100

}

101

}

　　标记之后，链表如上图。
4、垃圾回收
　　回收的过程，就是销毁不可达链表内对象。下面代码就是list的清除方法：

01	/* Methods */

02

03	static void

04	list_dealloc(PyListObject *op)

05

{

06	Py_ssize_t i;

07	PyObject_GC_UnTrack(op);

08	Py_TRASHCAN_SAFE_BEGIN(op)

09	if (op->ob_item != NULL) {

10	/* Do it backwards, for Christian Tismer.

11	There's a simple test case where somehow this reduces

12	thrashing when a *very* large list is created and

13	immediately deleted. */

14	i = Py_SIZE(op);

15	while (--i >= 0) {

16	Py_XDECREF(op->ob_item);

17

}

18	PyMem_FREE(op->ob_item);

19

}

20	if (numfree < PyList_MAXFREELIST && PyList_CheckExact(op))

21	free_list[numfree++] = op;

22

else

23	Py_TYPE(op)->tp_free((PyObject *)op);

24	Py_TRASHCAN_SAFE_END(op)

25

}