内存管理

导读

• 物理内存是操作系统需要管理的一个重要资源，让运行在一台机器上的多个应用程序不用“争抢”，都能随时得到想要的任意多的内存，是操作系统的想要达到的理想目标。提高系统物理内存的动态使用效率，通过隔离应用的物理内存空间保证应用间的安全性，把“有限”物理内存变成“无限”虚拟内存，是操作系统的一系列重要的目标，本章展现了操作系统为实现“理想”而要扩展的一系列功能

  • 通过动态内存分配，提高了应用程序对内存的动态使用效率
  • 通过页表的虚实内存映射机制，简化了编译器对应用的地址空间设置
  • 通过页表的虚实内存映射机制，加强了应用之间，应用与内核之间的内存隔离，增强了系统安全
  • 通过页表的虚实内存映射机制，可以实现空分复用（提出，但没有实现）

• 上一章，我们分别实现了多道程序和分时多任务系统，它们的核心机制都是任务切换。由于多道程序和分时多任务系统的设计初衷不同，它们在任务切换的时机和策略也不同。有趣的一点是，任务切换机制对于应用是完全透明(Transparent)的，应用可以不对内核实现该机制的策略做任何假定（除非要进行某些针对性优化），甚至可以完全不知道这机制的存在

• 在大多数应用（也就是应用开发者）的视角中，它们会独占一整个 CPU 和特定（连续或不连续）的内存空间（平时写程序还真是这样）

• 当然，通过上一章的学习，我们知道在现代操作系统中，出于公平性的考虑，我们极少会让独占CPU这种情况发生

• 所以应用自认为的独占CPU只是内核想让应用看到的一种幻象(Illusion)，而CPU计算资源被时分复用(TDM, Time-Division Multiplexing)的实质被内核通过恰当的抽象隐藏了起来，对应用不可见

• 与之相对，我们目前还没有对内存管理功能进行进一步拓展，仅仅是把程序放到某处的物理内存中

  • 在内存访问方面，所有的应用都直接通过物理地址访问物理内存，这使得应用开发者需要了解繁琐的物理地址空间布局，访问内存也很不方便

• 在上一章中，出于任务切换的需要，所有的应用都在初始化阶段被加载到内存中并同时驻留下去直到它们全部运行结束。而且，所有的应用都直接通过物理地址访问物理内存。这会带来以下问题：

  • 首先，内核提供给应用的内存访问接口不够透明，也不好用

    • 由于应用直接访问物理内存，这需要它在构建的时候就清楚所运行计算机的物理内存空间布局，还需规划自己需要被加载到哪个地址运行
    • 为了避免冲突可能还需要应用的开发者们对此进行协商，这显然是一件在今天看来不够通用且极端麻烦的事情

  • 其次，内核并没有对应用的访存行为进行任何保护措施，每个应用都有计算机系统中整个物理内存的读写权力

    • 即使应用被限制在 U 特权级下运行，它还是能够造成很多麻烦：比如它可以读写其他应用的数据来窃取信息或者破坏其它应用的正常运行（很危险！）

    • 甚至它还可以修改内核的代码段来替换掉原本的 trap_handler 函数，来挟持内核执行恶意代码。总之，这造成系统既不安全、也不稳定

  • 再次，目前应用的内存使用空间在其运行前已经限定死了，内核不能灵活地给应用程序提供的运行时动态可用内存空间

    • 比如一个应用结束后，这个应用所占的空间就被释放了，但这块空间无法动态地给其它还在运行的应用使用

• 因此，为了简化应用开发，防止应用胡作非为，本章将更好地管理物理内存，并提供给应用一个抽象出来的更加透明易用、也更加安全的访存接口，这就是基于分页机制的虚拟内存

  • 站在应用程序运行的角度看，就是存在一个从“0”地址开始的非常大的可读/可写/可执行的地址空间(Address Space)

  • 站在操作系统的角度看，每个应用被局限在分配给它的物理内存空间中运行，无法读写其它应用和操作系统所在的内存空间

