草庐IT

CMS和G1改用三色标记法，可达性分析到底做错了什么？

Hollis 2023-03-28 原文
我们都知道， 当JVM判断对象不再存活的时候，便会在下一次GC时候将该对象回收掉，为堆腾出空间，而JVM判断对象存活的算法大家比较熟知的有两种，分别是引用计数法和可达性分析算法

  • 引用计数法：给对象中添加一个引用计数器，每当有一个地方引用它，计数器就加 1；当引用失效，计数器就减 1；任何时候计数器为 0 的对象就是不可能再被使用的。这个方法实现简单，效率高，但是目前主流的虚拟机中并没有选择这个算法来管理内存，其最主要的原因是它很难解决对象之间相互循环引用的问题。
  • 可达性分析算法：这个算法的基本思想就是通过一系列的称为 “GC Roots” 的对象作为起点，从这些节点开始向下搜索，节点所走过的路径称为引用链，当一个对象到 GC Roots 没有任何引用链相连的话，则证明此对象是不可用的。
但是这两种算法其实并不完美，主要存在以下问题：

1、循环引用问题，如果两个对象互相引用，就形成了一个环形结构，如果采用引用计数法的话，那么这两个对象将用于无法被回收。

2、误标记的问题，在多线程环境下，如果一个线程正在遍历对象图，而另一个线程在同时修改对象图，就会导致遍历结果不准确。

3、STW时间长，可达性分析的整个过程都需要STW，以避免对象的状态发生改变，这就导致GC停顿时长很长，大大影响应用的整体性能。

为了解决上面这些问题，就引入了三色标记算法

什么是三色标记法

三色标记法将对象分为三种状态：白色、灰色和黑色。

白色：该对象没有被标记过。

灰色：该对象已经被标记过了，但该对象的引用对象还没标记完。

黑色：该对象已经被标记过了，并且他的全部引用对象也都标记完了。

三色标记法的标记过程可以分为三个阶段：初始标记（Initial Marking）、并发标记（Concurrent Marking）和重新标记（Remark）。

这三个阶段看上去是不是很熟悉，这不就是CMS的四个阶段中的前三个么？没错，就是他们。

  • 初始标记：遍历所有的根对象，将根对象和直接引用的对象标记为灰色。在这个阶段中，垃圾回收器只会扫描被直接或者间接引用的对象，而不会扫描整个堆。因此，初始标记阶段的时间比较短。（Stop The World）
  • 并发标记：在这个过程中，垃圾回收器会从灰色对象开始遍历整个对象图，将被引用的对象标记为灰色，并将已经遍历过的对象标记为黑色。并发标记过程中，应用程序线程可能会修改对象图，因此垃圾回收器需要使用写屏障（Write Barrier）技术来保证并发标记的正确性。（不需要STW）
  • 重新标记：重新标记的主要作用是标记在并发标记阶段中被修改的对象以及未被遍历到的对象。这个过程中，垃圾回收器会从灰色对象重新开始遍历对象图，将被引用的对象标记为灰色，并将已经遍历过的对象标记为黑色。（Stop The World）
在重新标记阶段结束之后，垃圾回收器会执行清除操作，将未被标记为可达对象的对象进行回收，从而释放内存空间。这个过程中，垃圾回收器会将所有未被标记的对象标记为白色（White）。

以上三个标记阶段中，初始标记和重新标记是需要STW的，而并发标记是不需要STW的。其中最耗时的其实就是并发标记的这个阶段，因为这个阶段需要遍历整个对象树，而三色标记把这个阶段做到了和应用线程并发执行，大大降低了GC的停顿时长。

写屏障

并发标记过程中，应用程序线程可能会修改对象图，因此垃圾回收器需要使用写屏障（Write Barrier）技术来保证并发标记的正确性。

写屏障是一种在对象引用被修改时，将其新的引用信息记录在特殊数据结构中的机制。在三色标记法中，写屏障技术被用于记录对象的标记状态，并且只对未被标记过的对象进行标记。

当应用程序线程修改了一个对象的引用时，写屏障会记录该对象的新标记状态。如果该对象未被标记过，那么它会被标记为灰色，以便在垃圾回收器的下一次遍历中进行标记。如果该对象已经被标记为可达对象，那么写屏障不会对该对象进行任何操作。

通过使用写屏障技术，三色标记法能够确保垃圾回收器能够准确地标记所有可达对象，并且避免了多次标记同一对象的情况。同时，写屏障技术也会带来一定的性能开销，因为每次引用被修改时都需要记录新的标记状态。为了减少性能开销，垃圾回收器通常会使用基于插入式写屏障的优化技术，来降低写屏障的开销。

多标的问题

所谓多标，其实就是这个对象原本应该被回收掉的白色对象，但是被错误的标记成了黑色的存活对象。从而导致这个对象没有被GC回收掉。

