看了一大堆的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...