Linux系列：内存管理 | 飙戈的博客

type

status

date

slug

summary

虚拟内存

如果进程可以直接使用绝对物理地址，容易造成同一个物理地址被两个不同的进程同时占用，从而导致进程出错的问题。解决办法是，

操作系统为每个进程分配独立的一套「虚拟地址」，然后操作系统会提供一种机制，将不同进程的虚拟地址和不同内存的物理地址映射起来

。如果程序要访问虚拟地址的时候，由操作系统转换成不同的物理地址，这样不同的进程运行的时候，写入的是不同的物理地址，这样就不会冲突了。这就是虚拟内存。

虚拟内存的工作过程：进程只持有虚拟内存地址，然后会通过 CPU 芯片中的内存管理单元(MMU)的映射关系，来转换变成物理内存地址，然后再通过物理内存地址访问内存。

内存分页管理

按照虚拟内存和物理内存的映射形式，可以分为：

内存分段

内存分页

内存分段

在内存分段的机制下，虚拟内存和物理内存通过 内存段表 进行映射。

把虚拟内存地址分为段选择子和段内偏移量。

段选择子就保存在段寄存器里面。段选择子里面最重要的是段号，用作段表的索引。

段内偏移量应该位于 0 和段界限之间，将段基地址加上段内偏移量得到物理内存地址。

将段表划分为这个段基地址、段界限和特权等级等，每一项段表项对应虚拟内存地址的一个段号。

分段机制会把程序的虚拟地址分成 4 个段，每个段在段表中有一个。虚拟内存地址通过段号在段表找到对应项的段基地址，再加上段内偏移量，即可就能找到物理内存中的地址。

内存分段会有两个问题：

第一个就是内存碎片的问题。

第二个就是内存交换的效率低的问题。

内存分页

为了解决内存分段的问题，后面就出现了内存分页。分⻚是把整个虚拟和物理内存空间切成一段段固定尺寸的大小。这样一个连续并且尺寸固定的内存空间，我们叫⻚(Page)。在 Linux 下，每一⻚的大小为 4KB 。虚拟地址与物理地址之间通过⻚表来映射。

在内存分页机制，虚拟内存和物理内存通过 内存页表 进行映射。

虚拟地址分为两部分：⻚号和⻚内偏移。⻚号作为⻚表的索引，页内偏移量等于物理地址上的偏移量。

⻚表分为虚拟页号和物理页号，虚拟页号对应虚拟地址的页号，物理⻚对应物理内存的基地址。

虚拟地址根据⻚号，从⻚表里面，查询对应的物理⻚号，再加上页内偏移量就得到了物理内存地址。

而且在分⻚的形式下，我们在加载程序的时候，不再需要一次性都把程序加载到物理内存中。我们只需要在进行虚拟内存和物理内存的⻚之间完成映射，而不用真的把⻚加载到物理内存里。

只有在程序运行中，需要用到对应虚拟内存⻚里面的指令和数据时，再加载到物理内存里面去

。

内存的加载和释放都是以页为单位的：

将分页从物理内存写入硬盘，称为换出(Swap Out)。

将内存从硬盘写入物理内存，称为换入(Swap In)。

多级页表

内存分页虽然解决了内存分段的碎片化问题，但是也存在空间消耗上的问题。

上面我们提到 linux 下的分页大小是 4KB，假如每一页对应的页表项大小为 4 个字节，那么分页和页表项的大小对比比例就是1000:1，换而言之，总内存和页表的大小对比比例就是1000:1。

假如32位系统下系统内存是4G，页表项大小为 4 个字节，那么就需要2^20个页表项，对应的页表大小就是4MB。因为每个进程都有单独的页表，假如有100个进程，就需要 400MB 的内存来存储⻚表。这是比较高的空间消耗了。

为了解决空间消耗的问题，提出多级⻚表(Multi-Level Page Table)的解决方案。

把 2^20 个「⻚表项」的单级⻚表进行二次分⻚：

一级页表包含1024个页表项，每项指向一个二级页表地址。

二级页表也包含1024个页表项，每项指向物理内存地址。

虚拟地址同时包含一级页号和二级页号。

理论上，使用二级页表需要的内存空间好像更多了，需要 4KB(一级⻚表)+ 4MB(二级⻚表)，但实际情况是：

一个进程往往用不到那么多内存，部分对应的⻚表项都是空的，根本没有分配，我们可以在进程真的用到内存的时候再分配内存。但是不管进程用了多少内存，⻚表映射一定要覆盖全部虚拟内存地址

。

如果使用单个页表就需要有 2^20 个⻚表项来映射全部虚拟内存地址。使用二级页表的话，

一级页表只需要 1024 个页表项就可以映射全部虚拟内存地址，二级页表在需要用到的时候再进行创建

。

