之前的几篇文章里面，我们相应介绍了计算机内部的进程，磁盘，cpu，网络等相关知识点，今天主要来一起探讨下关于计算机的内存分配问题。

有限的物理内存 计算机在运行的时候，其所拥有的内存空间其实是有限的。在早期的Dos操作系统中，通常就是4mb的内存，那时候的应用软件还不怎么流行，基本4mb的内存空间就足够程序运作了。不过到了后期阶段，随着各种硬件设备的不断完善，往往可能会存在内存空间小于程序的大小。（例如：内存空间4mb，程序大小16mb） 解决思路 设计一个虚拟存储器，将需要用到指定程序加载到内存中进行计算，其他情况下程序存储在硬盘中。如果需要切换执行其他程序，就将原先内存数据清空，分配给新的策划个程序应用，这部分的工作主要由操作系统负责。

地址空间是什么

表示计算机内部的内存占用大小，主要分为了两类型：物理地址空间，逻辑地址空间

物理地址空间

和硬件直接对应，例如说内存条对应的地址，磁盘对应的存储地址。

逻辑地址空间

运行程序所看到的内存范围。

cpu在进行计算的时候其实是无法直接去识别程序内部的逻辑地址空间，这里就需要借助一些“转换器“的帮助来处理，而这个”转换器“就是cpu内部的MMU计算模块。

在CPU的内部有一个专门负责将物理地址和逻辑地址做映射转换的模块，叫做MMU。

操作系统和MMU是这样配合的：

操作系统在初始化或分配、释放内存时会执行一些指令在物理内存中填写页表，然后用指令设置MMU，告诉MMU页表在物理内存中的什么位置。

设置好之后，CPU每次执行访问内存的指令都会自动引发MMU做查表和地址转换操作，地址转换操作由硬件自动完成，不需要用指令控制MMU去做。

我们在程序中使用的变量和函数都有各自的地址，在程序被编译后，这些地址就成了指令中的地址，指令中的地址就成了CPU执行单元发出的内存地址，所以在启用MMU的情况下， 程序中使用的地址均是虚拟内存地址，都会引发MMU进行查表和地址转换操作。（注意理解这句话），流程如下所示：

如果没有开启MMU功能，那么CPU执行单元发出的内存地址会直接传输到处理器芯片上边。

物理地址和逻辑地址映射转换的细节点

大多数的MMU转换器中对于逻辑地址的识别是以页作为内存单位做划分的，而物理地址大多数是页帧作为单位进行划分的。所以当逻辑地址的页单位和物理地址的页帧单位进行转换的时候就需要考虑这两种单位的映射处理。

按照自己的一些过往经验总结，操作系统分配内存的主要两大场景分别是：

内存分配是什么 其实内存的分布区域可以看作是这么一张图： 一个个小格子代表了内存块，橙色表示该内存块已经被分配使用，白色代表空闲区域。 假设有一个程序准备要在CPU中执行，那么此时需要由操作系统分配指定的空间给到它。执行过程如下图所示：

操作系统内部提供了以下几种基本的内存分配策略，在不同的场景下可以适当做分配调整。（这里我介绍的分配是在连续内存分配的场景下，非连续内存分配下文会有详细讲解）

首次适配算法

从内存块的首部地址往尾部地址查找，第一项匹配满足的内存块即作为分配使用。 如下图，白色代表空闲内存区域。按照首次适配算法，140kb的程序空间在第一个内存块就能匹配到位。

优点： 简单。 缺点： 分配之后也容易产生内存碎片出现，不确定性较高。

最佳分配算法 从内存块的首部地址往尾部地址查找，查找分配之后产生的内存碎片最小的空间块。 特点： 这种算法需要将空闲块按照大小顺序先进行排序，从而提升分配的计算速率。 分配过程中需要对散落的内存碎片进行合并。 优点： 可以避免大空闲块被分割。 最小化外部空闲碎片的尺寸。 缺点： 依旧容易产生内存碎片。 容易产生很多没什么用处的细小碎片内存。

