前言
主要介绍linux操作系统的虚拟内存以及动态内存分配的概念，从硬件，内核，用户程序3个层面自底而上地概述一下linux内存管理的要点。
虚拟内存
我们平时看到的内存条，在插入主板后被操作系统当做物理内存使用，区别于物理内存，计算机系统抽象出了一个虚拟内存的概念。它是在硬件与操作系统的结合下工作的。实际上它是虚拟出了一段独立的内存空间，与实际的物理内存空间产生映射关系，用户程序以及操作系统程序只需要与这个虚拟的内存空间打交道，在底层硬件的帮助下会自动地将这个虚拟内存空间映射到物理内存。
它主要有以下优点：
- 作为物理磁盘的缓存。这个概念非常重要，整个虚拟内存都是作为物理磁盘的缓存存在的，每一个内存地址都能映射到实际的磁盘存储区域。通过这个方式加速程序IO。
- 每个进程使用独立的虚拟内存，这就提供了隔离性，让进程之间的数据不会互相破坏。同时，每个进程的内存结构都是相同的，方便了内存管理以及操作系统的链接。
虚拟内存工作原理
硬件的虚拟内存管理
地址翻译
要认识虚拟内存的工作原理，首要前提是明白虚拟内存如何与物理内存映射起来的。
虚拟内存被划分成很多4KB或者4MB这种内存块，每一个内存块都与物理内存相同大小的内存块相对应。这个匹配关系linux用内存页表来存储。内存页表由许多页表条目（PTE）组成，每一个页表条目存储了一个物理内存块的第一个字节的物理地址，当然PTE里还存储了一些元信息，例如该地址的访问权限，该虚拟地址是否已经分配等等。内存映射的关键便是通过虚拟地址，先找到内存页表相应的PTE，然后取出该PTE储存的物理内存块地址，再根据虚拟内存找到该4KB或者4MB块的某个内存偏移，再读出相应的字节。
以32位地址空间，4KB内存页为例。将32位虚拟地址分成两部分，第一部分20bit组成，用来索引内存页表的PTE，因此内存页表共有1024*1024个PTE。找到PTE后，取出20bit的物理地址高位，再与虚拟地址第二部分的12bit偏移量组合起来，形成物理地址。
从上面例子可以看到，无论PTE是否分配，都需要1024*1024个PTE常驻内存，如果每个PTE是4个字节，那么就需要4MB的空间，其中很多空间是浪费的。所以实际操作系统往往采用多级页表的形式。
以二级页表为例，32bit的虚拟地址分成3部分。第一部分10bit作为一级页表的索引，找出二级页表的物理地址。然后再用第二部分10bit作为二级页表的索引，找出PTE，取出20bit的物理地址高位，再与再与虚拟地址第三部分的12bit偏移量组合起来，形成物理地址。从这个例子可以看出，常驻内存的只有一级页表，4KB的内存空间，内存消耗降低了1024倍。
页表层级越多，内存消耗越少，但是容易想到，翻译内存耗时也会增加，因为要读某个内存地址的数据，都要沿着页表层级依次读出相应内存页表的PTE。实际上CPU芯片里有一个TLB（翻译后备缓冲器）的结构，作为PTE的缓存，访问速度非常快，多级页表的性能影响基本可以忽略。
CPU如何读取内存数据
由于内核以及应用程序都是通过虚拟内存地址来访问内存，所以，我们可以从CPU执行一条读内存的指令开始，去分析这个指令的执行过程。
- CPU发送虚拟地址给CPU芯片上的内存管理单元MMU。
- MMU从CPU芯片的TLB（翻译后备缓冲器）里查找是否缓存了PTE。其中多级页表需要查找多次。缓存命中则跳到3。否则跳到5。
- MMU得到PTE，如果该PTE页命中且权限正确，则取出高20bit物理地址，并与虚拟地址低12bit偏移量组合，得到物理地址，返回CPU。如果该PTE没有分配，或权限错误，则产生段错误，触发一个一般保护故障，跳到异常处理程序。若PTE缺页，则跳到缺页异常处理程序。由于内存是磁盘的缓存，该程序会读取磁盘的相应数据，然后在内存中找出牺牲页，如果该页数据已被修改，则写回磁盘，然后用新读取的页替换掉该牺牲页。当异常处理程序返回时，会重新执行该读内存指令，因此跳到1重新执行。再次执行就会是页命中了。
- CPU用得到的物理地址向高速缓存/主存请求数据。
- TLB缓存不命中，需要向高速缓存/主存请求PTE。得到后跳到3。
内核的虚拟内存管理
前面主要讲了硬件部分如何进行地址翻译，这一节讲一下内核是如何协助硬件管理虚拟内存的。linux可执行文件结构及链接过程分析 之前写的关于链接过程的文章中也说了，linux系统对于内存实际是分段管理的，分成数据段、代码段、共享库内存映射区域、栈、堆等等。在内核中，每一个进程都维护了自己的元数据，其中有两个字段pgd和mmap非常重要，前者是第一级页表的基址，在内存调度时会把该地址CR3基址寄存器，MMU工作时会从该地址获取内存页表。第二个字段是指向维护了所有虚拟内存区域的链表，每个区域主要有以下4个字段：
- vm_start，区域的起始地址。
- vm_end，区域的结束地址。
- vm_prot，区域的读写许可权限。
- vm_flags，描述该区域是共享的或者是私有的。
细看缺页异常程序
在讲CPU读取内存数据时，提到了缺页异常处理程序。这里再详细补充一下该程序的功能：
- 判断虚拟地址是否合法。即判断该地址是否在某个内存区域的vm_start和vm_end内。
- 判断内存访问是否合法。即判断是否有读写该区域的权限。这个判断不同于MMU根据PTE的某些标志位的判断，这个判断不是硬件层面的，是内核层面进行进一步的过滤。
- 进行页替换，重新执行缺页指令。
内存与磁盘的映射
这个关系是内核建立并维护的。虚拟内存地址必须与某个磁盘地址对应起来。内核实际上是把某段内存区域映射到某个磁盘文件上。
可以映射成普通文件，例如在执行exec系统调用时，就会建立起内存区域与磁盘的可执行文件的代码段与数据段的映射，然后进行按需页面调度。按需页面调度，实际上就是利用上面提到的缺页异常程序按需把磁盘的数据拷贝到内存里，再刚映射时并没有任何数据传输。
也可以映射成匿名文件，这些匿名文件的创建与删除完全由内核负责，linux系统上的swap区域就是干这个事。例如进程的栈，堆等没有真实文件可以对应的，就会映射到swap区域的匿名文件，并用二进制0初始化该区域。当内存不足，必须要把某些内存页交换到磁盘时，就会产生从内存到swap区域的数据传输，在刚开始建立映射时也是没有任何数据交换的。
要特别注意的是，当进程运行过程中，修改了数据段的某些内容时，如果内存不足造成缺页，此时内核不会把内存交换回真实文件区域，而是交换到swap区域，并重新建立映射关系。
内存区域要么是共享的，要么是私有的。由于每个区域都有唯一的文件名相对应，因此内核很容易判断是否有其他进程的虚拟内存映射相同的物理内存。共享区域的管理比较简单，读写都会更改到同样的物理内存上，并且当内存区域被修改，dirty页最终会被写回真实文件上。私有区域的管理则稍微复杂一点，采用写时复制的策略，即一开始多个进程的内存页表都指向同样的物理内存，当某个进程对该区域产生修改时，则会另外分配一个副本，并调整内存映射关系。fork系统调用就是基于该写时复制策略来实现的。
动态内存分配
用户态的内存管理
前面所讲的内存管理，按照由底层到高层的顺序，分别讲述了硬件与内核互相协调的内存管理策略。而我们在写程序时候动态分配的内存，例如c程序的malloc库函数，是一个用户态的内存管理工具，它帮助我们管理堆空间的内存。
堆在用户进程内存模型中是向上增长的，内核维护了一个brk指针来标识当前堆的最高地址，用户进程通过系统调用sbrk来增加或者缩小brk指针。c标准库中的malloc便是通过调用sbrk来管理用户进程分配的内存。
分配器实现
这里介绍几种经典的分配器内存管理策略。分配器在找不到空闲内存块满足用户进程需求时，会调用sbrk系统调用向内核请求内存。但分配器不会往内核归还内存，即便调用free这类函数，也只是把内存标记为空闲，由malloc这样的分配器去管理空闲块，进行下一次分配。分配器主要工作便是维护空闲块链表满足用户进程的分配和释放需求。
分配器的吞吐率和内存利用率
衡量分配器的两个指标，一个是吞吐率：每单位时间完成分配和释放的操作数；一个是内存利用率：实际使用内存占总分配内存的比率。
其中内存利用率又可以用两个指标来表现，内部碎片与外部碎片。内部碎片是已分配块比有效载荷大，一些内存分配的字节对齐，或者添加内存块的头部尾部进行管理等等都可能导致内部碎片。外部碎片是虽然总空闲内存满足分配要求，但找不到一个单独的连续的空闲块可以满足这次请求。
吞吐率和内存利用率是相互矛盾的。
分配器的数据组织方式
隐式空闲链表
隐式空闲链表没有单独将空闲块抽出来用独立的链表维护，而只是简单地通过每个内存块的头部和尾部的块大小、分配标志位来区分空闲块与已分配块，在分配内存时，时间复杂度与所有内存块的数量成线性关系。
通过内存块头部和尾部的大小，可以把前后块像链表一样连起来。并且在释放内存的时候，可以在常数时间判断前后内存块是否空闲，空闲的话合并起来，避免假碎片现象。
显式空闲链表
把空闲块单独组织成一个链表，在分配内存时时间复杂度与所有空闲块的数量成线性关系。
通过空闲块的pred与succ指针，找到上一个与下一个空闲块的位置。当释放内存时，可以选择把空闲块放到链表的头部（后进先出LIFO），这样只需要常数时间。也可以按照地址顺序维护链表，这样释放就需要线性时间。但按地址排序的首次适配比LIFO排序的首次适配有更高的内存利用率，接近最佳适配。显式链表的缺点是空闲块必须足够大，以容纳头部，尾部与所有指针，潜在提高了内存碎片的程度。
分离的空闲链表
对显式空闲链表的优化方式，是把空闲链表按大小分类，每个类维护一个单独的空闲链表，分配器维护一个空闲链表数组，那么每次分配只搜索相应大小类的空闲链表即可。只有在当前空闲链表找不到满足的空闲块时，才搜索下一个链表。
比较经典的有两种实现方式，简单分离存储与分离适配。
- 简单分离存储。每个大小类包含大小相等的空闲块。空闲块不分割，不合并。链表为空，就向内核申请固定数量的内存页，然后分割成相等的块，连成链表；否则分配时从开头第一个取即可。已分配块的大小可以从地址推断出来，而且没有合并，所以不需要头部和脚部。分配和释放都从空闲链表起始处开始，所以只需要succ指针，最小块为1个字。分配和释放都是常数时间，但由于没有合并和分割，每个链表的块大小都一样，容易造成内部碎片与外部碎片。
- 分离适配。每个空闲链表是一个大小类，大小不相等。对空闲链表做首次适配，如果找到，就分割并把剩余部分插入适当的空闲链表；如果找不到，就搜索下一个空闲链表。如果所有空闲链表都搜索完，仍然找不到合适的块，则向内核请求堆内存。释放的时候需要合并，然后放到合适的空闲链表中。对分离空闲链表的首次适配搜索，内存利用率近似最佳适配。malloc采用了分离适配的方式。伙伴系统是分离适配的一个特例，是linux内核采用的内存管理手段。其大小类为2的幂，分配和释放都递归地2分内存块或组合相应的伙伴。给定一个内存块的地址，容易计算出其伙伴的地址，适合快速搜索与合并，便于管理。由于块大小只能是2的幂，可能会导致内部碎片。一般适合于块大小肯定是2的幂的系统。
分配策略
- 首次适配。从链表头部开始，找到第一个可以分配的内存块马上分配，这种方式倾向于把大的空闲块放到链表后面，在链表起始处留下小的空闲块“碎片”，增加了大块的搜索时间。
- 下一次适配。在上一次查询结束的地方开始搜索，比首次适配要快，但内存利用率较低。
- 最佳适配。检查每一个空闲块，选择最适合大小的空闲块。内存利用率最高，但性能最差。