jvm

发布日期: 2023-04-05

字数: 5.7k

阅读时间: 20 分钟

《深入Java虚拟机：JVM G1GC的算法与实现》-算法篇笔记

这一篇文章主要是用于记录《深入Java虚拟机：JVM G1GC的算法与实现》一书中算法篇部分的笔记,主要分为引子、并发标记、转移、软实时性、分代G1GC模式;

G1 GC是什么?

在G1GC之前JVM中存在的垃圾收集器主要是Parallel Scavenge和Parallel Old,在jdk9将G1设置为默认处理器后,截至现在的jdk 20都是默认的垃圾收集器,目前G1GC就是JDK平台跨最多版本的默认垃圾收集器;

G1GC设计的出发点与之前的GC收集器有明显的不同,之前的不管是串行的Serial还是并发Paraller都是基于吞吐量和缩短最大暂停时间来进行设计的;
目前JVM的生态或者说面向的应用还是偏向于Web处理方面的,这一类应用的特点短、快,因此需要具有软实时性和高吞吐量的垃圾收集器;

软实时性指的是处理时间可以超出最后期限,但是超出最后期限的频率很重要.只有超出的频率在用户能够容忍的范围之内,才能称之为"软实时性"
举一个栗子: 公司都允许每个考勤周期内迟到2或者3次,公司可以容忍这种情况发生,但是超过规定的次数之后就不能忍受了,这种行为就叫"软实时性";与之相反的"硬实时性",例如"职务侵占"公司就一次都不能忍受;

咱们已经了解了为什么需要重头开始设计一个GC算法了,下面就看一下具体的内存结构和算法实现.

G1GC的内存结构

内存布局

G1GC内存布局

首先G1GC的内存布局最大的特点是抛弃了内存中对于老年代和年轻代的内存范围划分,而是采用区域(region),默认大小为1MB的形式进行划分.
对于region内存的大小用户可以随意设置,但是在内部会将用户设置的值向上调整为2的指数幂(2^n),1000kb->1024kb;

对象引用

这里的对象引用指的不是对象与对象之间的引用,而是在GC查找对象时持有的引用关系,一个典型的栗子就是老年代中引用年轻代存储关系的记忆集;

G1GC 跨代引用布局

Card Table

Card Tables and Concurrent Phases If a garbage collector does not collect the entire heap (an incremental collection), the garbage collector needs to know where there are pointers from the uncollected part of the heap into the part of the heap that is being collected. This is typically for a generational garbage collector in which the uncollected part of the heap is usually the old generation, and the collected part of the heap is the young generation. The data structure for keeping this information (old generation pointers to young generation objects), is a remembered set. A card table is a particular type of remembered set. Java HotSpot VM uses an array of bytes as a card table. Each byte is referred to as a card. A card corresponds to a range of addresses in the heap. Dirtying a card means changing the value of the byte to a dirty value; a dirty value might contain a new pointer from the old generation to the young generation in the address range covered by the card. 如果垃圾收集器不收集整个堆而是进行增量收集，则垃圾收集器需要知道从堆的未收集部分到正在收集的堆部分的指针在哪里。这通常适用于分代垃圾收集器，其中堆的未收集部分通常是老年代，堆中已收集的部分是新生代。保存此信息的数据结构（指向年轻代对象的老年代指针）是一个记忆集(RS)。 Card Table是一种特殊类型的记忆集。 Java HotSpot VM 使用字节数组作为卡片表。每个字节称为一张卡片。一张卡片对应堆中的一个地址范围。弄脏一张卡片意味着将字节的值更改为脏值；一个脏值可能包含一个新的指针，在卡覆盖的地址范围内从老一代到年轻一代。

Card Table是用于简化年轻代收集,类似与一个被老年代持有年轻代对象的索引,在年轻代进行垃圾收集时按图索骥就可以把这些被跨代引用的对象找出来,之后会详细的讲述一下执行过程;