• 实现地址空间的第一步就是实现分页机制，建立好虚拟内存和物理内存的页映射关系。此过程需要硬件支持，硬件细节与具体CPU相关，涉及地址映射机制等，相对比较复杂。总体而言，我们需要思考如下问题

  • 硬件中物理内存的范围是什么？

  • 哪些物理内存空间需要建立页映射关系？

  • 如何建立页表使能分页机制？

  • 如何确保OS能够在分页机制使能前后的不同时间段中都能正常寻址和执行代码？

  • 页目录表（一级）的起始地址设置在哪里？

  • 二级/三级等页表的起始地址设置在哪里，需要多大空间？

  • 如何设置页目录表项/页表项的内容？

  • 如果要让每个任务有自己的地址空间，那每个任务是否要有自己的页表？

  • 代表应用程序的任务和操作系统需要有各自的页表吗？

  • 在有了页表之后，任务和操作系统之间应该如何传递数据？

• 虚拟内存（Virtual memory）技术概念首次由德国的柏林工业大学（Technische Universität Berlin）博士生 Fritz-Rudolf Güntsch 提出
• 在他的博士论文中设想了一台计算机，其内存地址空间大小为$ 10^5 $个字，可精确映射到作为二级存储的磁鼓（大小也为$ 10^5 $个字）上，应用程序读写的数据的实际位置由硬件和监控器（即操作系统）来管理和控制，并在物理主存(RAM)和辅存(二级存储)之间按需搬移数据
• 即主存中只放置应用程序最近访问的数据，而应用程序最近不访问的数据会搬移到辅存中，在应用程序需要时再搬回内存中
• 这个搬移过程对应用程序是透明的
• 虚拟内存的设想在 1959 年变成了现实。英国曼彻斯特大学的Tom Kilburn教授领导的团队于 1959 年展示了他们设计的Atlas计算机和Atlas Supervisor操作系统，开创了在今天仍然普遍使用的操作系统技术：分页（paging）技术和虚拟内存（virtual memory，当时称为 one-level storage system）。他们的核心思想中的根本性创新是区分了“地址（address）”和“内存位置（memory location）”。并因此创造了三项发明：
  • 地址转换：硬件自动将处理器生成的每个地址转换为其当前内存位置
  • 按需分页（demand paging）：由硬件地址转换触发缺页中断后，由操作系统将缺失的数据页移动到主存储器中，并形成正确的地址转换映射
  • 页面置换算法：检查最无用（least useful）的页，并将其移回二级存储中，这样可以让经常访问的数据驻留在主存中
• 计算机科学家对Atlas Supervisor操作系统给予高度的评价。Brinch Hansen 认为它是操作系统史上最重大的突破。Simon Lavington 认为它是第一个可识别的现代操作系统

内存管理主要做了什么？

• 内存的分配与回收 ：对进程所需的内存进行分配和释放，malloc 函数：申请内存，free 函数：释放内存

• 地址转换 ：将程序中的虚拟地址转换成内存中的物理地址

• 内存扩充 ：当系统没有足够的内存时，利用虚拟内存技术或自动覆盖技术，从逻辑上扩充内存

• 内存映射 ： 将一个文件直接映射到进程的进程空间中，这样可以通过内存指针用读写内存的办法直接存取文件内容，速度更快

• 内存优化 ： 通过调整内存分配策略和回收算法来优化内存使用效率

• 内存安全 ： 保证进程之间使用内存互不干扰，避免一些恶意程序通过修改内存来破坏系统的安全性

• …

什么是内存碎片？

• 内存碎片是由内存的申请和释放产生的，通常分为下面两种

  • 内部内存碎片(Internal Memory Fragmentation，简称为内部碎片)

    • 已经分配给进程使用但未被使用的内存
    • 导致内部内存碎片的主要原因是，当采用固定比例比如2的幂次方进行内存分配时，进程所分配的内存可能会比其实际所需要的大
      • 举个例子，一个进程只需要 65 字节的内存，但为其分配了$ 128（2^7） $大小的内存，那 63 字节的内存就成为了内部内存碎片

  • 外部内存碎片(External Memory Fragmentation，简称为外部碎片)

    • 由于未分配的连续内存区域太小，以至于不能满足任意进程所需要的内存分配请求，这些小片段且不连续的内存空间被称为外部碎片

    • 也就是说，外部内存碎片指的是那些并为分配给进程但又不能使用的内存。

