garbage-collection - HotSpot 使用的 Mark-Compact 算法是什么？

大免责声明：我不是 GC 专家/作家；下面写的所有内容都会发生变化，其中一些可能过于简单化。请把这个和一粒盐一起吃。

我只会谈论Shenandoah，因为我认为我理解它；这不是分代 GC。

这里实际上有两个阶段：Mark和Compact。我要在这里强烈强调两者都是并发的，并且确实在您的应用程序运行时发生（带有一些非常短的 STW 事件）。

现在到细节。我在这里解释了一些事情，但是因为那个答案与某种不同的问题有关；我会在这里解释更多。我认为遍历活动对象图对您来说不是新闻，毕竟您正在阅读一本关于GC. 正如该答案所解释的，当应用程序完全停止（也称为安全点）时，识别活动对象很容易。没有人改变你脚下的任何东西，地板是僵硬的，你控制着一切。并行收集器执行此操作。

真正痛苦的方法是同时做事。Shenandoah 采用了一种称为Snapshot at the beginning（那本书解释它 AFAIK）的算法SATB，简称它。基本上这个算法是这样实现的：“我将开始同时扫描对象图（从 GC 根），如果在我扫描时发生任何变化，我不会改变堆，但会记录这些变化并在以后处理它们” .

您需要提问的第一部分是：当我扫描时。这是如何实现的？好吧，在做之前concurrent mark，有一个STW event叫Initial Mark. 在该阶段完成的一件事是设置一个标志，表明并发标记已经开始。稍后，在执行代码时，会检查该标志（Shenandoah因此在解释器中使用了更改）。在伪代码中：

if(!concurrentMarkingActive) {
    // do whatever you were doing and alter the heap
} else {
    // shenandoah magic
}

在可能如下所示的机器代码中：

test %r11, %r11 (test concurrentMarkingActive flag)
jne // concurrent marking is currently active

现在 GC 知道何时发生并发标记。

但是并发标记是如何实现的。当堆本身发生突变（不稳定）时，如何扫描堆？你脚下的地板增加了更多的洞，也将它们移除。

那就是“神仙魔法”。对堆的更改被“拦截”而不是直接持久化。因此，如果 GC 在此时执行并发标记，并且应用程序代码尝试改变堆，则这些更改会记录在每个线程中SATB queues（开头的快照）。当并发标记结束时，这些队列被排空（通过STW event调用Final Mark）并且那些被排空的更改被再次分析（记住在STW event现在）。

当这个阶段Final Mark结束时，GC 知道什么是活着的，因此什么是隐含的垃圾。

接下来是紧凑阶段。Shenandoah现在应该将活动对象移动到不同的区域（以紧凑的方式）并将当前区域标记为我们可以再次分配的区域。当然，简单STW phase来说，这很容易：移动对象，更新指向它的引用。完毕。当你必须同时做...

您不能将对象简单地移动到不同的区域，然后一一更新您的参考。想想看，假设这是我们拥有的第一个状态：

 refA, refB
     |
 ---------
 | i = 0 |
 | j = 0 |
 ---------

此实例有两个引用：refA和refB。我们创建此对象的副本：

refA, refB
     |
 ---------       ---------
 | i = 0 |       | i = 0 |
 | j = 0 |       | j = 0 |
 ---------       ---------

我们创建了一个副本，但尚未更新任何参考。我们现在移动一个引用以指向副本：

   refA            refB
     |               |
 ---------       ---------
 | i = 0 |       | i = 0 |
 | j = 0 |       | j = 0 |
 ---------       ---------

现在有趣的部分：ThreadAdoes refA.i = 5， while ThreadBdoes refB.j = 6so 你的状态变成：

   refA            refB
    |                |
 ---------       ---------
 | i = 5 |       | i = 0 |
 | j = 0 |       | j = 6 |
 ---------       ---------

你现在如何合并这些对象？老实说 - 我不知道这是否可能，这也不是一条路线Shenandoah。

