许可优化
许可优化
产品
产品
解决方案
解决方案
服务支持
服务支持
关于
关于
软件库
当前位置:服务支持 >  软件文章 >  内存管理和垃圾收集第七篇:内存分配算法

内存管理和垃圾收集第七篇:内存分配算法

阅读数 9
点赞 0
article_banner

本节讨论方向

  • BoehmGC内存分配器的底层原理
  • IncreamentalGC的工作原理

版权声明

本文为"优梦创客"原创文章,您可以自由转载,但必须加入完整的版权声明

文章内容不得删减、修改、演绎

因文章视频大小限制,项目中的画面效果无法动态展示,相关内容请见文末参考视频(如有)

贝母内存分配器底层原理详解

各位小伙伴大家好,在上次项目的分享当中,我们学习了 Boehm 垃圾收集器的底层原理

实际上,Boehm不仅是一个垃圾收集器,准确来说它是一个内存管理器。也就是说,除了垃圾收集,Boehm还负责内存的分配

所以,本节我们就来进一步学习‘Boehm 内存分配器’的底层原理

BoehmGC:内存分配的三个特点

Boehm 内存管理器在内存分配上有三个特点:

不分代:不会像 SGen 一样对内存进行分代划分

不合并:不会像SGen 一样通过合并内存对象来防止内存碎片

非精准:包含两层含义:

  1. 已分配但无任何引用的内存,不一定能被回收
  2. 未分配使用的内存,当需要分配时也不一定能成功分配

为什么会出现上述三种情况呢?

前面我们提到过,最主要的原因是为了性能优化 —— 以较低的 CPU 代价或带宽代价实现内存的垃圾收集

BoehmGC:内存分配的基本结构

上图右测红框中的图,是 Boehm 的内存管理模型

Boehm内存管理器的内存分配可从三个层次理解

按内存类型分类

BoehmGC内存分配的第一个层次,将内存分为三类:

  • 自由指针类型(PtrFree)
  • 普通数据类型(Normal)
  • 不可收集类型(Uncollectable)

哪些类型是‘不可收集类型’?

  • 例如 ,Boehm 内存管理器自身进行内存分配、垃圾收集所占用的内存(即系统为内存管理占用的内存),就属于不可回收的 “不可收集类型”

按内存块大小管理


这是BoehmGC内存分配的第二层次

在第一层次的‘内存类型分类’基础上,针对某一种特定类型的内存块,BoehmGC内存管理器会将其按大小分别管理

具体来说,Boehm 会为每种类型的内存建立多个链表,这些链表具有以下特征:

  • 链表按‘内存块’的字节数划分,如 16 字节链表、32 字节链表、64 字节链表
  • 其中,每个链表下的所有‘内存块’(Block)大小统一

如上图右侧

  • 白色方框圈出的Size(16)、黄色方框圈出的Size(32)、绿方框圈出的Size(64),分别是按照16字节,32字节,64字节在Kind(a)这个类型下建立的链表头
  • 在此基础上,Size(16)下的Block0,Block1,Block2,这几个节点,所代表的内存块的大小是同一的,即16字节
  • 同理,Size(32)下的节点Block0,Block1,Size(64)下的节点(如果有),都应遵循此逻辑

链表关联内存块


这是BoehmGC内存分配的第三个层次

在上述‘第二层次’中,我们说到,每一种‘不同字节大小的链表头指针’下面,都通过数据结构中的 “链表”形式,来关联到第一个内存块

  • 注:‘不同字节大小的链表头指针’这个概念,在上图中,具体指的是Size(16),Size(32),Size(64)这几个链表头

然后,第一个内存块通过指针指向第二个,再之后,第二个指向第三个,以此类推

这里涉及链表的基础知识,和之前讲的 “树” 一样,都是数据结构的基础内容,大家如果还不清楚的话,可以通过我们的 “小白的游戏梦” 项目进行系统学习,详情参考文末关于《Unity全栈开发大师》的链接

说到这里,那么,大家也可以猜测一下,‘不同字节大小的链表头指针’又是如何进行存储的呢?

大家可以进群讨论~

那么,在掌握了 Boehm 内存管理器的基本结构后,下面我们将通过几个问题,来看一看, Boehm内存管理器是如何处理内存分配的

Boehm:内存分配的核心问题解析

思考1:如何分配一个8字节内存?


这里有一个前置知识点需要补充一下:

  • 其实在上图中我们也可以看到,贝母内存管理器呢,它管理内存最小的单位是16个字节
  • 然后,在16字节的基础上,贝母再按倍去递增,比如,16乘以2得32,再乘以2得64……以此类推