二级分⻚再推广到多级⻚表，就会发现⻚表占用的内存空间更少了，例如 64 位的系统下变成了四级目录：

全局⻚目录项 PGD(Page Global Directory)

上层⻚目录项 PUD(Page Upper Directory)

中间⻚目录项 PMD(Page Middle Directory)

⻚表项 PTE(Page Table Entry)

TLB

多级页表虽然解决了单表带来的空间消耗的问题，但是如果每次查找虚拟内存地址对应的物理内存地址都要经过多次查找，就会带来效率上的问题。

程序是有局部性的，即在一段时间内，整个程序的执行仅限于程序中的某一部分。相应地，执行所访问的存储空间也局限于某个内存区域。利用这一特性，把程序最常访问的⻚表项存到 Cache 然后放到 CPU 里面，这个 Cache 就是 TLB(Translation Lookaside Buffer)。

有了 TLB 后，CPU 在通过 MMU 查找物理内存地址的时候，先查 TLB，如果没找到，才会继续查常规的⻚表。

Linux内存管理

虚拟内存和物理内存

linux 下也分为虚拟内存和物理内存，虚拟内存是为了满足物理内存的不足而提出的策略，它是利用磁盘空间虚拟出的一块逻辑内存。用作虚拟内存的磁盘空间被称为交换空间（又称 swap 空间）。

Linux 会在物理内存不足时，使用「最近最经常使用」算法，将一些不经常使用的页面文件写到 swap 区，这样一来，物理内存得到了释放，这块内存就可以用于其他目的；当需要用到原始的内容时，这些信息会被重新从 swap 区读入物理内存。

但内存交换也不一定在内存不足的时候才发生，Linux 系统会不时地进行页面交换操作，以保持尽可能多的空闲物理内存。即使并没有什么事情需要内存，Linux 也会交换出暂时不用的内存页面，因为这样可以大大节省等待交换所需的时间。有时我们会看到这么一个现象，Linux 物理内存还有很多，但是 swap 区也使用了很多，其实这并不奇怪。例如，一个占用很大内存的进程运行时，需要耗费很多内存资源，此时就会有一些不常用页面文件被交换到虚拟内存中，但后来这个占用很多内存资源的进程结束并释放了很多内存时，刚才被交换出去的页面文件并不会自动交换进物理内存（除非有这个必要），那么此时系统物理内存就会空闲很多，同时交换空间也在被使用，就出现了刚才所说的现象了。

但现在 swap 区用的比较少，频率的内存交换会影响系统的性能，一些服务器甚至会禁用掉 swap 区的功能。一般情况下，如果已经用到 swap 区说明硬件配置已经不太够了，需要升级硬件了。

分页管理

Linux 的内存管理采取的是分页管理，但是也涉及一点分段的概念。

Linux 系统中的每个段都是从 0 地址开始的整个 4GB 虚拟空间(32 位环境下)，也就是所有的段的虚拟地址空间都是一样的

。这意味着，Linux 系统中的代码，包括操作系统本身的代码和应用程序代码，所面对的地址空间都是线性地址空间(虚拟地址)，这种做法相当于屏蔽了处理器中的逻辑地址概念，段只被用于访问控制和内存保护。

虚拟地址空间的内部又被分为内核空间和用户空间两部分，分别对应着下图中， CPU 特权等级的 Ring 0 和 Ring 3。

内核空间（Ring 0）具有最高权限，可以直接访问所有资源；

用户空间（Ring 3）只能访问受限资源，不能直接访问内存等硬件设备，必须通过系统调用陷入到内核中，才能访问这些特权资源。

虽然每个进程都各自有独立的虚拟内存，但是每个虚拟内存中的内核地址关联的都是相同的物理内存。这样，进程切换到内核态后，就可以访问相同的内核空间内存。

不同位数的系统，地址空间的范围也不同。比如最常⻅的 32 位和 64 位系统：

32 位系统的内核空间占用 1G ，位于最高处，剩下的 3G 是用户空间;

64 位系统的内核空间和用户空间都是 128T ，分别占据整个内存空间的最高和最低处，剩下的中间部分是未定义的。

缺页异常

当 CPU 访问的⻚面不在物理内存时，便会产生一个缺页异常（Page Fault），请求操作系统将所缺⻚调入到物理内存。

在 CPU 里访问一条 Load M 指令，然后 CPU 会去找 M 所对应的⻚表项。

如果该⻚表项的状态位是「有效的」，那 CPU 就可以直接去访问物理内存了，如果状态位是「无效的」，则 CPU 则会发送缺⻚中断请求。

操作系统收到了缺⻚中断，则会执行缺⻚中断处理函数，先会查找该⻚面在磁盘中的⻚面的位置。

找到磁盘中对应的⻚面后，需要把该⻚面换入到物理内存中，但是在换入前，需要在物理内存中找空闲⻚，如果找到空闲⻚，就把⻚面换入到物理内存中。

