关于java:从零开始手写GC算法-标记清除附完整可运行源码

42次阅读

共计 4003 个字符,预计需要花费 11 分钟才能阅读完成。

看了一大堆的 GC 算法实践,是不是还是感觉差点什么呢?那就跟着本文的思路,本人入手写个标记 - 革除算法试试吧

首个值得纪念的 GC 算法就是 GC 标记 – 革除算法(Mark-Sweep GC)。自其问世以来,始终到半个世纪后的明天,它仍然是各种处理程序所用的平凡的算法。

GC 标记 – 革除算法由标记阶段和革除阶段形成。

标记阶段是把所有流动对象(可达对象,reachable)都做上标记的阶段。革除阶段是把那些没有标记的对象,也就是非流动对象回收的阶段。通过这两个阶段,就能够复用已开释的空间。

本文内容次要参考《垃圾回收的算法与实现》,应用 C 语言实现;文末附有源码地址,残缺可运行

名词解释

对象

对象在 GC 的世界里,代表的是数据汇合,是垃圾回收的根本单位。

指针

能够了解为就是 C 语言中的指针(又或者是 handle),GC 是依据指针来搜寻对象的。

mutator

这个词有些中央翻译为赋值器,但还是比拟奇怪,不如不翻译……

mutator 是 Edsger Dijkstra 推敲进去的词,有“扭转某物”的意思。说到要扭转什么,那就是 GC 对象间的援用关系。不过光这么说可能大家还是不能了解,其实用一句话概括的话,它的实体就是“应用程序”。

mutator 的工作有以下两种:

  • 生成对象
  • 更新指针

mutator 在进行这些操作时,会同时为应用程序的用户进行一些解决(数值计算、浏览网页、编辑文章等)。随着这些解决的逐步推进,对象间的援用关系也会“扭转”。随同这些变动会产生垃圾,而负责回收这些垃圾的机制就是 GC。

GC ROOTS

GC ROOTS 就是援用的起始点,比方栈,全局变量

堆 (Heap)

堆就是过程中的一段动态内存,在 GC 的世界里,个别会先申请一大段堆内存,而后 mutatar 在这一大段内存中进行调配

流动对象和非流动对象

流动对象就是能通过 mutatar(GC ROOTS)援用的对象,反之拜访不到的就是非流动对象。

筹备工作

在标记革除算法中,应用闲暇链表(free-list)的内存调配策略

闲暇链表 (free-list) 内存调配

闲暇链表调配应用某种数据结构(个别是链表)来记录闲暇内存单元的地位和大小,该数据结构即为闲暇内存单元的汇合。

在须要分配内存时,程序遍历每一个内存单元,找到第一个闲暇的内存单元应用。

在本文中,为了升高复杂度,只应用了最根本的 闲暇链表(free-list)调配法,free-list 数据结构如下图所示:

为了实现简略,在本文代码中,每个单元只存储一个对象,不思考单元拆分合并等问题

数据结构设计

首先是对象类型的构造:

为了动静拜访“对象”的属性,此处应用属性偏移量来记录属性的地位,而后通过指针的计算取得属性

typedef struct class_descriptor {
    char *name;// 类名称
    int size;// 类大小,即对应 sizeof(struct)
    int num_fields;// 属性数量
    int *field_offsets;// 类中的属性偏移,即所有属性在 struct 中的偏移量
} class_descriptor;

复制代码 

而后是对象的构造,尽管 C 语言中没有继承的概念,然而能够通过独特属性的 struct 来实现:

typedef struct _object {
    class_descriptor *class;// 对象对应的类型
    byte marked;// 标记对象是否可达(reachable)} object;

// 继承
//"继承对象" 需和父对象 object 根本属性保持一致,在根本属性之后,能够定义其余的属性
typedef struct emp {
    class_descriptor *class;// 对象对应的类型
    byte marked;// 标记对象是否可达(reachable)int id;
    dept *dept;
} emp;

复制代码 

free-list 结构设计

struct _node {
    node *next;
    byte used;// 是否应用
    int size;// 单元大小
    object *data;// 单元中的数据
};

复制代码 

有了根本的数据结构,上面就能够进行算法的实现了,以下执行 GC 前堆的状态图:

算法实现

创建对象 & 内存调配

依据后面介绍的 free-list 内存调配策略,在新建对象时只须要搜寻出闲暇内存单元即可:

node *find_idle_node() {for (next_free = head; next_free && next_free->used; next_free = next_free->next) {}

    // 还找不到就触发回收
    if (!next_free) {gc();
    }

    for (next_free = head->next; next_free && next_free->used; next_free = next_free->next) {}

    // 再找不到真的没了……
    if (!next_free) {printf("Allocation Failed!OutOfMemory...n");
        abort();}
}

复制代码 

在找到的闲暇内存单元中调配新对象,并初始化

object *gc_alloc(class_descriptor *class) {if (!next_free || next_free->used) {find_idle_node();
    }

    // 赋值以后 freePoint
    node *_node = next_free;

    // 新调配的对象指针
    // 将新对象调配在 free-list 的节点数据之后,node 单元的空间内除了 sizeof(node),剩下的地址空间都用于存储对象
    object *new_obj = (void *) _node + sizeof(node);
    new_obj->class = class;
    new_obj->marked = FALSE;

    _node->used = TRUE;
    _node->data = new_obj;
    _node->size = class->size;

    for (int i = 0; i < new_obj->class->num_fields; ++i) {//*(data **) 是一个 dereference 操作,拿到 field 的 pointer
        //(void *)o 是强转为 void* pointer,void* 进行加法运算的时候就不会按类型减少地址
        *(object **) ((void *) new_obj + new_obj->class->field_offsets[i]) = NULL;
    }
    next_free = next_free->next;

    return new_obj;
}

复制代码 

GC 代码,当调配新对象并且可用内存有余时调用该办法

void gc() {for (int i = 0; i < _rp; ++i) {mark(_roots[i]);
    }
    sweep();}

复制代码 

标记阶段

标记阶段,要从 GC ROOTS 开始,遍历对象图(graph),对所有可达(reachable)的对象打上标记

for (int i = 0; i < _rp; ++i) {mark(_roots[i]);
}

复制代码 

标记的代码逻辑很简略,就是递归查找对象并标记

void mark(object *obj) {
    // 防止反复标记,因为一个对象可能被援用屡次
    if (!obj || obj->marked) {return;}
    // 给对象打上标记
    obj->marked = TRUE;
    // 递归标记对象的援用
    // 通过对象的 field_offsets 拜访对象的援用对象
    for (int i = 0; i < obj->class->num_fields; ++i) {mark(*((object **) ((void *) obj + obj->class->field_offsets[i])));
    }
}

复制代码 

从下面的代码逻辑能够得出,标记阶段的耗时和堆大小无关,耗时和存活对象的数量成正比

下图是标记完结后,堆的状态:

革除阶段

革除阶段须要遍历全堆(这里是遍历 free-list),革除所有没有标记的对象并回收对应的内存单元

void sweep() {for (node *_cur = head; _cur && _cur; _cur = _cur->next) {if (!_cur->used)continue;
        object *obj = _cur->data;
        if (obj->marked) {obj->marked = FALSE;} else {
            // 回收对象所属的 node
            memset(obj, 0, obj->class->size);

            // 通过地址计算出,对象所在的 node
            node *_node = (node *) ((void *) obj - sizeof(node));
            _node->used = FALSE;
            _node->data = NULL;
            _node->size = 0;

            // 将 next_free 更新为以后回收的 node
            next_free = _node;
        }
    }

}

复制代码 

革除阶段后,堆的状态如下图所示:

毛病

标记阶段的耗时和堆大小无关,耗时和存活对象的数量成正比。如果存活对象很少,那么在标记阶段的开销就有点大了。

所以会有分代回收算法,依据对象特点进行分代,每代执行不同的回收算法。本文中的革除算法就不适用于“年老代”,因为年老代每次存活少,革除算法中要革除大量的对象,更适宜存活多的“老年代“,须要革除的对象足够少

因为本文没有实现 free-list 中闲暇单元的拆分与合并,所以没有波及内存碎片化 (fragmentation) 问题.

如果实现闲暇单元拆分合并的话,可能会导致一直的拆分后,呈现有数的小扩散单元遍布整个堆,造成极大的内存节约,并且减少 free-list 的扫描时间。

残缺代码

github.com/kongwu-/gc_…

参考

  • 《垃圾回收的算法与实现》中村成洋 , 相川光 , 竹内郁雄 (作者) 丁灵 (译者)
  • 《垃圾回收算法手册 主动内存治理的艺术》理查德 · 琼斯 著,王雅光 译

参考:《2020 最新 Java 根底精讲视频教程和学习路线!》
链接:https://juejin.cn/post/694545…

正文完
 0