“AI 技术+人才”如何成为企业增长新引擎?戳此了解>>> 了解详情
写点什么

图解 Go 内存分配器

  • 2019-03-07
  • 本文字数:4587 字

    阅读完需:约 15 分钟

图解Go内存分配器

内存分配器一直是性能优化的重头戏,其结构复杂、内容抽象,涉及的数据结构繁多,相信很多人都曾被它搞疯了。本文将从内存的基本知识入手,到一般的内存分配器,进而延伸到 Go 内存分配器,对其进行全方位深层次的讲解,希望能让你对进程内存管理有一个全新的认识。

物理内存 VS 虚拟内存

在研究内存分配器之前,让我们先看一下物理内存和虚拟内存的背景知识。剧透一下,内存分配器实际上操作的不是物理内存而是虚拟内存。



物理内存细胞结构简化图


内存细胞作为物理内存结构的最小单元,工作原理如下:


  1. 地址线(三相晶体管)其实是连接数据线与数据电容的三相开关。

  2. 当地址线负载时(红线),数据线开始向电容中写数据,电容处于充电状态,逻辑值变为 1

  3. 当地址线空载时(绿线),数据线不能向电容中写数据,电容处于未充电状态,逻辑值为 0

  4. 当 CPU 从 RAM 中读值时,它首先会给地址线发送一个电流信号从而合上开关,连通数据电路。这时如果电容处于高电位,则电容中的电流会流向数据线,CPU 读数为 1;否则,数据线中没有电流负载,CPU 读数为 0。



CPU 和内存的交互


CPU 实际上通过地址总线、数据总线和控制总线实现对内存的访问。


  • 数据总线:在 CPU 和内存之间传递数据的通道;

  • 控制总线:在 CPU 和内存之间传递各种控制/状态信号的通道;

  • 地址总线: 传送地址信号,以确定所要访问的内存地址。


让我们进一步分析一下地址线按字节寻址:



  1. 在 DRAM 中,每一个字节都有一个唯一的地址。“可寻址字节不一定等于地址线的数量”,

  2. 例如 16 位的 Intel 8088、PAE(物理地址扩展)等,其物理字节大于地址线数量。

  3. 每一条地址线可以传送 1-bit 的数值,可表示寻址字节中的一位。

  4. 图中有 32 位地址线,所以可认为可寻址字节是 32 位的。


[ 00000000000000000000000000000000 ] —低位内存地址。


[ 11111111111111111111111111111111 ] — 高位内存地址。


4. 因为上图物理字节有 32 条地址线,所以其寻址空间大小为 2 的 32 次方,也就是 4GB


可寻址字节的大小其实取决于地址线的数量,例如具有 64 个地址线的 CPU(x86–64 处理器)可以寻址 2 的 64 次方,但是目前大多数 64 位的 CPU 其实只使用了其中的 48 位(AMD)或者 42 位(Intel)。尽管理论上可访问 2 的 64 次方(256TB)大小的地址空间,但是通常操作系统并没有完全支持它们(Linux 的四层页表结构允许处理器访问 128TB 大小的地址空间,Windows 支持 192TB)。


由于实际物理内存的大小是有限制的,所以每个进程都运行在各自的沙盒中,也就是所谓的“虚拟地址空间”,简称虚拟内存。


虚拟内存中的字节地址其实并不是实际的物理地址。操作系统需要记录所有虚拟地址到物理地址的映射转换,也就是我们熟知的页表。


进程中的虚拟地址如下图所示:



虚拟地址空间示意图


所以当 CPU 执行内存中一条指令的时候,它首先需要把 VMA(虚拟内存区域)中的逻辑地址转换为线性地址,转化过程通过 MMU(内存管理单元)实现。



虚拟地址与实际物理地址的映射


由于逻辑地址太大很难被有效地管理,于是引入了页(page)的概念。所有的虚拟内存空间被分成很多相对较小的区域(通常为 4KB),也就是我们所称的页。页是虚拟内存管理中最小的单位,虚拟内存通常不存储任何内容,只是简单的将程序地址空间映射到底层的物理地址。


用户进程只能使用虚拟内存地址。让我们来看一下程序如何申请堆内存空间:



(堆内存申请的汇编实现)



