标记-清除算法的实现流程:标记、清除与空闲链表

雨芳君_7815

雨芳君_7815

2026-08-20

304人浏览

原创

标记-清除算法分三步:标记存活对象、清除未标记垃圾、组织空闲链表;不移动对象导致内存碎片,标记时间取决于存活对象数,清除时间取决于堆总大小,空闲链表分配常用first-fit策略。

标记-清除算法的实现流程:标记、清除与空闲链表

标记-清除算法的核心流程就三步:先标记所有存活对象,再清除未标记的垃圾,最后把回收的空间组织成空闲链表供后续分配。整个过程不移动对象,实现直接,但会带来碎片问题。

标记阶段:从根出发递归标记存活对象

标记从 GC Roots(如栈帧中的局部变量、静态字段、寄存器等)开始,逐层访问引用的对象,并设置其 mark 位为 true。使用深度优先搜索(DFS)更节省栈空间,且能自然处理循环引用——遇到已标记对象直接跳过,避免重复递归。

  • 伪代码中 mark(obj) 先判空再递归子对象,确保每个对象最多标记一次
  • mark 位必须存在对象头中,通常用一个比特位实现,开销小
  • 标记时间与活动对象数量成正比,和堆总大小无关

清除阶段:遍历堆,回收未标记内存块

清除阶段线性扫描整个堆内存,对每个对象检查 mark 位:若为 false,说明不可达,将其加入空闲链表;若为 true,则清除 mark 位(为下次 GC 复位),并保留该对象。

  • 清除时间与堆总大小成正比,哪怕只有少量垃圾也要扫完整个堆
  • 回收时需知道每个对象的 size 字段(也存于对象头),才能正确计算下一个对象地址
  • 相邻的未标记块会在清除过程中自动合并,减少碎片

空闲链表:管理回收内存,支持快速再分配

清除后,所有回收块按单链表形式串在一起,形成 free_list。当程序申请新内存时,分配器从中查找合适大小的块。

  • 常用策略是 first-fit:找到第一个 ≥ 请求大小的块就返回,兼顾速度与利用率
  • best-fit 虽更省空间,但需遍历全链表,性能差;worst-fit 容易产生大量小碎片,一般不用
  • 若找到的块比请求大,就分割:前段分配,后段作为新空闲块插回链表
  • 实际系统常采用多级空闲链表(如按 16B/32B/64B… 分桶),大幅加速小对象分配

不复杂但容易忽略:标记-清除本身不做对象移动,所以无法缓解内存碎片;而空闲链表的查找效率直接受碎片程度影响——块越碎,分配越慢。

PHP速学视频免费教程(入门到精通)
PHP速学视频免费教程(入门到精通)

PHP怎么学习?PHP怎么入门?PHP在哪学?PHP怎么学才快?不用担心,这里为大家提供了PHP速学教程(入门到精通),有需要的小伙伴保存下载就能学习啦!

下载

相关标签:

本站声明:本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系admin@php.cn

相关专题

更多
页面置换算法
页面置换算法

页面置换算法是操作系统中用来决定在内存中哪些页面应该被换出以便为新的页面提供空间的算法。本专题为大家提供页面置换算法的相关文章,大家可以免费体验。

2023.08.14

7316

4

GoFrame框架Web开发与路由中间件
GoFrame框架Web开发与路由中间件

本专题聚焦GoFrame框架的Web开发,拆解路由注册与匹配规则、请求参数获取、参数校验与中间件执行顺序,说明统一响应、JWT鉴权、文件上传与接口文档生成的落地方式,并补充优雅重启与测试实践。

2026.11.17

0

15

GoFrame框架安装与gf命令行工具
GoFrame框架安装与gf命令行工具

本专题围绕GoFrame框架的安装与工具链配置展开,讲清Go版本要求、gf命令行的安装方式、代理镜像与依赖准备,说明项目初始化、热编译、交叉编译打包的做法,并整理安装阶段的常见报错与验证步骤。

2026.11.17

20

15

GoFrame框架零基础入门
GoFrame框架零基础入门

本专题整理GoFrame框架的入门知识,从模块化设计理念、环境准备到跑通第一个Web服务,讲清目录分层、配置加载、日志与中间件的用法,并对比Gin、Go-Zero的差异,帮助Go开发者建立整体认知。

2026.11.17

0

15

SQLAlchemy 一对多关系怎么建立
SQLAlchemy 一对多关系怎么建立

SQLAlchemy 一对多关系怎么建立?本专题整理父子表外键、relationship 双向映射、关联查询、级联删除和加载优化等相关文章,帮助你理解并实现常见的 ORM 关系建模。

2026.11.17

0

10

SQLAlchemy 如何增删改查
SQLAlchemy 如何增删改查

SQLAlchemy 如何增删改查?本专题整理 ORM 新增记录、条件查询、更新和删除、Session 事务提交与批量处理等实用文章,帮助你掌握 Python 数据库操作流程。

2026.11.17

0

11

SQLAlchemy ORM 模型怎么写
SQLAlchemy ORM 模型怎么写

SQLAlchemy ORM 模型怎么写?本专题整理模型类定义、Mapped 字段映射、主键与约束、表结构创建和常见报错的相关文章,帮助你从基础配置到实际建模逐步掌握 SQLAlchemy。

2026.11.17

0

16

Go-Zero API开发使用教程
Go-Zero API开发使用教程

本专题聚焦Go-Zero的API开发,拆解.api描述文件的语法结构、路由与分组定义、参数绑定与校验规则,说明统一响应体、JWT鉴权、跨域与接口文档生成的落地方式,并给出网关聚合与接口测试的实践建议。

2026.11.12

180

15

Go-Zero安装与goctl环境配置教程
Go-Zero安装与goctl环境配置教程

本专题围绕Go-Zero的安装与工具链配置展开,讲清Go版本要求、goctl安装方式、代理镜像、protoc依赖与环境变量设置,说明多版本共存、升级回退与CI流水线安装的做法,并整理安装阶段的常见报错与验证步骤。

2026.11.12

120

15

热门下载

更多
网站特效
/
网站源码
/
网站素材
/
前端模板

精品课程

更多
热门推荐
/
最新课程
phpStudy极速入门视频教程
phpStudy极速入门视频教程

共6课时 | 54.7万人学习

独孤九贱(4)_PHP视频教程
独孤九贱(4)_PHP视频教程

共89课时 | 134.3万人学习