操作系统内核学习之：内存管理教程

1. 内存地址基本概念

（1）逻辑地址

每一个逻辑地址由段和偏移量组成。

（2）线性地址（虚拟地址）

线性地址是一个32位无符号整数，可以用来表示4GB的地址，范围为0x000000-0xfffffff

（3）物理地址

用于内存芯片级内存单元寻址，与cpu的地址引脚发送到内存总线上的电信号相对应。

（4）内存控制单元（MMU）

（5）硬件分段

（1）段选择符：标示选择哪个段，16bit
（2）段描述符：描述段的特征，8字节（64bit），可以描述一个段的具体信息（基地址，偏移等）
（3）段选择符和段描述符的关系
[段选择符和段描述符关系]
（4）逻辑地址与线性地址转换

（6）Linux中的分段

由于段描述符的base都是从0开始，所以逻辑地址的偏移量字段的值与相应的线性地址的值总是一致的。

（1）每个CPU对应一个GDT
（2）用户态进程共享或者会自定义LDT

（7）分页

（1）页框，指一组线性地址（线性地址空间）；页指包含在这组地址中的数据（对应的物理地址中的数据），每个页框可以装入一个页。
（2）线性地址转换的二级模式作用：提高效率，节省内存
（3）TLB：加速线性地址到物理地址的转换，直接将线性地址对应的物理地址加到TLB中。，加上高速缓存，弥补了内存和CPU之间的速度差异。

2.地址映射关系

（1）内核态和用户态

从进程的角度来看（每个进程都是一样的），内存主要分为内核态和用户态两部分。

（2）地址转换（二级模式为例）

3. 内存管理

（1）分页机制

优点：可以灵活分配内存，不必一定要分配大块的连续内存，但是分配时仍然倾向于分配连续内存
缺点：容易造成内存碎片，如何补救？伙伴系统。

（2）伙伴系统算法

伙伴算法主要解决的问题是外部分片问题。即频繁地请求和释放不同大小的一组连续页框，必然导致在已分配页框的块内分散了许多小块的空闲页面，由此带来的问题是，即使有足够的空闲页框可以满足请求，但要分配一个大块的连续页框可能无法满足请求。

伙伴算法（Buddy system）把所有的空闲页框分为11个块链表，每个块链表中分别包含特定的连续页框地址空间，比如第0个块链表中每个节点包含大小为2^0（页）的连续页框，第1个块链表中每个节点包含大小为2^1（页）的连续地址，….，第10个块链表中，每个链表元素代表4M的连续地址空间。每个链表中元素的个数在系统初始化时决定，在执行过程中，动态变化。

伙伴算法每次只能分配2的幂次页的空间，比如一次分配1页，2页，4页，8页，…，1024页(2^10)等等，每页大小一般为4K，因此，伙伴算法最多一次能够分配4M的内存空间。
[伙伴系统算法图解]

申请和回收过程：
申请：比如，我要分配4(2^2)页（16k）的内存空间，算法会先从free\_area[2]中查看nr\_free是否为空，如果有空闲块，则从中分配，如果没有空闲块，就从它的上一级free\_area[3]（每块32K）中分配出16K，并将多余的内存（16K）加入到free\_area[2]中去。如果free\_area[3]也没有空闲，则从更上一级申请空间，依次递推，直到free\_area[max\_order]，如果顶级都没有空间，那么就报告分配失败。
回收：回收是申请的逆过程，当释放一个内存块时，先在其对于的free\_area链表中查找是否有伙伴存在，如果没有伙伴块，直接将释放的块插入链表头。如果有或板块的存在，则将其从链表摘下，合并成一个大块，然后继续查找合并后的块在更大一级链表中是否有伙伴的存在，直至不能合并或者已经合并至最大块2^10为止。
内核试图将大小为b的一对空闲块（一个是现有空闲链表上的，一个是待回收的），合并为一个大小为2B的单独块，如果它成功合并所释放的块，它会试图合并2b大小的块。

（3）slab分配技术