堆内存增长


程序通常使用系统调用brk(sbrk/mmap)来获取更多的内存,内核仅更新堆的 VMA,并没有进行进行实际的申请操作。


系统在内存分配的时候,其实并没有申请相应的物理页帧,只有在真正赋值的时候才会申请物理页帧。这也是 VSZ(进程虚拟内存大小)和 RSS(常驻物理内存大小)的最大区别。

内存分配器

相信通过前面对“虚拟地址空间”以及堆内存申请的学习,相信我们对内存分配器说也就不难理解了。


如果堆中有足够多的内存空间,那么分配器就可以独立完成内存的申请而不需要访问内核。否则,系统将会通过系统调用函数 brk 来扩展堆,通常是增加变量 MMAP_THRESHOLD 的默认值(128KB)。


当然内存分配器的职责不仅仅是更新 brk 地址,更多的还是用于减少碎片以及快速分配内存块。让我们来看一个实例:假设我们的程序通过函数 malloc 来申请一块连续内存块,使用函数 free 来释放申请的内存块,步骤 p1 到 p4 的整个操作顺序如下:



内存碎片演示


到步骤 p4 的时候,尽管剩余的内存块数量大于需要申请的数量,但是因为碎片的关系,我们已经不能获得 6 个连续的内存块了。我们该如何减少内存碎片呢?答案要取决于具体使用的分配算法。


由于 Go 内存分配器同 TCMalloc 分配器非常相似,我们先看一下相对简单的 TCMalloc。

TCMalloc

TCMalloc(Thread Cache Malloc)的核心思想是将内存分解为多层,从而减小内存锁的粒度。TC-Malloc 内存管理分为线程内存以及页堆两部分:

线程内存

为减少内存碎片,每个内存页都被分成了多个固定类大小的空闲列表。这样每一个线程都都有一个不带锁的小对象缓存,从而可以高效的为并行程序分配小对象(<=32KB)。



线程缓存 (每个线程都有一个本地线程缓存)

页堆

TCMalloc 管理的堆其实由一组页构成,而这样一组连续的页又被称为页堆(span)。当我们申请大于 32K 的对象时,TCMalloc 将使用页堆进行分配。



页堆 (span)管理


当没有足够的内存来分配小对象时,将使用页堆内存;而如果页堆内存也不不能满足时,将会向操作系统申请更多的内存。这种基于用户空间内存池的管理模式极大地提高了内存分配和释放的效率。


注: 早期的 go 内存分配器是基于 TCMalloc 开发的,但时至今日,两者已经大不相同了。

Go 内存分配器

Go 运行时调度器其实把 Goroutines (G)绑定到逻辑处理器(P)上执行。同 TCMalloc 一样,Go 内存分配器将内存页分成了 67 个不同类大小的块。


如果你不熟悉 Go 调度器的话,建议先阅读一下文章(Go scheduler: Ms, Ps & Gs)。



Go 中的内存页大小列表


Go 中内存的最小粒度为 8KB,如果页被分成大小为 1KB 的块,那么将会有如下 8 个块。



8 KB 的页被成了 8 个大小为 1KB 的块


Go 通过数据结构 mspan 来管理这些页。

mspan

简单来讲,mspan 是一个双端链表,包含了页起始地址,span 类以及这个类中页的数量。



mspan 示意图

mcache

同 TCMalloc 一样,Go 内存分配器为每一个逻辑处理器§提供了一个本地线程缓存,也就是 mcache。如果 Goroutine 需要内存,可以直接从 mcache 中获取,由于只有一个 Goroutine 运行在逻辑处理器(P)上,所以中间不需要使用任何锁。


mcache 包含了所有类大小的 mspan。



Go 中 P、mcache 以及 mspan 的关系示意图


由于 mcache 是基于 CPU 存在的,从 mcache 获取内存时没有必要使用锁机制。


每一种类大小的 mspan 都有两种类型:


  1. scan — 含有指针的对象。

  2. noscan — 没有指针的对象。


这样分类的好处是在垃圾回收的时候,不需要遍历 noscan 对象(noscan 中根本就没有指针)。


那什么情况下内存分配器会从 mcache 中申请内存呢?


  • <=32K 字节的对象将直接从 mchae 中相应大小的 mspan 申请。*


