内存管理(mmu)/内存分配原理/多级页表

1.为什么要做内存管理？

随着进程对内存需求的扩大，和同时调度的进程增加，内存是比较瓶颈的资源，如何更好的高效的利于存储资源是一个重要问题。

这个内存管理的需求也是慢慢发展而来，早期总线上的master是直接使用物理地址，再到发展出对CPU进行内存管理的MMU，到现在给SOC内部的各个具有DMA功能的模块进行内存管理的IOMMU或者叫做SMMU

在没有内存管理的时代，物理空间只能连续的使用，一个进程要用多少存储，在进程开始就确定好了，但是进程在运行过程中由于程序局部性的原理，在一段时间内可能只使用了分配好的内存的一部分，其余大部分时间都是空闲的；另外一个问题就是在分配内存过程中会出现一些小的且不连续的内存空间，这些空间(内存碎片)无法满足任何进程的使用，造成了一定的空间浪费。

所以内存管理解决的就是就是两个问题：

让进程在运行过程中动态分配存储空间，即根据需求在运行过程中不断的分配空间【这同时促进了多级页表的产生】，而不需要一次分配很大的空间，这样可以提高进程并行调度能力
降低空间碎片的产生

内存管理采用虚拟地址到物理地址的映射，这种用虚拟空间来隔离进程的做法又促进了虚拟化/虚拟机【VM】的发展，本文先不讨论VM。

1.1 内存碎片

内存碎片是由内存的申请和释放产生的，通常分为内部碎片和外部碎片。

内部碎片是由于采用固定大小的内存分区，即以固定的大小块为单位来分配，采用这种方法，进程所分配的内存可能会比所需要的大，这多余的部分便是内部碎片。
外部碎片是由于未分配的连续内存区域太小，以至于不能满足任意进程所需要的内存分配请求，这些小片段且不连续的内存空间被称为外部碎片。

2.内存管理算法

linux每一个用户进程都对应有自己的页表，我们不禁要问这些页表或者说物理空间是如何分配的？为什么每个进程对应一个页表？

通俗的来讲，每一个用户进程看到的都是一样大小的虚拟空间，所以它们并不知道实际可用的物理地址有哪些。【物理地址空间的管理和分配是一个独立于这些用户进程的，实际是OS操作系统管理的】当运行一个新的进程时,OS根据当前可用的PA【OS知道哪些PA正在被使用】，建立VA到PA的映射，也就是产生一个新的对应该进程的页表【每一个进程运行时当前可用PA都是不一样的，所以每个进程都要自己的页表】。

2.1内存管理的伙伴系统算法

linux使用的时伙伴系统来管理和分配内存

Linux内核使用二进制伙伴算法来管理和分配物理内存页面, 该算法由Knowlton设计, 后来Knuth又进行了更深刻的描述.
伙伴系统是一个结合了2幂次个分配器和空闲缓冲区合并计技术的内存分配方案, 其基本思想很简单. 内存被分成含有很多页面的大块, 每一块都是2^n个页面大小. 如果找不到想要的块, 一个大块会被分成两部分, 这两部分彼此就成为伙伴. 其中一半被用来分配, 而另一半则空闲. 这些块在以后分配的过程中会继续被二分直至产生一个所需大小的块. 当一个块被最终释放时, 其伙伴将被检测出来, 如果伙伴也空闲则合并两者.

具体的算法请参考本人的转载文章：

内存管理之伙伴系统分析-CSDN博客

3.多级页表及节省内存

页表：是存储PTE的一个内存分页，而PTE是描述VA与PA映射关系的entry。

多级页表结构分为PGD/PUD/PMD/PTE这几个层级，P代表page，G代表global，D代表目录（Director），U代表上级，M代表中间，T代表Table，E代表Entry，所以：

PGD：page global director

PUD：page upper director

PMD：page middle director

PTE：page table entry

PTE是页表项。他们之间的关系是层级结构，通过PGD访问到最低端的PTE，访问方式是上一层地址+偏移量(offset）。PTE+页内偏移量可以访问到具体的物理地址。

为什么要建立多级页表的结构呢？

先给出结论【经过确认的结论】就是多级页表是为了节省页表的存储空间。

举个例子，4GB的DDR空间，4KB的页大小，一个PTM 4B,总共需要4GB/4K=1M个PTE，如果每个进程都要产生并存储一个1Mx4B的PTE，就会占用不少内存空间。

只要进程需要寻址4GB内存空间的能力，无论建立多少级的页表，最终都需要1Mx4B的PTE，在加上多出来的几级页表存储空间只会更多，那么为什么会说多级页表可以节省内存空间呢？

在这里先做一个统一，最底层的PTE这一级我们叫做第一级，PMD，PUD，PGD分别是第二/三/四级【这里PMD/PUD只是一个相对的层级，可能代表有多个中间层和上层，也可能没有，这里假设每一个就代表一层】，这样最底层为底层的话，无论增加多少层它的叫法不变。

写到这里有一个问题：页表既然是存在内存中的，那么有没有为页表空间建立页表？

其实多级页表可以理解为对上级页表对下级页表建立的页表，比如只有两级页表，配置了第二级页表的基地址，我们可以用虚拟地址的高位来映射第一级页表的物理地址。这样就可以理解高层页表是为了底层页表能够不连续的存储

多级页表的好处是可以将PTE分散存储，而不是用连续的物理地址存储。即使只有一级的PTE页表，也可以根据程序运行的局部特性只在特定时刻生成一部分PTE页表，但关键不在于只生成一部分的PTE，而是只有一级页表的话需要连续物理地址空间，即使只生成一部分的PTE，这1Mx4B的地址空间也不能给别人用。【这一原因也是很多文章没有说清楚的地方】

另外多级页表还有一个优势，就是可以将那些不常用的低级页表swap out到硬盘中，当进程再次访问到该页表映射的物理内存是，内核将页表从硬盘中swap in到内存中。当然最顶层的PGD页表是必须常驻内存的。

既然多级页表也是存储在DDR的页上的数据，那么和其他数据一样就可以经过cache来高速缓存，其对应的高速缓存cache就是TLB(translation lookaside buffer，转换后备缓冲区，又常被称为快表)。这里不在详细介绍。

总结起来多级页表能够节省内存空间的原因如下：