Python解决循环引用的方案

Python解决循环引用的方案 #

使用了引用计数的地方，就会存在循环引用。例如下图中的四个对象，A 是根对象，它与 B 之间有循环引用，那么它们都不是垃圾对象。C 和 D 之间也有循环引用，但因为没有外界的引用指向它们了，所以它们就是垃圾对象，但是循环引用导致他们都不能释放。 Python 为了解决这个问题，在虚拟机中引入了一个双向链表，把所有对象都放到这个链表里。Python 的每个对象头上都有一个名为 PyGC_Head 的结构：

/* GC information is stored BEFORE the object structure. */
typedef union _gc_head {
    struct {
        union _gc_head *gc_next;
        union _gc_head *gc_prev;
        Py_ssize_t gc_refs;
    } gc;
    long double dummy;  /* force worst-case alignment */
} PyGC_Head;

在这个结构里，gc_next 和 gc_prev 的作用就是把对象关联到链表里。而 gc_refs 则是用于消除循环引用的。当链表中的对象达到一定数目时，Python 的 GC 模块就会执行一次标记清除。

具体来讲，一共有四步。

1. 将 ob_refcnt 的值复制到 gc_refs 中。对于上面的例子，它们的 gc_refs 的值就如下图所示：

1. 遍历整个链表，对每个对象，将它直接引用的对象的 gc_refs 的值减一。比如遍历到 A 对象时，只把 B 对象的 gc_refs 值减一；遍历到 B 对象时，再把它直接引用的 A 对象的 gc_refs 值减一。经过这一步骤后，四个对象的 gc_refs 的值如下图所示：

1. 将 gc_refs 值为 0 的对象，从对象链表中摘下来，放入一个名为“临时不可达”的链表中。之所以使用“临时”，是因为有循环引用的垃圾对象的 gc_refs 在此时一定为 0，比如 C 和 D。但 gc_refs 值为 0 的对象不一定是垃圾对象，比如 B 对象。此时，B、C 和 D 对象就被放入临时不可达链表中了，示意图如下所示：

1. 以可达对象链表中的对象为根开始深度优先搜索，将所有访问到 gc_refs 为 0 的对象，再从临时不可达链表中移回可达链表中。最后留在临时不可达链表中的对象，就是真正的垃圾对象了。

接下来就可以使用 _Py_Dealloc 逐个释放链表中的对象了，对于上面的例子，就是把 B 对象重新加回到可达对象链表中，然后将 C 和 D 分别释放。

Viewpoint #

From #

24 | GC实例：Python和Go的内存管理机制是怎样的？

Links #