澳门太阳娱乐集团官网-太阳集团太阳娱乐登录

自己动手写垃圾收集器[译]
分类:脚本专栏

之前写过几篇自己动手系列的文章,简要实现了栈,二叉堆,malloc等函数,对于垃圾收集器,一直也有所耳闻。像python中主要使用引用计数手段来管理内存,为了解决循环引用的问题,引入了分代收集和标记-清除方式。当然python中可能产生循环引用的只可能是容器类对象如list,dict,class等,而像int,string是不可能产生循环引用的。当然python中的垃圾收集器实现是比较复杂的,我也没有看过具体代码,昨天在网上看到一篇简单实现垃圾收集器的好文章,于是,翻译到这里,供大家参阅。这篇文章中实现了一个mark-sweep的垃圾收集器,代码不多,我这里没有照文翻译,只是把核心的实现翻译了过来,原文链接Baby's First Garbage Collector

一、思考GC需要完成3件事情

  1. 哪些内存需要回收?
  2. 什么时候回收?
  3. 如何回收?

参考 《深入理解Java虚拟机 JVM高级特性与最佳实践》 3.5节

假想一台机器有无限的内存,这样开发人员只需要不停的分配内存即可,不用考虑回收内存的的问题。当然,理想是丰满的,现实是骨感的。机器没有无限内存,当你在分配了许多内存后,程序运行慢下来了,需要考虑回收垃圾了。

二、哪些内存需要回收?

Java 内存运行时区域的各个部分,其中程序计数器、虚拟机栈、本地方法栈3个区域随线程而生,随线程而灭;栈中的栈帧随着方法的进入和退出而有条不紊地执行着出栈和入栈操作。这几个区域的内存分配和回收都具备确定性,在这几个区域就不需要考虑内存回收的问题。而Java堆和方法区的内存分配和回收都是动态的,垃圾收集器所关注的是这部分内存。

1.垃圾收集器概览

图片 1

HotSpot的收集器们

在本文上下文中,垃圾就是指的就是之前分配过的现在不再使用的内存。为了让程序能够在有限的内存里面工作,需要保证“不再使用”是非常安全的,一旦准备收集垃圾,这些待收集对象一定要能够保证不再使用,也不能通过任何方式引用到。我们要收集的是“不再使用”的对象,这里先给出"在使用"的定义(注:因为我们是要标记在使用的对象,然后清除没有标记的对象即不再使用的对象):

三、什么时候回收?判断对象是否存活的算法

2.Serial收集器

  • 使用单线程收集垃圾
  • 收集垃圾时,需要停下其他所有工作线程,直到收集结束
  • 优点是简单粗暴,效率最高
  • 可以跟CMS收集器配合使用

    图片 2

    Serial配合Serial Old收集器

  • 1任何在代码范围内被变量引用的对象是在使用中的。
  • 2任何被其他在使用中的对象引用的对象是在使用中的。

1. 引用计数算法

给对象添加一个引用计数器,每当有一个地方引用它,计数器值就加1;当引用失效时,计数器值就减1;任何时刻计数器为0的对象就是不可能再被使用的。但是它很难解决对象之间相互循环引用的问题。

3.ParNew收集器

  • ParNew就是Serial收集器的多线程版本
  • 可以跟CMS收集器配合使用
  • ParNew收集器在单核环境下绝对不会比Serial收集器有更好的效果,因为有线程调度的开销,而这些线程调度的开销下,双核环境下的ParNew收集器的表现都不一定比Serial收集器好
  • 解释一下两个名词:
    • 并行(Parallel):指多条垃圾收集线程并行工作,但此时用户线程仍然处于等待状态。
    • 并发(Concurrent):指用户线程与垃圾收集线程同时执行(但不一定是并行的,可能会交替执行),用户程序在继续运行,而垃圾收集程序运行于另一个CPU上。
    • 并行和并发的关键区别是否是多个同类线程同时执行。在垃圾收集中,多条垃圾收集线程是同类线程,它们同时执行就是并行,而垃圾收集线程和用户线程就不是同类线程,它们同时执行就是并发。

图片 3

ParNew配合Serial Old收集器

