欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  后端开发

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

程序员文章站 2022-05-12 14:47:21
...
无意中看到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开发的垃圾回收,介绍了基于计数的,更方便的用法。

一共也没多少页。主流的垃圾回收机制都有哪些?

声明:本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系admin@php.cn核实处理。

相关文章

相关视频


相关标签: JavaScript Python