C++ 八股文：内存管理

一、Linux 虚拟地址空间

概念

首先引入虚拟地址的概念，我们应该知道，平时在代码中使用的一系列函数地址、变量地址都是虚拟地址，我们使用 new 和 malloc 在堆上分配的内存，也只是为程序在虚拟内存上分配了虚拟地址。系统为了防止不同进程同一时刻在物理内存中运行而对物理内存的争夺和践踏，采用了虚拟内存。

虚拟内存技术使得不同进程在运行过程中，它所看到的是自己独自占有了当前系统的 4G 内存。所有进程共享同一物理内存，每个进程只把自己目前需要的虚拟内存空间映射并存储到物理内存上。

事实上，在每个进程创建加载时，内核只是为进程“创建”了虚拟内存的布局，具体就是初始化进程控制表中内存相关的链表，实际上并不立即就把虚拟内存对应位置的程序数据和代码，比如 .text、.data 段，拷贝到物理内存中，只是建立好虚拟内存和磁盘文件之间的映射，也就是存储器映射，等到运行到对应的程序时，才会通过缺页异常来拷贝数据。

还有进程运行过程中，要动态分配内存，比如 malloc 时，也只是分配了虚拟内存，即为这块虚拟内存对应的页表项做相应设置，当进程真正访问到此数据时，才引发缺页异常。

请求分页系统、请求分段系统和请求段页式系统都是针对虚拟内存的，通过请求实现内存与外存的信息置换。

虚拟内存的好处

  • 扩大地址空间。
  • 内存保护：每个进程运行在各自的虚拟内存地址空间，互相不能干扰对方。虚存还对特定的内存地址提供写保护，可以防止代码或数据被恶意篡改。
  • 公平内存分配。采用了虚存之后，每个进程都相当于有同样大小的虚存空间。
  • 当进程通信时，可采用虚存共享的方式实现。
  • 当不同的进程使用同样的代码时，比如库文件中的代码，物理内存中可以只存储一份这样的代码，不同的进程只需要把自己的虚拟内存映射过去就可以了，节省内存。
  • 虚拟内存很适合在多道程序设计系统中使用，许多程序的片段同时保存在内存中。当一个程序等待它的一部分读入内存时，可以把 CPU 交给另一个进程使用。在内存中可以保留多个进程，系统并发度提高。
  • 在程序需要分配连续的内存空间的时候，只需要在虚拟内存空间分配连续空间，而不需要实际物理内存的连续空间，可以利用碎片。

虚拟内存的代价

  • 虚存的管理需要建立很多数据结构，这些数据结构要占用额外的内存。
  • 虚拟地址到物理地址的转换，增加了指令的执行时间。
  • 页面的换入换出需要磁盘 I/O，这是很耗时的。
  • 如果一页中只有一部分数据，会浪费内存。

二、虚拟内存和物理内存的映射方式：页式管理内存

概念

页式内存管理，内存分成固定长度的一个个页片。操作系统为每一个进程维护了一个从虚拟地址到物理地址的映射关系的数据结构，叫页表，页表的内容就是该进程的虚拟地址到物理地址的一个映射。页表中的每一项都记录了这个页的基地址。

通过页表，由逻辑地址的高位部分先找到逻辑地址对应的页基地址，再由页基地址偏移一定长度就得到最后的物理地址，偏移的长度由逻辑地址的低位部分决定。

一般情况下，这个过程都可以由硬件完成，所以效率还是比较高的。页式内存管理的优点就是比较灵活，内存管理以较小的页为单位，方便内存换入换出和扩充地址空间。

以上的映射方式摘自一段八股文，实际内部的方式远比这一段复杂得多，感兴趣的小伙伴可以在网上找相关文章细研究一发。

三、缺页中断

概念

在上面的虚拟内存概念中，提到一个概念叫做缺页异常。缺页异常和缺页中断实际上指的一回事。

进程创建初期或是使用 malloc、new 分配内存时，只是先建立了虚拟内存到物理内存的映射，只有程序在第一次使用到该内存时，系统才会将实际的物理内存块从外存移动到进程内存中。而在访问第一次使用到的内存时，由于进程中还未加载该部分物理内存，则会产生一个异常，从而触发中断来处理这个异常。这个异常就是缺页异常，这个中断就是缺页中断。

缺页中断本身是一种中断，与一般的中断一样，需要经过 4 个处理步骤：

  1. 保护 CPU 现场。
  2. 分析中断原因。
  3. 转入缺页中断处理程序进行处理。在缺页中断的处理程序中，操作系统会根据页表中的外存地址在外存中找到所缺的一页，将其调入内存。
  4. 恢复 CPU 现场，继续执行。

但是缺页中断是由于所要访问的页面不存在于内存时，由硬件所产生的一种特殊的中断，因此，与一般的中断存在区别：

  • 在指令执行期间产生和处理缺页中断信号。
  • 一条指令在执行期间，可能产生多次缺页中断。
  • 缺页中断返回时，执行产生中断的一条指令，而一般的中断返回是执行下一条指令。

四、OS 缺页置换算法

概念

在处理缺页异常时，会做一个将物理内存块从外存移动到进程内存中的操作，但是进程存储内存物理帧，也就是物理内存块，的空间并不是无限大的。当这个空间满时，如果想将需要的内存块插入到内存中，就需要先从内存中取出一个内存块来获得空间。而如何选择换出的内存，就涉及到多种 OS 缺页置换算法。

当前操作系统最常采用的缺页置换算法如下：

  • 先进先出 FIFO 算法：置换最先调入内存的页面，即置换在内存中驻留时间最久的页面。按照进入内存的先后次序排列成队列，从队尾进入，从队首删除。
  • 最近最少使用 LRU 算法：置换最近一段时间以来最长时间未访问过的页面。根据程序局部性原理，刚被访问的页面，可能马上又要被访问；而较长时间内没有被访问的页面，可能最近不会被访问。
  • LFU 算法：该算法根据数据的历史访问频率来淘汰数据，其核心思想是“如果数据过去被访问多次，那么将来被访问的频率也更高”。优先淘汰访问次数最少的内存块，如果访问次数相同，则淘汰最久未使用的那一块。

缺页置换的算法还有很多，感兴趣的小伙伴可以继续参考相关资料。

关于 LRU 和 LFU 算法，这两个算法也属于比较经典的笔试题目，建议掌握到能手撕的程度。

    1. LFU 缓存
    1. LRU 缓存机制