前言
前一篇，我谈到了C++堆内存管理机制，其实就是如下图所示，在已经知道如何实现我们自己的allocator时，其实我们还没有涉及到堆内存管理的底层，所以本篇开始会从C的角度去分析堆内存管理的细节。
image
首先,衡量堆内存分配/释放的内存量的最小单位是字节(bytes),通常习惯将最小单位的内存空间称为“块(block)”，也有使用“字(word)”来衡量堆内的块空间大小，而字主要是衡量CPU通过寄存器单次吞吐最大数据量的度量单位，不同的位宽的CPU衡量一个字的标准是不一样的。例如32位的CPU一次存取4个字节,64位的CPU一次能存取8个字节，甚至一些远古的8位和16位的CPU，如此类推。
Ok,也就是说 一个字就是CPU的自然尺寸,准确地说其寄存器的位宽。 因此，具有IA32架构的CPU的自然字长为32位(4个字节)。 具有x86_64架构的CPU自然字长为64位(8字节)。我举个例子
对于16位宽的CPU
1字=16位(一个字长)
32位=双字长 (就是上面1个字的2倍)
64位=两个双字长 (就是上面一个双子长的2倍)
对于32位宽的CPU
1字=32位(一个字长)
64位=双字长 (就是上面1个字的2倍)
128位=两个双字长 (就是上面一个双子长的2倍)
请注意，过去IA32架构下,约定俗称地认为int(4个字节)通常被人为地认为是CPU的单位字长(逻辑上)，一直沿用到x86_64的平台，也就是说基于32位宽架构的字长与字节的换算方法，仍然在x86_64平台上会被认为是合理的.通俗地说,除非在显式注明具体的字节数表示一个字长,不论IA32平台，还是x86_64平台都会被默认为
1 word=32bits=4bytes
备注:因为好些资料在讲解堆的内部原理为了去除某种特定编程语言的限制，采用字长来描述堆内存块的尺寸，所以我在这里额外补充字长和字节的基本关系，而值得注意的是，网上好些坑资料在讲解字长和字节撇开了具体的CPU类型的基本定量换算就是瞎扯的，重要的事情说三遍:字长是一个动量!动量!动量!。
我们下面是一个堆的示例,malloc分配了4个字的空间，最大闲置的内存块却达到了6个字。
堆内存
堆内存示例
我们多次向堆内存申请内存空间时，可能同时伴随之前申请过的内存需要被释放，那么我们堆内存就容易产生内存碎片，所谓的内存碎片就是已分配的内存块之间随机地分散在堆空间内，而已分配的区块之间的间隙是空闲的内存块。
例如我们第一次malloc(3),获得了三个字的内存空间
接着又分别获取4个字和6个字的内存空间，如下图
而我们这次对之前指针p2指向的堆内存执行free操作,此时之前p2指向的堆内存回被标记为空闲的内存块。
而之后申请3个字的内存空间，mallc或许优先利用之前回收的闲置内存块，例如下面的灰色和棕色的已分配区域之间存在4个字的闲置内存块，而申请分配的内存数量不超过空闲的块数，那么可用的最小内存区域会被优先利用。
上面的例子，引出了一个重要的问题，当我们实现自己版本的malloc时，它需要什么信息来很好地跟踪这些随机分布的已分配的区块位置和闲置的区块位置.
通常来说，我们需要一个数据结构，以便找到需要分配的的块，以及知道那些块是闲置的。
从应用程序的角度来看,对 堆内存接口会产生如下两个事实：
- 会随机发无序的malloc请求或free请求
- free请求必须根据之前mallc请求返回的指针发出。
从堆内存分配的角度来看，分配器的内存分配受到以下客观因素影响
- 无法控制已分配区域的尺寸或数量。这是应用程序执行请求的事情，而分配器只是服务于这些请求。malloc不知道应用程序需要什么只是希望立即响应成用程序的请求。
- 必须对malloc请求立即响应,无法缓存请求或对请求排序。
- 内存块的分配必须从闲置内存块中分配。因为堆空间是一个公共空间，已分配的区块由其他进程或子线程所持有,堆内存管理器应该尊重其他程序申请的(已分配)堆内存块
- 一经分配的内存区域无法移动，已分配区块的数据要么被拷贝,要么被释放。
- 必须满足内存对齐条件，这个前面的文章已经剖析的很清楚。
从上面提到的这些因素，malloc分配器的实现必须遵循严格的规则，并且其实现必须考虑两个性能指标
- 最大的数据吞吐量:这意味着在应用程序给定一系列malloc请求以及free请求后，最大程度地提高数据吞吐量。
- 内存利用的峰值
但上面两个指标在实践中往往相抵触的，因为如果需要实现最大化吞吐量，换句话说,可以非常快地响应所有请求，则无法通过复杂的管理逻辑最大程度地提高内存闲置区块的回收再利用率。衡量内存的利用率的一个侧面指标就是内存碎片的严重程度。而关于这方面有具体的量化指标就不详述。
内存碎片
从堆内存管理角度来说，内存碎片主要有两类
- 给定的内存块，若有效负载(payload)的尺寸小于内存块的尺寸，就会产生内部碎片,对于程序来说，实际用于存放实体数据就是payload的部分，其余部份对于程序不可见的都是内部碎片的来源，有些资料也叫内部碎片称为overhead
- 这是用于维护堆基本数据结构产生的开销。
- 作为内存对齐操作的额外填充位置。
- 内存块的预缓存策略，例如为程序的小尺寸的内存块申请预留更多已分配但尚未使用的内存块。
单次已分配区块的堆结构
我们着重说一下上面的第三点，很多重新实习的第三方malloc的基本思路，就是为申请堆内存的app预留更多的“已分配但当前尚未使用”的内存块，并且这些内存从物理布局上是连续的，这样的内存块有一个更pro的名称聚合堆内存空间(Aggregate Heap Memory)这样做的好处,出于性能开销的考虑,std::vector就是类似这种内存分配策略。
- 应用程序由于有预留的堆内存块可用,减少后续malloc内存的申请次数。
- 由于申请的内存块是一大片连续的,可以一次性释放，从而减少了外部碎片的产生,并且这些回收后的内存块更容易被堆管理器回收再用。
OK,我们又引申一个叫外部碎片的概念，当存在大量聚合内存块,但没有单个足够大的闲置区块空间,导致堆管理无法再利用的，这样的闲置区块就叫外部碎片。
举个例子，比如下面的堆内存空间，如果应用程序需要申请3个字的堆内存，但由于分散在堆内的闲置区块的尺寸无法达到申请的数量，因此堆会返回一个NULL指针告知应用程序，内存分配失败.
ss8.png
Ok,需要注意的是外部碎片是一个相对的概念，判断一个闲置区块能否再利用，是以malloc请求的内存数量而定的，读者到这里，应该要有一个清晰的概念，设计一个高效合理的底层内存分配器，至少要满足如下需求。
- 最大限度地减少外部碎片的产生
- 最大限度地减少内部碎片的产生
- 立即响应内存分配/释放请求
小结
我们梳理了堆内存管理有关的概念，因为当您尝试设计自己的堆内存分配器时，这些概念是必须清楚的。对于那些无聊读者的私信“你重做轮子干嘛！”，不值得我反驳，送你一个字“滚~!!”
网友评论