linux内存管理(1)

Linux内存管理（1）

虚拟内存

我们知道一个进程是与其他进程共享CPU和内存资源的。为了防止进程之间内存泄漏的问题，现代操作系统提供了一种对主存的抽象概念，即是虚拟内存（Virtual Memory）。虚拟内存为每个进程提供了一个一致的、私有的地址空间，它让每个进程产生了一种自己在独享主存的错觉（每个进程拥有一片连续完整的内存空间）。

因为使用虚拟地址可以带来诸多好处：

在支持多进程的系统中，如果各个进程的镜像文件都使用物理地址，则在加载到同一物理内存空间的时候，可能发生冲突。
直接使用物理地址，不便于进行进程地址空间的隔离。
物理内存是有限的，在物理内存整体吃紧的时候，可以让多个进程通过分时复用的方法共享一个物理页面（某个进程需要保存的内容可以暂时swap到外部的disk/flash），这有点类似于多线程分时复用共享CPU的方式。

既然使用虚拟地址，就涉及到将虚拟地址转换为物理地址的过程，也即CPU寻址。

CPU寻址

内存通常被组织为一个由M个连续的字节大小的单元组成的数组，每个字节都有一个唯一的物理地址（Physical Address PA），作为到数组的索引。CPU访问内存最简单直接的方法就是使用物理地址，这种寻址方式被称为物理寻址。

现代处理器使用的是一种称为虚拟寻址（Virtual Addressing）的寻址方式。使用虚拟寻址，CPU需要将虚拟地址翻译成物理地址，这样才能访问到真实的物理内存。它需要MMU（Memory Management Unit）和页表（page table）的共同参与。

MMU

MMU是处理器/核（processer）中的一个硬件单元，通常每个核有一个MMU。它的功能是将虚拟地址转换为物理地址。MMU需要借助存放在内存中的页表(page table)来动态翻译虚拟地址，该页表由操作系统管理。

MMU由两部分组成：TLB(Translation Lookaside Buffer)和table walk unit。

Page Table

page table是每个进程独有的，是软件实现的，是存储在main memory（比如DDR）中的。所谓页表就是一个存放在物理内存中的数据结构，它记录了虚拟页与物理页的映射关系。

页表是一个元素为页表条目（Page Table Entry, PTE）的集合，每个虚拟页在页表中一个固定偏移量的位置上都有一个PTE。下面是PTE仅含有一个有效位标记的页表结构，该有效位代表这个虚拟页是否被缓存在物理内存中。

虚拟页VP 0、VP 4、VP 6、VP 7被缓存在物理内存中，虚拟页VP 2和VP 5被分配在页表中，但并没有缓存在物理内存，虚拟页VP 1和VP 3还没有被分配。

在进行动态内存分配时，例如malloc()函数或者其他高级语言中的new关键字，操作系统会在硬盘中创建或申请一段虚拟内存空间，并更新到页表（分配一个PTE，使该PTE指向硬盘上这个新创建的虚拟页）。

页命中

如下图所示，MMU根据虚拟地址在页表中寻址到了PTE 4，该PTE的有效位为1，代表该虚拟页已经被缓存在物理内存中了，最终MMU得到了PTE中的物理内存地址（指向PP 1）。

缺页

如下图所示，MMU根据虚拟地址在页表中寻址到了PTE 2，该PTE的有效位为0，代表该虚拟页并没有被缓存在物理内存中。虚拟页没有被缓存在物理内存中（缓存未命中）被称为缺页。

当CPU遇见缺页时会触发一个缺页异常，缺页异常将控制权转向操作系统内核，然后调用内核中的缺页异常处理程序，该程序会选择一个牺牲页，如果牺牲页已被修改过，内核会先将它复制回硬盘（采用写回机制而不是直写也是为了尽量减少对硬盘的访问次数），然后再把该虚拟页覆盖到牺牲页的位置，并且更新PTE。

当缺页异常处理程序返回时，它会重新启动导致缺页的指令，该指令会把导致缺页的虚拟地址重新发送给MMU。由于现在已经成功处理了缺页异常，所以最终结果是页命中，并得到物理地址。

这种在硬盘和内存之间传送页的行为称为页面调度（paging）：页从硬盘换入内存和从内存换出到硬盘。当缺页异常发生时，才将页面换入到内存的策略称为按需页面调度（demand paging），所有现代操作系统基本都使用的是按需页面调度的策略。

虚拟内存跟CPU高速缓存（或其他使用缓存的技术）一样依赖于局部性原则。虽然处理缺页消耗的性能很多（毕竟还是要从硬盘中读取），而且程序在运行过程中引用的不同虚拟页的总数可能会超出物理内存的大小，但是局部性原则保证了在任意时刻，程序将趋向于在一个较小的活动页面（active page）集合上工作，这个集合被称为工作集（working set）。根据空间局部性原则（一个被访问过的内存地址以及其周边的内存地址都会有很大几率被再次访问）与时间局部性原则（一个被访问过的内存地址在之后会有很大几率被再次访问），只要将工作集缓存在物理内存中，接下来的地址翻译请求很大几率都在其中，从而减少了额外的硬盘流量。

如果一个程序没有良好的局部性，将会使工作集的大小不断膨胀，直至超过物理内存的大小，这时程序会产生一种叫做抖动（thrashing）的状态，页面会不断地换入换出，如此多次的读写硬盘开销，性能自然会十分“恐怖”。所以，想要编写出性能高效的程序，首先要保证程序的时间局部性与空间局部性。

