前言：该系列文章为笔者学习清华大学《操作系统原理》相关课程笔记，参考书籍《操作系统概念》《现代操作系统等》。如果涉及相关书籍或课程版权，联系即删～

《操作系统原理》学习笔记：第4章 非连续内存分配

• • • 4.1 为什么需要非连续内存分配
    • 4.2 分段（Segmentation）
    • 4.3 分页（Paging）
    • 4.4 页表（Page Table，分页机制中的映射表）
    • • 4.4.1 概述
      • 4.4.2 快表（Translation Look Buffer，TLB）
      • 4.4.3 二级/多级页表
      • 4.4.4 反向页表（inverted page table）

4.1 为什么需要非连续内存分配

连续内存分配的缺点：
分配给一个程序的物理内存是连续的
内存利用率低
有外碎片、内碎片问题

非连续分配的优点：
一个程序的物理地址空间是非连续的
更好的内存利用和管理
允许共享代码与数据（共享库等……）
支持动态加载和动态链接

非连续分配缺点：
如何建立虚拟地址和物理地址之间的转换

• 软件方案（开销过大）
• 硬件方案
  分段
  分页

4.2 分段（Segmentation）

需要考虑的问题：

• 程序的分段地址空间（内存地址空间如何寻址）

• 分段寻址方案（寻址机制如何实现）

虚拟的逻辑地址空间是连续的，通过分段之后将堆栈段，运行库，程序数据等有效隔离开。比如可以使用户代码段和主程序段相互之间访问，有些数据之间可以隔离，更加安全。

逻辑地址到物理地址转换需要映射机制，映射之后大小和位置都不同

分段寻址方案：

一个段：一个内存“块”

逻辑地址空间是一维的，程序访问内存地址需要一个二维的二元组（s 段号，addr 段内偏移）

• 段寄存器+地址寄存器实现方案：segment与address分离

• 单地址实现方案：段内与段内偏移合并形成完整地址
  

4.3 分页（Paging）

分段中段的尺寸可变，分页中页大小固定

• 划分物理内存至固定大小的帧：大小是2的幂，e.g 512, 4096, 8192

• 划分逻辑地址空间至相同大小的页：大小是2的幂，e.g 512

• 建立映射方案转换逻辑地址为物理地址（pages to frames），使用到如下技术，可加速地址转换：

  • 页表
  • MMU（内存管理单元）/TLB（快表，完成对页面的缓存）

帧（Frame）

• 物理页：物理内存的组织/布局方式

• 一个内存物理地址是一个二元组（f,o）
  f ：帧号（F组，共有2^F组）
  o ：帧内偏移（S位，每帧有2^S字节）
  物理地址 = 2^S * f + o

页（Page）

• 逻辑页：逻辑地址空间被划分为大小相等的页

• 页内偏移的大小=帧内偏移的大小；页号大小 <> 帧号大小

• 一个逻辑物理地址是一个二元组（p,o）
  p ：页号（P组，共有2^P组）
  o ：页内偏移（S位，每页有2^S字节）
  虚拟地址 = 2^S * p + o
  

• 一般逻辑地址空间 > 物理地址空间，不是所有的页都有对应的帧（3.4.3页表中详述原因）

• 页是连续的虚拟内存，映射到帧后是非连续的物理内存，优点：减少碎片

4.4 页表（Page Table，分页机制中的映射表）

4.4.1 概述

页表：有效实现从逻辑地址到物理地址的转换
PTBR：页表基址寄存器，存储页表的起始位置

操作系统和硬件相互配合实现：更加高效，节省空间的实现
每个运行的程序都有一个页表，属于程序运行状态，会动态变化

页表项的内容

• Flags（页表项标志位）
  • dirty bit (修改位)：判断页是否被修改过
  • resident bit（存在位）：判断页是否有物理页与其对应，有为1
  • clock/reference bit（引用位）：页是否有过对它的引用
  • 还有其它标志，比如是否读写标志
• 帧号 f

e.g 地址转换的实例：

具有16位地址（64kB）的系统
32KB的物理内存（逻辑地址空间通常大于物理地址空间）
每页1024byte（物理页与逻辑页大小相等）

逻辑地址
（4，0）逻辑页号为4，页内偏移为0
（3，1023）

