内存管理

1.虚拟内存

物理内存就是系统硬件提供的内存大小，是真正的内存。

虚拟内存就是为了满足物理内存的不足而提出的策略，，它是利用磁盘空间虚拟出的一块逻辑内存，用作虚拟内存的磁盘空间被称为交换空间（Swap Space）。在程序装入时，可以将程序的一部分装入内存，而将其余部分留在外存（或者说写到交换空间中），就可以启动程序执行。在程序执行过程中，当所访问的信息不在内存时，由操作系统将所需要的部分调入内存,然后继续执行程序。另一方面，操作系统将内存中暂时不使用的内容换出到外存上，从而腾出空间存放将要调入内存的信息。这样，系统好像为用户提供了一个比实际内存大得多的存储器，称为虚拟存储器。

之所以将其称为虚拟存储器，是因为这种存储器实际上并不存在，只是由于系统提供了部分装入、请求调入和置换功能后（对用户完全透明），给用户的感觉是好像存在一个比实际物理内存大得多的存储器。虚拟存储器的大小由计算机的地址结构决定，并非是内存和外存的简单相加（linux中进程的虚拟内存空间为4G）。虚拟存储器有以下三个主要特征：
多次性，是指无需在作业运行时一次性地全部装入内存，而是允许被分成多次调入内存运行。
对换性，是指无需在作业运行时一直常驻内存，而是允许在作业的运行过程中，进行换进和换出。

虚拟性，是指从逻辑上扩充内存的容量，使用户所看到的内存容量，远大于实际的内存容量。

访问虚拟内存时，会访问MMU（内存管理单元），页表存在于MMU中，通过页表由虚拟地址换算出物理地址，如果虚拟内存的页不存在于物理内存中，会产生缺页中断，从磁盘中取得缺的页放入内存。

需要了解的一些点：

（1）Linux系统会不时的进行页面交换操作，以保持尽可能多的空闲物理内存，即使并没有什么事情需要内存，Linux也会交换出暂时不用的内存页面。这可以避免等待交换所需的时间；

（2）Linux进行页面交换是有条件的，不是所有页面在不用时都交换到虚拟内存，Linux内核根据”最近最经常使用“算法，仅仅将一些不经常使用的页面文件交换到虚拟内存。还有就是即使进程释放了占用的内存，之前交换出去的页面并不会自动交换进物理内存，所以可能发生内存很多空余空间而交换空间也在被使用

（3）交换空间的页面在使用时会首先被交换到物理内存，如果此时没有足够的物理内存来容纳这些页面，它们又会被马上交换出去，如此以来，虚拟内存中可能没有足够空间来存储这些交换页面，最终会导致Linux出现假死机、服务异常等问题，Linux虽然可以在一段时间内自行恢复，但是恢复后的系统已经基本不可用了。因此，合理规划和设计Linux内存的使用，是非常重要的。

2.虚拟内存的实现

虚拟内存的实现需要建立在离散分配的内存管理方式的基础上。虚拟内存的实现有以下三种方式：

（1）请求分页存储管理（2）请求分段存储管理（3）请求段页式存储管理

不管哪种方式，都需要有一定的硬件支持。一般需要的支持有以下几个方面：
一定容量的内存和外存。
页表机制（或段表机制），作为主要的数据结构。
中断机构，当用户程序要访问的部分尚未调入内存，则产生中断。

地址变换机构，逻辑地址到物理地址的变换。

3.操作系统对内存的管理

3.1内存管理方式

块式管理：主存分为一大块一大块（比页大），所需程序段不在主存就分配一块主存空间，把程序片段load入主存

页式管理：建立在基本分页的基础上的，为了能支持虚拟存储器功能而增加了请求调页功能和页面置换功能。每次调入和换出的基本单位都是长度固定的页面，这使得请求分页系统在实现上要比请求分段系统简单