常见的内存管理方式有那些？

• 内存管理方式可以简单分为下面两种
  • 连续内存管理 ： 为一个用户程序分配一个连续的内存空间，内存利用率一般不高
  • 非连续内存管理 ： 允许一个程序使用的内存分布在离散或者说不相邻的内存中，相对更加灵活一些

连续内存管理

• 块式管理是早期计算机操作系统的一种连续内存管理方式，存在严重的内存碎片问题

• 块式管理会将内存分为几个固定大小的块，每个块中只包含一个进程。如果程序运行需要内存的话，操作系统就分配给它一块，如果程序运行只需要很小的空间的话，分配的这块内存很大一部分几乎被浪费了

  • 这些在每个块中未被利用的空间，我们称之为内部内存碎片

• 除了内部内存碎片之外，由于两个内存块之间可能还会有外部内存碎片，这些不连续的外部内存碎片由于太小了无法再进行分配

• 在Linux系统中，连续内存管理采用了 伙伴系统（Buddy System）算法 来实现，这是一种经典的连续内存分配算法，可以有效解决外部内存碎片的问题

  • 伙伴系统的主要思想是将内存按 2 的幂次划分（每一块内存大小都是 2 的幂次比如$ 2^6=64 KB$）。并将相邻的内存块组合成一对伙伴（注意：必须是相邻的才是伙伴）

  • 当进行内存分配时，伙伴系统会尝试找到大小最合适的内存块。如果找到的内存块过大，就将其一分为二，分成两个大小相等的伙伴块。如果还是大的话，就继续切分，直到到达合适的大小为止

  • 假设两块相邻的内存块都被释放，系统会将这两个内存块合并，进而形成一个更大的内存块，以便后续的内存分配。这样就可以减少内存碎片的问题，提高内存利用率

• 虽然解决了外部内存碎片的问题，但伙伴系统仍然存在内存利用率不高的问题（内部内存碎片）
  • 这主要是因为伙伴系统只能分配大小为$2^n$的内存块，因此当需要分配的内存大小不是$2^n$的整数倍时，会浪费一定的内存空间

• 对于内部内存碎片的问题，Linux采用SLAB进行解决（非重点）

非连续内存管理

• 非连续内存管理存在下面 3 种方式：

  • 段式管理 ： 以段(—段连续的物理内存)的形式管理/分配物理内存

    • 应用程序的虚拟地址空间被分为大小不等的段，段是有实际意义的，每个段定义了一组逻辑信息，例如有主程序段MAIN、子程序段X、数据段D及栈段S等

  • 页式管理 ： 把物理内存分为连续等长的物理页，应用程序的虚拟地址空间划也被分为连续等长的虚拟页，现代操作系统广泛使用的一种内存管理方式

  • 段页式管理机制 ： 结合了段式管理和页式管理的一种内存管理机制，把物理内存先分成若干段，每个段又继续分成若干大小相等的页

虚拟内存

• 虚拟内存(Virtual Memory) 是计算机系统内存管理非常重要的一个技术，本质上来说它只是逻辑存在的，是一个假想出来的内存空间，主要作用是作为进程访问主存（物理内存）的桥梁并简化内存管理