多级页表

上面讨论的只是单页表，但在实际的环境中虚拟空间地址都是很大的（一个32位系统的地址空间有2^32 = 4GB，更别说64位系统了）。在这种情况下，使用一个单页表明显是效率低下的，而且非常占内存空间。

常用方法是使用层次结构的页表。

假设我们的环境为一个32位的虚拟地址空间，它有如下形式：

虚拟地址空间被分为4KB的页，每个PTE都是4字节。
内存的前2K个页面分配给了代码和数据。
之后的6K个页面还未被分配。
再接下来的1023个页面也未分配，其后的1个页面分配给了用户栈。

下图是为该虚拟地址空间构造的二级页表层次结构（真实情况中多为四级或更多），一级页表（1024个PTE正好覆盖4GB的虚拟地址空间，同时每个PTE只有4字节，这样一级页表与二级页表的大小也正好与一个页面的大小一致都为4KB）的每个PTE负责映射虚拟地址空间中一个4MB的片（chunk），每一片都由1024个连续的页面组成。二级页表中的每个PTE负责映射一个4KB的虚拟内存页面。

这个结构看起来很像是一个B-Tree，这种层次结构有效的减缓了内存要求：

如果一个一级页表的一个PTE是空的，那么相应的二级页表也不会存在。这代表一种巨大的潜在节约（对于一个普通的程序来说，虚拟地址空间的大部分都会是未分配的）。
只有一级页表才总是需要缓存在内存中的，这样虚拟内存系统就可以在需要时创建、页面调入或调出二级页表（只有经常使用的二级页表才会被缓存在内存中），这就减少了内存的压力。

TLB

表是被缓存在内存中的，尽管内存的速度相对于硬盘来说已经非常快了，但与CPU还是有所差距。为了防止每次地址翻译操作都需要去访问内存，CPU使用了高速缓存与TLB来缓存PTE。CPU会首先在TLB中查找，因为在TLB中找起来很快。TLB之所以快，一是因为它含有的entries的数目较少，二是TLB是集成进CPU的，它几乎可以按照CPU的速度运行。

TLB（Translation Lookaside Buffer, TLB）旁路缓冲器,或叫做页表缓存，它是MMU中的一个缓冲区。

TLB命中：

第一步，CPU将一个虚拟地址交给MMU进行地址翻译。
第二步和第三步，MMU通过TLB取得相应的PTE。
第四步，MMU通过PTE翻译出物理地址并将它发送给高速缓存/内存。
第五步，高速缓存返回数据到CPU（如果缓存命中的话，否则还需要访问内存）。

TLB未命中:

当TLB未命中时，MMU必须从高速缓存/内存中取出相应的PTE，并将新取得的PTE存放到TLB（如果TLB已满会覆盖一个已经存在的PTE）。如下图：

综上，整个cpu寻址的过程可以用下图表示：

如果在TLB中找到了含有该虚拟地址的entry（TLB hit），则可从该entry【1】中直接获取对应的物理地址，否则就不幸地TLB miss了，就得去查找当前进程的page table。这个时候，组成MMU的另一个部分table walk unit就被召唤出来了，这里面的table就是page table。

如果在page table中找到了该虚拟地址对应的entry的p（present）位是1，说明该虚拟地址对应的物理页面当前驻留在内存中，也就是page table hit。找到了还没完，接下来还有两件事要做：

既然是因为在TLB里找不到才找到这儿来的，自然要更新TLB。
进行权限检测，包括可读/可写/可执行权限，user/supervisor模式权限等。如果没有正确的权限，将触发SIGSEGV（Segmantation Fault）。

如果该虚拟地址对应的entry的p位是0，就会触发page fault（缺页中断），可能有这几种情况：

这个虚拟地址被分配后还从来没有被access过（比如malloc之后还没有操作分配到的空间，则不会真正分配物理内存）。触发page fault后分配物理内存，也就是demand paging，有了确定的demand了之后才分，然后将p位置1。
对应的这个物理页面的内容被换出到外部的disk/flash了，这个时候page table entry里存的是换出页面在外部swap area里暂存的位置，可以将其换回物理内存，再次建立映射，然后将p位置1。

如果这个虚拟地址在进程的page table中根本不存在，说明这个虚拟地址不在该进程的地址空间中，这时也会触发segmantation fault。

HugePage

上面中提到使用多级页表的方式对于减少页表自身占用的内存空间确实是非常有效的。然而，为此付出的代价就是增加了地址转换过程中对内存的访问次数，进而增加了转换时间。那在除了前面介绍的TLB之外，还有哪些可以减少内存访问次数，加快地址转换的方法呢？HugePage即可以。

而HugePage它是使用较大的内存页来代替默认的4k大小，这就意味相同的物理内存，内存页的数量会更少，所以需要的page table（页表条目也会变少），同样TLB的条目数也会变少。
好处是：
节约了页表所占用的内存大小，并且地址转换变少。所以缺页中断变少，TLBmiss变少。从而提高了内存访问性能、TLB命中率，从整体上提高了系统的效率。

另外，由于地址转换所需的信息一般保存在CPU的缓存中，huge page的使用让地址转换信息减少，从而减少了CPU缓存的使用，减轻了CPU缓存的压力，让CPU缓存能更多地用于应用程序的数据缓存，也能够在整体上提升系统的性能。