虚拟内存
1.1. 为什么要使用虚拟内存技术
1.2. 理论前提
1.3. 虚拟内存实现
1.4. 页机制
1.5. MMU
1.6. 物理内存映射
进程的内存分布
2.1. 内核态
2.2. 用户态
进程内存管理
3.1. 物理内存管理
3.2. node、zone、page
3.3. 伙伴算法
3.4. slab

Linux 内存管理

虚拟内存

众所周知，Linux采用虚拟内存管理技术，每个进程都有独立的进程地址空间。这是Linux内存管理的基础，所以我们先讲解一下虚拟内存技术。虚拟内存技术是基于交换技术（swap）的，只不过交换的是页或者段。

为什么要使用虚拟内存技术

或者说使用虚拟技术的好处：

扩大内存（主要催生虚拟内存原因）
安全性提高（不直接访问物理内存）
易于开发（每个进程拥有独立的用户空间）

举一个栗子来说明：

如果我们直接使用物理内存，CPU需要某一个值的时候，直接去物理内存中取就可以了，简单直接。

但是我们需要知道物理地址的值，每次程序开始执行，也就是执行程序从磁盘被load到物理内存中之后，我们必须告诉CPU，程序是从哪一个地址开始执行的(即PC寄存器的值)；

还有一个致命的缺点是：程序使用的内存会被物理内存所限制，比如我们的机器上只有512M内存，那我们的程序就不能使用需占1G内存的程序了，这点或许是催生虚拟内存产生的最主要原因。

理论前提

我们知道想要装下超过物理内存大小的程序，那么我们可以选择增加内存条（硬扩充），同时也可以通过软件进行扩充（软扩充），其中交换技术（包括虚拟内存技术）就属于软扩充。

虚拟内存技术就是只装入程序的一部分，就开始运行整个程序。那么这样内存压力就会变小，能够运行大内存需求的软件。

那么这么做可以吗？当然可以，当时提出一个理论来支撑：程序局部性原理。

在一段时间内，整个程序的执行仅限于程序中的某一部分。相应地，执行所访问的存储空间也局限于某个内存区域。局部性原理又表现为：时间局部性和空间局部性。

时间局部性是指如果程序中的某条指令一旦执行，则不久之后该指令可能再次被执行；如果某数据被访问，则不久之后该数据可能再次被访问。空间局部性是指一旦程序访问了某个存储单元，则不久之后。其附近的存储单元也将被访问。

虚拟内存实现

实现原理：

当进程要求运行的时，不是将他的全部信息装入内存，而是将其一部分先装入内存，另一部分暂时留在外存，进程在运行过程中，要使用信息不在内存时，发生中断，由操作系统将他们调如内存，以保证进程的正常运行。

但是呢，从进程角度来说，会认为它拥有连续可用的内存（一个连续完整的地址空间），而实际上，它通常是被分隔成多个物理内存碎片，还有部分暂时存储在外部磁盘存储器上，在需要时进行数据交换。

而这一部分外部磁盘存储（辅存）就叫做交换分区。交换分区的主要功能是当全部的 RAM 被占用并且需要更多内存时，用磁盘空间代替 RAM 内存。

内核使用一个内存管理程序来检测最近没有使用的内存块（内存页）。内存管理程序将这些相对不经常使用的内存页交换到硬盘上专门指定用于“分页”或交换的特殊分区。那些换出到硬盘的内存页面被内核的内存管理代码跟踪，如果需要，可以被分页回 RAM。

总结一下，虚拟内存实现可以总结为三步：

先加载进程的一部分数据
需要不在内存的数据，发生中断（缺页中断/缺段中断）
将数据调入内存

我们知道，根据存储管理可以分为分页式存储、段式存储、段页式存储3种。Linux 采用的是段页式存储，但是，大多数文章为什么都没有提及段式存储相关，为什么呢？

因为在Linux内部的地址的映射过程为逻辑地址–>线性地址–>物理地址，逻辑地址经段机制转化成线性地址；线性地址又经过页机制转化为物理地址。简单的讲就是，在虚拟内存管理的时候，实质上的管理的是一段一段的（逻辑段），这一段一段的内存组和起来就是我们常规理解的线形地址，而在这一段一段的虚拟内存再使用页机制转化到物理内存上。