• 总结来说，虚拟内存主要提供了下面这些能力

  • 隔离进程：物理内存通过虚拟地址空间访问，虚拟地址空间与进程一一对应。

    • 每个进程都认为自己拥有了整个物理内存，进程之间彼此隔离，一个进程中的代码无法更改正在由另一进程或操作系统使用的物理内存

  • 提升物理内存利用率 ： 有了虚拟地址空间后，操作系统只需要将进程当前正在使用的部分数据或指令加载入物理内存

  • 简化内存管理 ： 进程都有一个一致且私有的虚拟地址空间，程序员不用和真正的物理内存打交道，而是借助虚拟地址空间访问物理内存，从而简化了内存管理

  • 多个进程共享物理内存 ： 进程在运行过程中，会加载许多操作系统的动态库。这些库对于每个进程而言都是公用的，它们在内存中实际只会加载一份。这部分称为共享内存。

  • 提高内存使用的安全性 ： 控制进程对物理内存的访问，隔壁不同进程的访问权限，提高系统的安全性

  • 提供更大的可使用内存空间 ： 可以让程序拥有超过系统物理内存大小的可用内存空间。这是因为当物理内存不够用时，可以用磁盘充当，将物理内存页（通常大小为$4KB$）保存到磁盘文件（会影响读写速度），数据或代码页会根据需要在物理内存与磁盘之间移动

没有虚拟内存有什么问题？

• 如果没有虚拟内存的话，程序直接访问和操作的都是物理内存，看似少了一层中介，但多了很多问题

• 例子

  • 用户程序可以访问任意物理内存，可能会不小心操作到系统运行必需的内存，进而造成操作系统崩溃，严重影响系统的安全
  • 同时运行多个程序容易崩溃。比如你想同时运行一个微信和一个 QQ 音乐，微信在运行的时候给内存地址1xxx赋值后，QQ 音乐也同样给内存地址1xxx赋值，那么 QQ 音乐对内存的赋值就会覆盖微信之前所赋的值，这就可能会造成微信这个程序会崩溃
  • 程序运行过程中使用的所有数据或指令都要载入物理内存，根据局部性原理，其中很大一部分可能都不会用到，白白占用了宝贵的物理内存资源
  • …

什么是虚拟地址和物理地址？

• 物理地址（Physical Address） 是真正的物理内存中地址，更具体点来说是内存地址寄存器中的地址。程序中访问的内存地址不是物理地址，而是虚拟地址（Virtual Address）

• 也就是说，我们编程开发的时候实际就是在和虚拟地址打交道。比如在C语言中，指针里面存储的数值就可以理解成为内存里的一个地址，这个地址也就是我们说的虚拟地址

• 操作系统一般通过 CPU 芯片中的一个重要组件MMU(Memory Management Unit，内存管理单元)将虚拟地址转换为物理地址，这个过程被称为地址翻译/地址转换（Address Translation）

• 通过MMU将虚拟地址转换为物理地址后，再通过总线传到物理内存设备，进而完成相应的物理内存读写请求

• MMU 将虚拟地址翻译为物理地址的主要机制有两种: 分段机制 和 分页机制

什么是虚拟地址空间和物理地址空间？

• 虚拟地址空间是虚拟地址的集合，是虚拟内存的范围。每一个进程都有一个一致且私有的虚拟地址空间
• 物理地址空间是物理地址的集合，是物理内存的范围

虚拟地址与物理内存地址是如何映射的？

• MMU 将虚拟地址翻译为物理地址的主要机制有 3 种:

1. 分段机制
2. 分页机制
3. 段页机制

• 其中，现代操作系统广泛采用分页机制，需要重点关注！

分段机制

• 分段机制（Segmentation） 以段(—段 连续 的物理内存)的形式管理/分配物理内存

• 应用程序的虚拟地址空间被分为大小不等的段，段是有实际意义的，每个段定义了一组逻辑信息，例如有主程序段 MAIN、子程序段 X、数据段D及栈段S等

段表有什么用？地址翻译过程是怎样的？

• 分段管理通过 段表（Segment Table） 映射虚拟地址和物理地址

• 分段机制下的虚拟地址由两部分组成

  • 段号 ：标识着该虚拟地址属于整个虚拟地址空间中的哪一个段
  • 段内偏移量 ：相对于该段起始地址的偏移量

---