第2条规则是递归的。如果对象A被一个变量引用,且对象A有字段引用了对象B,那么对象B是使用中的,因为你可以从A引用到B。最终的结果就是一个可达对象图(reachable objects graph)-那些你可以通过变量遍历到的对象。而任何不在可达对象集合中的对象都已经成为了垃圾,它们占用的内存可以被回收了。

2. 可达性分析算法

基本思路就是通过一系列的称为“GC Roots”的对象作为起点,从这些节点开始向下搜索,搜索所走过的路径称为引用链,当一个对象到GC Roots 没有任何引用链相连时,则证明此对象是不可用的。
  在Java中,可作为GC Roots的对象包括下面几种:

  • 虚拟机栈(栈帧中的本地变量表)中引用的对象。
  • 方法区中类静态属性引用的对象。
  • 方法区中常亮引用的对象。
  • 本地方法栈中JNI(即一般说的Native方法)引用的对象。

虽然这些算法可以判定一个对象是否能被回收,但是当满足上述条件时,一个对象并不一定会被回收。当一个对象不可达GC Root时,这个对象并
不会立马被回收,而是出于一个死缓的阶段,若要被真正的回收需要经历两次标记。
如果对象在可达性分析中没有与GC Root的引用链,那么此时就会被第一次标记并且进行一次筛选,筛选的条件是是否有必要执行finalize()方法。当对象没有覆盖finalize()方法或者已被虚拟机调用过,那么就认为是没必要的。
如果该对象有必要执行finalize()方法,那么这个对象将会放在一个称为F-Queue的队列中,虚拟机会触发一个Finalize()线程去执行,此线程是低优先级的,并且虚拟机不会承诺一直等待它运行完,这是因为如果finalize()执行缓慢或者发生了死锁,那么就会造成F-Queue队列一直等待,造成了内存回收系统的崩溃。GC对处于F-Queue中的对象进行第二次被标记,这时,该对象将被移除"即将回收"集合,等待回收。

4.Parallel Scavenge收集器

  • 和CMS更关注收集垃圾时的暂停时间相比,Parallel Scavenge(后称PS)更关注吞吐量
  • 停顿时间短适合强交互的程序,但是每次的停顿时间短肯定意味着总的停顿时间会变长,而PS的目标就是总的停顿时间最短

回收不再使用的对象有很多种方法,不过最早和最简单的算法就是标记-清除法。发明该方法的人是John McCarthy大牛,他还发明了Lisp语言。

四、如何回收?垃圾收集算法

5.Serial Old收集器

  • Serial收集器的老年代版本
  • 单线程收集器,使用“标记-整理”算法
  • 在Server模式下,作为CMS收集器的备胎方案,如果CMS并发收集时出现Concurrent Mode Failure时使用
