三色标记算法在并发情况下的漏标问题分析【纯理论】

还是延着上一次【https://www.cnblogs.com/webor2006/p/11147545.html】的理论继续前行。。上一次学到这了:

下面来看一下三色标记算法的整个过程:

  • 根对象被置为黑色,子对象被置为灰色。如下图:

    其中可以看到灰色对象是已经被扫描过了,但是灰色对象里面所引用的子对象还未被扫描,所以可以看到灰色对象指向了未被扫描过的白色对象。

  • 继续由灰色遍历,将已扫描了子对象的对象置为黑色,如下:

    可以看到由于灰色里面的子对象已经被扫描过了,所以原灰色对象就变成了黑色了,而它所引用的白色对象由于被扫描到了,所以白色变成了灰色了。

  • 遍历了所有可达的对象后,所有可达的对象都变成了黑色。不可达的对象既为白色,需要被清理:

    其中:

    因为这三个对象被扫描完之后就会由白色变成灰色,然后由于这三个对象里面没有任何其它子对象,所以就由灰度变为了黑色了。

  • 但是如果在标记过程中,应用程序也在运行,那么对象的指针就有可能改变。这样的话,我们就会遇到一个问题:对象丢失问题。那问题是如何产生的呢,下面来说一下。
  • 当垃圾收集器扫描到下面情况时:
  • 由于在GC扫描时应用程序线程也在同步执行,这时候应用程序执行了以下操作:
    A.c = C
    B.c = null

  • 这样, 对象的状态图变成如下情形:

  • 这时候垃圾收集器再标记扫描的时候就会变成下图这样:
  • 由于A变成了黑色,垃圾收信器是永远不会再扫描它了,因为垃圾回收器认为A里面的所有子对象都已经扫描完了,而问题就来了,此时C是白色,被认为是垃圾需要清理掉,显示这是不合理的,明明C是一个正常可用的对象。
原文地址:https://www.cnblogs.com/webor2006/p/11147893.html