当前位置:Gxlcms > Python > 主流的垃圾回收机制都有哪些?

主流的垃圾回收机制都有哪些?

时间:2021-07-01 10:21:17 帮助过:113人阅读

无意中看到JavaScript V8和Python中也是使用引用计数和标记清除作为垃圾回收的基础方法,想问问 是否还有其他的垃圾回收算法?

回复内容:

前面有不少回答了,其中有部分靠谱的内容,感觉要补充也挺麻烦的,俺就放个俺推荐的书单吧:
[Garbage Collection][垃圾回收][自动无用内存单元回收]相关读物
《The Garbage Collection Handbook》非常开眼界,能完美回答题主的问题。

不想买书的话从这个网站开始学习也行:Introduction to memory management

也欢迎关注这个HLLVM群组的论坛,高级语言虚拟机
我以前发过一些帖,例如说介绍copying GC的基础实现:HotSpot VM Serial GC的一个问题
以及G1 GC的实现:[HotSpot VM] 请教G1算法的原理
以及几种GC的比较:并发垃圾收集器(CMS)为什么没有采用标记

引用计数与tracing GC的讨论俺也就放个传送门好了:垃圾回收机制中,引用计数法是如何维护所有对象引用的? - RednaxelaFX 的回答

=======================================================

另外对问题描述吐个槽:
无意中看到JavaScript V8和Python中也是使用引用计数和标记清除作为垃圾回收的基础方法,想问问 是否还有其他的垃圾回收算法?
(C)Python是用引用计数为主、mark-sweep为备份没错。

但是V8的GC并不是单纯基于mark-sweep的。

最初发布的时候,V8还比较简单,采用分两代的GC,其中new space用copying GC,然后global GC根据碎片化状况选择性使用mark-sweep或mark-compact。
其抽象思路可以看这个入口函数:v8/mark-compact.cc at 0.1 · v8/v8 · GitHub
void MarkCompactCollector::CollectGarbage() {
  Prepare();

  MarkLiveObjects();

  SweepLargeObjectSpace();

  if (compacting_collection_) {
    EncodeForwardingAddresses();

    UpdatePointers();

    RelocateObjects();

    RebuildRSets();

  } else {
    SweepSpaces();
  }

  Finish();
}
感觉 Wikipedia 上的 Reference counting 和 Tracing garbage collection 条目讲的还是挺好的。总的来说,GC 可以有很多种分类方式:

有一部分 GC 一定要遍历需要 GC 的对象的图,从而获得一个精确的哪个对象活着哪个对象死了的信息。我们称这种 GC 为 tracing GC,不需要遍历的称为 non-tracing GC (比如 reference counting,它只能获得一个近似的信息,所以无法处理图里的环)。

有的 GC 需要程序员/编译器提供合作,以精确的知道哪个 pointer 是对象(指需要 GC 的对象)。有的 GC 不需要,光靠猜(猜也是很难的!猜不出来就只能当做是 pointer 了),也能做到 GC。前者称之为 precise GC,后者称之为 conservative GC(比如 Boehm GC)。我们下面主要讨论 precise GC。

有的 GC 分配了内存之后,这块内存可能会被移动到另外一个地方去,防止内存碎片化,提高缓存局部性(cache locality,这个怎么翻译呢..),这种 GC 被称为 moving GC,而不这么做的 GC 就称为 non-moving GC。moving GC 自然都是 tracing GC,因为它们必须要知道怎么遍历需要 GC 的对象的图,不然没法移动(毕竟移动某个对象的时候,也要修改存有这个对象的地方的值,指向新的位置)。

有的 GC 一次处理整个对象图,有的 GC 则做了优化,一部分时间只处理较新的对象。这个优化是建立在一个现象上的:新的对象比较容易指向老的对象,而老的对象较少指向新的对象;新的对象比较容易死掉,而活了比较久的对象则很有可能会活更久。很多编程的方式都会造成这种现象,比如 immutable data structures 等等。那么针对性的,GC 就可以区分对象的年纪,把内存分配的区域分为(较大的)老区和(较小的,为了缓存局部性)新区,然后根据老区满了与否,每次 GC 判断到底是只需要 GC 新区还是全都需要 GC。如果只需要 GC 新区,那么遍历对象图的时候只要遇到了老区的对象,就直接当做这个对象是活着的,后面的图就不用看了,直接剪掉。遇到了新区的对象,就根据对象存活了几次 GC 来看要不要将其移动到老区里。当然这个现象并不是绝对的,还是会出现老对象指向新对象的情况,怎么办呢?这就要在每次修改对象的时候(这种做法被称为 GC write barrier,就是每次修改对象之前都要有个检查),检查被修改的对象是不是老对象,修改成的值是不是新对象,如果确实是这样,那么就用一种方法(比如 remembered set,card marking 等等)来记住这个例外的情况。这么做的 GC 称之为 generational GC。

最常见的 non-tracing GC 方式就是 reference counting 了,在 Python,Objective-C,C++,Rust 里都能见到。一个较为易读的实现是(玛德 libstdc++ 的 shared_ptr 真难看,真喜欢看 C++ 的话 protobuf 里的 protobuf/shared_ptr.h at master · google/protobuf · GitHub 可读性还不错) rust/rc.rs at master · rust-lang/rust · GitHub