我们要知道，页是信息的物理单位，分页是为实现离散分配方式，以消减内存的外零头，提高内存的利用率。段则是信息的逻辑单位，它含有一组其意义相对完整的信息。分段的目的是为了能更好地满足用户的需要。这也是段和页的区别。

Linux上的段机制和页机制下面会分开讲解。段机制是Linux在组织虚拟出来的虚拟内存，而页机制则是在实现虚拟内存。

页机制

虚拟内存空间中的地址叫做“虚拟地址”；而实际物理内存空间中的地址叫做“实际物理地址”或“物理地址”。

尽管处理器的最小可寻址单位通常为字或字节，但是Linux中内存管理单元(MMU，把虚拟地址转换为物理地址的硬件设备)是以页为单位处理。我们把虚拟出来的内存分成等大的内存块，叫做页（虚拟内存空间的顺序划分），把物理内存分成同等大小的内存块，叫做页框（对物理内存按顺序等大小的划分）。

我们知道，缺页中断过后操作系统会将对应的页调入内存，那么常规操作系统是怎么实现这个逻辑的呢？

首先检测是否有空闲的页框，如果有，那么将从交换分区调入的页装配到空闲页框中（swap in）。如果没有空闲页框，那系统按预定的置换策略（页面置换算法）自动选择一个或一些在内存的页面，如果这个或者这些页面为dirty，那么就将其换到（swap out）交换分区，空出页框了，就可以安置所需的页（swap in）。

值得说明的是，交换分区的数据来源于从物理内存中淘汰出来的页面，同时当缺页中断的时候，就是将交换分区中的页面调入物理内存中。

但是，在页面置换算法上，Linux 并没有采取这一种常规做法，Linux有一个守护进程kswapd，比较每个内存区域的高低水位来检测是否有足够的空闲页面来使用。每次运行时，仅有一个确定数量的页面被回收。这个阈值是受限的，以控制I/O压力。每次执行回收，先回收容易的，再处理难的。回收的页面会加入到空闲链表中。

Linux采用的页面置换算法是一种改进地LRU算法--最近最少使用（LRU）页面的衰老算法，维护两组标记：活动/非活动和是否被引用。第一轮扫描清除引用位，如果第二轮运行确定被引用，就提升到一个不太可能回收的状态，否则将该页面移动到一个更可能被回收的状态。

处于非活动列表的页面，自从上次检查未被引用过，因而是移除的最佳选择。被引用但不活跃的页面同样会被考虑回收，是因为一些页面是守护进程访问的，可能很长时间不再使用。

状态转换如下：

页框置换算法中考虑的页面状态

另外，内存管理还有一个守护进程pdflush，会定期醒来，写回脏页面；或者可用内存下降到一定水平后被内核唤醒。

MMU

经过前面讲解，对于一个进程（程序）来说，看到的就是一大块连续的线形地址了。但是想要探究更为具体的实现，那就要介绍MMU了。

内存管理单元（Memory Management Unit）简称MMU，MMU位于处理器内核和连接高速缓存以及物理存储器的总线之间。当处理器内核取指令或者存取数据的时候，都会提供一个有效地址(effective address)，或者称为逻辑地址、虚拟地址，MMU会将逻辑地址映射为物理地址。

这对于多进程系统非常重要。例如，在32位Linux里，进程A在地址0x08048000映射了可执行文件，进程B同样在地址0x08048000映射了可执行文件，如果A进程读地址0x08048000，读到的是A的可执行文件映射到RAM的内容，而进程B读取地址0x08048000时，则读到的是B的可执行文件映射到RAM的内容。意思就是说，两个进程虽然虚拟地址是一样的，但是他们的对应的真实数据页可能是不一样的。

要将虚拟地址转换成物理地址，可以通过建立一张映射表完成。页帧（Page Frame）是指物理内存中的一页内存，MMU虚实地址映射就是寻找物理页帧的过程。

MMU软件配置的核心是页表（Page Table），它描述MMU的映射规则，即虚拟内存哪(几)个页映射到物理内存哪(几)个页帧。页表由一条条代表映射规则的记录组成，每一条称为一个页表条目（Page Table Entry），整个页表保存在片外内存，MMU通过查找页表确定一个虚拟地址应该映射到什么物理地址，以及是否有权限映射。