那么,在这种情况下

  • 如果我只想分配一个8字节,4字节,甚至只有1个字节的内存,Boehm 会会如何去做呢?

基于上述规定,我们可以合理推测

  • 哪怕只需要分配小于 16 字节的内存(比如只分配8字节内存),贝母内存管理器也会从 16 字节链表下的内存块中找到空闲块,然后分配给需求对象
  • 当然,Boehm也确实是这样做的
  • 此外,需注意的是,如果 16 字节链表下的所有块均被占用,贝母内存管理器就会新建一个 16 字节的块,然后将被新建的内存块分配给需求对象

显然,这样的设定方式,其实是存在一定问题的

  • 比如,上述情况中,无论是‘空闲块’还是‘新建块’,都是16字节的块
  • 一个16字节的块,对于8个字节的对象来说,是绝对会存在8个字节被浪费掉的情况的

既然问题如此明显,又为什么还要这样设计呢?

  • 其根本原因,在于对系统性能的考虑
  • 如果再细分出 8 字节、4 字节甚至 1 字节的链表,将导致内存分配过于琐碎,容易产生内存碎片,反而不利于内存管理

思考2:要分配16字节,但如果没有空闲Block,怎么办?


关于这个问题,我们可以从下面几个方面来聊一聊

问题描述:

  • 若需分配 16 字节内存,但 16 字节链表的所有块均已被占用
  • 也就是说,Size(16)下的所有现存Block,都已经是‘正在使用’状态
  • 这种情况下,Boehm 会如何处理?

答案公布:

  • 事实上,为了避免频繁分配小内存块导致碎片,在这种情况下,Boehm 不会直接新建 16 字节的块,而是会查找 32 字节的内存链表
  • 若32 字节的内存链表中存在空闲块,就会将这个 32 字节的块 “一分为二”
  • 其中 16 字节分配给用户使用,并挂到 16 字节链表的末尾
  • 剩余 16 字节作为空闲块保留,若后续再需 16 字节内存,可直接使用该空闲块,无需新建

这种方式有两个好处

  1. 避免频繁分配小内存块,减少内存碎片产生
  2. 两个拆分后的 16 字节块在物理地址上连续,释放任意一个时,Boehm 会检查相邻块是否空闲,若均为空闲,则合并为 32 字节块。这样,空出来的内存块就不是16个字节,而是32个字节,从而,就可以支持更大内存的分配,进一步避免内存碎片

拓展解读

  • 在前面的思考1里,我们讨论的是‘小于’16字节的情况
  • 这里,我们则进一步考虑了另一个‘极限’情况——当需要分配的内存‘等于’16字节的情况,
  • 这种‘极限’情况下,Boehm的处理方式是否也相同?
  • 正如我们所见,显然是不同的
  • 这个问题其实需要从两个方面进行考虑
  1. 当Size(16)链表下,存在空闲内存块时,那么,像‘思考1’一样,Boehm会直接将空闲块进行分配
  2. 而当Size(16)链表下,不存在空闲内存块,这就和‘思考1’中所描述的情况出现了差别,显然,Boehm对这种情况进行了单独的优化处理

这是Boehm垃圾收集器在进行内存分配和垃圾回收时候的一些技巧,也是面试时一个比较硬核的一个考点,希望大家能够掌握

思考3:当两个物理连接的Block都被回收,如何优化以防止内存碎片?


答案在问题 2 中已提及,这里不再赘述

简而言之,Boehm 会检查物理上相邻的内存块,若均处于空闲状态,会将它们合并为一个更大的内存块,便于后续大内存分配,减少碎片

上面,我们知道了关于Boehm内存分配的一些知识

内存有分配,就必然要有释放

那么,Boehm是如何进行内存释放的呢?

我们可以这么说:Boehm的内存释放,有一点‘不靠谱’

那具体怎么个‘不靠谱’法呢?

接下来,就让我们一起来看一看

BochmGC:内存释放


前面提到, Boehm 内存管理器在释放内存时是 “非精准” 的

下面,我们就结合几张图片,来一起理解一下Boehm 的‘非精准’内存释放

上图中有一个对象A

对象A中包含一个值为的字段

由于 Boehm 不是语言层面的编译器,因此,它无法区分是对象引用还是普通数值

那么,对于这种情况,Bochm垃圾收集器是怎么样去进行垃圾收集的呢?

答案是,靠猜

也即是,它会将所有内存数值,都视为潜在指针

