技术编程|GC垃圾回收算法 |

【技术编程|GC垃圾回收算法】
GC定义
「GC」是Garbage Collection的缩写，即回收垃圾，那么「垃圾」指的是什么呢？
当然这里指的不是现实世界的垃圾，在程序世界中垃圾定义为
?
程序不用的内存空间视为垃圾
?
「GC」需要做的是?找到内存里面的垃圾回收垃圾，让内存空间再利用?指针
在GC 算法中，指针是不可或缺的。我们用星号（*）访问指针所引用的内存空间。例如：我们把指针「ptr」指向的对象表示为 *「ptr」。

本文插图

对象，头，域对象和指针

本文插图

对象和指针mutator
mutator 是Edsger Dijkstra琢磨出来的词，有“改变某物”的意思。说到要改变什么，那就是GC 对象间的引用关系。
mutator 实际进行的操作有以下2 种。
生成对象
更新指针堆

本文插图

堆活动对象与非活动对象

本文插图

活动对象与非活动对象最大暂停时间
因执行「GC」而暂停执行mutator 的最长时间。如下图，最大暂停时间是A～C 的最大值，也就是B 。

本文插图

GC执行图
如上图：假设GC对象的对大小为HEAP_SIZE 。在大小为HEAP_SIZE的堆进行内存管理，要花费的时长为（＋＋）。因此，这种情况下GC 的吞吐量为HEAP_SIZE /（A ＋ B ＋ C）。 GC性能评价标准
吞吐量
最大暂停时间（需要缩短最大暂停时间）
堆使用效率（可用的堆越大， GC 运行越快）
访问的局部性什么是访问的局部性
另一方面，具有「引用关系的对象之间通常很可能存在连续访问」的情况。这在多数程序中都很常见，称为“访问的局部性” 。考虑到访问的局部性，把具有引用关系的对象安排在堆中较近的位置，就能提高在缓存中读取到想利用的数据的概率，令mutator高速运行。垃圾回收算法GC标记-清除算法
GC 标记- 清除算法由标记阶段和清除阶段构成。标记阶段是把所有活动对象都做上标记的阶段。清除阶段是把那些没有标记的对象，也就是非活动对象回收的阶段。通过这两个阶段，就可以令不能利用的内存空间重新得到利用。标记阶段

本文插图

执行GC前堆的状态

本文插图

标记阶段结束后堆的状态
?
搜索对象进行标记是采用的算法：深度优先搜索，，深度优先搜索比广度优先搜索更能压低内存使用量。因此我们在标记阶段经常用到深度优先搜索。
?

本文插图

深度优先搜索
深度优先搜索是纵向搜索，如上图的搜索顺序。清除阶段

本文插图

清除阶段结束后堆的状态分配
将回收的垃圾进行再利用，需要分配。在清除阶段，我们把垃圾对象连接到空闲的链表，搜索空闲链表并寻找大小合适的分块，这项操作就叫作分配。合并
根据分配策略的不同可能会产生大量的小分块。但如果它们是连续的，我们就能把所有的小分块连在一起形成一个大分块。这种“连接连续分块”的操作就叫作合并（coalescing），合并是在清除阶段进行的。位图标记
只收集各个对象的标志位并表格化，不跟对象一起管理。在标记的时候，不在对象的头里置位，而是在这个表格中的特定场所置位。像这样集合了用于标记的位的表格称为“位图表格”（bitmap table），利用这个表格进行标记的行为称为“位图标记” 。位图表格的实现方法有多种，例如散列表和树形结构和整数型数组等。

本文插图

位图标记延迟清除法
清除操作所花费的时间是与堆大小成正比的，如果处理的堆越大，清除算法所花费的时间就越长。
延迟清除法，在标记操作结束后，不一定会进行清除操作，会缩减mutator的暂停时间。标记清除算法的优缺点
?
优点：标记清除算法实现简单，与其他的的算法组合也就相对简单；
缺点：标记清楚算法不会移动对象，但容易产生碎片化的空间，造成内存浪费。
?
如图：