段式管理：地址结构由段号和段内地址组成。 请求分段系统在换进和换出时是可变长度的段。每一段的空间比页小很多，但是如果一个程序片段分为几十段，很多时间被浪费在计算每一段物理地址上

段页式管理：其地址结构由段号、段内页号及页内地址三部分所组成。每取一次地址，需要访问3次内存（个人理解：由于其结构是由三部分，每读一部分就有去一趟内存）

x86 CPU采用了段页式地址映射模型。进程代码中的地址为逻辑地址，经过段页式地址映射后，才真正访问物理内存。

3.2分页和分段的主要区别：

a)、页是信息的物理单位，分页是为实现离散分配方式，以消减内存的外零头，提高内存的利用率；段则是信息的逻辑单位，它含有一组其意义相对完整的信息，分段的目的是为了能更好地满足用户的需要；b)、页的大小固定且由系统决定，由系统把逻辑地址划分为页号和页内地址两部分，是由机器硬件实现的，因而在系统中只能有一种大小的页面；而段的长度却不固定，决定于用户所编写的程序，通常由编译程序在对源程序进行编译时，根据信息的性质来划分；c)、分页的作业地址空间是一维的，即单一的线性地址空间，程序员只需利用一个记忆符，即可表示一个地址；而分段的作业地址空间则是二维的，程序员在标识一个地址是，即需给出段名，又需给出段内地址。

4.进程空间和内核空间对内存的管理不同

通常32位Linux内核地址空间划分0~3G为用户空间，3~4G为内核空间。注意这里是32位内核地址空间划分，64位内核地址空间划分是不同的。

目前现实中，64位Linux内核不存在高端内存，因为64位内核可以支持超过512GB内存。若机器安装的物理内存超过内核地址空间范围，就会存在高端内存。

32位系统用户进程最大可以访问3GB，内核代码可以访问所有物理内存。64位系统用户进程最大可以访问超过512GB，内核代码可以访问所有物理内存。

在内核态申请内存比在用户态申请内存要更为直接，它没有采用用户态那种延迟分配内存技术。内核认为一旦有内核函数申请内存，那么就必须立刻满足该申请内存的请求，并且这个请求一定是正确合理的。相反，对于用户态申请内存的请求，内核总是尽量延后分配物理内存，用户进程总是先获得一个虚拟内存区的使用权，最终通过缺页异常获得一块真正的物理内存。

5.高端内存（是指物理内存中>896MB的）

通常32位Linux内核地址空间划分0~3G（0-0xc0000000）为用户空间，3~4G（0xc0000000 ~ 0xffffffff）为内核空间。

内核地址空间分为三部分：ZONE_DMA（开始的16M）、ZONE_NORMAL（16MB~896MB）和 ZONE_HIGHMEM（896MB~1024MB/0xF8000000 ~ 0xFFFFFFFF）。ZONE_HIGHMEM即为高端内存。

高端内存不能全部映射到内核空间，也就是说这些物理内存没有对应的线性地址。不过，内核为每个物理页框都分配了对应的页框描述符，所有的页框描述符都保存在mem_map数组中，因此每个页框描述符的线性地址都是固定存在的。内核此时可以使用alloc_pages()和alloc_page()来分配高端内存，因为这些函数返回页框描述符的线性地址（通过操作页框描述符来绑定对应的对应物理内存的线性地址）。

当内核想访问高于896MB物理地址内存时，从0xF8000000 ~ 0xFFFFFFFF地址空间范围内找一段相应大小空闲的逻辑地址空间，借用一会。内核的虚拟和物理地址只差一个偏移量：物理地址 = 逻辑地址 – 0xC0000000。借用这段逻辑地址空间，建立映射到想访问的那段物理内存（即填充内核PTE页面表），临时用一会，用完后归还。这样别人也可以借用这段地址空间访问其他物理内存，实现了使用有限的地址空间，访问所有所有物理内存。

