虚拟内存管理
# 为什么出现虚拟内存？
尽管基址寄存器和界限寄存器可以用于创建地址空间的抽象，还有另一个问题需要解决：管理软件的膨胀（bloatware）。虽然存储器容量增长快速，但是软件大小的增长更快。
这一发展的结果是，需要运行的程序往往大到内存无法容纳，而且必然需要系统能够支持多个程序同时运行，即使内存可以满足其中单独一个程序的需要，但总体来看，它们仍然超出了内存大小。**交换技术（swapping）**并不是一个有吸引力的解决方案，因为一个典型的SATA磁盘的峰值传输率最高达到100MB/s，这意味着至少需要10秒才能换出一个1GB的程序，并需要另一个10秒才能再将一个1GB的程序换入。换句话说，就是访问磁盘的速度远远慢于访问内存的速度。
虚拟内存的基本思想是：每个程序拥有自己的地址空间，这个空间被分割成多个块，每一块称作一页或页面（page）。每一页有连续的地址范围。这些页被映射到物理内存，但并不是所有的页都必须在内存中才能运行程序。当程序引用到一部分在物理内存中的地址空间时，由硬件立刻执行必要的映射。当程序引用到一部分不在物理内存中的地址空间时，由操作系统负责将缺失的部分装入物理内存并重新执行失败的指令。
从某个角度来讲，虚拟内存是对基址寄存器和界限寄存器的一种综合。8088为正文和数据分离出专门的基址寄存器（但不包括界限寄存器）。而虚拟内存使得整个地址空间可以用相对较小的单元映射到物理内存，而不是为正文段和数据段分别进行重定位。
# 内存分页有什么问题？
虚拟地址到物理地址的映射必须非常快。
如果虚拟地址空间很大，页表也会很大。
在32位环境下，虚拟地址空间共有4GB，假设一个页的大小是4KB（2^12），那么就需要大约100万（2^20）个页，而每个页表项需要使用4个字节大小来存储，那么整个4GB的内存空间的映射需要有4MB的内存来存储页表。
这4MB大小的页表，看起来不是很大，但是要知道每个进程都需要有自己的虚拟地址空间，也就是说每个进程都需要有自己的页表。
# 解决分页内存管理的问题？
# 多级页表
为了解决虚拟地址太大导致页表也变得很大的问题，需要采用一种叫做多级页表的解决方案。
我们把上面提到的100万个页表项进行再次分页，把页表分为一级页表和二级页表，一级页表中有1024个页表项，每个二级页表中也包含1024个页表项。
我们仔细观察这个二级页表，我们可以计算一下，发现映射4GB的地址空间需要4KB（一级页表大小）+4MB（所有二级页表所占内存之和），这样一看，页表所占用的内存似乎更大了？
如果4GB的虚拟地址全部映射到了物理内存中，那么二级分页占用的空间确实更大了，但是我们往往不会一次性为一个进程分配那么多内存。
如果使用了二级页表，一级页表可以覆盖整个4GB虚拟地址空间，但如果某个一级页表没有被用到，那么这个页表项对应的二级页表也就不需要创建了。
# TLB-快表
为了解决虚拟地址到物理地址的映射速度慢的问题，特别是在使用了多级页表后，虚拟地址到物理地址的转换就多了几道转换的工序，这显然会降低地址转换的速度，所以快表被提出。
根据程序局部性原理可以知道，在一段时间内，整个程序的执行权限仅限于程序的某一个部分，相对应的，执行所访问的存储空间也局限于某个内存区域。所以，我们在CPU芯片内部，加入了一个专门存放程序最常访问的页表项的缓存，这个就是TLB，也被叫做页表缓存，转址旁路缓存，快表等。
有了TLB之后，CPU在寻址时，会先去查询TLB，如果没有找到，才会继续查找常规的页表。
# Linux中的虚拟地址空间分布？
用户在用户态时，只能访问用户空间内存，只有进入内核态后才能访问内核空间的内存。
虽然每个进程都有各自的独立虚拟空间，但是每个虚拟内存中的内核地址，其实关联的都是相同的物理内存。这样，进程切换到内核态后，就可以方便地访问内核空间内存。
# 页分配机制？
Linux支持多种内存分配机制。分配物理内存页框的主要机制是页面分配器，它使用了著名的伙伴算法。 ^z2mpge
# 伙伴算法
管理一块内存的基本思想如下。刚开始，内存由一块连续的片段组成，图10-17a的简单例子中是64个页面。当一个内存请求到达时，首先上舍入到2的幂，比如8个页面。然后整个内存块被分割成两半，如图b所示。因为这些片段还是太大了，较低的片段被再次二分（c），然后再二分（d）。现在我们有一块大小合适的内存，因此把它分配给请求者，如图d所示。
现在假定8个页面的第二个请求到达了。这个请求有（e）直接满足了。此时4个页面的第三个请求到达了。最小可用的块被分割（f），然后其一半被分配（g）。接下来，8页面的第二个块被释放（h）。最后，8页面的另一个块也被释放。因为刚刚释放的两个邻接的8页面块来自同一个16页面块，它们合并起来得到一个16页面的块（i）。
Linux用伙伴算法管理内存，同时有一些附加特性。它有个数组，其中的第一个元素是大小为1个单位的内存块列表的头部，第二个元素是大小为2个单位的内存块列表的头部，下一个是大小为4个单位的内存块列表的头部，以此类推。通过这种方法，任何2的幂次大小的块都可以快速找到。
对于一个 2^{k} 个连续页框大小的内存申请， 伙伴系统首先查看 zone->free_area[k] （这个链表中的块的大小都是2^k大小的）中是否有空闲的块。如果找到，则直接分配给请求对象。 否则， 查找 zone->free_area[k+1] 是否有空闲块，如果有: 则摘下一块，并且分成两等分，分配一份给请求对象，另一份插入到 zone->free_area[k] 中。 如果仍旧没找到， 则依次往上查找，直到满足需求。
这个算法导致了大量的内部碎片，因为如果想要65页面的块，必须要请求并且得到一个128页面的块（向上取舍到2的幂次个页面）。
# slab分配器
在Linux中，伙伴分配器（buddy allocator）是以页为单位管理和分配内存。但在内核中的需求却以字节为单位（在内核中面临频繁的结构体内存分配问题）。假如我们需要动态申请一个内核结构体（占 20 字节），若仍然分配一页内存，这将严重浪费内存。那么该如何分配呢？slab 分配器专为小内存分配而生，由Sun公司的一个雇员Jeff Bonwick在Solaris 2.4中设计并实现。slab分配器分配内存以字节为单位，基于伙伴分配器的大内存进一步细分成小内存分配。换句话说，slab 分配器仍然从 Buddy 分配器中申请内存，之后自己对申请来的内存细分管理。
为了缓解这个问题，Linux有另一个内存分配器，slab分配器。它使用伙伴算法获得内存块，但是之后从其中切出slab（更小的单元）并且分别进行管理。
对于每个内核中的相同类型的对象，如：task_struct、file_struct 等需要重复使用的小型内核数据对象，都会有个 slab 缓存池，缓存住大量常用的「已经初始化」的对象，每当要申请这种类型的对象时，就从缓存池的**slab** 列表中分配一个出去；而当要释放时，将其重新保存在该列表中，而不是直接返回给伙伴系统，从而避免内部碎片，同时也大大提高了内存分配性能。
因为内核频繁地创建和撤销一定类型的对象（如task_struct），它使用了对象缓存。这些缓存由指向一个或多个slab的指针组成，而slab可以存储大量相同类型的对象。每个slab要么是满的，要么是部分满的，要么是空的。
例如，当内核需要分配一个新的进程描述符（一个新的task_struct）的时候，它在task结构的对象缓存中寻找，首先试图找一个部分满的slab并且在那里分配一个新的task_struct对象。如果没有这样的slab可用，就在空闲slab列表中查找。最后，如果必要，它会分配一个新的slab，把新的task结构放在那里，同时把该slab连接到task结构对象缓存中
kmem_cache是一个cache_chain的链表，描述了一个高速缓存，每个高速缓存包含了一个slabs的列表，这通常是一段连续的内存块。存在3种slab：slabs_full(完全分配的slab),slabs_partial(部分分配的slab),slabs_empty(空slab,或者没有对象被分配)。slab是slab分配器的最小单位，在实现上一个slab有一个或多个连续的物理页组成（通常只有一页）。单个slab可以在slab链表之间移动，例如如果一个半满slab被分配了对象后变满了，就要从slabs_partial中被删除，同时插入到slabs_full中去。