如果 mcache 没有可用空间的时候会怎么样?


将会从 mcentra 中相应大小的 mspanl 列表中分配一个新的 mspan。

mcentral

mcentral 对象收集了所有给定类大小的 span,每一个 mcentral 都包含了两个 mspan 列表:


  1. empty mspanList — 没有空闲对象或者已经被 mcache 缓存的 mspans 列表。

  2. noempty mspanList — 所有空闲对象的 span 列表。



mcentral 结构示意图


每一个 mcentral 结构体都由 mheap 结构体维护。

mheap

mheap 是一个全局变量,管理着 Go 中所有的虚拟地址空间。



mheap 示意图


如上图所示:mheap 保存了一个 mcentral 的数组,而 mcentral 又保存了所有 span。


central [numSpanClasses]struct {    mcentral mcentral      pad      [sys.CacheLineSize unsafe.Sizeof(mcentral{})%sys.CacheLineSize]byte}
复制代码


因为我们用 mcentral 保存了所有 span,当 mchache 向 mcentral 申请一个 mspan 的时候,我们需要锁住 mcentral 层,但我们还是可以同时请求其他大小的 mspan。


Padding(对齐填充)确保了 mcentrals 按照 CacheLine 的大小对齐,所以每一个 MCentral.lock 都可以获得自己的的 cache line,避免了伪共享问题。


如果 mcentral 为空会发生什么呢?mcentral 会从 mheap 中申请一些页来创建不同大小的 span。


  • free[_MaxMHeapList]mSpanList: 一个 spanList 数组。每一个 spanList 中的 mspan 都包含了 1 ~ 127 个页 (_MaxMHeapList - 1) 。例如,free[3]是一个包含了 3 个页的 mspan 链表,Free 表示列表为空,未分配,对应 busy list。

  • freelarge mSpanList: 一个 mspan 列表。每一个元素的页数大于 127。通过数据结构 mtreap 来管理,对应 busylarge。


大于 32K 的对象被称为大对象,直接从 mheap 中申请。每次申请大对象都需要事先调用一个全局锁,因此每次只能处理一个 P 申请。


  • 小于 16B,使用 mcache 的 Tiny 分配。

  • 大小介于 16B 和 32k,计算 sizeClass 的大小,然后在 mcache 中申请相应大小的内存块。

  • 大于 32k 的大对象, 直接从 mheap 中分配。

  • 如果 mcache 中找不到相应大小的内存块,则转向 mcentral 申请。

  • 如果 mcentral 中也没有相应大小的内存块,则转向 mheap 申请,使用 BestFit 策略找寻最合适的 mspan;如果申请到的 mspan 太大,则根据用户的需求进行切分,剩余的页构成一个新的 mspan,并放回到 mheap 的空闲列表。

  • 如果 mheap 中没有可用的 span,将会直接向操作系统申请新的内存页(至少 1M)


如果要申请更大的内存块(arena),将会转向操作系统申请。一次申请大批量的内存页会减少访问操作系统的次数。


所有在在堆上申请的内存都来自 arena,让我们接下来看一看 arean:

Go 虚拟内存:Arena

让我们通过一个简单的 Go 程序来看一下内存使用情况:


func main() {    for {}}
复制代码



程序进程信息统计


即便是只有三行的小程序也使用了大约 100MB 的虚拟内存,但 RSS(实际物理内存占用大小)


仅为 696KB。让我们先看一下两者的区别:



map 和 smap 统计


这里有一些大小为 2MB、32MB 和 64MB 的内存区域,这些区域其实就是 arena 内存块。


Go 的虚拟内存其实由一系列的 arena 构成,初始堆映射也是一个 arena,如 go 1.11.5


采用了 64MB 的 arena 内存块。



不同系统中 arena 大小


当前 Go 内存分配器是按照程序需要逐步增加内存映射的,初始只预留留了一个 arena 的大小(约 64MB)。而早期的 Go 内存分配器会先保留一大段虚拟内存,在 64 位系统上为 512GB(发散问题:如果申请的内存太大,以至于被 mmap 拒绝了怎么办?)


这些 arena 就是我们所说的堆。Go 中每一个 arena 都按照 8KB 的粒度进行管理。