这个一般发生在并发标记过程中，该对象还是有引用的，但是在过程中，应用程序执行过程中把他的引用关系删除了，导致他变成了一个垃圾对象。

多标的话，会产生浮动垃圾，这个问题一般都不太需要解决，因为这种垃圾一般都不会太多，另外在下一次GC的时候也都能被回收掉。

多标的问题

所谓漏标，和多标刚好相反，就是说一个对象本来应该是黑色存活对象，但是没有被正确的标记上，导致被错误的垃圾回收掉了。

这种情况一旦发生是很危险的，一个正常使用的对象被垃圾回收掉了，这对系统来说是灾难性的问题，那么如何解决呢？

具体的解决方式，在CSM和G1中也不太一样。CMS采用的是增量更新方案，G1则采用的是原始快照的方案。

漏标的问题想要发生，需要同时满足两个充要条件：

1、至少有一个黑色对象在自己被标记之后指向了这个白色对象

2、所有的灰色对象在自己引用扫描完成之前删除了对白色对象的引用

那么，增量更新方案就是破坏了第一个条件，而原始快照方案就是破坏了第二个条件。

增量更新

“至少有一个黑色对象在自己被标记之后指向了这个白色对象”，这个条件如果被破坏了，那么就不会出现漏标的问题。所以：

如果有黑色对象在自己标记后，又重新指向了白色对象。那么我就把这个黑色对象的引用记录下来，在后续「重新标记」阶段再以这个黑色对象为根，对其引用进行重新扫描。通过这种方式，被黑色对象引用的白色对象就会变成灰色，从而变为存活状态。

这种方式有个缺点，就是会重新扫描新增的这部分黑色对象，会浪费多一些时间。但是其实这个浪费还好，因为本来这种漏标的情况就并不是特别常见，所以这部分需要重新扫描的黑色对象也并不多。

原始快照

“所有的灰色对象在自己引用扫描完成之前删除了对白色对象的引用”，这个条件如果被破坏了，那么就不会出现漏标的问题。所以：

如果灰色对象在扫描完成前删除了对白色对象的引用，那么我们就在灰色对象取消引用之前，先将灰色对象引用的白色对象记录下来。

在后续「重新标记」阶段再以这些白色对象为根，对它的引用进行扫描，从而避免了漏标的问题。通过这种方式，原本漏标的对象就会被重新扫描变成灰色，从而变为存活状态。

但是这种放回寺可能会把本来真的要取消引用的对象给错误的复活了，从而产生浮动垃圾。但是就像前面说的，多标的问题是可以忽略的。

总结

为了解决传统的引用计数法和可达性分析算法存在的循环引用问题、误标记问题以及STW时间长的问题，咋CMS和G1中引入了三色标记算法，其实就是在标记过程中将对象的状态划分为白色、灰色、和黑色三种状态。

同时把一次标记拆分成初始标记、并发标记以及重新标记三个阶段。并且只有初始标记和重新标记是STW的，而耗时最长的重新标记不需要STW，可以和应用线程并行。

但是因为并发标记过程中是不需要STW的，这就需要采用写屏障的方式避免并发。但是还是会存在漏标和多标的问题。

多标的问题我们一般可以忽略，因为下次GC还是可以回收掉的。但是漏标的问题还是要解决的，避免对象使用过程中被回收了，为了解决这个问题，CMS和G1分别采用了增量更新和原始快照两种方案来实现的，都能帮助我们解决漏标的问题。

色标改用回收器的对象开发前端$CMSG1三色标

