关于标记-清除算法的疑问

[honwhy]

原文是这样的，

标记清除算法分为两个步骤，标记和清除。 首先将需要回收的对象标记起来，然后统一清除。

标记阶段是从GC Roots开始做可达性分析，标记的应该是不要回收的对象；
参考这篇文章可能说得比较清晰，标记-清除算法

[wanyinsheng]

标记的应该是不被回收的对象

[PansonPanson]

原文是这样的，

标记清除算法分为两个步骤，标记和清除。 首先将需要回收的对象标记起来，然后统一清除。

标记阶段是从GC Roots开始做可达性分析，标记的应该是不要回收的对象；
参考这篇文章可能说得比较清晰，标记-清除算法

在《深入理解Java虚拟机》第2版书中，69页写的是：

首先标记出出所有要回收的对象，在标记完成后统一回收所有被标记的对象。
关于此问题，R大也在博客中写过：垃圾回收与弱引用

引用计数方式会为每个已分配内存单元设置计数器，当计数器减少到0的时候就意味着该单元无法再被引用，于是立即执行释放内存的动作。垃圾回收方式的基本思想是mark-and-sweep（标记-清除），每隔一段时间或者在堆空间不足的时候才进行一次垃圾回收，每次垃圾回收先将所有堆上分配的内存单元标记为“不可到达”，然后从一组根引用开始扫描，把所有从根引用出发可以达到的单元标记为“可以到达”；然后把标记为“不可到达”的内存单元回收到可用的堆空间中。

[crossoverJie]

这个问题有点意思，我查阅了一些资料。

这里有一个维基百科的图片：

Naive mark-and-sweep in action on a heap containing eight objects. Arrows represent object references. Circles represent the objects themselves. Objects #1, #2, #3, #4, and #6 are strongly referenced from the root set. On the other hand, objects #5, #7, and #8 are not strongly referenced either directly or indirectly from the root set; therefore, they are garbage.

https://en.wikipedia.org/wiki/Tracing_garbage_collection#Na.C3.AFve_mark-and-sweep

从图片和内容中确实表述的也是标记可达对象，也就是不可回收对象。

https://blogs.msdn.microsoft.com/abhinaba/2009/01/30/back-to-basics-mark-and-sweep-garbage-collection/

这里也是谈到只标记可达对象。

但是如 @PansonPanson 所说在《深入理解Java虚拟机》第2版中确实写的是标记所有要回收的对象
并且网上不少这样的说法，我估计都是来自于这本书。

结合目前查阅到的一些国外资料来看，我也认为标记的是不可回收对象。

[apt-getyou]

标记的应该还是可回收对象，如果不是这么操作，那如何解决未标记的新对象被清理的问题，

[crossoverJie]

@apt-getyou

不管标记可回收还是不可回收对于清除来说都没影响，反正他们肯定是分开的，能分开就知道回收哪些了。

[honwhy]

@apt-getyou
标记-清除算法是两阶段的算法，先标记不可回收的对象，再遍历所有堆对象，然后判断是否需要清除；
看上面提到文章的伪代码

另外如果是标记要回收的对象，那么需要逆向逻辑，要确定所有的其他对象都没有引用这个对象，才能确定是否要回收，这样的算法复杂度是多少呢？

[crossoverJie]

@honwhy

可以提一个 PR 修复这个描述。

[kuhnpeng]

Oracle官方文档： https://docs.oracle.com/en/java/javase/11/gctuning/concurrent-mark-sweep-cms-collector.html#GUID-4CB5DCEB-FCBF-4A57-83A1-F2C47BF0B3D7