首页 / 算法 / GC算法-标记清除算法
GC算法-标记清除算法
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了GC算法-标记清除算法,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含1674字,纯文字阅读大概需要3分钟。
内容图文
概述
标记清除算法, 描述起来很简单, 从名字上就能看出, 分为两个阶段:
- 标记阶段: 遍历所有对象, 将活动对象都打上标记
- 清除阶段: 遍历堆, 将没有标记的对象释放掉.
介绍完毕, 本文结束. 开玩笑, 确实看上去很简单啦. 那就具体思考一下实现吧.
实现
介绍写的很清楚了, 实现也是两个阶段呗, 先打tag, 后清除.
标记
寻找所有的活动对象, 要从一个起点开始, 根集合(包括栈、常量池等等), 然后一层一层找下去. 简单来说就像这样:
add_mark(obj){
// 防止重复标记
if(obj.mark == true) return;
obj.mark = true
// 遍历所有子对象
for(o in objs){
add_mark(o)
}
}
将根基合的所有对象都调用一遍, 标记完成.
清除
标记时遍历的是活动对象, 清除阶段呢? 遍历堆. 将堆上所有非活动对象清除. 就比如:
当然, 其中的free
函数也不是简单的将地址回收, 而是将其记录到一个链表中, 以方便下次申请内存. 实现大概如下:
free(p){
// 这里有一个全局变量, 保存链表头: FREE_HEAD
// 若当前对象和上一次回收的对象是连续内存, 直接合并
if(FREE_HEAD + FREE_HEAD.size == p){
FREE_HEAD.size += p.size
}else{
p.next = FREE_HEAD
FREE_HEAD = p
}
}
这样, 申请内存时遍历FREE_HEAD, 找到大小合适的分块. 若没有找到, 就动态扩容咯. 这里其实还有一个优化的小方向, 开始的时候忘记了. 为了提高查找内存时速度, 可以将空闲链表按照大小进行区分, 这样, 需要多大的内存, 直接到对应的链表中找就行了.
虽然实现写的很粗糙, 但大致意思有了.
问题
1.内存的碎片化
从上面可以看到, 只对内存进行了清除, 但是没有整理. 而内存的申请有事动态的, 就会导致出现很多离散的小片空闲内存. 极端情况甚至可能内存中还有200mb的空闲内存, 但是申请个10kb的空间却找不到.
2.暂停时间长
其暂停时间与堆的大小成正比, 堆越大, 遍历清除耗费的时间就越久.
为了解决标记清除算法的问题, 衍生出了位图标记法
, BiBOP法
,延迟清除算法
等等个人感觉很鸡肋(好吧, 或许是我未得其精髓).
为了解决标记清除的问题, 有衍生出了 标记复制
, 标记整理
算法, 之后再议.
内容总结
以上是互联网集市为您收集整理的GC算法-标记清除算法全部内容,希望文章能够帮你解决GC算法-标记清除算法所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。