最差匹配算法 使用空间最大的空闲块进行分配，一开始就拆大块。 优点： 分配速率快。 缺点： 对于需要占用大块内存空间的请求不利。 也是会产生有内存碎片。

从上边的几类内存分配算法来看，会发现它们都存在一个共同的特点，那就是内存碎片问题。接下来我们一同来分析下内存碎片问题。

上边我们介绍的内存分配是基于连续内存分配的场景下使用策略，这种分配策由于是基于连续物理空间进行划分，容易产生出大小不一的内存碎片。这里可以将内存碎片再做深入一层的划分：

内碎片 在分配单元中的未使用内存空间，例如下图中的白色空闲区域。 外碎片 分配单元之间的未使用内存空间，例如下方的空闲块所指向区域。 其实在上边提及的集中内存分配的过程中都会出现一个共同的情况，那就是内存碎片化的问题，为了降低分配空间造成的内存碎片影响便陆续有人发明了一些减少内存碎片功能的设计。

压缩空间减少碎片化 这是一种常见的思路，主要思路就是通过将内存块中的空闲区域进行合并，从而降低小块内存碎片的数目。（比较好理解，这里就不画图了）

交换式内存压缩 前边我们提到过cpu在进行计算的时候需要将程序从磁盘中加载到内存中进行计算。假设说当前内存只有4mb的空间，目前已经运行了4mb的程序，此时如果有个1mb的程序也希望加入进行运作，那么此时可以尝试使用交换式内存的策略。 如下图所示，此时内存中已经运行满了程序A，程序B，程序C，新的程序D也希望参与到计算当中，但是此时内存空间已经出现不足

为了解决这一问题，操作系统内部提供了一种机制，当程序A，B，C任意程序的运行状态正好处于进程等待状态（此时不需要利用CPU，一般是处于等待IO响应的情况）。这时候可以将内存中的程序数据拷贝到磁盘当中运行，从而腾出一部分空闲区域给程序D使用。 上边的交换式和压缩式策略都有一个共同点就是将可移动的内存块进行拷贝从而腾出更多的内存空间。 内存拷贝的过程中涉及到的对象拷贝时机，对象拷贝的开销都是非常复杂的逻辑。那么是否还有更加高效的内存分配策略呢？

上边我们讲解的最佳分配算法，最差匹配算法，首次适配算法都是基于连续内存分配的条件下进行分析的，那么如果考虑非连续内存的分配，是否能够较好地利用起内存碎片这些空闲小区域的空间呢？ 前边我们介绍了连续内存分配的几种算法，会发现都存在相同的问题：

分配给程序的物理内存是一个连续的空间 内存的利用率较低 有存在内存碎片化的问题 非连续内存分配

假设说OS可以将连续的逻辑地址映射到不同的物理地址上，那么就能实现非连续内存分配的模型了。实际上现有的x86操作系统就是这么设计的。这里需要介绍两个在os中非常重要的概念，段（Segement）和页（Page）。

非连续内存分配中，逻辑地址空间和物理地址空间的映射细节如下图所示： 之前我们介绍了MMU是专门用于做逻辑地址空间和物理地址空间的映射转换的，这里我会更加深入地分析下内部的一些机理。

在基于段访问机制的设计中，逻辑地址主要划分了两个部分，段号和地址偏移量，当程序需要访问内存地址的时候，CPU会将逻辑地址中的段号提取出来，然后到段表中去搜索匹配，查找到对应的Segment Item，以及对应的物理地址区间段的边界值。接下来操作系统会先进行该内存区域的边界值安全监测（有些内存区域是不允许用户态程序随意访问的），最终定位到最终的物理地址。 但是这种基于段机制的内存访问存在一个弊端，那就是段的大小不是固定一致的。这种情况对于物理硬件的开发造成了一定的难度。例如下图，不同的内存块存储区域虽然都是使用了一个段空间，但是每个段空间的大小区域不同。