• 具体的地址翻译过程如下
  • MMU首先解析得到虚拟地址中的段号
  • 通过段号去该应用程序的段表中取出对应的段信息（找到对应的段表项）
  • 从段信息中取出该段的起始地址（物理地址）加上虚拟地址中的段内偏移量得到最终的物理地址

• 段表中还存有诸如段长(可用于检查虚拟地址是否超出合法范围)、段类型（该段的类型，例如代码段、数据段等）等信息

---

• 通过段号一定要找到对应的段表项吗？得到最终的物理地址后对应的物理内存一定存在吗
• 不一定。段表项可能并不存在
  • 段表项被删除 ：软件错误、软件恶意行为等情况可能会导致段表项被删除
  • 段表项还未创建 ：如果系统内存不足或者无法分配到连续的物理内存块就会导致段表项无法被创建

分段机制为什么会导致内存外部碎片？

• 分段机制容易出现外部内存碎片，即在段与段之间留下碎片空间(不足以映射给虚拟地址空间中的段)。从而造成物理内存资源利用率的降低

---

• 举个例子：假设可用物理内存为 5G 的系统使用分段机制分配内存。现在有 4 个进程，每个进程的内存占用情况如下

  • 进程 1：0~1G（第 1 段）

  • 进程 2：1~3G（第 2 段）

  • 进程 3：3~4.5G（第 3 段）

  • 进程 4：4.5~5G（第 4 段）

• 此时，我们关闭了进程 1 和进程 4，则第 1 段和第 4 段的内存会被释放，空闲物理内存还有 1.5G。由于这 1.5G 物理内存并不是连续的，导致没办法将空闲的物理内存分配给一个需要 1.5G 物理内存的进程

分页机制

• 分页机制（Paging） 把主存（物理内存）分为连续等长的物理页，应用程序的虚拟地址空间划也被分为连续等长的虚拟页。现代操作系统广泛采用分页机制

• 注意：这里的页是连续等长的，不同于分段机制下不同长度的段

---

• 在分页机制下，应用程序虚拟地址空间中的任意虚拟页可以被映射到物理内存中的任意物理页上，因此可以实现物理内存资源的离散分配

• 分页机制按照固定页大小分配物理内存，使得物理内存资源易于管理，可有效避免分段机制中外部内存碎片的问题

页表有什么用？地址翻译过程是怎样的？

• 分页管理通过 页表（Page Table） 映射虚拟地址和物理地址。我这里画了一张基于单级页表进行地址翻译的示意图

• 在分页机制下，每个应用程序都会有一个对应的页表

• 分页机制下的虚拟地址由两部分组成：

  • 页号 ：通过虚拟页号可以从页表中取出对应的物理页号
  • 页内偏移量 ：物理页起始地址+页内偏移量=物理内存地址

• 具体的地址翻译过程如下：

  • MMU 首先解析得到虚拟地址中的虚拟页号
  • 通过虚拟页号去该应用程序的页表中取出对应的物理页号（找到对应的页表项）
  • 用该物理页号对应的物理页起始地址（物理地址）加上虚拟地址中的页内偏移量得到最终的物理地址

---

• 页表中还存有诸如访问标志（标识该页面有没有被访问过）、页类型（该段的类型，例如代码段、数据段等）等信息

• 通过虚拟页号一定要找到对应的物理页号吗？找到了物理页号得到最终的物理地址后对应的物理页一定存在吗？

  • 不一定！可能会存在 页缺失 。也就是说，物理内存中没有对应的物理页或者物理内存中有对应的物理页但虚拟页还未和物理页建立映射（对应的页表项不存在）。

单级页表有什么问题？为什么需要多级页表？

• 以 32 位的环境为例，虚拟地址空间范围共有 $2^{32}（4G）$。假设 一个页的大小是 $2^{12}（4KB）$，那页表项共有 $\frac{4G}{4K} = 2^{20}$个，每个页表项为一个地址，占用 4 字节，$2^{20} \times \frac{2^2}{1024\times1024}= 4MB$（页内地址用12位，页号用20位）。也就是说一个程序啥都不干，页表大小就得占用$4M$（页表开太小导致了地址位数太多了）