对 于高端内存，可以通过 alloc_page() 或者其它函数获得对应的 page（page结构对应一个页框），但是要想访问实际物理内存，还得把 page 转为线性地址才行，也就是说，我们需要为高端内存对应的 page 找一个线性空间，这个过程称为高端内存映射。

对应高端内存的3部分，高端内存映射有三种方式：

5.1 映射到”内核动态映射空间”（noncontiguous memory allocation）--VMALLOC_START~VMALLOC_END

这种方式很简单，因为通过 vmalloc() ，在”内核动态映射空间”申请内存的时候，就可能从高端内存获得页面（参看 vmalloc 的实现），因此说高端内存有可能映射到”内核动态映射空间”中。（vmalloc分配非连续的物理内存块，再修改页表，把内存映射到逻辑地址空间的连续区域，返回指针指向逻辑上连续的一块内存区）

5.2 持久内核映射（permanent kernel mapping）

如果是通过 alloc_page() （分配内存块，返回指向内存块起始页的指针（或者说页框描述符的线性地址），个人理解用alloc_page分配物理内存，与此虚拟内存的PKMAP_BASE 到 FIXADDR_START映射，获得用户空间的页）获得了高端内存对应的 page，内核专门为此留出一块线性空间（个人理解不是指线性地址），从 PKMAP_BASE 到 FIXADDR_START ，用于映射高端内存。在 2.6内核上，这个地址范围是 4G-8M 到 4G-4M 之间。这个空间起叫”内核永久映射空间”或者”永久内核映射空间”。这个空间和其它空间使用同样的页目录表，对于内核来说，就是 swapper_pg_dir，对普通进程来说，通过 CR3 寄存器（CR3中含有页目录表物理内存基地址）指向。通常情况下，这个空间是 4M 大小，因此仅仅需要一个页表即可，内核通过来 pkmap_page_table 寻找这个页表。通过 kmap()，可以把一个 page 映射到这个空间来（个人理解：将刚分配已经和内存块绑定的有页表的页与这个空间连接上）。由于这个空间是 4M 大小，最多能同时映射 1024 个 page。因此，对于不使用的的 page，及应该时从这个空间释放掉（也就是解除映射关系），通过 kunmap() ，可以把一个 page 对应的线性地址从这个空间释放出来（个人理解这三个空间是指高端内存的空间，这里个page指页框）。

高端内存不能全部映射到内核空间，也就是说这些物理内存没有对应的线性地址。不过，内核为每个物理页框都分配了对应的页框描述符，所有的页框描述符都保存在mem_map数组中，因此每个页框描述符的线性地址都是固定存在的。内核此时可以使用alloc_pages()和alloc_page()来分配高端内存，因为这些函数返回页框描述符的线性地址。

vmalloc()的内存分配原理与用户态的内存分配相似，都是通过连续的虚拟内存来访问离散的物理内存，并且虚拟地址和物理地址之间是通过页表进行连接的，通过这种方式可以有效的使用物理内存。但是应该注意的是，vmalloc()申请物理内存时是立即分配的，因为内核认为这种内存分配请求是正当而且紧急的；相反，用户态有内存请求时，内核总是尽可能的延后，毕竟用户态跟内核态不在一个特权级。

5.3临时映射（temporary kernel mapping）

内核在 FIXADDR_START 到 FIXADDR_TOP 之间保留了一些线性空间用于特殊需求。这个空间称为”固定映射空间”在这个空间中，有一部分用于高端内存的临时映射。
这块空间具有如下特点：
（1）每个 CPU 占用一块空间
（2）在每个 CPU 占用的那块空间中，又分为多个小空间，每个小空间大小是 1 个 page，每个小空间用于一个目的，这些目的定义在 kmap_types.h 中的 km_type 中。
当要进行一次临时映射的时候，需要指定映射的目的，根据映射目的，可以找到对应的小空间，然后把这个空间的地址作为映射地址。这意味着一次临时映射会导致以前的映射被覆盖。通过 kmap_atomic() 可实现临时映射。