有关CMS和G1改用三色标记法，可达性分析到底做错了什么？的更多相关文章

  1. ruby - 为什么我可以在 Ruby 中使用 Object#send 访问私有(private)/ protected 方法？ - 2

    类classAprivatedeffooputs:fooendpublicdefbarputs:barendprivatedefzimputs:zimendprotecteddefdibputs:dibendendA的实例a=A.new测试a.foorescueputs:faila.barrescueputs:faila.zimrescueputs:faila.dibrescueputs:faila.gazrescueputs:fail测试输出failbarfailfailfail.发送测试[:foo,:bar,:zim,:dib,:gaz].each{|m|a.send(m)resc

  2. ruby-on-rails - Rails - 子类化模型的设计模式是什么？ - 2

    我有一个模型:classItem项目有一个属性“商店”基于存储的值，我希望Item对象对特定方法具有不同的行为。Rails中是否有针对此的通用设计模式？如果方法中没有大的if-else语句，这是如何干净利落地完成的？ 最佳答案 通常通过Single-TableInheritance. 关于ruby-on-rails-Rails-子类化模型的设计模式是什么？，我们在StackOverflow上找到一个类似的问题： https://stackoverflow.co

  3. ruby - 什么是填充的 Base64 编码字符串以及如何在 ruby​​ 中生成它们？ - 2

    我正在使用的第三方API的文档状态:"[O]urAPIonlyacceptspaddedBase64encodedstrings."什么是“填充的Base64编码字符串”以及如何在Ruby中生成它们。下面的代码是我第一次尝试创建转换为Base64的JSON格式数据。xa=Base64.encode64(a.to_json) 最佳答案 他们说的padding其实就是Base64本身的一部分。它是末尾的“=”和“==”。Base64将3个字节的数据包编码为4个编码字符。所以如果你的输入数据有长度n和n%3=1=>"=="末尾用于填充n%

  4. ruby - 解析 RDFa、微数据等的最佳方式是什么，使用统一的模式/词汇(例如 schema.org)存储和显示信息 - 2

    我主要使用Ruby来执行此操作，但到目前为止我的攻击计划如下:使用gemsrdf、rdf-rdfa和rdf-microdata或mida来解析给定任何URI的数据。我认为最好映射到像schema.org这样的统一模式，例如使用这个yaml文件，它试图描述数据词汇表和opengraph到schema.org之间的转换:#SchemaXtoschema.orgconversion#data-vocabularyDV:name:namestreet-address:streetAddressregion:addressRegionlocality:addressLocalityphoto:i

  5. ruby - 为什么 4.1%2 使用 Ruby 返回 0.0999999999999996？但是 4.2%2==0.2 - 2

    为什么4.1%2返回0.0999999999999996？但是4.2%2==0.2。 最佳答案 参见此处:WhatEveryProgrammerShouldKnowAboutFloating-PointArithmetic实数是无限的。计算机使用的位数有限(今天是32位、64位)。因此计算机进行的浮点运算不能代表所有的实数。0.1是这些数字之一。请注意，这不是与Ruby相关的问题，而是与所有编程语言相关的问题，因为它来自计算机表示实数的方式。 关于ruby-为什么4.1%2使用Ruby返

  6. ruby - ruby 中的 TOPLEVEL_BINDING 是什么？ - 2

    它不等于主线程的binding，这个toplevel作用域是什么？此作用域与主线程中的binding有何不同？>ruby-e'putsTOPLEVEL_BINDING===binding'false 最佳答案 事实是，TOPLEVEL_BINDING始终引用Binding的预定义全局实例，而Kernel#binding创建的新实例>Binding每次封装当前执行上下文。在顶层，它们都包含相同的绑定(bind)，但它们不是同一个对象，您无法使用==或===测试它们的绑定(bind)相等性。putsTOPLEVEL_BINDINGput

  7. ruby - Infinity 和 NaN 的类型是什么？ - 2

    我可以得到Infinity和NaNn=9.0/0#=>Infinityn.class#=>Floatm=0/0.0#=>NaNm.class#=>Float但是当我想直接访问Infinity或NaN时:Infinity#=>uninitializedconstantInfinity(NameError)NaN#=>uninitializedconstantNaN(NameError)什么是Infinity和NaN？它们是对象、关键字还是其他东西？ 最佳答案 您看到打印为Infinity和NaN的只是Float类的两个特殊实例的字符串

  8. ruby-on-rails - 如果 Object::try 被发送到一个 nil 对象，为什么它会起作用？ - 2

    如果您尝试在Ruby中的nil对象上调用方法，则会出现NoMethodError异常并显示消息:"undefinedmethod‘...’fornil:NilClass"然而，有一个tryRails中的方法，如果它被发送到一个nil对象，它只返回nil:require'rubygems'require'active_support/all'nil.try(:nonexisting_method)#noNoMethodErrorexceptionanymore那么try如何在内部工作以防止该异常？ 最佳答案 像Ruby中的所有其他对象

  9. ruby - 为什么 SecureRandom.uuid 创建一个唯一的字符串？ - 2

    关闭。这个问题需要detailsorclarity.它目前不接受答案。想改进这个问题吗？通过editingthispost添加细节并澄清问题.关闭8年前。Improvethisquestion为什么SecureRandom.uuid创建一个唯一的字符串？SecureRandom.uuid#=>"35cb4e30-54e1-49f9-b5ce-4134799eb2c0"SecureRandom.uuid方法创建的字符串从不重复？

  10. ruby - 当使用::指定模块时，为什么 Ruby 不在更高范围内查找类？ - 2

    我刚刚被困在这个问题上一段时间了。以这个基地为例:moduleTopclassTestendmoduleFooendend稍后，我可以通过这样做在Foo中定义扩展Test的类:moduleTopmoduleFooclassSomeTest但是，如果我尝试通过使用::指定模块来最小化缩进:moduleTop::FooclassFailure这失败了:NameError:uninitializedconstantTop::Foo::Test这是一个错误，还是仅仅是Ruby解析变量名的方式的逻辑结果？ 最佳答案 Isthisabug,or

随机推荐