其大概的处理逻辑为:探测是否为Boehm管理的有效内存地址,若是,则认为指向一个对象,该地址内存不可回收


  • 如上图,ObjectA中的字段0x011指向的ObjectB是一个有效内存地址,这种情况,我们会认为0x011指向了一个对象

而这样的方式,必然会导致一定的“误判”

  1. ‘误判’的第一种情况
  • 比如说,若A中还包含另一个值为0x012的字段,这个值实际是普通数值,但恰好又是 Boehm 管理的一个有效的内存地址
  • 这种情况下,Boehm会误判其为一个对象的引用,从而导致该内存地址无法被回收
  • 这一现象,对应 贝母垃圾收集器的“非精准” 的第一层含义:无引用的内存无法回收(已分配但无任何引用的内存,不一定能被回收)

    2. ‘误判’的第二种情况


  • 若对象A还有一个值为0x013的字段
  • 这个值同样是普通数值,并且,和0x012一样,该值也恰好命中Boehm 管理的一个有效的内存地址
  • 那么,Boehm 会将0x013指向的地址标记为 “正在使用”,
  • 这种情况下,分配内存时,贝母垃圾收集器就会刻意绕开该地址,不去使用这块内存
  • 这样的话,当我们需要进行大内存分配的时候,可能因该地址被误标记而无法使用相邻空闲块,只能向操作系统申请更多内存
  • 如上图,箭头所指的白框内所演示的情况下
  • 相邻的三个内存块明明都可以使用,但由于中间的地址被误标记为‘正在使用’,导致连续的内存块被‘切割’为零碎的几个部分,从而无法进行大内存分配
  • 这一现象,对应贝母垃圾收集器的“非精准”的 第二层含义:需分配的内存无法成功分配(未分配使用的内存,当需要分配时也不一定能成功分配)

以上,就是本节关于BochmGC非精准内存释放的所有内容

这部分内容较难理解,若对内存管理不熟悉,建议结合视频,多回顾几遍

BoehmGC:算法流程


上图中,展示了Boehm 内存管理器的源码流程

这张流程图是通过阅读 Boehm 内存管理器源码整理的

由于篇幅有限,这里无法展开细节,但面试资深开发、主程等岗位,经常会考查相关内容,建议大家参考文末链接提前准备

下面呢,我们再看另外一种Unity的新的内存垃圾收集器——IncreamentalGC

IncreamentalGC:工作原理


IncreamentalGC,翻译过来,就是‘增量垃圾收集器’,或者‘渐增式垃圾收集器’

IncreamentalGC的核心逻辑是 “分片处理垃圾回收工作”,也就是每一帧仅回收一部分内存

这样做的好处是,如果内存中垃圾较多,分片回收可降低 CPU 在垃圾回收时的计算压力

限于时间关系,这里没办法进一步展开讲解渐增式垃圾收集器的底层算法和源码实现

更多学习内容

更多的学习内容,大家可以关注我们的贝母垃圾收集器的底层原理、源码详解,以及最佳实践的一些指引

此外,渐增式垃圾收集器, SGen、引用计数式垃圾回收等的面试高频内容,都可以关注我们的专项学习资源,比如Unity主程进阶、Unity全栈开发,来进行进一步的学习

参考

完整视频请点击本链接观看:https://ymck.top/video/detail/296455

其它相关参考链接:

  • 《Unity全栈开发大师》:https://ymck.top/video/detail/245008

更多技术干货v:alice17173


免责声明:本文系网络转载或改编,未找到原创作者,版权归原作者所有。如涉及版权,请联系删

相关文章
技术文档
QR Code
微信扫一扫,欢迎咨询~
customer

online

联系我们
武汉格发信息技术有限公司
湖北省武汉市经开区科技园西路6号103孵化器
电话:155-2731-8020 座机:027-59821821
邮件:tanzw@gofarlic.com
Copyright © 2023 Gofarsoft Co.,Ltd. 保留所有权利
遇到许可问题?该如何解决!?
评估许可证实际采购量? 
不清楚软件许可证使用数据? 
收到软件厂商律师函!?  
想要少购买点许可证,节省费用? 
收到软件厂商侵权通告!?  
有正版license,但许可证不够用,需要新购? 
联系方式 board-phone 155-2731-8020
close1
预留信息,一起解决您的问题
* 姓名:
* 手机:

* 公司名称:

姓名不为空

姓名不为空

姓名不为空
手机不正确

手机不正确

手机不正确
公司不为空

公司不为空

公司不为空