对应物理地址
查询页表，标志位页号4对应的物理页帧不存在，3存在，对应的物理页帧为4，则（3，1024）对应的物理地址（4，1023）
分页机制的性能问题

性能问题？

• 空间的代价问题

  逻辑地址空间很大，导致页表可能非常大，n个程序有n个页表

• 时间开销问题

  页表非常大，无法放在CPU中，如果放在内存中，访问一个内存单元需要2次内存访问，一个用于获取页表项，一次用于访问数据

如何处理？

• 缓存(cacheing)：把常用数据缓存在离CPU近的地方

• 间接(Indirection)访问：将大拆分为小，比如索引，多级页表机制

4.4.2 快表（Translation Look Buffer，TLB）

缓存近期访问的页表项于CPU中

• 由两项（key:p, value:f）组成，使用associative memory（关联内存）实现，具备快速访问特性

• 访问时，先访问TLB，如果命中，物理页号很快被获取
  如果TLB未命中，查询内存中的页表，对应的页表项被更新到TLB中

• 注意：
  编程时，将访问集中在一个区域，尽量避免TLB缺失，避免访问内存中页表
  TLB中页号缺失，反写页号到TLB中，在x86，该过程由硬件完成，对于另一类CPU，该过程可能由操作系统实现

4.4.3 二级/多级页表

多级页表：使页表所占空间尽量小，对大page table的寻址转为多个小page table的寻址

• 二级页表
  p1存二级页表的起始地址，p2中存frame numer
  有些不存在的页表项不会占用内存，比如p1中查找映射关系就不存在，p2中就不需要保存

• 多级页表
  通过把页号分位为k个部分，来实现多级间接页表
  建立页表“树”
  每次访问的开销越来越大，但节省了空间，以时间换空间，时间的开销又可以通过TLB缓解

4.4.4 反向页表（inverted page table）

根据物理帧号去查逻辑页号

页表大小与逻辑地址大小相关，逻辑地址越大，页表越大。如何使页表与逻辑地址无直接关系，将页表大小与物理地址相关？反向页表

1⃣️ 页寄存器方案

使用页寄存器（Page Registers）每个帧和一个寄存器关联，寄存器内容包括：

• Residence bit：此帧是否被占用
• Occupier：对应的页号p
• Protection bits：保护位

e.g 页寄存器

物理内存大小：4096*4096=4K*4KB=16MB

页面大小：4906bytes=4KB

页寄存器使用的空间（假设8bytes/resgister)：8*4096=32Kbytes

页寄存器带来的额外开销：32K/16M=0.2%（大约）

虚拟内存的大小：任意

页寄存器方案的权衡

• 利
  转换表的大小相对于物理内存来说很小
  转换表的大小跟逻辑地址空间的大小无关

• 弊
  需要的信息回调了，根据帧号可以找到页号，如何转换回来？即根据页号找到帧号
  需要在反向页表中搜索想要的页号

2⃣️ 基于关联存储器（associative memory）的方案

• 优点：可以并行查找页号所对应的页帧号（key 页号，value 帧号）

• 缺点：开销太大，设计成本过高，硬件设计复杂，导致容量无法变大，需要放在CPU

在反向页表中搜索一个页对应的帧号

• 如果帧数较少，页寄存器可以被设置在关联内存中

• 在关联内存中查找逻辑页
  成功：帧号被提取
  失败：页错误异常（page fault）

• 限制因素：
  大量的关联内存非常昂贵
  难以在单个时钟周期内完成
  耗电

3⃣️ 基于哈希（hash）查找的方案

优点：可以有效缓解完成映射的开销

缺点：查找时可能发生哈希碰撞，通过程序PID缓解这种情况

根据page number查找frame number使用hash table实现，在反向页表中通过哈希算法来搜索一个页对应的帧号

• 对页做哈希计算，为了在“帧表”（每帧拥有一个表项）中获取对应的帧号
• 页p被放置在表中 f(p)= h(PID, p) 的位置，其中f是设定的哈希函数使用
• 为了查找页i，执行以下操作：
  • 计算哈希函数f(i)，并且使用它作为页寄存器表的索引
  • 获取对应的页寄存器
  • 检查寄存器标签是否包含i，如果包含，则代表成功，否则失败