执行过程

G1GC底层算法是标记-压缩算法,这样的话它的执行步骤可以划分为两个部分:

并发标记阶段
并发标记阶段主要是在尽量不暂停mutator线程(即访问和修改Manage Object的线程,如所有Java Thread及其Attach到JVM的thread)的情况下标记出存活的对象,而且在标记过程中会记录下每个区域(region)内存活的对象数量;
转移压缩阶段
转移压缩阶段主要是将待回收区域内的存活对象复杂到其他空闲区域中,然后将空闲出来的区域标记为空闲状态,类似于GC算法,但是是以单位进行的;

需要注意的是并发标记和转移压缩在处理顺序上是没有先后顺序的,并发标记的结果对于转移压缩阶段也不是必须的.

上面简单的描述了一下G1GC的执行过程,下面我们来详细的看一下并发标记阶段做的事情

并发标记阶段

标记位图

首先解释"并发标记"是在标记什么?

并发标记是在标记所有的存活对象和可以回收的对象,并发标记并不是直接在对象内存上添加标记,而是在标记位图上

标记位图如图所示

标记位图

标记位图是对region中分配的对象进行一个类似于索引标记的数据结构,每个bit位对应一个对象,默认最小的对象为8字节,0代表活动对象;

每个region都有两个标记位图分别是nextBitMap和prevBitMap用于保存本次的位图和上一次的位图;

由于在并发标记阶段Mutator线程可以继续分配对象或者yuang GC,会破坏已经进行过标记的内存区域,因此需要用4个标记位来确定,分别是bottom、TOP、prevTAMS、nextTAMS

bottom-TOP范围表示的开始标记前的某个区域的底部和顶部
TAMS(Top-at-Mark-Start,标记开始时的top)，prevTAMS和nextTAMS即上/下一次的标记的top

nextTAMS-TOP范围表示就就是标记过程中新产生的对象所占用的区域

执行步骤

并发标记过程包括以下5个步骤:

初始标记阶段
并发标记阶段
最终标记阶段
存活对象计数阶段
收尾阶段

初始标记阶段

创建标记位图

在初始化阶段,GC线程会首先创建Next MarkBitmap
对GC Root可达对象进行扫描和标记,为了防止GC Root对象变化,Mutator是暂停执行的,这里需要注意的是初始标记阶段有且只会对GC Root的可达对象进行标记

初始标记阶段结果

并发标记阶段

并发标记阶段,GC线程会继续扫描在初始化阶段被标记过的对象,分析它们的引用关系,完成大部分存活对象的标记

并发标记阶段结果

在并发标记阶段GC线程和Mutator线程是并发执行的,那么是如何解决标记遗漏问题的楠?

标记遗漏

首先说一下标记遗漏产生的原因,从上图中可以看到我们的GC线程已经标记到第二层对象,这个时候Mutator线程将Obj1-Obj3直接的引用关系去除,并且GCRoot-Obj3产生新的引用关系,由于Obj1标记完成后已经没有下属的任何引用那么就不会在标记Obj3,就发生了标记遗漏,可以看到发生标记遗漏的两个条件:

新产生一条或多条从黑色对象(已标记对象)到白色对象(未标记对象)的新引用;
删除灰色对象(正在标记对象)到白色对象的引用关系;

那么解决标记遗漏的问题就在于对这两个关系的破坏或者记录:

在CMS中采用的是增量更新(Incremental Update)方案,破坏的是第一个条件，当黑色对象插入新的指向白色对象的引用关系时，就将这个新插入的引用记录下来，等并发扫描结束之后，再将这些记录过的引用关系中的黑色对象为根，重新扫描一次;

在G1GC中采用的是原始快照(Snapshot At The Beginning,SATB)方案,破坏的是第二个条件，当灰色对象要删除指向白色对象的引用关系时，就将这个要删除的引用记录下来，在并发扫描结束之后，再将这些记录过的引用关系中的灰色对象为根，重新扫描一次;