既然所有发往内存的地址信号都要经过MMU处理，那么MMU就可以以很小的代价承担更大的责任，比如内存保护。可以在PTE条目中预留出几个比特，用于设置访问权限的属性，如禁止访问、可读、可写和可执行等。设好后，CPU访问一个虚拟地址时，MMU找到页表中对应PTE，把指令的权限需求与该PTE中的限定条件做比对，若符合要求就把虚拟地址转换成物理地址，否则不允许访问，并产生异常。

物理内存映射

我们知道Linux MMU处理单位为页，一个32bits虚拟地址，每页大小4k，可以划分为2^20个内存页，如果物理页帧随意映射，页表的空间占用就是(2^20)*sizeof(PTE)*进程数（每个进程都要有自己的页表），PTE一般占4字节，即每进程4M，这对空间占用和MMU查询速度都很不利。

实际应用中不需要每次都按最小粒度的页来映射，很多时候可以映射更大的内存块。因此最好采用变化的映射粒度，既灵活又可以减小页表空间。Linux 采用的就是三级页表。随着64位CPU，比如X86_64，出现四级页表页开始诞生，原理相同，这里看一下Linux的三级页表。

页全局目录 (Page Global Directory，即PGD) ：全局字典，指向中间页目录。
页中间目录( Page Middle Directory，即PMD) ：中间字典，也可以理解为二级目录，指向PTE中的表项。
页表 (Page Table，即PTE)：页表(PTE)，指向物理页面。
偏移量(Page Offset)：即页内偏移。

线性地址、页表和页表项线性地址不管系统采用多少级分页模型，线性地址本质上都是索引+偏移量的形式.

进程的内存分布

以32位的计算机为例，一共可以虚拟出4G（2^32）的虚拟内存，每个进程都有各自独立的进程地址空间，意思就是每一个进程都有4G的线性虚拟地址空间。4G进程地址空间被划分两部分，内核空间和用户空间。用户空间从0到3G，内核空间从3G到4G；但是内核空间是由内核负责映射，不会跟着进程变化；内核空间地址有自己对应的页表，用户进程各自有不同的页表。可以理解为每个普通进程都有自己的用户空间，但是内核空间被所有普通进程所共享（每个进程虚拟空间的3G~4G部分是相同的）。

另外，用户态进程只能访问0-3G，但是内核态进程既可以访问0-3G，也可以访问3G-4G地址空间。

那内核态到底是什么呢？运行在内核态的进程相比于用户态的进程拥有更高的权限，用户态的进程能够访问的资源受到了极大的控制，而运行在内核态的进程可以“为所欲为”，它能够控制计算机的硬件资源，例如协调CPU资源，分配内存资源，并且提供稳定的环境供应用程序运行。

下面来看看进程在虚拟内存中的分布情况

内核态

固定映射区（Fixing Mapping Region）：该区域和4G的顶端只有4k的隔离带，其每个地址项都服务于特定的用途，如ACPI_BASE等。

永久内存映射区（PKMap Region）：该区域可访问高端内存。访问方法是使用alloc_page(_GFP_HIGHMEM)分配高端内存页或者使用kmap函数将分配到的高端内存映射到该区域。

动态内存映射区（Vmalloc Region）：该区域由内核函数vmalloc来分配，特点是：线性空间连续，但是对应的物理空间不一定连续。vmalloc分配的线性地址所对应的物理页可能处于低端内存，也可能处于高端内存。

直接映射区（Direct Memory Region）：线性空间中从3G开始最大896M的区间，为直接内存映射区，该区域的线性地址和物理地址存在线性转换关系：线性地址=3G+物理地址。

用户态

栈：栈是用户存放程序临时创建的局部变量，也就是说我们函数括弧“{}”中定义的变量（但不包括static声明的变量，static意味着在数据段中存放变量）。除此以外，在函数被调用时，其参数也会被压入发起调用的进程栈中，并且待到调用结束后，函数的返回值也会被存放回栈中。

mmap 内存映射区：用于文件映射（包括动态库）和匿名映射。常见的就是使用 mmap 分配的虚拟内存区域。

堆：堆是用于存放进程运行中被动态分配的内存段，它的大小并不固定，可动态扩张或缩减。当进程调用malloc等函数分配内存时，新分配的内存就被动态添加到堆上（堆被扩张）；当利用free等函数释放内存时，被释放的内存从堆中被剔除（堆被缩减）。