6.伙伴算法

6.1 Buddy（伙伴的定义）：
这里给出伙伴的概念，满足以下三个条件的称为伙伴：
1）两个块大小相同；
2）两个块地址连续；

3）两个块必须是同一个大块中分离出来的；

6.2 伙伴位图

用一位描述伙伴块的状态位码，称之为伙伴位码。比如，bit0为第0块和第1块的伙伴位码，如果bit0为1，表示这两块至少有一块已经分配出去，如果bit0为0，说明两块都空闲，还没分配。

释放过程根据位图判断伙伴是否存在，如果对相应位的异或操作得1，则没有伙伴可以合并，如果异或操作得0，就进行合并，并且继续按这种方式合并伙伴，直到不能合并为止。

6.3 结构图

 free_area数组中，第K个元素，它标识所有大小为2^k的空闲块，所有空闲快由free_list指向的双向循环链表组织起来。其中的nr_free（在每个free_area中），它指定了对应空间剩余块（剩几个2^K个page）的个数。

6.4 申请和回收过程

假如系统需要4(2*2)个页面大小的内存块，该算法就到free_area[2]中查找，如果链表中有空闲块，就直接从中摘下并分配出去。如果没有，算法将顺着数组向上查找free_area[3],如果free_area[3]中有空闲块，则将其从链表中摘下，分成等大小的两部分，前四个页面作为一个块插入free_area[2]，后4个页面分配出去，free_area[3]中也没有，就再向上查找，如果free_area[4]中有，就将这16(2*2*2*2)个页面等分成两份，前一半挂如free_area[3]的链表头部，后一半的8个页等分成两等分，前一半挂free_area[2]的链表中，后一半分配出去。假如free_area[4]也没有，则重复上面的过程，知道到达free_area数组的最后，如果还没有则放弃分配。

内存的释放是分配的逆过程，也可以看作是伙伴的合并过程。当释放一个块时，先在其对应的链表中考查是否有伙伴存在，如果没有伙伴块，就直接把要释放的块挂入链表头；如果有，则从链表中摘下伙伴，合并成一个大块，然后继续考察合并后的块在更大一级链表中是否有伙伴存在，直到不能合并或者已经合并到了最大的块(2*2*2*2*2*2*2*2*2个页面)。

6.5 优缺点

优点：
     较好的解决外部碎片问题
     当需要分配若干个内存页面时，用于DMA的内存页面必须连续，伙伴算法很好的满足了这个要求
     只要请求的块不超过512个页面(2K)，内核就尽量分配连续的页面。

     针对大内存分配设计。

缺点：

      1. 合并的要求太过严格，只能是满足伙伴关系的块才能合并，比如第1块和第2块就不能合并。
      2. 碎片问题：一个连续的内存中仅仅一个页面被占用，导致整块内存区都不具备合并的条件
      3. 浪费问题：伙伴算法只能分配2的幂次方内存区，当需要8K（2页）时，好说，当需要9K时，那就需要分配16K（4页）的内存空间，但是实际只用到9K空间，多余的7K空间就被浪费掉。

      4. 算法的效率问题： 伙伴算法涉及了比较多的计算还有链表和位图的操作，开销还是比较大的，如果每次2^n大小的伙伴块就会合并到2^(n+1)的链表队列中，那么2^n大小链表中的块就会因为合并操作而减少，但系统随后立即有可能又有对该大小块的需求，为此必须再从2^(n+1)大小的链表中拆分，这样的合并又立即拆分的过程是无效率的。

7. Linux的slab层（slab分配器）

内核中物理内存的管理机制主要有伙伴算法、slab高速缓存和vmalloc机制。

其中伙伴算法和slab高速缓存都在物理内存映射区分配物理内存（896MB），而vmalloc机制则在高端内存映射区分配物理内存。

slab分配器是基于对象进行管理的，所谓的对象就是内核中的数据结构