页访问机制和段访问机制的最大不同就在于每个页单位的大小都是固定的，这样有助于硬件层面的实现。 在文章的前边介绍MMU的时候我有提到过页和页帧两个概念，它们分别代表了逻辑地址和物理地址的基本单位，而且两个单位之间的大小是1：1的关系。 逻辑地址空间内部被划分为了大小相同的多个页。 页的寻址方式 页的寻址方式其实本质上和段的寻址方式差别不大，如下图所示： 页表的建立时机 这里我们会发现页表存储了Page No和Segment No（页号和页帧号的映射关系），它们之间的映射对照其实是在操作系统刚启动的时候就建立好存储的了。

一级页表空间的大小 如今常用的操作系统是64位的空间，那么也就意味着内部该处理器能够处理的最大位数为2 ^ 64， 64位系统的最大寻址空间为2的64次方=4294967296(bit)的32次方（好大的一个数字）。假设一个页的大小为1024字节，那么一个页表的体积大小就是2^64/1024 , 如此之庞大的一个页表需要存储到CPU内部是不太可能的。

那么将页表存储到内存可以吗？

从实现上来说是可以的，但是我们从设计的角度分析下，本身内存寻址就是要往内存中查找，现在的设计需要先从内存中访问页表，再去访问实际物理地址，实际上走了两次内存查找，这样对于性能的消耗有些大。为了减少这种两次内存访问的开销，于是后边又有了新的技术。例如：

加入一些Cache机制。 通过间接索引的方式将大的页表拆解为多级页表。

OS在启动之后会建立一个叫做TLB（Translation Look-aside Buffer）的缓冲区域,内部会将最常访问的Page No给存储进来。从而提高我们的内存查询效率。当TLB中没有存在对应的数据时，就只能从页表中去读数据了。TLB实际上是位于CPU的内部，计算速度比从内存提取要快速很多，但是容量有限。

局部性设计的源头

在梳理到TLB的时候，我很想多提一些关于平时写代码时候的局部性原理。由于CPU内部的TLB实际上空间有限，所以如果想要高效利用TLB减少TLB MISS的情况发生，我们需要在编程的时候多注意一些程序访问局部性的设计机理。例如MySQL的数据读取，一般都是以页为单位从磁盘中读取到内存内进行计算。

当出现了TLB MISS的情况时，数据从页表加载到TLB中的这个过程在X86操作系统中是由硬件来实现的，其他的一些操作系统可能是由程序实现，所以这种机制没有绝对的实现方式。

ps：有没有感觉操作系统底层的很多设计思想在实际项目开发中都会有类似的影子，例如本地缓存，分布式缓存，缓存命中率，局部性访问设计。

关于多级页表的理解其实有点类似于我们的树结构，通过对Page No去建立索引，区分对应的存储区间，从而减少我们查询的次数。如下图所示：

使用了多级页表之后，查询的过程就分为了：先定位具体的页表NO所在区间，再去该区间查询详细的页表地址。而如果直接将多级页表全部都存储到内存区域的话，实际上消耗的空间也就更多了，因此通常都是将一级页表存储到内存中，二级，三级页表存储到虚拟内存当中。 假如说一级页表不存在，那么后续的多级页表也就没有必要存储，可以直接释放对应的空间。

反向页表的设计思路

不同厂商对于多级页表在操作系统中的实现机制各有相同，这里我们来看看通过建立反向页表的方式解决页表查询性能的设计。如下图所示： 首先获取到页码，然后进行一次哈希计算定位到具体的segment no（页帧号），通过反向页表查询到指定的详细物理地址。这种设计的好处在于减少了内存空间的开销。（因为通常情况下物理地址空间要远远小于逻辑地址空间的体积） 现有的一些CPU厂商就是采用这类思路来进行设计实现的，当然在硬件成本方面这类设计的难度也是比较高的。