精华内容
下载资源
问答
  • CMS 三色标记法
    2021-06-27 20:55:40

    为什么引入三色标记法

    为了提供 JVM 垃圾回收的性能,从 CMS 垃圾收集器开始,引入了并发标记的概念(此处的并发标记是指与用户线程一起工作)。引入并发标记的过程就会带来一个问题,在业务执行的过程中,会对现有的引用关系链出现改变。具体如下图:

    在这里插入图片描述

    当 GC 线程开始标记对象的时候,如果这个时候用户线程修改了 F 和 A 的引用,因为此时 A对象已经被遍历完成了,GC线程就不会再对 A 有新的标记操作,这样 GC 线程就会认为 B,C,D 对象没有被任何对象引用,就会被当成垃圾回收。

    很明显在并发的情况下,“两色“的标记法是无法满足要求的。

    三色标记的过程

    为了解决并发的问题,我们可以引入中间的状态(灰色),当一个对象被标记的时候,会有下面几个过程:

    1. 首先被标记成灰色
    2. 检测当前所有的灰色对象,遍历子节点
    3. 如果子节点被遍历完了,把当前节点标记成黑色

    在这里插入图片描述

    在上图中,第一个过程是把 A,E 标记成灰色,后续再遍历 A,E 的子节点,发现了 A 有 C 节点,E 有 F 节点,这样 C,F在后续就会被标记成活着的对象(此处还会存在缺陷,后面讨论)

    三色标记的问题

    从上面的分析可以得出,三色标记法解决了并发的场景的引用链变动的问题,但是也会存在问题。

    在上面的场景中,如果 GC 线程标记 A 成黑色后,用户线程修改了 A 的引用,这个时候 A 是黑色,C 因为没有找到引用的变量,还是会被当成垃圾回收。

    CMS 如何解决

    理解了问题的本质,问题就容易解决了,G1 收集器采用的 SATB 解决方案(略),CMS 采用了 Incremental Update 解决方案:如果发现对象子节点有新的引用,增加一个写入屏障,同时把黑色改成灰色

    CMS 为什么还需要重新标记?

    在采用了 Incremental Update 解决方案后,还是会存在一个巨大的缺陷,在上述的场景中,如果有多个 GC 线程对 A 标记,两个线程判断可能存在不一致,具体如下图:

    在这里插入图片描述

    在上面的场景中,我们假设GC 线程 1 发生在用户线程之前,GC 线程 2 发生在业务线程后:

    当 GC 线程 1 发现 A 有没有,会把 A 变成黑色。

    当 GC 线程 2 发现 A 有子节点,会把 A 变成灰色。

    这样就对垃圾回收的结果产生了误判,所以CMS 在并发标记后还需要一次重新标记,当然这次重新标记会带来更长的 STW。
    这个也许是 CMS 不是任何版本 JDK 的默认垃圾回收器了。

    更多相关内容
  • 三色标记法

    千次阅读 2022-02-15 16:22:24
    本文主要介绍了三色标记法的基本思路、多标导致的浮动垃圾、漏标的处理方案等。 1. 垃圾回收的简单回顾 关于垃圾回收算法,基本就是那么几种:标记-清除、标记-复制、标记-整理。在此基础上可以增加分代(新生代/...

    前言

    本文主要介绍了三色标记法的基本思路、多标导致的浮动垃圾、漏标的处理方案等。

    1. 垃圾回收的简单回顾

    关于垃圾回收算法,基本就是那么几种:标记-清除、标记-复制、标记-整理。在此基础上可以增加分代(新生代/老年代),每代采取不同的回收算法,以提高整体的分配和回收效率。
    无论使用哪种算法,标记总是必要的一步。这是理算当然的,你不先找到垃圾,怎么进行回收?

    垃圾回收器的工作流程大体如下:

    1. 标记出哪些对象是存活的,哪些是垃圾(可回收);
    2. 进行回收(清除/复制/整理),如果有移动过对象(复制/整理),还需要更新引用。

    本文着重来看下标记的部分。

    2. 三色标记法

    2.1 基本算法

    要找出存活对象,根据可达性分析,从GC Roots开始进行遍历访问,可达的则为存活对象:

    最终结果:A/D/E/F/G 可达

    我们把遍历对象图过程中遇到的对象,按“是否访问过”这个条件标记成以下三种颜色:

    白色:尚未被GC访问过的对象,如果全部标记已完成依旧为白色的,称为不可达对象,既垃圾对象。
    黑色:本对象已经被GC访问过,且本对象的子引用对象也已经被访问过了(本对象的孩子节点也都被访问过)。
    灰色:本对象已访问过,但是本对象的子引用对象还没有被访问过,全部访问完会变成黑色,属于中间态(本对象的孩子节点还没有访问)。
     

    标记过程:

    • 初始时,所有对象都在 【白色集合】中;
    • 将GC Roots 直接引用到的对象 挪到 【灰色集合】中;
    • 从灰色集合中获取对象:
      3.1. 将本对象 引用到的 其他对象 全部挪到 【灰色集合】中;
      3.2. 将本对象 挪到 【黑色集合】里面。
    • 重复步骤3,直至【灰色集合】为空时结束。
    • 结束后,仍在【白色集合】的对象即为GC Roots 不可达,可以进行回收

    问题:由于此过程是在和用户线程并发运行的情况下,对象的引用处于随时可变的情况下,那么就会造成多标和漏标的问题。

    浮动垃圾:本应该被标记为白色的对象,没有被标记,造成该对象可能不会被回收。

    假设已经遍历到E(变为灰色了),此时应用执行了 objD.fieldE = null ,D和E之间的线断开,此刻之后,对象E/F/G是“应该”被回收的。然而因为E已经变为灰色了,其仍会被当作存活对象继续遍历下去。最终的结果是:这部分对象仍会被标记为存活,即本轮GC不会回收这部分内存

    另外,针对并发标记开始后的新对象,通常的做法是直接全部当成黑色,本轮不会进行清除。这部分对象期间可能会变为垃圾,这也算是浮动垃圾的一部分。

    漏标:灰色对象指向白色对象的引用消失了,然后一个黑色的对象重新引用了白色对象。假设GC线程已经遍历到E(变为灰色了),此时应用线程先执行了:

    var G = objE.fieldG;

    objE.fieldG = null; // 灰色E 断开引用 白色G

    objD.fieldG = G; // 黑色D 引用 白色G

    此时切回GC线程继续跑,因为E已经没有对G的引用了,所以不会将G放到灰色集合;尽管因为D重新引用了G,但因为D已经是黑色了,不会再重新做遍历处理。
    最终导致的结果是:G会一直停留在白色集合中,最后被当作垃圾进行清除。这直接影响到了应用程序的正确性,是不可接受的。


    漏标只有同时满足以下两个条件时才会发生:
    条件一:灰色对象 断开了 白色对象的引用;即灰色对象 原来成员变量的引用 发生了变化。
    条件二:黑色对象 重新引用了 该白色对象;即黑色对象 成员变量增加了 新的引用。

    解决方案:

    写屏障 + 增量更新,当对象D的成员变量的引用发生变化时(objD.fieldG = G;),我们可以利用写屏障,当D是黑色G是白色的话将D标为灰色,等待遍历,即增量更新(Incremental Update)。

    注:

    CMS(Concurrent Mark Sweep):写屏障 + 增量更新

     

    • 初始标记(STW initial mark):只标记被gc root直接引用的对象
    • 并发标记(Concurrent marking)
    • 并发预清理(Concurrent precleaning)
    • 重新标记(STW remark)
    • 并发清理(Concurrent sweeping)
    • 并发重置(Concurrent reset)

    初始标记 :在这个阶段,需要虚拟机停顿正在执行的任务,官方的叫法STW(Stop The Word)。这个过程从垃圾回收的"根对象"开始,只扫描到能够和"根对象"直接关联的对象,并作标记。所以这个过程虽然暂停了整个JVM,但是很快就完成了。

    并发标记 :这个阶段紧随初始标记阶段,在初始标记的基础上继续向下追溯标记。并发标记阶段,应用程序的线程和并发标记的线程并发执行,所以用户不会感受到停顿。

    并发预清理 :并发预清理阶段仍然是并发的。在这个阶段,虚拟机查找在执行并发标记阶段新进入老年代的对象(可能会有一些对象从新生代晋升到老年代, 或者有一些对象被分配到老年代)。通过重新扫描,减少下一个阶段"重新标记"的工作,因为下一个阶段会Stop The World。

    重新标记 :这个阶段会暂停虚拟机,收集器线程扫描在CMS堆中剩余的对象。扫描从"根对象"开始向下追溯,并处理对象关联。

    并发清理 :清理垃圾对象,这个阶段收集器线程和应用程序线程并发执行。

    并发重置 :这个阶段,重置CMS收集器的数据结构,等待下一次垃圾回收。

    重新标记必须从头扫描一次的原因:

     

    展开全文
  • 一、GO 1.3之前的标记删除 1.第一步,暂停程序业务逻辑,找出不可达对象,和可达对象 2.第二部,开始标记,程序找出它所有的可达对象,并做上标记 3.标记完之后,开始清楚未标记对象 4,停止暂停,让程序继续跑。...

    一、GO 1.3之前的标记删除

    1.第一步,暂停程序业务逻辑,找出不可达对象,和可达对象
    2.第二部,开始标记,程序找出它所有的可达对象,并做上标记
    3.标记完之后,开始清楚未标记对象
    4,停止暂停,让程序继续跑。然后循环重复这个过程直到process程序生命周期结束请添加图片描述

    标记-清除方法的缺点

    1.stw(stop the world)让程序暂停,程序出现卡顿
    2.标记需要扫描整个heap(堆)
    3.清除数据会产生heap碎片
    4.并发时,导致先前未被标记的误删除

    改进

    1.缩小stw范围,将清除挪出来,先恢复程序,再清除
    2.->使用三色标记法

    二、三色标记法(GO V1.5之后)

    程序RootSet根节点关联着对象1和对象4,而对象1关联对象2,对象2关联对象3,对象7引用着对象2;另一个分支,对象4引用对象5;对象6处于游离状态。下图展示的就是以上所表述的内存情况,从可达性分析得到,GC应该回收对象6与对象7,那么三色标记法如何识别到对象6和对象7呢?

    三色标记法是用于寻找从程序RootSet所关联的对象出发,只遍历一次,为每一个对象标记颜色。标记结束后,被标记为白色的对象需要释放空间,而被标记为黑色的对象继续保留。一次三色标记法结束后,是不存在被标记为灰色的对象的。

    如图下所示,第一步我们把所有的对象都标记为白色。请添加图片描述
    第二步,把在程序根结点集合RootSet里的对象标记为灰色。如下图所示,标记为灰色的是对象1和对象4。请添加图片描述
    第三步,遍历标记为灰色的对象,找到关联的对象,并标记为灰色,同时把自己标记为黑色。如下图所示,遍历灰色对象发现:对象1关联对象2,对象4关联对象5。那么,把对象2和对象5标记为灰色,同时对象1和对象4标记为黑色。请添加图片描述
    此时,被标记为灰色的对象是对象2和对象5。第四步,重复第三步,遍历寻找灰色对象所关联的对象,并标记为灰色。如下图所示,对象2关联对象3,对象5没有关联对象。那么把对象3标记为灰色,对象2和对象4标记为黑色。请添加图片描述
    到了这一步,还剩对象3,对象6和对象7没处理。我们继续,第五步,我们发现对象3没有关联对象,那么如下图,把对象3标记为黑色。

    请添加图片描述
    终于把全部对象标记颜色,此时释放被标记为白色的对象的内存空间,保留被标记为黑色的对象,已经不存在被标记为灰色的对象了。

    假设三色标记无STW,会发生什么:

    参考视频
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    三色标记最不希望发生的事:
    1.一个白色对象被黑色对象引用(条件一)
    2.灰色对象与它之间的可达关系的白色对象遭到破坏(条件二)
    (两个条件同时满足,对象丢失)

    强弱三色不变式:

    强三色不变式:不许黑色对象引用白色对象(破坏条件一)
    弱三色不变式:黑色可以引用白色,白色对象存在其他灰色对象对他的引用,或者可达它的链路上游存在灰色对象(破坏条件二)

    三、插入写屏障

    想要实现强弱三色不变式,需要学习插入写屏障

    插入屏障(不在栈上使用

    对象被引用时 触发的机制

    具体操作:在A对象引用B对象时,B对象被标记为灰色(将B挂在A的下游,B必须被标记为灰色)
    满足:强三色不变式(不存在褐色对象引用白色对象的情况了,因为白色会被强制变为灰色)

    //伪代码
    添加下游对象(当前下游对象slot,新下游对  象ptr){
    	//1
    	标记灰色(新下游对象ptr)
    	//2
    	当前下游对象slot = 新下游对象ptr
    }
    

    //场景
    A.添加下游对象(nil,B) //A之前无对象,新加B,B标记为灰
    A.添加下游对象(C,B) // A 将下游对象更换为B, B被标记为灰色

    插入写屏障的不足

    为了保证栈的速度,因此不会给栈加插入屏障
    那么扫描结束时需要stw来重新扫描栈,大约需要10-100ms

    删除屏障

    对象被删除时 触发的机制
    具体操作:被删除的对象,如果自身为灰色或者白色,那么被标记为灰色
    满足:弱三色不变式.(保护灰色对象到白色对象的路径不会断)

    //伪代码
    添加下游对象(当前下游对象slot,新下游对  象ptr){
    	//1 注:删除就是添加一个空
    	if(当前下游对象slot是灰色||当前下游对象slot是白色){
    		灰色标记(当前下游对象slot)
    	}
    	//2
    	当前下游对象slot = 新下游对象ptr
    }
    

    A.添加下游对象(B,nil) //A对象,删除B对象的引用。B被A删除,被标记为灰(如果B之前为白)
    A.添加下游对象(B,C) //A对象,更换下游对象为C。B被A删除,被标记为灰(如果B之前为白)

    删除写屏障的不足

    回收精度低,
    一个对象即使被删除了最后一个指向它的指针也依旧可以活过这一轮,在下一轮GC中被清理掉

    Go V1.8的三色标记法+混合写屏障机制

    具体操作:
    1.GC开始将栈上的对象全部扫描标记为黑色(之后不再进行二次重复扫描,无需stw)
    2.GC期间,任何在栈上创建的新对象,均为黑色
    3.被删除的对象标记为灰色(栈+堆)
    4.被添加的对象标记为灰色

    满足:变形的弱三色不变式(结合了插入、删除写屏障两者的优点)

    //伪代码
    添加下游对象(当前下游对象slot,新下游对  象ptr){
    	//1
    	标记灰色(当前下游对象slot)//只要当前下游对象被移走,就标记为灰色
    	//2
    	标记灰色(新下游对象ptr)
    	//3
    	当前下游对象slot = 新下游对象ptr
    }
    

    在这里插入图片描述
    在这里插入图片描述

    场景

    场景一

    对象被一个堆对象删除引用,成为栈对象的下游

    //伪代码
    //前提:堆对象4->对象7 = 对象7; 对象7 被 对象4 引用
    栈对象1 -> 对象7 = 堆对象7; // 将堆对象7 挂在 栈对象1 下游
    堆对象4 -> 对象7 = null // 对象4 删除引用 对象7

    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述

    场景二

    对象被一个栈对象删除引用,成为另一个栈对象的下游

    //伪码
    new 栈对象9;
    对象9 -> 对象3 = 对象3;//将栈对象3 挂在 栈对象9 下游
    对象2 -> 对象3 = null; //对象2 删除引用 对象3

    在这里插入图片描述
    在这里插入图片描述

    在这里插入图片描述
    在这里插入图片描述

    场景三

    对象被一个堆对象删除引用,成为另一个堆对象的下游

    //伪码
    堆对象10 -> 对象7 = 对象7;//将栈对象7挂在 栈对象10下游
    堆对象4 -> 对象7= null; //对象4 删除引用 对象7

    在这里插入图片描述
    在这里插入图片描述

    在这里插入图片描述

    场景三

    对象被一个栈对象删除引用,成为另一个堆对象的下游

    //伪码
    栈对象1 ->对象2 = null; //对象1 删除引用 对象2
    栈对象4 -> 对象2 = 栈对象2;//对象4 添加 下游 栈对象4
    栈对象4 -> 对象7 = null; //对象4 删除引用 对象7

    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述

    展开全文
  • 文章目录前言什么是垃圾回收JAVA的垃圾回收回顾GO的垃圾回收学习**三色标记法(tricolor mark-and-sweep algorithm)**Dijkstra方法(插入屏障,强三色,Go1.7之前)Yuasa方法(删除屏障,弱三色,Go1.8)Hybrid方法...

    前言

    ​ 众所周知,一门优秀的语言总会需要考虑很多点,比如说性能、内存、并发处理等,把其语言开发到一个高度。这一期我们学习的内容是内存方面的,并且结合java和go语言去阐述经典的内存垃圾对象回收算法。

    什么是垃圾回收

    在计算机科学中,垃圾回收(英语:Garbage Collection,缩写为GC)是指一种自动的存储器管理机制。当某个程序占用的一部分内存空间不再被这个程序访问时,这个程序会借助垃圾回收算法向操作系统归还这部分内存空间。

    通常占用程序空间都是一些运行对象,对象可包含的数据在一定限度是非常占用内存空间的,在某一时刻,就会达到操作系统规划的内存空间,若数量多起来了,就会超过该空间导致机器卡顿或者宕机情况发生。

    我们思考的方向便是既要最大化的利用计算机性能,又要保护计算机正常稳定的运转下去,就如同大自然一样,循环利用资源,这样才有可能实现持久化程序生态。

    现在业界垃圾回收器可以总结为两种收集器

    引用计数收集器
    最早的也是最简单的垃圾回收实现方法,这种方法为占用物理空间的对象附加一个计数器,当有其他对象引用这个对象时计数器加一,反之引用解除时减一。这种算法会定期检查尚未被回收的对象的计数器,为零的话则回收其所占物理空间,因为此时的对象已经无法访问。这种方法无法回收循环引用的存储对象。

    跟踪收集器
    近现代的垃圾回收实现方法,这种算法会定期遍历它管理的内存空间,从若干根储存对象开始查找与之相关的存储对象,然后标记其余的没有关联的存储对象,最后回收这些没有关联的存储对象占用的内存空间。

    这两个收集器的思想也会在java和go的垃圾回收器中有所体现,下面开始介绍。

    JAVA的垃圾回收回顾

    引用计数法

    将资源(可以是对象、内存或磁盘空间等等)的被引用次数保存起来,当被引用次数变为零时就将其释放的过程。使用引用计数技术可以实现自动资源管理的目的。同时引用计数还可以指使用引用计数技术回收未使用资源的垃圾回收算法。

    优点:实现简单,垃圾对象便于辨识;判定效率高,回收没有延迟性

    缺点:循环引用会造成垃圾对象无法回收

    例子:

    public class GcDemo {
    
        public void demo {
            //分为6个步骤
            GcObject obj1 = new GcObject(); //Step 1
            GcObject obj2 = new GcObject(); //Step 2
    
            obj1.instance = obj2; //Step 3
            obj2.instance = obj1; //Step 4
    
            obj1 = null; //Step 5
            obj2 = null; //Step 6
        }
    }
    
    class GcObject{
        public Object instance = null;
    }
    

    实现图如下所示

    [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-9AbmrERJ-1643795450807)(/Users/jackthwu/Library/Application Support/typora-user-images/image-20210914115020827.png)]

    可以看出即便obj1和obj2断开了引用链的链接但依然存在内部引用关系链,这样如果大家看到这里还是很可能不明不白的,比如说为啥计数器是2而不是1这样。我们得从底层出发,这里简单的介绍下关于java的内存模型,结合内存模型来说下。

    [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-WsEzQegb-1643795450808)(/Users/jackthwu/Desktop/杂七杂八的东西/技术文档/三色回收/image-20210914120825322.png)]

    Step1:GcObject实例1的引用计数加1,实例1的引用计数=1;

    Step2:GcObject实例2的引用计数加1,实例2的引用计数=1;

    Step3:GcObject实例2的引用计数再加1,实例2的引用计数=2;

    Step4:GcObject实例1的引用计数再加1,实例2的引用计数=2;

    执行到Step 4,则GcObject实例1和实例2的引用计数都等于2。

    断开引用后

    [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-IzkOlovo-1643795450809)(/Users/jackthwu/Desktop/杂七杂八的东西/技术文档/三色回收/image-20210914120918126.png)]

    会发现实际上obj1和obj2均不指向Java的堆,但是在堆内实例对象还会相互引用,计数器还是没有为零,这导致实际上应该回收obj1和obj2的没有回收,导致内存泄露。

    可达性分析法

    可达性分析算法,又叫根搜索算法或者追踪性垃圾收集

    可达性分析算法是以根对象集合(GC Roots)为起始点,按照从上至下的方式搜索被根对象集合所连接的目标对象是否可达。使用可达性分析算法后,内存中的存活对象都会被根对象集合直接或间接连接着,搜索所走过的路径称为引用链(Rererence Chain)。如果目标对象没有任何引用链相连,则是不可达的,就意味着该对象已经死亡,可以标记为垃圾对象。在可达性分析算法中,只有能够被根对象集合直接或者间接连接的对象才是存活对象

    [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-8aa0N3Ad-1643795450810)(/Users/jackthwu/Desktop/杂七杂八的东西/技术文档/三色回收/image-20210914143348772.png)]

    优点:解决引用计数器所不能解决的循环引用问题。 即便对象a和b相互引用,只要从GC Roots出发无法到达a或者b,那么可达性分析便不会将它们加入存活对象合集之中。

    缺点:由于需要从GC Roots开始逐个检查引用,所以耗时是缺点之一,而且在此期间,需要保证整个执行系统的一致性,对象的引用关系不能发生变化,所以会导致GC进行时必须停顿所有Java执行线程(STW)。(遍历耗时长)

    GO的垃圾回收学习

    三色标记法(tricolor mark-and-sweep algorithm)

    首先将对象用三种颜色表示,分别是黑色、灰色和白色。最开始所有对象都是白色的,然后把其中全局变量和函数栈里的对象置为灰色。第二步把灰色的对象全部置为黑色,然后把原先灰色对象指向的变量都置为灰色,以此类推。等发现没有对象可以被置为灰色时,所有的白色变量就一定是需要被清理的垃圾了。

    遍历集合,判断垃圾对象回收步骤:

    Step 1: 创建:黑、灰、白 三个集合。

    Step 2: 将所有对象放入白色集合中。

    Step 3: 从根节点开始遍历所有对象,把遍历到的对象从白色集合放入灰色集合(备注:这里放入灰色集合的都是根节点的对象)。

    Step 4: 遍历灰色集合,将灰色对象引用的对象从白色集合放入灰色集合,然后将分析过的灰色对象放入黑色集合。

    Step 5: 重复以上的步骤直到对象遍历结束

    [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-sY9SdOd7-1643795450810)(/Users/jackthwu/Desktop/杂七杂八的东西/技术文档/三色回收/image-20210914151241659.png)]

    [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-ZCGsvMTb-1643795450811)(/Users/jackthwu/Desktop/杂七杂八的东西/技术文档/三色回收/image-20210914151222232.png)]

    虽然这样很容易理解,但是也是理想情况回收,真正在我们的程序运行中会有很多情况发生。这些情况就会造成该对象应该不被回收但是被错误回收,应该被回收的没有被回收。可以总结以下两种问题:多标-浮动垃圾漏标-悬挂指针问题

    多标-浮动垃圾

    对象之间的引用链断开却没有把其变为可回收对象,反倒作为灰色对象继续存活下去。这部分垃圾对象没有被正确的回收成为“浮动垃圾”。

    [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-IcUvGLiB-1643795450811)(/Users/jackthwu/Desktop/杂七杂八的东西/技术文档/三色回收/image-20210915232430676.png)]

    漏标-悬挂指针问题

    指中间对象之间断开引用链后,指向在引用的对象断开的引用对象并没有在做遍历处理,导致对象没有遵循三色原则作为垃圾对象被回收。

    [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-fOhC4b6g-1643795450812)(/Users/jackthwu/Desktop/杂七杂八的东西/技术文档/三色回收/image-20210915234001517.png)]

    Step1:正常遍历,E断开H的引用,但是此时没有将H放入灰色集合,D直接引用H

    Step2:继续正常遍历,E变成黑色,F变成灰色,但是由于E断开了H的引用而D是黑色不会再次遍历对H的引用

    Step3:H作为白色对象被回收

    Ps:所以本想用H的,你给我回收了?

    这就是设计最不可被接受的一点。

    😠😠

    于是后续有大神提出了内存屏障原理。

    A memory barrier, is a type of barrier instruction that causes a central processing unit (CPU) or compiler to enforce an ordering constraint on memoryoperations issued before and after the barrier instruction. This typically means that operations issued prior to the barrier are guaranteed to be performed before operations issued after the barrier.

    翻译过来就是

    内存屏障是一种屏障指令,它使中央处理器(CPU)或编译器对屏障指令前后发出的内存操作强制执行排序约束,在屏障之前发布的操作一定优先于屏障之后发布的操作。

    什么意思呢?

    提取几个关键词:CPU/编译器 强制执行 排序约束 屏障操作

    用我自己的一句话来说就是——硬核排序

    排序的强制约束会让程序执行的过程中不会导致指令乱序,操作之前的指令还是操作之前的指令,不会因为程序的xx原因导致的指令乱序,而影响程序正常的表达。

    比如在三色中,程序在遍历所有的集合去染色,在某个操作前的染色还未执行完,难道操作后的染色比操作前的染色执行的更早吗?那肯定不行的。

    所以就有了以下两种三色定性要求

    • 强三色不变性(strong tri-color invariant):黑色不会到白色,只有黑和灰;

    • 弱三色不变性(weak tri-color invariant):黑色对象可以到白色对象,该白色对象上游一定存在一个灰色对象引用,并且所有被黑色对象引用的白色对象都处于灰色保护状态;

      [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-UB3mvjam-1643795450812)(/Users/jackthwu/Desktop/杂七杂八的东西/技术文档/三色回收/image-20210917103921450.png)]

    Dijkstra方法(插入屏障,强三色,Go1.7之前)
    //伪代码 Dijkstra
    DijkstraWritePointer(slot, ptr)
      //如果对象不是灰色对象,先置灰
      shade(slot)
      //赋值
      *slot = ptr
    

    Dijkstra方法是标准的强三色处理方式,但是这样就需要在STW 期间必须重新扫描许多堆栈,重新扫描就意味着额外的性能开销,这个对于优良程序设计是不太友好的。

    看看在《Proposal: Eliminate STW stack re-scanning》一文中提到

    writes to pointers on the stack must have write barriers, which is prohibitively expensive, or stacks must be permagrey. Go chooses the later, which means that many stacks must be re-scanned during STW. The garbage collector first scans all stacks at the beginning of the GC cycle to collect roots. However, without stack write barriers, we can‘t ensure that the stack won’t later contain a reference to a white object, so a scanned stack is only black until its goroutine executes again, at which point it conservatively reverts to grey.

    翻译过来就是:

    写入堆栈上的指针必须要有写屏障,但是这意味着代价相当的高,且堆栈必须是恒灰。Go 选择在 STW 期间必须重新扫描大量的栈。垃圾收集器首先在 GC 周期开始时扫描所有堆栈以收集根对象。然而如果没有栈写屏障操作,我们无法确保栈后面是否不会包含对白色对象的引用,因此直到它的 goroutine 再次执行之前扫描的栈只有黑色的,此时它会恢复为灰色。

    用一句话来解释就是:

    这个方法得先标记对象为灰色后重新扫描这些栈而导致的大量的性能开销,且栈必须要有写屏障,这个如果没有,那么在栈上的对象在断开再次引用其他对象的时候很有可能下一个被引用的对象因为没被写屏障置灰会被回收。

    这个方法有篇文章介绍的很好:https://cloud.tencent.com/developer/article/1769823

    Yuasa方法(删除屏障,弱三色,Go1.8)

    这个是Yuasa提出的删除屏障概念,满足弱三色的处理方式,

    其思想是集合中取出灰对象或白色对象删除白色指针时,通过写屏障这个操作通知给并发回收器

    在GC开始时STW扫描堆栈来记录初始快照,这个过程会记录开始时刻的所有存活对象,但结束时无需STW

    //伪代码 Yuasa
    YuasaWritePointer(slot, ptr)
      //假设对象为黑色,确保在ptr赋值前不是白色,先置灰
      //这样总能从下往上找到找到一条到达灰色对象的路径,保证弱三色原理
    	//删除屏障
      shade(*slot)
        if current stack is grey: // 这行可以忽略
    				// 插入屏障
            shade(ptr) 
      //赋值
      *slot = ptr
    
    Hybrid方法(混合写屏障)

    它的原理很简单,对正在覆盖的对象置灰,如果扫描未完成,指针也置灰。

    这是吸收了Yuasa和Dijkstra方法,这样做不仅简化 GC 的流程,也减少标记终止阶段的重扫成本。

    //伪代码 Hybrid
    HybridwritePointer(slot, ptr):
    //对象先置灰
        shade(*slot)
    //如果栈是灰色的
        if current stack is grey:
    //ptr置为灰色
            shade(ptr)
    //slot指针置灰
        *slot = ptr
    

    同时GC阶段也有个强制点,新建对象全部置黑色,防止被回收器错误回收。

    总结

    ​ 学习了这三种的收集器不禁感叹其实很多语言设计着在这一块可谓绞尽脑汁去思考,因为对于一门优秀的语言来说如何去更好的让它实现持久化、智能自动化处理的程序运行下去,既需要技术也是需要时间沉淀的。我在想go能不能直接抄了java的这个回收器得了,虽然因为go语言和java在很多方面还是有所区别,所以不能是统一个回收机制。

    ​ ps:你怎么知道人家没想过抄呢?😄

    文章致谢

    • 《可达性算法笔记》

    • 《两万字长文带你深入Go语言GC源码》-三色回收

    • 《维基百科-垃圾回收(计算机科学)一章》

    • Proposal: Eliminate STW stack re-scanning: https://go.googlesource.com/proposal/+/master/design/17503-eliminate-rescan.md

    • GC时写屏障与栈的引用变化: https://cloud.tencent.com/developer/article/1769823

    展开全文
  • JVM实战:三色标记法

    2022-03-09 18:00:31
    垃圾回收流程的一些流程 哪些对象是垃圾?...不可达对象会进行2次标记的过程,通过GC ROOT不可达,会被第一次标记。如果需要执行finalize()方法,则这个对象会被放入一个队列中执行finalize(),如果在fina.
  • 三色标记法详细图解

    2022-01-18 18:51:24
    为了能解释清楚这个问题,我们引入三色标记(Tri-color Marking)作为工具来辅 助推导,把遍历对象图过程中遇到的对象,按照“是否访问过”这个条件标记成三种颜色: 三色标记法 顾名思义,用三种颜色进行标记 白色...
  • 聊聊Go的三色标记法

    2021-08-07 00:21:42
    最近正好在学习 Golang,对它的里面用到的三色标记法的 GC 机制有些好奇(最开始是因为名字让我联想到了三色杯冷饮~),就稍微多深入了解了一下,在这里分享出来,或许将来对你面试啥的有些帮助。 /01 判断对象存活...
  • 由于,「可达性分析」思路是主流,所以后续发展出来的很多回收算法都以这个思路为基础的,三色标记法就是其中之一。我们今天主要来聊聊它。 02 三色标记法 在讲具体原理之前先了解一个概念,「Stop The World 」,...
  • 标记存活对象和可回收对象(可达性分析算法、计数) 对可回收对象采用进行垃圾回收处理 1.3 标记方法: 可达性分析算法:可达性分析算法是以根对象集合(GC Roots)为起始点,按照从上至下的方式进行搜索,搜索...
  • 垃圾回收简称 GC,就是对程序中不再使用的内存资源进行自动回收释放的操作。...标记-清除:从根变量开始遍历所有引用的对象,引用的对象会被标记,没有被标记的则进行回收。 优点:解决了引用计数的缺点; 缺点:需要
  • 文章目录题目题目解析题目解析普通dfs回溯(超时)三色标记法优化dfs 题目 题目解析 题目解析 读完题目我们需要知道的是,这题就是需要我们判断以某个点为起点的所有路径不能含有环,我们只需要判断出这一条件即可...
  • JVM垃圾回收-三色标记法JVM垃圾回收简单回顾如何确定垃圾引用计数法可达性分析GC roots第一次标记第二次标记三色标记法三色标记算法思想多标漏标CMS 之 Increment UpdateCMS 收集过程写屏障G1 之 SATBG1 收集Card ...
  • GC中的 三色标记法

    千次阅读 2020-06-12 19:00:19
    最近在看JVM 查资料的时候看到一篇关于三色标记法的文章觉得不错。拿过来收藏一下。因为他的配图是gif。让人一目了然啊。 原文地址《三色标记法与读写屏障》 以下内容图为摘录: 三色标记法: 首先要知道 在JVM中...
  • 详细图解JVM三色标记法

    千次阅读 2020-09-08 14:18:37
    JVM垃圾回收—三色标记
  • 一、为什么需要三色标记算法 JVM 中的垃圾回收是基于 标记-...那么后来就有了并发标记,适用于CMS和G1,并发标记的意思就是 可以在不暂停用户线程的情况下对其进行标记,那么实现这种并发标记的算法就是 三色标记法,三
  • 垃圾收集器与三色标记法垃圾收集算法1.分代收集理论标记-复制算法标记-清除算法标记-整理算法垃圾收集器1.Serial收集器2.Parallel Scavenge收集器3.ParNew收集器4.CMS收集器CMS的相关核心参数三色标记法多标-浮动...
  • jvm 三色标记法

    千次阅读 2020-04-17 21:19:00
    三色标记法 这个算法就是把 GC 中的对象划分成三种情况: 白色:还没有搜索过的对象(白色对象会被当成垃圾对象) 灰色:正在搜索的对象 黑色:搜索完成的对象(不会当成垃圾对象,不会被GC) 上面说的这个问题...
  • 首先标记有三个阶段: 初始标记 ->...标记复制算法中的标记阶段所用到的标记算法(三色标记算法); GC如果想查找到存活的对象,根据GCRoot可达分析算法 根据GCRoot引用链遍历存活对象。根据GCRoot..
  • 1. 垃圾回收的简单回顾关于垃圾回收算法,基本就是那么几种:标记-清除、标记-复制、标记-整理。在此基础上可以增加分代(新生代/老年代),每代采取不同的回收算法,以提高整体的分配和回收效率。无论使用哪种算法,...
  • 三色标记法GC 垃圾回收器其主要的目的是为了实现内存的回收,在这个过程中主要的两个步骤就是:内存标记,内存回收。三色标记法简介三色标记法,主要是为了高效的标记可被回收的内存块。三色标记(Tri-color Marking...
  • 三色标记法是一种垃圾回收法,它可以让JVM不发生或仅短时间发生STW(Stop The World),从而达到清除JVM内存垃圾的目的。 三色标记法-算法思想 三色标记法将对象的颜色分为了黑、灰、白,三种颜色。 黑色:该对象...
  • 一、Go垃圾回收发展历史 1.3之前:原始的标记清除算法(mark and sweep) 1.3 减少STW暂停的时间范围 1.5 三色并发标记 1.8 混合写屏障(hybrid write barrier)机制
  • CMS是采用三色标记法来进行垃圾的收集:三色标记即是用三种三色来标记对象的引用情况: 黑色标记:表示此对象及其所有的引用都已经被扫描过,表明这个对象是存活的,肯定不会被垃圾回收; 灰色标记:表示此对象被...
  • 三色标记法: GC HandBook把对象分成三种颜色: 黑色(Black) - 根对象,自身及可达对象都已经被标记 灰色 (Grey) - 自身已经被标记,可达对象还未被标记 白色 (White) - 还未被标记、垃圾对象 举个栗子吧: A.b...
  • 三色标记法
  • 内存屏障中的读写屏障及三色标记法一、并发问题1、概述2、Volatile通过读写屏障保证可见性和有序性2.1、保证可见性2.2、保证有序性二、 垃圾回收问题1、三色标记法1.1 基本算法1.2 多标-浮动垃圾1.3 漏标-读写屏障...
  • 【JVM】三色标记法与读写屏障

    千次阅读 2020-05-24 10:54:22
    首先:CMS和G1都使用了三色标记法 关于垃圾回收算法,基本就是那么几种:标记-清除、标记-复制、标记-整理。在此基础上可以增加分代(新生代/老年代),每代采取不同的回收算法,以提高整体的分配和回收效率。 无论...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 2,298
精华内容 919
关键字:

三色标记法