为了便于结构的频繁分配和回收，编程人员常常会用到空闲链表。空闲链表中包含可供使用的，已经分配好的数据结构块。当代码需要一个新的数据结构实例时，就可以从空闲链表中抓取一个，而不需要再去执行一些分配内存的代码，这样不仅高效而且使用简单。以后，当不需要这个数据结构时，我们不能简单的释放这块内存，而是需要把它放回空闲链表中.

在内核中，空闲链表面对的一个主要问题就是不能全局控制（个人理解：空闲链表申请时就会给出，不知道有多少空闲链表已经申请出，没有一个总体的统一管理）。当可用内存变得紧缺时，内核无法通知每个空闲链表，让其收缩缓存的大小以便释放出一些内存来。实际上，内核根本不知道存在任何空闲链表。为了解决这个问题，Linux内核引入了slab层的概念。slab分配器扮演了通用数据结构缓存层的角色。

slab层把不同的对象划分为高速缓存，其中每个高速缓存组中存放的都是不同类型的数据结构对象，高速缓存又被划分为slab（由一个或多个物理上连续的页组成，一般情况下，slab也就仅仅一页。每个高速缓存可以由多个slab组成）

每个slab都包含一些数据成员，这里的成员指的是缓存的数据结构。每个slab处于三种状态之一：满，部分满或空。
当内核的某一部分需要一个对象时，就要由slab分配了，首先考虑的是部分满的slab，如果不存在部分满的slab则去空的slab分配，如果也不存在空的slab，则内核需要申请页重新分配高速缓存。

slab层的管理是在每个高速缓存的基础上的，通过给整个内核一个简单的接口来完成的。通过接口就可以创建和撤销高速缓存，并在高速缓存内分配和释放对象。高速缓存及其slab的复杂管理完全通过slab层的内部机制来处理。当你创建了一个高速缓存之后，slab层所起的作用就像一个专用的分配器，可以为具体的对象类型进行分配。

8.linux vma

进程的虚拟内存空间会被分成不同的若干区域，每个区域都有其相关的属性和用途。一个vma就是一块连续的线性地址空间的抽象，它拥有自身的权限(可读，可写，可执行等等) ，每一个虚拟内存区域都由一个相关的struct vm_area_struct结构来描述。

代码区、数据区、堆栈区

用户进程的虚拟地址空间包含了若干区域，这些区域的分布方式是特定于体系结构的，不过所有的方式都包含下列成分：
可执行文件的二进制代码，也就是程序的代码段；存储全局变量的数据段；用于保存局部变量和实现函数调用的栈；环境变量和命令行参数；程序使用的动态库的代码；用于映射文件内容的区域

【名词解释】

页表--页表是一种特殊的数据结构，放在系统空间的页表区，存放逻辑页与物理页帧的对应关系。 每一个进程都拥有一个自己的页表，PCB（进程控制块）表中有指针指向页表。

快表--目的是加快地址映射速度。在虚拟页式存储管理中设置了快表，用于保存正在运行进程页表的子集，通常快表存放在（高速缓冲存储器Cache）中。

页框--内核以页框为基本单位管理物理内存，分页单元中，页指一组数据，而存放这组数据的物理内存就是页框，当这组数据被释放后，若有其他数据请求访问此内存，那么页框中的页将会改变。

        快表与页表（同样是为地址转换）区别：页表指出逻辑地址中的页号与所占主存块号的对应关系。快表就是存放在高速缓冲存储器的部分页表。它起页表相同的作用。

基本分页存储管理方式--用固定大小的页(Page)来描述逻辑地址空间，用相同大小的页框(Frame)来描述物理内存空间，由操作系统实现从逻辑页到物理页框的页面映射，同时负责对所有页的管理和进程运行的控制。

页表条目 (Page Table Entry),即pte,是页表的最低层,它直接处理页,该值包含某页的物理地址，还包含了说明该条目是否有效及相关页是否在物理内存中的位