Naive mark-and-sweep 是较为简单的一种 tracing GC,需要遍历两次对象图,第一次 mark,第二次 sweep。我有一个玩具 Scheme interpreter 里用到了它:overminder/sanya-c · GitHub ,详见 sgc.c (代码里还是有不少噪声的.. 因为 stack 并不完全是一个 root set,需要避开一些位置)

Cheney's semi-space copying GC 是较为简单的一种 moving GC,就是分配 2 块一样大的内存,第一块用完了就开始 GC,将活着的对象移动到第二块上去,死了的就不管了,周而复始。我有一个玩具 Scheme JIT 里用到了它:overminder/sanya-native · GitHub ,详见 gc.cpp。

我还有一个玩具 Scheme compiler 里实现了简单的 generational GC:YAC/scm_generational_gc.c at master · overminder/YAC · GitHub 。只有 2 代,用的是 remembered set。这个确实是比实现过的其他 GC 都复杂,当时也是各种 segfault,用 Valgrind debug 了好久...

——————————
晚上修改了一下,应该叫 precise GC 而不是 exact GC。添加了一个能看的 shared_ptr 的实现。 垃圾回收算法可以分为两类:一种是基于reference counting的引用计数法 一种是基于tracing的,这类展开的有拷贝收集,标记清扫,标记压缩,世代收集以及后来G1里的将整个堆做划分,对每个block做一个remember set进行管理。这些方法具体的展开和优缺点以及相对应的内存分配方法都可以在The Garbage Collection Handbook第二版(2011)里找到。G1得去搜sun公司的论文了。 之前回答过一个类似的问题,可以参考:各种编程语言的实现都采用了哪些垃圾回收算法?这些算法都有哪些优点和缺点? - 谢之易的回答 引用计数是判断哪些对象需要被回收,而标记复制标记清理还有标记整理是垃圾回收方式。 Mark-and-Sweep Garbage Collection
CSAPP上提到过一点,不过我个人不记得了。。。 引用计数GC处理什么是引用计数

引用计数是一种垃圾回收的形式,每一个对象都会有一个计数来记录有多少指向它的引用。其引用计数会变换如下面的场景

  • 当对象增加一个引用,比如赋值给变量,属性或者传入一个方法,引用计数执行加1运算。
  • 当对象减少一个引用,比如变量离开作用域,属性被赋值为另一个对象引用,属性所在的对象被回收或者之前传入参数的方法返回,引用计数执行减1操作。
  • 当引用计数变为0,代表该对象不被引用,可以标记成垃圾进行回收。

引用遍历GC处理什么是引用对象遍历

垃圾回收器从被称为GC Roots的点开始遍历遍历对象,凡是可以达到的点都会标记为存活,堆中不可到达的对象都会标记成垃圾,然后被清理掉。 GC Roots有哪些

  • 类,由系统类加载器加载的类。这些类从不会被卸载,它们可以通过静态属性的方式持有对象的引用。注意,一般情况下由自定义的类加载器加载的类不能成为GC Roots
  • 线程,存活的线程
  • Java方法栈中的局部变量或者参数
  • JNI方法栈中的局部变量或者参数
  • JNI全局引用
  • 用做同步监控的对象
  • 被JVM持有的对象,这些对象由于特殊的目的不被GC回收。这些对象可能是系统的类加载器,一些重要的异常处理类,一些为处理异常预留的对象,以及一些正在执行类加载的自定义的类加载器。但是具体有哪些前面提到的对象依赖于具体的JVM实现。

了解详细可以访问 垃圾回收器如何处理循环引用 GC(Garage Collection)主要有四种吧

1. Reference Counting: 每个对象有个计数器, 记录引用次数, 计数器0的时候被GC.
2. Mark and Sweep: 遍历(能遍历到就说明还有reference存在)每个还能找到对象并标记, 然后GC所有不带标记的对象.
3. Copy Collection: 2的改版, 2在sweep的时候需要扫描heap中所有对象, 对CPU符合大.而CC的方式则是用复制代替标记, 直接把遍历到的对象复制到另一个heap区, 然后之前清空旧heap完成GC.
4. Generational Collection: 也是2的改版,因为3中的复制也很慢. 简单说就是把heap分成四个区域, Eden, Survivor1, Survivor2, Tenured. Eden满了就触发GC操作, 这个GC发生在 Eden, Survivor1,2区. 在GC中存活的Eden区对象移到Survivor1和2区, 而Survivor区的对象在多次GC后还存活, 则移到Tenured区. Tenured 也会有GC发生, 但是频率很低. 一句话说就是: 我查你好几遍没问题的话, 就降低查你的频率.

还有很多奇奇怪怪的GC一般都是在这几种上的改良.
比如现在的JVM一般是
Generational Collection + Parallel Collector + Concurrent Mark and Sweep Collector

我不太喜欢把回答说的太长太详细. 所以他们存在的缺点优点我就不细述了. 引用计数(reference counting)不是回收机制,它和根可达性分析(Root Reachability Analysis)是用来判断对象是否存活的算法。

往后才是垃圾回收算法:
  1. 标记清除(Mark-Sweep)
  2. 标记压缩(Mark-Compact)
  3. 分代收集(Generational Collection)
  4. 复制(Copying)
看三本书里的相关章节
1CLR via C#,只介绍了巨硬认为最好的
2深入理解Java虚拟机,JVM高级特性与最佳实践,讲了算法更多变种,演进优化的过程更详细。
3cocos2d-x 权威指南,可以当作是介绍oc,也就是ios开发的垃圾回收,介绍了基于计数的,更方便的用法。

一共也没多少页。

人气教程排行