• 系统运行的应用程序多起来的话，页表的开销还是非常大的。而且，绝大部分应用程序可能只能用到页表中的几项，其他的白白浪费了

• 总结

  • 页表必须连续存放，因此当页表很大的时候，需要占用很多个连续的页框
  • 没有必要让整个页表常驻内存，因为进程在一段时间内可能只需要访问某几个特定的页面

• 为了解决这个问题，操作系统引入了多级页表，多级页表对应多个页表，每个页表也前一个页表相关联。32 位系统一般为二级页表，64 位系统一般为四级页表。

  • 这里以二级页表为例进行介绍：二级列表分为一级页表和二级页表
  • 一级页表共有 1024 个页表项，一级页表又关联二级页表，二级页表同样共有 1024 个页表项
  • 二级页表中的一级页表项是一对多的关系，二级页表按需加载（只会用到很少一部分二级页表），进而节省空间占用

• 多级页表属于时间换空间的典型场景，利用增加页表查询的次数减少页表占用的空间

（和多级cache做对比，比较相似，增加访问次数来减内存，多级页表通过二次切割页表不让大段的页表留在内存里面，用的时候从辅存里面调就行，这也就是节省内存的原理，也是借鉴了多级cache的局部性原理）

TLB 有什么用？使用 TLB 之后的地址翻译流程是怎样的？

• 为了提高虚拟地址到物理地址的转换速度，操作系统在 页表方案 基础之上引入了 转址旁路缓存(Translation Lookasjde Buffer，TLB，也被称为快表)

• 在主流的 Arch64 和 x86-64 体系结构下，TLB 属于 (Memory Management Unit，内存管理单元) 内部的单元，本质上就是一块高速缓存（Cache）

• 使用TLB之后的地址翻译流程是这样的：

  1. 用虚拟地址中的虚拟页号作为 key 去 TLB 中查询；

  2. 如果能查到对应的物理页的话，就不用再查询页表了，这种情况称为 TLB 命中（TLB hit)。

  3. 如果不能查到对应的物理页的话，还是需要去查询主存中的页表，同时将页表中的该映射表项添加到 TLB 中，这种情况称为 TLB 未命中（TLB miss)。

  4. 当 TLB 填满后，又要登记新页时，就按照一定的淘汰策略淘汰掉快表中的一个页。

（和cache一样）

• 由于页表也在主存中，因此在没有 TLB 之前，每次读写内存数据时 CPU 要访问两次主存。有了 TLB 之后，对于存在于 TLB 中的页表数据只需要访问一次主存即可。

• TLB 的设计思想非常简单，但命中率往往非常高，效果很好。这就是因为被频繁访问的页就是其中的很小一部分。

• 快表和我们平时经常在开发系统中使用的缓存（比如 Redis）很像

换页机制有什么用？

• 换页机制的思想是当物理内存不够用的时候，操作系统选择将一些物理页的内容放到磁盘上去，等要用到的时候再将它们读取到物理内存中。也就是说，换页机制利用磁盘这种较低廉的存储设备扩展的物理内存。

• 这也就解释了一个日常使用电脑常见的问题：为什么操作系统中所有进程运行所需的物理内存即使比真实的物理内存要大一些，这些进程也是可以正常运行的，只是运行速度会变慢。

• 这同样是一种时间换空间的策略，你用CPU的计算时间，页的调入调出花费的时间，换来了一个虚拟的更大的物理内存空间来支持程序的运行。

什么是页缺失？

页缺失（Page Fault，又名硬错误、硬中断、分页错误、寻页缺失、缺页中断、页故障等）指的是当软件试图访问已映射在虚拟地址空间中，但是目前并未被加载在物理内存中的一个分页时，由 MMU 所发出的中断