本文插图

上图的「根」指的是「GC root」，通过「根可达算法」确认是不是垃圾。这里简单介绍下根可达算法的定义：从GC Root作为起点开始搜索，那么整个连通图中对象都是活的，对于GC Root无法达到的对象便是垃圾对象，随时可被GC回收。
如果我需要3空间的内存，而2空间的内存就存不下。就会被空闲，造成内存浪费。引用计数法
引用计数法中引入了一个计数器。计数器表示的是对象的引用次数。如果对象引用次数为0 ，那么这个对象可以被清除。优缺点
「优点」：可即刻回收垃圾，空间不会被垃圾长久占用。
「缺点」：计数器值的增减处理繁重，计数器也需要占用内存。无法回收循环引用。 GC复制算法
简单来说， GC复制算法就是把空间里的活动对象复制到其他空间。把原空间里的所有对象都回收掉。如图所示：

本文插图

当From空间被占满时， GC将活动的对象全部复制到To空间。当复制完成后，该算法会将From空间和To空间互换， GC结束。。 From 空间和To 空间大小必须一致。这是为了保证能把From 空间中的所有活动对象都收纳到To 空间里。优缺点
优秀的吞吐量，可实现高速分配，不会发生碎片化。
但是复制算法需要把堆进行二等分，只有一半的堆能被使用。造成堆的浪费。还有复制算法在复制某个对象时要递归复制它的对象，这里会带来额外的负担，有栈溢出的可能。 GC标记压缩算法
此算法分为标记阶段和压缩阶段，标记阶段同上面几种算法的标记功能一样，我们来说说压缩阶段，分为3步骤：?设定forwarding 指针更新指针移动对象?
标记压缩实际上就是将活动的对象xi整理到一边，尽量的减少碎片化，来看看实际的效果：

本文插图

image-20200730141439426优缺点
可有效利用堆，但是压缩会有计算成本。
GC主要的回收算法就介绍这么多了，其实际的算法很复杂。有兴趣的可以自行研究。
「参考：」
《垃圾回收的算法与实现》作者: 中村成洋 / 相川光

技术编程|GC垃圾回收算法

推荐阅读

春节放鞭炮的来历

中国人寿保险公司官网?信泰人寿保险公司的网址是多少?

【鱼籽酱】吃一口就让你破产的鱼籽酱，到底好吃不好吃？

承诺美国经济明年会大反弹，特朗普呼吁再给他4年任期

新东方|新东方招聘“双语主播”，月薪有望超过5万，还这类毕业生更吃香

北京地铁土桥站改造八通线4站停运8天

「流浪大师」2年前爆红的“流浪大师”沈巍，自曝身价200万，如今在做什么？

阴阳师翅膀幼女是什么？翅膀幼女

漫科书|魔王学院不适合者：专属魔王的后宫粉丝团，魔族剑圣转生再次相遇

物质汽车先|低配车上6个实用的隐藏功能？可能有些新手还不知道

军人|德赫亚：我希望在曼联结束职业生涯！

小李子八卦事|走中性风穿男装，衣服一看就是男友的，有种“共用衣柜”叫关晓彤

为啥日本化妆品眼霜很少

体坛扒客|不止是为了世界杯！，国足归化又一原因揭晓！76岁中国足球教父发声

青年《星际恐龙》讲述的是亚杰博士不顾法律的规定

如何防止上瘾(如何解除王者荣耀中的2小时限制)

nba|被讽刺刷数据！NBA史上最有争议的一届MVP！

火爆新闻|《刺客信条：王朝》：安禄山与杨贵妃登场，李萼要在花卉盛宴动手

贝壳|斜肩连体裤搭配白色贝壳包，精致时尚，职场范十足

北京日报|北京市发布冰雹黄色预警