技术编程|GC垃圾回收算法
GC定义
「GC」是Garbage Collection的缩写 ， 即回收垃圾 ， 那么「垃圾」指的是什么呢？
当然这里指的不是现实世界的垃圾 ， 在程序世界中垃圾定义为
?
程序不用的内存空间视为垃圾
?
「GC」需要做的是?找到内存里面的垃圾回收垃圾 ， 让内存空间再利用?指针
在GC 算法中 ， 指针是不可或缺的 。 我们用星号（*）访问指针所引用的内存空间 。 例如：我们把指针「ptr」 指向的对象表示为 *「ptr」 。
本文插图
对象 ， 头 ， 域对象和指针
本文插图
对象和指针mutator
mutator 是Edsger Dijkstra琢磨出来的词 ， 有“改变某物”的意思 。 说到要改变什么 ， 那就是GC 对象间的引用关系 。
mutator 实际进行的操作有以下2 种 。
生成对象
更新指针堆
【技术编程|GC垃圾回收算法】
本文插图
堆活动对象与非活动对象
本文插图
活动对象与非活动对象最大暂停时间
因执行「GC」 而暂停执行mutator 的最长时间 。 如下图 ， 最大暂停时间是A～C 的最大值 ， 也就是B 。
本文插图
GC执行图
如上图：假设GC对象的对大小为HEAP_SIZE 。 在大小为HEAP_SIZE的堆进行内存管理 ， 要花费的时长为（＋＋） 。 因此 ， 这种情况下GC 的吞吐量为HEAP_SIZE /（A ＋ B ＋ C） 。 GC性能评价标准
吞吐量
最大暂停时间（需要缩短最大暂停时间）
堆使用效率（可用的堆越大 ， GC 运行越快）
访问的局部性什么是访问的局部性
另一方面 ， 具有「引用关系的对象之间通常很可能存在连续访问」的情况 。 这在多数程序中都很常见 ， 称为“访问的局部性” 。 考虑到访问的局部性 ， 把具有引用关系的对象安排在堆中较近的位置 ， 就能提高在缓存中读取到想利用的数据的概率 ， 令mutator高速运行 。 垃圾回收算法GC标记-清除算法
GC 标记- 清除算法由标记阶段和清除阶段构成 。 标记阶段是把所有活动对象都做上标记的阶段 。 清除阶段是把那些没有标记的对象 ， 也就是非活动对象回收的阶段 。 通过这两个阶段 ， 就可以令不能利用的内存空间重新得到利用 。 标记阶段
本文插图
执行GC前堆的状态
本文插图
标记阶段结束后堆的状态
?
搜索对象进行标记是采用的算法：深度优先搜索 ，， 深度优先搜索比广度优先搜索更能压低内存使用量 。 因此我们在标记阶段经常用到深度优先搜索 。
?
本文插图
深度优先搜索
深度优先搜索是纵向搜索 ， 如上图的搜索顺序 。 清除阶段
本文插图
清除阶段结束后堆的状态分配
将回收的垃圾进行再利用 ， 需要分配 。 在清除阶段 ， 我们把垃圾对象连接到空闲的链表 ， 搜索空闲链表并寻找 大小合适的分块 ， 这项操作就叫作分配 。 合并
推荐阅读
- 行业互联网|华为 | 车载以太网物理层及TSN发展现状 与技术趋势
- 技术编程|什么是Plesk虚拟主机控制面板？
- 电池技术|法国发明出世界最快的电极：可将锂电池的密度提高3倍
- 技术编程|人工智能在大视频运维中如何实现CDN硬盘故障预测？
- 电池技术|关于惠州赣锋建设高端聚合物锂电池研发及生产基地建设，赣锋锂业要干大事
- |加速冲刺世界级技术领先地位，大族机器人获1.65亿元A轮融资
- 解码器|苹果 ProRes 视频编解码器获 2020 技术工程艾美奖
- 明星八卦|毛晓彤：出生被扔垃圾堆，成名被索要5000万，父亲：她挣钱太容易
- 数据|徐叶润：另类数据技术是驱动资管科技的核心
- 中关村在线|垃圾打包怕手脏？你可能需要一台智能垃圾桶