• 常见的页缺失有下面这两种：

  • 硬性页缺失（Hard Page Fault） ：物理内存中没有对应的物理页。于是，Page Fault Handler 会指示 CPU 从已经打开的磁盘文件中读取相应的内容到物理内存（把之前在磁盘的页表给调回到内存里面来），而后交由 MMU 建立相应的虚拟页和物理页的映射关系。

  • 软性页缺失（Soft Page Fault）：物理内存中有对应的物理页，但虚拟页还未和物理页建立映射。于是，Page Fault Handler 会指示 MMU 建立相应的虚拟页和物理页的映射关系。

• 发生上面这两种缺页错误的时候，应用程序访问的是有效的物理内存，只是出现了物理页缺失或者虚拟页和物理页的映射关系未建立的问题。如果应用程序访问的是无效的物理内存的话，还会出现 无效缺页错误（Invalid Page Fault）

  常见的页面置换算法有哪些？

1. 最佳页面置换算法（OPT，Optimal） ：优先选择淘汰的页面是以后永不使用的，或者是在最长时间内不再被访问的页面，这样可以保证获得最低的缺页率。但由于人们目前无法预知进程在内存下的若干页面中哪个是未来最长时间内不再被访问的，因而该算法无法实现，只是理论最优的页面置换算法，可以作为衡量其他置换算法优劣的标准。

2. 先进先出页面置换算法（FIFO，First In First Out） : 最简单的一种页面置换算法，总是淘汰最先进入内存的页面，即选择在内存中驻留时间最久的页面进行淘汰。该算法易于实现和理解，一般只需要通过一个 FIFO 队列即可需求。不过，它的性能并不是很好。

3. 最近最久未使用页面置换算法（LRU ，Least Recently Used） ：LRU 算法赋予每个页面一个访问字段，用来记录一个页面自上次被访问以来所经历的时间 T，当须淘汰一个页面时，选择现有页面中其 T 值最大的，即最近最久未使用的页面予以淘汰。LRU 算法是根据各页之前的访问情况来实现，因此是易于实现的。OPT 算法是根据各页未来的访问情况来实现，因此是不可实现的。

4. 最少使用页面置换算法（LFU，Least Frequently Used） : 和 LRU 算法比较像，不过该置换算法选择的是之前一段时间内使用最少的页面作为淘汰页。

5. 时钟页面置换算法（Clock） ：可以认为是一种最近未使用算法，即逐出的页面都是最近没有使用的那个。

---

LRU 算法是实际使用中应用的比较多，也被认为是最接近 OPT 的页面置换算法。

不过，需要注意的是，实际应用中这些算法会被做一些改进，就比如 InnoDB Buffer Pool（ InnoDB 缓冲池，MySQL 数据库中用于管理缓存页面的机制）就改进了传统的 LRU 算法，使用了一种称为"Adaptive LRU“的算法（同时结合了LRU和LFU算法的思想）

分页机制和分段机制有哪些共同点和区别？

• 共同点 ：

  • 都是非连续内存管理的方式

  • 都采用了地址映射的方法，将虚拟地址映射到物理地址，以实现对内存的管理和保护

• 区别

  • 分页机制以页面为单位进行内存管理，而分段机制以段为单位进行内存管理。页的大小是固定的，由操作系统决定，通常为 2 的幂次方。而段的大小不固定，取决于我们当前运行的程序

  • 页是物理单位，即操作系统将物理内存划分成固定大小的页面，每个页面的大小通常是 2 的幂次方，例如 4KB、8KB 等等。而段则是逻辑单位，是为了满足程序对内存空间的逻辑需求而设计的，通常根据程序中数据和代码的逻辑结构来划分

  • 分段机制容易出现外部内存碎片，即在段与段之间留下碎片空间(不足以映射给虚拟地址空间中的段)。分页机制解决了外部内存碎片的问题，但仍然可能会出现内部内存碎片

  • 分页机制采用了页表来完成虚拟地址到物理地址的映射，页表通过一级页表和二级页表来实现多级映射；而分段机制则采用了段表来完成虚拟地址到物理地址的映射，每个段表项中记录了该段的起始地址和长度信息

  • 分页机制采用了页表来完成虚拟地址到物理地址的映射，页表通过一级页表和二级页表来实现多级映射；而分段机制则采用了段表来完成虚拟地址到物理地址的映射，每个段表项中记录了该段的起始地址和长度信息