作用：主要是解决在同一页框如何分配小内存（远不足一页）问题。
思想：slab分配器的基本思想是将内核中经常使用的对象放到高速缓存中，并且由系统保持为初始的可利用状态。比如进程描述符，内核中会频繁对此数据进行申请和释放。当一个新进程创建时，内核会直接从slab分配器的高速缓存中获取一个已经初始化了的对象；当进程结束时，该结构所占的页框并不被释放，而是重新返回slab分配器中。如果没有基于对象的slab分 配器，内核将花费更多的时间去分配、初始化以及释放一个对象。
slab分配器有以下三个基本目标：
1.减少伙伴算法在分配小块连续内存时所产生的内部碎片；
2.将频繁使用的对象缓存起来，减少分配、初始化和释放对象的时间开销。
3.通过着色技术调整对象以更好的使用硬件高速缓存；

**注意：伙伴系统和slab技术的目的都是为了防止内存碎片。内存碎片又分为外部碎片和内部碎片之说，所谓内部碎片（页内）是说系统为了满足一小段内存区（连续）的需要，不得不分配了一大区域连续内存给它，从而造成了空间浪费；外部碎片（页之间）是指系统虽有足够的内存，但却是分散的碎片，无法满足对大块“连续内存”的需求。slab分配器使得一个页面内包含的众多小块内存可独立被分配使用，避免了内部分片，节约了空闲内存。伙伴关系把内存块按大小分组管理，一定程度上减轻了外部分片的危害，因为页框分配不在盲目，而是按照大小依次有序进行，不过伙伴关系只是减轻了外部分片，但并未彻底消除

（4）内核虚拟内存（vmalloc）

作用：将多个不连续的物理页通过虚拟转换形成在逻辑上连续的页，可以解决外部碎片问题
应用场景：用伙伴系统分配10 x 4KB的数据时，会去16 x 4KB的空闲列表里面去找（这样得到的物理内存是连续的），但很有可能系统里面有内存，但是伙伴系统分配不出来，因为他们被分割成小的片段。那么，vmalloc就是要用这些碎片来拼凑出一个大内存，相当于收集一些“边角料”，组装成一个成品后“出售”。

4. 缺页异常

通过写实复制（cow）技术，实现将物理页真正的挂载在页框中。只有当进程真正的需要物理页时才会产生缺页异常，从而分配物理页。在实际需要某个虚拟内存区域的数据之前，和物理内存之间的映射关系不会建立。如果进程访问的虚拟地址空间部分尚未与页帧关联，处理器自动引发一个缺页异常。
尽管每个进程独立拥有3GB的可访问地址空间，但是这些资源都是内核开出的空头支票，也就是说进程手握着和自己相关的一个个虚拟内存区域(vma)，但是这些虚拟内存区域并不会在创建的时候就和物理页框挂钩，由于程序的局部性原理，程序在一定时间内所访问的内存往往是有限的，因此内核只会在进程确确实实需要访问物理内存时才会将相应的虚拟内存区域与物理内存进行关联(为相应的地址分配页表项，并将页表项映射到物理内存)，也就是说这种缺页异常是正常的，而第一种缺页异常是不正常的，内核要采取各种可行的手段将这种异常带来的破坏减到最小。
缺页异常的处理函数为do\_page\_fault()，该函数是和体系结构相关的一个函数，缺页异常的来源可分为两种，一种是内核空间(访问了线性地址空间的第4个GB)，一种是用户空间(访问了线性地址空间的0~3GB)，以X86架构为例，先来看内核空间异常的处理。

解释：
两种情况：

1. 触发异常的线性地址处于用户空间的vma中，但还未分配物理页，如果访问权限OK的话内核就给进程分配相应的物理页了
   2、触发异常的线性地址不处于用户空间的vma中，这种情况得判断是不是因为用户进程的栈空间消耗完而触发的缺页异常，如果是的话则在用户空间对栈区域进行扩展，并且分配相应的物理页，如果不是则作为一次非法地址访问来处理，内核将终结进程

说明：本文部分图片引用自以下参考资料，如有侵权，请告知。
参考资料：
[1]http://www.sohu.com/a/216719739\_236714
[2]https://www.cnblogs.com/cherishui/p/4246133.html
[3]https://my.oschina.net/fileoptions/blog/968320
[4]https://www.ibm.com/developerworks/cn/linux/l-linux-slab-allocator/
[5]http://soft.chinabyte.com/os/18/12408018.shtml
[6]https://cloud.tencent.com/developer/article/1432751
[7]深入理解Linux内核，第2/8章