![](https://upload-images.jianshu.io/upload_images/3084829-cce04664252acc35.png)

Serial配合Serial Old收集器

标记-清除方法的流程很简单:

1. 标记—清除算法

算法分为“标记”和“清除”两个阶段:首先标记出所有需要回收的对象,在标记完成后统一回收所有被标记的对象。它的主要不足有两个:一个是效率问题,标记和清除两个过程的效率都不高;另一个是空间问题,标记清除之后会产生大量不连续的内存碎片,空间碎片太多可能会导致以后在程序运行过程中需要分配较大对象时,无法找到足够的连续内存而不得不提前触发另一次垃圾收集动作。

6.Parallel Old收集器

  • 注意,这个是Parallel Scavenge收集器的老年代版本,不是ParNew的老年代版本
  • 因为之前的情况是使用了Parallel Scavenge收集器的话,就只能使用Serial Old老年代收集器了,这让PS收集器很尴尬,所以又搞了个Parallel Old来配合PS收集器
  • 搞了个Parallel Old收集器后,就可以和PS配合使用,这样就可以在吞吐量优先的场景下发挥它们的最大威力
![](https://upload-images.jianshu.io/upload_images/3084829-b2204bc123e3ee07.png)

PS配合Parallel Old收集器
  • 从根出发,遍历可达对象图,每次遇到一个可达对象,设置对象标记为true。
  • 然后,遍历目前分配的所有对象,如果该对象标记没有设置为true,则该对象不可达,需要删除来释放内存。

2. 复制算法

为了解决效率问题,一种称为“复制”的收集算法出现了,它将可用内存按容量划分为大小相等的两块,每次只使用其中的一块。当这一块的内存用完了,就将还存活着的对象复制到另一块上面,然后再把已使用过的内存空间一次清理掉。这样使得每次都是对整个半区进行内存回收,内存分配时也就不用考虑内存碎片等复杂情况,实现简单,运行高效。只是这种算法的代价是将内存缩小为了原来的一半,未免太高了点。
  HotSpot 虚拟机默认 Eden 和 Survivor 的大小比例是 8:1。

7.CMS(Concurrent Mark Sweep)收集器

  • CMS收集器是以最短停顿时间为目标的
  • CMS有4个阶段
    • 初始标记:标记与GC Roots直接关联的对象们,速度很快,因为只需要标记处于GC Roots关联的第一层对象,需要stop the world
    • 并发标记:标记出大部分存活的对象,为什么说是大部分呢,因为这个阶段是并发的,用户线程在标记过程仍然可以使引用链发送改变,不需要stop the world
    • 重新标记:因为并发标记是和用户线程一起执行的,而这个阶段可能会有标记结果产生变动的对象,所以需要在这个阶段再进行一次标记,这个阶段会比初始标记慢一点,比并发标记和并发清除快很多,需要stop the world
    • 并发清除:不需要stop the world
  • CMS的优缺点:
    • CMS在并发标记和并发清除的时候会和用户线程分享CPU资源,所以在CPU资源紧张的场合,使用CMS收集器可能会降低程度的速度
    • CMS无法处理浮动垃圾,可能出现“Concurrent Mode Failure”失败而导致另一次Full GC产生。浮动垃圾是怎么产生的呢?因为在垃圾回收的最后阶段,也就是并发清除过程中,用户线程仍然可以产生垃圾!这些垃圾已经无法在本轮GC中被回收,就是所谓的浮动垃圾,如果这些垃圾的量很大,而剩余的空间又不足的话,就会引发“Concurrent Mode Failure”,然后使用Serial Old作为替代方案进行垃圾收集。所以老年代一般不会设定为满了才开始垃圾回收,要是这样的话百分百会导致“Concurrent Mode Failure”,想想啊,要是你满了才开始回收,那用户线程产生的垃圾放哪里?可以通过设置-XX:CMSInitiatingOccupancyFraction来设置出发老年代垃圾回收的百分比。
    • CMS是基于“标记- 清除”算法实现的收集器,这样的收集器都会有一个毛病,就是回产生大量的内存碎片,那既然会产生内存碎片,那为什么不用“标记-整理”算法呢,因为“标记-整理”算法的整理过程是需要stop the world的!这和CMS的设计理念(尽可能短的暂停时间)相悖,所以没有使用“标记-整理”算法。为了解决这个问题,CMS提供了一个-XX:+UseCMSCompactAtFullCollection开关参数(默认开启),当CMS收集器顶不住要进行FullGCT时开启内存碎片的合并并整理过程。还有一个参数-XX:CMSFullGCsBeforeCompaction设置执行多少次不压缩的Full GC后,跟着一次带压缩的整理。

在实现标记-清除算法之前,先来定义几个对象。假想我们是在实现一个语言解释器,该语言只有两种对象类型,因此,我们用枚举类型定义对象类型ObjectType如下:

3. 标记 — 整理算法

标记过程仍然与“标记 — 清除”算法一样,但后续步骤不是直接对可回收对象进行清理,而是让所有存活的对象都向一端移动,然后直接清理掉端边界以外的内存。

8.G1收集器感觉说的不是很清楚,就是草草介绍了一下

typedef enum { OBJ_INT, OBJ_PAIR} ObjectType;

4. 分代收集算法

一般是把Java 堆分为新生代和老年代,这样就可以根据各个年代的特点采用最适当的收集算法。

9.理解GC日志

直接看书里的好了,就是一些规则

OBJ_INT是一个整数类型对象,而OBJ_PAIR是一个pair对象,它可以包含两个整数,也可以是一个整数和一个pair,因为我们定义中只有这两种对象类型,要么int要么pair,因此采用union类型来定义对象是十分合适的,定义如下:

五、垃圾收集器

typedef struct sObject { ObjectType type; union { /* OBJ_INT */ int value; /* OBJ_PAIR */ struct { struct sObject* head; struct sObject* tail; }; };} Object;

1. Serial 收集器

是一个单线程的收集器,在它进行垃圾收集时,必须暂停其它所有的工作线程,直到它收集结束。

其中type字段说明了对象类型,而union对象用于存储对象内容,要么是int的值,或者是一个pair结构体。

2. ParNew 收集器

ParNew 收集器其实就是 Serial 收集器的多线程版本。

接下来实现一个虚拟机对象,它的角色就是用栈来存储我们当前范围内的对象。许多语言的虚拟机都是基于栈的,如JVM和CLR,也有基于寄存器的,如Lua。在我们的例子中,采用的是基于栈的,它用于存储局部变量和临时变量。代码如下:

3. Parallel Scavenge 收集器

#define STACK_MAX 256typedef struct { Object* stack[STACK_MAX]; int stackSize;} VM;

4. Serial Old 收集器

有了虚拟机的数据结构,我们看下创建虚拟机以及初始化的代码,以及操作虚拟机的代码:

5. Parallel Old 收集器

VM* newVM() { VM* vm = malloc(sizeof; vm->stackSize = 0; return vm;}void push(VM* vm, Object* value) { assert(vm->stackSize < STACK_MAX, "Stack overflow!"); vm->stack[vm->stackSize++] = value;}Object* pop { assert(vm->stackSize > 0, "Stack underflow!"); return vm->stack[--vm->stackSize];}

6. CMS 收集器

有了虚拟机以及虚拟机操作,现在可以来创建对象了,相关代码如下:

7. G1收集器

Object* newObject(VM* vm, ObjectType type) { Object* object = malloc(sizeof; object->type = type; return object;}

六、简述 Java 垃圾回收机制

在java中,程序员是不需要显示的去释放一个对象的内存的,而是由虚拟机自行执行。在JVM中,有一个垃圾回收线程,它是低优先级的,在正常情况下是不会执行的,只有在虚拟机空闲或者当前堆内存不足时,才会触发执行,扫描那些没有被任何引用的对象,并将它们添加到要回收的集合中,进行回收。

创建对象后,需要压入到虚拟机的栈中,由于有两种不同对象int和pair,因此有两个不同函数,实现代码如下:

七、简述java内存分配与回收策率以及Minor GC和Major GC

  1. 对象优先在堆的Eden区分配。
      2. 大对象直接进入老年代。
      3. 长期存活的对象将直接进入老年代。

当Eden区没有足够的空间进行分配时,虚拟机会执行一次Minor GC。Minor GC通常发生在新生代的Eden区,在这个区的对象生存期短,往往发生GC的频率较高,回收速度比较快;Full GC/Major GC 发生在老年代,一般情况下,触发老年代GC的时候不会触发Minor GC,但是通过配置,可以在Full GC之前进行一次Minor GC这样可以加快老年代的回收速度。

void pushInt(VM* vm, int intValue) { Object* object = newObject(vm, OBJ_INT); object->value = intValue; push(vm, object);}Object* pushPair { Object* object = newObject(vm, OBJ_PAIR); object->tail = pop; object->head = pop; push(vm, object); return object;}

为了实现标记,我们需要在之前的Object定义中加一个marked字段,用于标识该对象是否可达。修改后定义如下:

typedef struct sObject { unsigned char marked; //新增的标记字段 ObjectType type; union { /* OBJ_INT */ int value; /* OBJ_PAIR */ struct { struct sObject* head; struct sObject* tail; }; };} Object;

每当我们创建一个对象,我们修改newObject()函数设置marked为0。为了标记所有可达对象,我们需要遍历可达对象栈。代码如下:

void markAll{ for (int i = 0; i < vm->stackSize; i++) { mark(vm->stack[i]); }}

在markAll中我们调用了mark函数,它的实现如下:

void mark(Object* object) { object->marked = 1;}

需要注意到的是,对象可达是递归的,因为我们还有pair类型的对象,因此mark函数修改如下:

void mark(Object* object) { /* If already marked, we're done. Check this first to avoid recursing on cycles in the object graph. */ if (object->marked) return; object->marked = 1; if (object->type == OBJ_PAIR) { mark(object->head); mark(object->tail); }}

标记完之后,下一步就是清除那些没有被标记的对象。但是现在有个问题是,我们找不到这些不可达的对象。

因此,我们还需要跟踪对象。最简单的方法就是在对象中加入一个链表用于跟踪我们分配过的对象,虚拟机结构中保存链表头指针,因此,Object和VM定义修改如下:

typedef struct sObject { /* The next object in the list of all objects. */ struct sObject* next; //新增链表指针 unsigned char marked; ObjectType type; union { /* OBJ_INT */ int value; /* OBJ_PAIR */ struct { struct sObject* head; struct sObject* tail; }; };} Object;typedef struct { /* The first object in the list of all objects. */ Object* firstObject; //新增对象链表头 Object* stack[STACK_MAX]; int stackSize;} VM;

创建对象的时候,需要将其加入到对象链,同时更新虚拟机的链表头指针的值。

Object* newObject(VM* vm, ObjectType type) { Object* object = malloc(sizeof; object->type = type; object->marked = 0; /* Insert it into the list of allocated objects. */ object->next = vm->firstObject; vm->firstObject = object; return object;}

接下来,我们就可以来清除不可达对象了。先标记可达对象,然后遍历对象链表,如果对象没有标记,则清除,有标记,则去掉标记,并从下一个对象接着遍历。

void sweep{ Object** object = &vm->firstObject; while  { if (!->marked) { /* This object wasn't reached, so remove it from the list and free it. */ Object* unreached = *object; *object = unreached->next; free(unreached); } else { /* This object was reached, so unmark it (for the next GC) and move on to the next. */ ->marked = 0; object = &->next; } }}

至此,垃圾收集器基本完成了。首先来组合一下标记和清除这两个函数。那么你可能会有疑惑的是我们应该在什么时候调用gc这个函数呢?这里我们采用一种简单的策略,只要分配对象超过了我们设定的最大数目就调用gc。为此,我们需要在VM中加入两个变量来记录已分配的对象数目和最大对象数目。

void gc { markAll; sweep;}

typedef struct { /* The total number of currently allocated objects. */ int numObjects; /* The number of objects required to trigger a GC. */ int maxObjects; /* Previous stuff... */} VM;VM* newVM() { /* Previous stuff... */ vm->numObjects = 0; vm->maxObjects = INITIAL_GC_THRESHOLD; return vm;}

代码中的INITIAL_GC_THRESHOLD就是我们首次开启gc的对象数目,这个值可以根据内存大小进行调整。因此,在newObject函数中,如果分配对象大于了最大对象数目,我们需要运行gc来清除不可达的对象。

Object* newObject(VM* vm, ObjectType type) { if (vm->numObjects == vm->maxObjects) gc; /* Create object... */ vm->numObjects++; return object;}

此外,我们在每次gc之后,会更新下最大对象数。修改后的gc函数代码如下:

void gc { int numObjects = vm->numObjects; markAll; sweep; vm->maxObjects = vm->numObjects * 2;}

完整版示例代码:

个人觉得容易错的是sweep函数,代码中使用了指向指针的指针来遍历链表,确实便捷很多。另外,在每次遍历时,如果对象可达,则需要设置mark标记为0并将遍历指针指向下一个对象.这里设置可达对象的mark标记为0十分重要,因为你每次sweep之前都会markAll,如果这里不标记为0,那么后续如果这个对象确实不可达了,由于mark标记没有复位为0,则以后都会收不到了。

另外,一定要看下完整代码,里面有完整的实例,可以解决你在看本文中的一些疑惑。

本文由澳门太阳娱乐集团官网发布于脚本专栏,转载请注明出处:自己动手写垃圾收集器[译]

上一篇:没有了 下一篇:没有了
猜你喜欢
热门排行
精彩图文