段页机制

• 结合了段式管理和页式管理的一种内存管理机制，把物理内存先分成若干段，每个段又继续分成若干大小相等的页。

• 在段页式机制下，地址翻译的过程分为两个步骤：

  1. 段式地址映射。

  2. 页式地址映射。

哈希页表

• 哈希页表（Hashed Page Table）是一种用于操作系统虚拟内存管理中的数据结构，用于实现虚拟地址到物理地址的映射。它将虚拟地址空间分割成一系列大小相等的页（Page），每个页都对应着一个物理地址页帧（Page Frame）

• 哈希页表的核心是一个哈希表，每个表项对应着一个虚拟地址页。每个表项包含了该页的页号和页表项（Page Table Entry），页表项中包含了页帧号和一些附加信息

• 哈希页表使用哈希函数将虚拟地址映射到哈希表的一个表项中。如果哈希冲突，即两个不同的虚拟地址映射到了同一个表项中，那么通常使用链表来解决冲突。具体地，哈希表的每个表项中不仅仅存储了一个页表项，还可以存储一个链表的头指针，当发生哈希冲突时，就将新的页表项插入到链表的尾部

• 通过哈希页表，操作系统可以快速地将虚拟地址映射到对应的物理地址，从而实现了虚拟内存管理的基本功能。而哈希页表的设计也充分考虑了哈希冲突的情况，通过链表解决了冲突问题，使得哈希表的性能得到了进一步的提升

---

• 有关链表和哈希冲突（类比Hash table里面的链表处理手法）
  • 在哈希表中，哈希函数将键映射到哈希表中的一个索引位置，但是不同的键可能映射到相同的索引位置，这就是哈希冲突
  • 解决哈希冲突的一种方法是使用链表。具体地说，当发生哈希冲突时，将新键添加到与索引位置相对应的链表的末尾。如果发生另一个哈希冲突，就将新键添加到链表的末尾
  • 当需要查找一个键时，首先将该键传递给哈希函数，然后找到相应的索引位置。然后，遍历位于该位置上的链表，以查找具有相同键的节点。如果找到了该键，就返回节点的值；否则，就返回“不存在该键”
  • 因此，通过使用链表，可以在哈希表中存储具有相同哈希值的键，并且可以在需要查找具有相同哈希值的键时找到它们

反向页表

• 另一种减小页表大小的方法

• 由于多级页表是树形结构，虚拟空间膨胀会很快，对于大地址空间，多级页表仍会变得非常繁琐。 为了克服这个指数爆炸的效应，我们从虚拟的逻辑空间中走出来，着眼于有限的物理空间，以物理地址空间为抓手建立索引。这就是页寄存器和反置页表的思路

• 在这种情况下，如果页面本身相对于页表项很大的话，页表的内存开销就不足为惧了

• 具体的实现方法是，让每一个物理帧都和一个页寄存器相关联。页寄存器包含如下的标志位

  • 使用位（residence bit）：此帧是否被进程占用
  • 占用页号（occupier）：对应的页号p
  • 保护位（protection bits）

• 这种方法的好处在于

  • 大大减省页表占用内存

  • 页表大小与逻辑地址空间相比往往很小

• 缺点在于其反转了逻辑，要能够依据帧号找页号（建立联系），同时在用页号查找时就相对困难

  • 如上的联系通过哈希的方法建立，对逻辑地址进行哈希，随后就可以在页寄存器反向建立的查找表中进行小范围查找
  • 这里还可以引入快表。尽管快表功耗大
  • 如果有冲突需要遍历冲突项

• 反置页表是在页寄存器的基础上引入PID（进程标识）一同哈希，随后与反置页表中指定哈希值处对应验证，如果不一样就说明有冲突，继续遍历冲突项。如果PID和虚拟基址都相同，则找到了对应的页表。多余的开销来自于hash冲突。总体仍然是一个很好的思路