单个 arena ( 64 MB )


Go 同时还有两个其它块:span 和 bitmap。两者都独立于堆内存空间之外,并且保存了所有 arena 的元数据。他们主要在垃圾回收的时候使用,我们暂且不在这里讨论。

结语

我们刚刚讨论的内存分配策略只是众多内存分配器的冰山一角。但其管理核心本质上是一致的:针对不同大小的对象,在不同的 cache 层中,使用不同的内存结构;将从系统中获得的一块连续内存分割成多层次的 cache,以减少锁的使用以提高内存分配效率;申请不同类大小的内存块来减少内存碎片,同时加速内存释放后的垃圾回收。


最后让我们用 GO 内存分配器的结构示意图作为结束:



内存分配器示意图


英文原文地址https://blog.learngoprogramming.com/a-visual-guide-to-golang-memory-allocator-from-ground-up-e132258453ed


2019-03-07 08:0011495

评论 2 条评论

发布
用户头像
第一张图 挂了,麻烦小编修复一下~~~
2019-03-07 11:01
回复
用户头像
图裂了
2019-03-07 09:07
回复
没有更多了
发现更多内容

不要在nodejs中阻塞event loop

程序那些事

node.js Event 事件循环 程序那些事 nodejs event

大背景 (28天写作 Day25/28)

mtfelix

28天写作 新能源汽车 新能源革命 碳中和

就算知道了答案,真的会改变吗?「幻想短篇 25/28」

道伟

28天写作

史上最清晰的Tarjan算法详解

华为云开发者联盟

算法 静态分析 语法树 Tarjan 数据流

OpenAI将k8s扩展至7500个节点以支持机器学习;Graph Diffusion Network提升交通流量预测精度

京东科技开发者

区块链 开源

python爬虫入门-通过茅台脚本讲些爬虫知识,应用和价值

大佬sam

Python python 爬虫 2月春节不断更

持续交付

lidaobing

持续交付 28天写作

第五周作业

oooh-la

产品经理训练营第0期-第三次作业

孙行者

第0期 产品经理训练营 问题

产品经理训练营作业 02

KingSwim

【并发编程的艺术】详解单例模式的实现方式(Java)

程序员架构进阶

设计模式 Java内存模型 七日更 28天写作 2月春节不断更

高性能缓存 Caffeine 原理及实战

vivo互联网技术

Java Caffeine 本地缓存

【WOW.js】Animate.css的黄金搭档

德育处主任

CSS 动画 js 28天写作 2月春节不断更

第十周 学习总结

简简单单

云原生动态周报 | Google推出VM Manager

华为云原生团队

Docker 开源 云原生 华为云

ModelArts AI Gallery与HiLens Kit联合开发丨行人社交距离风险提示Demo

华为云开发者联盟

华为云 modelarts hilens 行人 社交距离

第三章: 产品解决方案作业

让时间说真话

产品经理 产品经理训练营

创业失败启示录|样茶里的商机

阿萌

28天写作 创业失败启示录 青城 2月春节不断更

安卓开发交流!一线互联网移动架构师筑基必备技能之Java篇,Android岗

欢喜学安卓

android 程序员 面试 移动开发

安卓开发软件有哪些?分析Android未来几年的发展前景,吐血整理

欢喜学安卓

android 程序员 面试 移动开发

时间约束帮助我写作

Justin

方法论 创意 习惯养成 28天写作

开发质量提升系列:标准模板(中)

罗小龙

最佳实践 方法论 28天写作

产品训练营第二章作业(二)

Arnold

传统线程同步通信技术

武哥聊编程

Java 多线程 28天写作

持续进步的不二法宝-PDCA

Ian哥

28天写作

第十周 模块分解作业

简简单单

第三章:产品解决方案作业

让时间说真话

产品经理

话题讨论|过年回家你带电脑吗?

熊斌

话题讨论 28天写作

机器学习·笔记之:Matrices and Vectors

Nydia

第三章:产品解决方案作业

让时间说真话

产品经理

Python 中 sorted 如何自定义比较逻辑

zikcheng

Python sorted cmp

图解Go内存分配器_编程语言_Ankur Anand_InfoQ精选文章