BSS段：BSS段包含了未初始化的全局变量，在内存中bss段全部置零。

数据段：数据段用来存放已初始化的全局变量，换句话说就是存放程序静态分配的变量和全局变量。

代码段：代码段是用来存放可执行文件的操作指令，也就是说是它是可执行程序在内存中的镜像。代码段需要防止在运行时被非法修改，所以是不可写的。

用一张图总结一下：

进程内存管理

进程内存管理的对象是进程线性地址空间上的内存镜像，这些内存镜像其实就是进程使用的虚拟内存区域（virtual memory areas，即VMA）。

Linux内核通过一个被称为进程描述符的task_struct 结构体来管理进程，这个结构体包含了一个进程所需的所有信息。mm_struct中的pgd为页表，就是前面讲的一级页表。task_struct中有一个结构体被称为内存描述符的mm_struct，描述了一个进程的整个虚拟地址空间。每个进程正是因为都有自己的mm_struct，才使得每个进程都有自己独立的虚拟的地址空间

每一段已经分配的虚拟内存区域都会以一个vm_area_struct结构体表示，而组织这些结构一共有两种形式：其中mm_struct->mm_rb是所有vm_area_struct组成的红黑树，而mm_struct->mmap是所有vm_area_struct组成的链表，vma这个数据结构被双重管理主要是为了加速查找速度（空间换时间）。

mm_struct中的mmap指针指向的vm_area_struct链表的每一个节点就代表进程的一个虚拟地址空间，即一个VMA。一个VMA最终可能对应ELF可执行程序的数据段、代码段、堆、栈、或者动态链接库的某个部分。

在这条链表上进行这样表示，我们就可以将其理解为最开始所说的逻辑分段了。

物理内存管理

通过mm_struct结构体完成了对虚拟内存的管理，那么物理内存是如何管理和分配的呢？

经过前面介绍，我们知道Linux以页为单位进行分配，随之而来的就会有两个问题：

如何解决页外碎片问题
如何解决页内碎片问题

Linux 采用 buddy 系统（伙伴系统）来解决页外碎片，采用 slab 分配器来解决页内碎片。同时 Linux 采用
了 Node，Zone 和 page三级结构来描述物理内存的。buddy 系统是建立在这三级结构之上的。
slab 同时又在 buddy 系统之上管理着物理页之内的内存请求（小内存分配）。

node、zone、page

在介绍管理物理内存之前我们要先了解一下什么是 UMA 和 NUMA。

在多核系统中，如果物理内存对所有CPU来说没有区别，每个CPU访问内存的方式也一样，则这种体系结构被称为Uniform Memory Access(UMA)。

如果物理内存是分布式的，由多个cell组成（比如每个核有自己的本地内存），那么CPU在访问靠近它的本地内存的时候就比较快，访问其他CPU的内存或者全局内存的时候就比较慢，这种体系结构被称为Non-Uniform Memory Access(NUMA)。

Linux适用于各种不同的体系结构, 而不同体系结构在内存管理方面的差别很大，因此linux内核需要用一种体系结构无关的方式来表示内存。因此linux内核把物理内存按照CPU节点划分为不同的node, 每个node作为某个cpu结点的本地内存, 而作为其他CPU节点的远程内存, 而UMA结构下, 则任务系统中只存在一个内存node, 这样对于UMA结构来说, 内核把内存当成只有一个内存node节点的伪NUMA。

内存节点的数据结构为pg_data_t, 也就是struct pglist_data，而Linux会将所有 pg_data_t 使用双向链表组织起来。

内存管理区(zone)，zone由struct zone_struct 数据结构来描述。zone的类型由zone_t表示，主要有ZONE_DMA, ZONE_NORMAL, ZONE_HIGHMEM 这三种类型。

分区	功能
ZONE_DMA	可以用于DMA操作的页
ZONE_NORMAL	正常的、规则映射的页
ZONE_HIGHMEM	高内存地址的页，并不永久性映射

内存区域的确切边界和布局是和硬件体系结构相关的。例如，在x86硬件上，一些设备只能在最低的16MB地址空间进行DMA操作，因此ZONE_DMA就在0-16M范围内，在决定分区的时候，先分配 ZONE_DMA 和 ZONE_HIGHMEM，剩下的就属于 ZONE_NORMAL。ZONE_DMA大小是硬件决定的，和ZONE_NORMAL属于低端内存，ZONE_HIGHMEM属于高端内存。

