面试题：Python标记清除算法与分代回收

标记清除算法解决循环引用问题

循环引用场景：在Python中，当两个或多个对象相互引用，形成一个封闭的循环时，就会出现循环引用。例如，定义两个类 A 和 B，它们互相持有对方的引用：

class A:
    def __init__(self):
        self.b = None


class B:
    def __init__(self):
        self.a = None


a = A()
b = B()
a.b = b
b.a = a

在这种情况下，如果没有标记清除算法，仅依靠引用计数，a 和 b 的引用计数不会降为0，即使外部没有对它们的引用，它们也无法被回收。 2. 标记清除算法原理： - 标记阶段：Python的垃圾回收器会从根对象集合（例如全局变量、栈上的变量等）出发，通过遍历对象之间的引用关系，标记所有可以从根对象访问到的对象。在上述例子中，由于 a 和 b 没有外部引用（不在根对象集合可达范围内），它们不会被标记。 - 清除阶段：标记完成后，垃圾回收器会扫描堆内存，回收所有未被标记的对象。因此，a 和 b 所占用的内存空间会被回收，从而解决了循环引用导致的内存泄漏问题。 - 底层实现：Python底层使用双向链表来管理堆中的对象。在标记阶段，垃圾回收器会沿着链表遍历对象，标记可达对象。在清除阶段，将未标记对象从链表中移除，并释放其内存。

分代回收算法提高垃圾回收效率

分代回收算法思想：分代回收基于一个假设，即新创建的对象通常比长期存在的对象更有可能很快变成垃圾。因此，Python将对象分为不同的代（通常是三代，0代、1代和2代）。
对象晋升机制：
- 0代：新创建的对象首先被放入0代。当0代中的对象数量达到一定阈值（可以通过 gc.get_threshold()[0] 获取）时，会触发对0代的垃圾回收。
- 晋升：在0代垃圾回收过程中，如果一个对象经过一次垃圾回收后仍然存活，它将被晋升到1代。同样，当1代中的对象数量达到一定阈值（gc.get_threshold()[1]）时，会触发对1代的垃圾回收，存活的对象晋升到2代。2代也有类似的阈值（gc.get_threshold()[2]）。
提高效率的原因：
- 减少扫描范围：由于新对象更可能成为垃圾，频繁地对0代进行垃圾回收，可以快速回收大量不再使用的对象。而对于1代和2代，由于对象存活时间较长，垃圾回收频率较低，减少了对长期存活对象的不必要扫描，从而提高了整体的垃圾回收效率。
- 底层实现：Python底层通过维护不同代的双向链表来管理对象。每次垃圾回收时，根据代的阈值决定是否对某一代进行回收。在回收过程中，同样采用标记清除算法来处理对象的回收和晋升。

面试题：Python标记清除算法与分代回收

知识考点

面试题答案

标记清除算法解决循环引用问题

分代回收算法提高垃圾回收效率