⻚面从磁盘换入到物理内存完成后，则把⻚表项中的状态位修改为「有效的」。

最后，CPU 重新执行导致缺⻚异常的指令。

缺页异常触发通常有两三种情况：

地址空间映射关系未建立

malloc/mmap申请虚拟的地址空间并未分配实际物理页，首次访问触发缺页异常。

地址空间映射关系已建立

要访问的页面已经被swapping到了磁盘，访问时触发缺页异常。

fork子进程时，子进程共享父进程的地址空间，写是触发缺页异常(COW技术)。

要访问的页面被KSM合并，写时触发缺页异常(COW技术)。

兼容的ARM32体系架构模拟PTE_DIRTY PTE_YOUNG比特。

访问的地址空间不合法

用户空间访问内核空间地址，触发缺页异常。

内核空间访问用户空间地址，触发缺页异常。(不包括copy_to/from_user的情况)

内存页面置换算法

上面提到处理缺页中断的过程中，会在物理内存找到一个空闲⻚载入磁盘上的内存页。如果此时内存满了，就需要一个内存页面置换算法来腾出内存页，选择一个合适的内存页写入磁盘。常⻅的⻚面置换算法有如下几种：

最佳⻚面置换算法(OPT)

先进先出置换算法(FIFO)

最近最久未使用的置换算法(LRU)

时钟⻚面置换算法(CLock)

最不常用置换算法(LFU)

最佳⻚面置换算法

最佳⻚面置换算法(OPT)的思路是：置换在「未来」最⻓时间不访问的⻚面。

在这个请求的⻚面序列中，缺⻚共发生了 7 次(空闲⻚换入 3 次 + 最优⻚面置换 4 次)，⻚面置换共发生了 4 次。

但由于人们目前无法预知进程在内存下的若千页面中哪个是未来最长时间内不再被访问的，因而该算法无法实现。最佳置换算法可以用来评价其他算法的效率。

先进先出算法

先进先出置换算法(FIFO)的思路：置换在内存驻留时间最⻓的⻚面。

在这个请求的⻚面序列中，缺⻚共发生了 10 次，⻚面置换共发生了 7 次，跟最佳⻚面置换算法比较起来，性能明显差了很多。

最近最久未使用算法

最近最久未使用的置换算法(LRU)的思路：置换最⻓时间没有被访问的⻚面。

在这个请求的⻚面序列中，缺⻚共发生了 9 次，⻚面置换共发生了 6 次，跟先进先出置换算法比较起来，性能提高了。

最近最久未使用算法近似于最优置换算法，最优置换算法是通过「未来」的使用情况来推测要淘汰的⻚面，而 LRU 则是通过「历史」的使用情况来推测要淘汰的⻚面。

虽然 LRU 在理论上是可以实现的，但实现起来比较困难：为了完全实现 LRU，需要在内存中维护一个所有⻚面的链表，页面按照「最近访问时间」排序，最近最多访问的⻚面在表头，最近最少访问的⻚面在表尾。每次访问内存的时候都要遍历整个链表找到指定页面，然后把他移动到表头。

所以，LRU 虽然看上去不错，但是由于开销比较大，实际应用中比较少使用。

时钟置换算法

LRU算法的性能接近于OPT，但是实现起来比较困难，且开销大；FIFO算法实现简单，但性能差。时钟⻚面置换算法(CLock)结合了两者的优点，现代操作系统置换算法很多都是时钟⻚面置换算法的变体。

时钟⻚面置换算法(CLock)的思路是：把所有的⻚面都保存在一个类似钟面的「环形链表」中，一个表针指向最老的⻚面。当发生缺⻚中断时，算法首先检查表针指向的⻚面：

如果它的访问位位是 0 就淘汰该⻚面，并把新的⻚面插入这个位置，然后把表针前移一个位置。

如果访问位是 1 就清除访问位，并把表针前移一个位置，重复这个过程直到找到了一个访问位为 0 的⻚面为止。

最不常用算法

最不常用置换算法(LFU)的思路：置换访问次数最少的页面。

它的实现方式是：对每个⻚面设置一个「访问计数器」，每当一个⻚面被访问时，该⻚面的访问计数器就累加 1。在发生缺⻚中断时，淘汰计数器值最小的那个⻚面。

但实际问题是：

如果要对这个计数器查找哪个⻚面访问次数最小，查找链表本身，如果链表⻓度很大，是非常耗时的，效率不高。

只考虑了频率问题，没考虑时间的问题，比如有些⻚面在过去时间里访问的频率很高，但是现在已经没有访问了，而当前频繁访问的⻚面由于没有这些⻚面访问的次数高，在发生缺⻚中断时，就会可能会误伤当前刚开始频繁访问，但访问次数还不高的⻚面。

由于最不常用算法效率不高，命中率也不高，实际很少应用。