节点、区域和页框之间的关系如下图：

上图中的zone_mem_map是一个页框的数组，它记录了一个内存分区的所有页框的使用情况。

用图总结下：

image

伙伴算法

内核子系统中有一个分区页框分配器,用于处理对连续页框组的内存分配请求。其中名为管理区分配器部分接受动态内存分配与释放请求。

image.png

在每个内存管理区（Zone）内，页框由伙伴系统来分配。为了达到更好的系统性能，一小部分页框保留在高速缓存中用于快速满足对单个页框的分配请求。

在 i386 体系结构中，整个物理内存被分为4k大小的页框，我们知道经过页机制我们可以不必要求有大块连续物理内存，我们可以通过页机制东拼西凑出一块内存，虽然物理内存不连续，但是通过页机制，在虚拟内存上就可以虚拟出一块连续的虚拟内存。但是，我们会更倾向于分配连续的物理内存（页框），因为分配连续内存时，页表不需要更改，因此能降低TLB的刷新率（频繁刷新会在很大程度上降低访问速度）。有兴趣的建议了解快表的机制。

那么为了能够分配连续的物理内存，就需要解决页外碎片（外部碎片）的问题，在Linux中采用伙伴算法来解决。

Buddy 算法将所有的空闲物理页分成 10 组，每组分别包含大小 1，2，4，8，16，32，64，
128，256，512 个连续物理页。每一组用链表组织起来。

image.png

分配：

对于一个 2^{order} 个连续页框大小的内存申请，伙伴系统首先查看 zone->free_area[order] 中是否有空闲的块。如果找到，则直接分配给请求对象。
如果没有，查找 zone->free_area[order+1] 是否有空闲块，如果有: 则摘下一块，并且分成两等分，分配一份给请求对象，另一份插入到 zone->free_area[order] 中。
如果没有，则依次往更大连续物理内存分组寻找，直到满足需求。

回收：
回收算法根据提供的块大小，将块放到大小对应的链表中。如果放入过程中发现有空闲伙伴块，则合并伙伴，形成更大的块放到对应链表中。

是否为伙伴块需要满足的条件：

两个块大小相同；
两个块地址连续；
两个块必须是同一个大块中分离出来的；

slab

通过页机制能够非常方便的分配到物理内存，但是通过伙伴算法分配的物理内存也产生了页内碎片（内部碎片）。但是内核使用的很多都是小对象，可能就几十字节，但是分配一个页框也是4K，这种分配造成的浪费非常大。比如存放文件描述符、进程描述符、虚拟内存区域描述符等行为所需的内存都不足一页。

Linux为了解决这种问题呢，在内核实现了slab分配器，主要针对内核中经常分配并释放的对象。核心思想就是存储池的运用。

slab会把对象池化，相同的对象放到一个存储池里，每个对象池都是一个 kmem_cache 结构的引用（称为一个 cache）。所有的对象池使用链表组织起来，即cache_chain。

image

而每一个对象池（kmem_cache）存在3种slab：

slabs_full：完全分配的slab
slabs_partial：部分分配的slab
slabs_empty：空slab,或者没有对象被分配

每一个slab就是一个或者多个连续的物理框（通常只有一个），他们是从伙伴系统中申请过来的物理内存，被划成很多小块，用于快速分配给对应的小对象。其中， slabs_empty 列表中的 slab 是进行回收（reaping）的主要备选对象。正是通过此过程，slab 所使用的内存被返回给操作系统供其他用户使用。

每一个slab是不断移动的。当一个 slab 中的所有对象都被使用完时，就从 slabs_partial 列表中移动到 slabs_full 列表中。当一个 slab 完全被分配并且有对象被释放后，就从 slabs_full 列表中移动到 slabs_partial 列表中。当所有对象都被释放之后，就从 slabs_partial 列表移动到 slabs_empty 列表中。

image

每当要申请这样一个对象时，slab分配器就从一个slab列表中分配一个这样大小的单元出去，而当要释放时，将其重新保存在该列表中，而不是直接返回给伙伴系统。slab 分配器还可以支持硬件缓存对齐和着色，这允许不同缓存中的对象占用相同的缓存行，从而提高缓存的利用率并获得更好的性能。

最后，用一张经典的图总结一下：