这里重新扫描的是灰色对象,然后是在快照中扫描,快照指的是GC在开始时对象之间的引用关系,这里会产生一个问题,将本来已经可以进行回收的对象标记为活动的,系统设计上应该是要保证没有漏掉的对象,防止不能回收掉这些内存.

G1GC采用的是写屏障技术来记录对象之间引用关系的变化,对于新分配的对象直接认为这部分对象是已经标记完成;

最终标记阶段

最终标记阶段是对SATB本地队列进行扫描,因为在并发标记介绍以后本地的SATB队列容量可能不满,不会刷新到全局SATB队列中,因此需要全局暂停来处理这些"残留的SATB本地队列";

全局SATB与局部SATB之间的关系

最终标记处理的就是上图中mutator1线程和mutator2线程对于的局部SATB队列;

存活对象计数阶段

通过上面三个标记步骤(初始、并发、最终)将本次GC需要进行内存收集的对象标记出来了,这个时候就需要扫描各个区域的next标记位图,统计各个区域内存活对象的字节数目;
这个计数步骤可以和mutator是并发执行的,但是不能和转移线程(Remembered set)线程并行执行,因为如果并行执行会破坏region内的计数正确性;

收尾阶段

在上面两个步骤(标记、计数)中我们已经得到GC所需的最重要的两个信息:

标记完成后存活对象和死亡对象之间的区分(标记位图)
存活对象的内存占用(内存占用字节数量)

有上面俩组数据之后,才能进行

转移压缩

转移压缩过程中涉及到一个比较重要的概念转移效率,指的是"死亡对象的字节数 % 转移所需时间",换句话说,转移效率指的是转移1个字节所需时间;

这里的转移指的是是对于存活对象转移的耗时,因为在一个需要对象回收比较多的region区域内,只需要将少量的存活对象转移出去,这块region就可以进行回收了;

通过历史转移效率的数据,就可以尝试预测下次内存需要进行回收的时间;

小结

在标记阶段主要是通过两种数据结构标记位图、SATB来实现对region的标识和计数,流程上分为:

初始标记阶段 -> GCRoot出发
并发标记阶段 -> 上一步中散发的引用的对象
最终标记阶段 -> 标记局部SATB中的对象
计数/收尾阶段 -> 计数统计和转移

对局部SATB的操作使用的是前置写屏障技术来实现的;

下面详细用一节来介绍一下转移的具体过程;

GC的转移功能

转移的先决条件

首先说一下为什么需要转移,由于内存特性会出现碎片化,因此需要对内存进行整理,才能继续分配对象,整理这个步骤具体的操作就是通过转移来实现的;

转移功能是通过具体的转移专用记忆集合来快速索引对象的,记录的是区域与区域之间的对象间的引用关系;通过使用转移专用记忆集合,在转移时即使不扫描所有区域内的对象,也可以查询到待转移对象
所在区域被其他区域引用的情况,从而简化单个区域回收的转移处理步骤;

G1GC是通过卡表(card table)来进行实现转移专用记忆集合的元素的;

在上图"G1GC 跨代引用布局"图列中的Remembered Set就是转移专用记忆集合,记录的元素就是card table的元素地址,如下所示

转移专用记忆集合

每个区域都有一个转移专业记忆集合,它是通过hash列表实现的,key为引用本区域的其他区域地址,value为一个数组,元素是引用区域对应的卡表中的元素;
通过RS和Card Table这样的数据结构,在进行跨代引用对象的转移时可以快速的根据数据来进行查找;

RS的写入是由专用的转移专用记忆集合维护线程来进行维护的,可以和mutator线程并发执行;

转移的执行步骤

转移的执行步骤可以分为以下三个:

选择回收集合
指的是根据上述标记阶段得到的信息来选择被转移的区域.被选中的区域被称为回收集合;
根转移
指的是将回收集合中的由GC Root对象直接引用的对象和被其他区域引用的对象转移到其他空间中;
转移
指的是以2步骤中转移的对象作为起点扫描其子孙对象,然后将这些对象转移到其他空间中;

选择回收集合

这个步骤是G1GC算法的核心部分,在选择需要进行回收的集合时,是按照两个原则来进行选择:

转移效率高的区域优先
整体区域转移预测的暂停时间需要在用户的容忍范围之内

在标记的最后一个步骤收尾阶段中我们介绍了什么是转移效率的概念,简单的理解就是存活的对象越少,这个region的转移效率就越高;
然后根据转移效率对所有region进行排序,就可以得到一个region数组;
每一个region都有一个预测的转移暂停时间,G1GC在选择本次的回收集合就是从region数据从上到下依次累积预测暂停时间,直到大于等于用户的容忍时间阀值,这个子集就是
本次需要进行回收的集合;

G1GC中的G1是Garbage First的简称,翻译成中文指的是"垃圾优先的垃圾回收"算法,而转移效率从高到低的顺序就是垃圾优先的具体实现方法;

根转移步骤

根转移指的是将对象或者引用转移到其他区域,包括三类数据:

由根直接引用的对象
并发标记处理中的对象
由其他区域对象直接引用的回收集合内的对象

对象转移

对象转移分为三类:

对于引用到回收集合内的对象,将该对象添加到转移队列中,然后进行回收;
对于引用到回收集合外的对象,将更新其他对象的转移专用记忆集合;
对于其他对象引用到回收对象时,更新回收对象的转移专用记忆集合;

转移

在完成根转移之后,哪些被转移队列引用的对象将会依次进行转移.直到转移队列都被清空,转移就全部完成了;至此,回收集合内所有存活的对象都被成功转移到存活区域了;

小结

在转移阶段是整个G1GC最核心的思想实现,一个是"垃圾优先的垃圾回收"算法的实现,一个是"根对象转移算法"的实现;

软实时性

G1GC是如何实现软实时性的?

在G1GC中用户可以设置以下三个值:

可用内存的上限
通过Xmn/xmx来指定堆空间最小/最大值,避免内存被过度占用,Xmn不建议使用,这个值会破坏我们对于暂停时间上限的配置
G1GC暂停时间上限
使用-XX:MaxGCPauseMillis=200 为所需的最大暂停时间设置目标值,默认值为 200 毫秒.这里有一个前提是在一个GC单位时间内的暂停时间上限;
GC单位时间
对于GC单位时间的配置,没有找到相关资料,但是肯定是有这个概念的;避免通过频繁的GC来达到暂停时间少的目的;

G1GC是根据预测转移时间和预测可信度这两个计算结果来实现软实时性的;

在G1GC内部有一个调度队列,其中的元素是暂停处理的开始时间和结束时间的组合.G1GC使用这个队列来高效的调度GC的暂停任务.调度队列中保存了最近一次
暂停处理的开始时间和介绍时间.调度队列中的元素有上限,如果添加元素时超过上限,队列头部最早添加的元素就会被删除;

如下展示一下GC暂停处理的调度过程

GC暂停处理的调度过程

图中1表示的是在当前时间开始预测下一次发生GC的暂停时间为X,第2步表示如果此时开始GC,在一个GC的单位时间之内会超过设定的GC暂停时间的上限,因此不进行暂停;
在第3步中,如果将暂停时间延迟,在GC的单位时间内不会超过设定的GC暂停时间上限;
需要注意的是调度程序会保证在任意截取的GC单位时间内,总的GC暂停时间都不会超过用户设置的GC暂停时间上限,当然在某些特殊情况下也会超出设置的暂停时间上限,这就是G1GC所保证的"乱实时性",这些特殊情况包括但是不限于"GC的预测时间不准确"和"堆内存空间不足"等;