相反，解决方案从Shenandoah做一件非常有趣的事情恕我直言。添加到每个实例的额外指针，也称为转发指针：

 refA, refB
      |
 fwdPointer1    
      |         
 ---------       
 | i = 0 |       
 | j = 0 |       
 ---------

refA并refB指向fwdPointer1，而fwdPointer1指向真实的对象。现在让我们创建副本：

 refA, refB
      |
fwdPointer1     fwdPointer2        
      |               |
 ---------       ---------  
 | i = 0 |       | i = 0 | 
 | j = 0 |       | j = 0 | 
 ---------       ---------

现在，我们要切换所有引用 (refA和refB) 以指向副本。如果您仔细观察，这只需要一个指针更改 - fwdPointer1。fwdPointer1指出，你fwdPointer2就完成了。这意味着一个单一的变化，而不是两个（在这个设置中）refA和refB。这里更大的胜利是您不需要扫描堆并找出指向您的实例的引用。

有没有办法自动更新引用？当然：（AtomicReference至少在java中）。这里的想法几乎是一样的，我们原子地改变fwdPointer1via a CAS（比较和交换），如下：

 refA, refB
      |
fwdPointer1 ---- fwdPointer2        
                     |
 ---------       ---------  
 | i = 0 |       | i = 0 | 
 | j = 0 |       | j = 0 | 
 ---------       ---------

所以，refA并refB指向fwdPointer1，它现在指向我们创建的副本。通过一个CAS操作，我们同时切换了对新创建副本的所有引用。

然后，GC 可以简单地（同时）更新所有引用refA并refB指向fwdPointer2. 最后有这个：

                 refA, refB
                     |
fwdPointer1 ---- fwdPointer2        
                     |
 ---------       ---------  
 | i = 0 |       | i = 0 | 
 | j = 0 |       | j = 0 | 
 ---------       ---------

所以，左边的对象现在是垃圾：没有指向它的引用。

但是，我们需要了解其中的弊端，没有免费的午餐。

首先，很明显：在堆中的每个实例中Shenandoah添加一个机器头（进一步阅读，因为这是错误的；但更容易理解）。
这些副本中的每一个都将在新区域中生成一个额外的对象，因此在某些时候，同一对象将至少有两个副本（因此需要额外的空间Shenandoah来运行）。
什么ThreadA时候refA.i = 5（从前面的示例中），它如何知道它是否应该尝试创建一个副本、写入该副本以及CAS简单forwarding pointer地写入对象？请记住，这是同时发生的。concurrentMarkingActive与标志相同的解决方案。有一个标志isEvacuationToADifferentRegionActive（不是实际名称）。如果该标志是true=> Shenandoah Magic，否则只需按原样进行写入。

如果您真的理解了最后一点，那么您的自然问题应该是：

“等一下！这是否意味着 Shenandoahif/else反对isEvacuationToADifferentRegionActive对实例的 EACH 和 SINGLE 写入 - 无论是原语还是引用？这是否也意味着必须通过 ? 访问每个读取forwarding pointer？”

答案曾经是 YES；但是事情发生了变化：通过这个问题（尽管我让它听起来比实际情况要糟糕得多）。现在他们Load对整个对象使用障碍，更多细节在这里。他们没有在每次写入时设置障碍（if/else针对标志）并通过forwarding pointer每次读取取消引用，而是移至load barrier. 基本上if/else只有在加载对象时才这样做。由于写入它意味着首先读取，因此它们保持“空间不变”。显然这更简单，更好，更容易优化。万岁！

还记得forwarding pointer吗？好吧，它已经不存在了。我不了解它的整个荣耀的细节（还），但它必须做一些可能使用 themark word和 the 的from space事情，因为添加了负载屏障，不再使用。更多细节在这里。一旦我了解它在内部的真正运作方式，将更新帖子。

G1与实际情况并没有太大的不同Shenandoah，但魔鬼在细节中。例如Compact，阶段G1是一个STW事件，总是。G1总是代代相传的——不管你是否想要（Shenandoah 可能有点像那样——有一个设置来控制它）等等。

garbage-collection - HotSpot 使用的 Mark-Compact 算法是什么？

问题描述

解决方案

推荐阅读