存储管理

内存管理相关概念

内存空间的分配与回收

操作系统作为系统资源的管理者，当然需要对内存进行管理，在管理内存的时候，需要管理什么呢？

1. 操作系统负责内存空间的分配与回收
2. 操作系统需要提供某种技术从逻辑上对内存空间进行扩充
3. 操作系统需要提供地址转换功能（地址重定位），负责程序的逻辑地址与物理地址
   • 绝对装入：编译时产生绝对地址 — 单道程序阶段，此时没有操作系统
   • 可重定位装入：装入时将逻辑地址转换为物理地址 — 用于早期的多道批处理操作系统
   • 动态运行时装入：运行时将逻辑地址转换为物理地址，需要设置重定位寄存器 — 用于现代操作系统
4. 操作系统需要提供内存保护功能，保证各进程在各自存储空间内运行，互不干扰
   • 进程只能访问属于自己的进程空间，不能访问属于操作系统或是其他进程的内存空间
   • 方法：
     1. 设置一对上下限寄存器，存放进程的上下限地址，进程的指令想要访问某一地址时，CPU检查是否越界
     2. 采用重定位寄存器（又称基址寄存器）和界地址寄存器（又称限长寄存器）进行越界检查。重定位寄存器存放进程的起始物理地址，界地址寄存器存放进程的最大逻辑地址。如果逻辑地址大于界地址寄存器里存放的地址，就会抛出越界异常，否则会和重定位寄存器里的地址相加，然后访问该物理地址的存储单元

进程的内存映像

内存空间的扩充：覆盖与交换

覆盖

思想：将程序分为多个段（多个模块），常用的段常驻内存，不常用的段在需要时调入内存

内存中分为一个“固定区”和若干个“覆盖区”

需要常驻内存的段放在“固定区”中，调入后就不再调出（除非运行结束）

不常用的段放在“覆盖区”，需要用到时调入内存，用不到时调出内存

必须由程序员声明覆盖结构，操作系统完成自动覆盖。缺点：对用户不透明，增加了用户编程负担。覆盖技术只用于早期的操作系统中。

交换

思想：当内存空间紧张时，系统将内存中某些进程暂时换出外存，把外存中某些已具备运行条件的进程换入内存（进程在内存与磁盘间动态调度）

暂时换出外存等待的进程状态为挂起状态（挂起态，suspend）

挂起态又可以进一步细分为就绪挂起、阻塞挂起两种状态

应该在外存（磁盘）的什么位置保存被换出的进程？

具有对换功能的操作系统中，通常把磁盘空间分为文件区和对换区两部分。文件区主要用于存放文件，主要追求存储空间的利用率，因此对文件区空间的管理采用离散分配方式；对换区空间只占磁盘空间的小部分，被换出的进程数据就存放在对换区。由于对换的速度直接影响到系统的整体速度，因此对换区空间的管理主要追求换入换出速度，因此通常对换区采用连续分配方式。总之，对换区的 I/O 速度比文件区的更快。

什么时候应该交换？

交换通常在有许多进程运行且内存吃紧时进行，而系统负荷降低时就暂停。例如：当发现许多进程在运行时经常发生缺页，说明内存紧张，此时可以换出一些进程；如果缺页率明显下降，就可以暂停换出。

应该换出哪些进程？

可优先换出阻塞进程，也可换出优先级低的进程。为了防止优先级低的进程在被调入内存后很快又被换出，有的系统还会考虑进程在内存的驻留时间等其他因素。

（PCB会常驻内存，不会被换出外存）

内存空间的分配与回收

连续分配管理方式

单一连续分配

固定分区分配

动态分区分配

动态分区分配又称为可变分区分配。这种分配方式不会预先划分内存分区，而是在进程装入内存时，根据进程的大小动态地建立分区，并使分区的大小正好适合进程的需要。因此，系统分区的大小和数目是可变的。（例如：假设某计算机内存大小为 64MB，系统区占 8MB，用户区共 56MB……）

系统使用什么样的数据结构记录内存的使用情况

空闲分区表：每个空闲分区对应一个表项，表项中包含分区号、分区大小、分区起始地址等信息

空闲分区链：每个分区的起始部分和末尾部分分别设置前向指针和后向指针。起始部分处还可以记录分区大小等信息

当有很多空闲分区都能满足需求时，应该选择哪个分区进行分配？

动态分区分配算法

如何进行分区的分配与回收操作？（以空闲分区表为例）

分配：直接修改分区大小和起始地址，如果分区大小会占满整个空闲分区，就直接从空闲分区表中删除

回收：改变分区大小和起始地址，或者合二/三为一，或者新增表项

动态分区分配没有内部碎片，但是有外部碎片。

• 内部碎片：分配给某进程的内存区域中，有些部分没有用上。
• 外部碎片：内存中的某些空闲分区由于太小而难以利用。

如果内存中空闲空间的总和本来可以满足某进程的要求，但由于进程需要的是一整块连续的内存空间，因此这些“碎片”不能满足进程的需求。可以通过紧凑（拼凑，Compaction）技术来解决外部碎片。【其实就是“挪位”】

—动态重定位！

动态分区分配算法

首次适应算法（First Fit）

• 算法思想：每次都从低地址开始查找，找到第一个能满足大小的空闲分区。
• 如何实现：空闲分区以地址递增的次序排列。每次分配内存时顺序查找空闲分区链（或空闲分区表），找到大小能满足要求的第一个空闲分区。

最佳适应算法（Best Fit）

• 算法思想：由于动态分区分配是一种连续分配方式，为各进程分配的空间必须是连续的一整片区域。因此为了保证当“大进程”到来时能有连续的大片空间，可以尽可能多地留下大片的空闲区，即，优先使用更小的空闲区。

• 如何实现：空闲分区按容量递增次序链接。每次分配内存时顺序查找空闲分区链（或空闲分区表），找到大小能满足要求的第一个空闲分区。

缺点：会留下来越来越多的、很小的、难以利用的内存块，从而产生很多的外部碎片

最坏适应算法（Worst Fit）

• 算法思想：为了解决最佳适应算法的问题——即留下太多难以利用的小碎片，可以在每次分配时优先使用最大的连续空闲区，这样分配后剩余的空闲区就不会太小，更方便使用。
• 如何实现：空闲分区按容量递减次序链接。每次分配内存时顺序查找空闲分区链（或空闲分区表），找到大小能满足要求的第一个空闲分区。

缺点：后续如果有大进程到达，就容易没有内存分区可用了

邻近适应算法（Next Fit）

• 算法思想：首次适应算法每次都从链头开始查找，可能会导致低地址部分出现很多小的空闲分区，而每次分配查找时都要经过这些分区，增加了查找的开销。如果每次都从上次查找结束的位置开始检索，就能解决上述问题。

• 如何实现：空闲分区以地址递增的顺序排列（可排成一个循环链表）。每次分配内存时从上次查找结束的位置开始查找空闲分区链（或空闲分区表），找到大小能满足要求的第一个空闲分区。

存储管理基础

存储管理的主要模式

地址的概念

• 逻辑地址（相对地址）：用户编程所使用的地址空间，从 0 开始编号
  • 一维逻辑地址：单一地址
  • 二维逻辑地址：段号 : 段内地址
• 物理地址（绝对地址）：程序执行时处理器实际使用的地址空间

段式程序设计

• 把一个程序设计成多个段：代码段、数据段、堆栈段等
• 用户可以自己应用段覆盖技术扩充内存空间使用量
• 段覆盖是程序设计技术，不是 OS 存储管理的功能

主存储器的复用

多道程序设计需要复用主存，有两种方式：

复用方式	划分方法	占用方式
按分区复用	主存划分为多个固定/可变尺寸的分区	一个程序/程序段占用一个分区
按页框复用	主存划分成多个固定大小的页框(page frame)	一个程序/程序段占用多个页框

四种基本存储管理模式

模式	逻辑地址空间	主存分配方式
单连续存储管理	一维	一个固定分区或可变分区
页式存储管理	一维	多个主存页框
段式存储管理	二维（段式）	多个可变分区
段页式存储管理	二维（段式）	多个主存页框

关键理解：编译连接后的可执行程序，根据逻辑地址空间结构（一维 vs 二维），选择不同的存储管理方式映射到物理内存。四种方式都可以支持虚拟化和共享。

---

存储管理的功能

1. 地址转换（重定位）

将逻辑地址转换为绝对地址，有两种方式：

• 静态重定位：程序装入内存时进行地址转换，由装入程序执行，早期小型 OS 使用
• 动态重定位：CPU 执行程序时进行地址转换，依赖硬件地址转换机构，效率更高

2. 主存空间的分配与去配

• 分配：进程装入主存时，存储管理软件进行主存分配，并设置表格记录分配情况
• 去配：进程撤离或归还主存时，收回存储空间，调整主存分配表

3. 主存空间的共享

• 共享主存资源：多道程序设计中，多个程序同时驻留主存
• 共享主存区域：协作进程共享程序块或数据块

4. 存储保护

• 私有主存区：可读可写
• 公共区共享信息：根据授权
• 非本进程信息：不可读写
• 软硬件协同完成：CPU 检查访问权限，不允许则产生地址保护异常，由 OS 处理

5. 主存空间的扩充

技术	原理	实现方式
对换技术	把不运行的进程整体调出到磁盘	对换进程决定对换，硬件调入
虚拟技术	只调入进程的部分内容	CPU 遇到不在主存的地址 → 虚拟地址异常 → OS 调入 → 重执指令

---

虚拟存储器的概念

提出背景

• 问题：主存容量有限，用户编程受限，多道程序设计道数受限
• 观察：程序执行具有局部性——顺序性、循环性（空间局部性）、某阶段集中执行（时间局部性）
• 结论：不必将进程全部装入主存，可以部分调入

基本思想

1. 进程全部信息放在辅存中
2. 执行时先将一部分装入主存
3. 根据执行行为随用随调入
4. 主存空间不足时，将暂时不用的信息调出到辅存

实现思路

• 建立并自动管理两个地址空间：
  • (辅存) 虚拟地址空间：容纳进程装入
  • (主存) 实际地址空间：承载进程执行
• 对用户透明，用户感知到一个容量大得多的主存空间

---

存储管理的硬件支撑

存储器层次结构

L0: 寄存器          ← 最快、最小、最贵
L1: L1 Cache (SRAM)  ← 分指令缓存和数据缓存，32-256KB
L2: L2 Cache (SRAM)  ← 512KB-8MB
L3: L3 Cache (SRAM)  ← 多核共享
L4: 主存 (DRAM)
L5: SSD（本地固态硬盘）
L6: 本地硬盘
L7: 远程存储（分布式文件系统、Web服务器）
                     ← 最慢、最大、最便宜

高速缓存 Cache

• 介于 CPU 和主存之间的高速小容量存储器（SRAM）
• 组成：高速存储器 + 联想存储器 + 地址转换部件 + 替换逻辑
  • 联想存储器：按内容寻址（非按地址访问）
  • 地址转换部件：命中时直接访问 Cache；未命中时从内存读入 Cache
  • 替换部件：缓存满时按策略替换数据块

地址转换 / 存储保护的硬件支撑

• 基址寄存器 + 限长寄存器：定义允许访问的地址范围
• 逻辑地址 + 基址 = 物理地址
• 逻辑地址 > 限长 → 越界中断

核心要点：动态重定位、存储保护、虚拟存储器都必须有硬件支撑，否则在效率上没有实现价值。

---

单连续分区存储管理

单连续分区存储管理

每个进程占用一个物理上完全连续的存储空间。

1. 单用户连续分区

• 主存划分为系统区和用户区
• 设置栅栏寄存器界分两个区域
• 一般采用静态重定位
• 适用于单用户单任务 OS（如 DOS）

2. 固定分区

• 分区数量固定、大小固定
• 可用静态重定位，硬件实现代价低
• 主存分配表记录每个分区的起始地址、长度、占用标志
• 地址转换：下限寄存器 B + 上限寄存器，逻辑地址加上基址，超过上限则越界中断

3. 可变分区（详见 3.2.2）

---

可变分区存储管理

基本思想

• 按进程的实际内存需求动态划分分区
• 创建进程时查看是否有足够空闲空间：有则按需分割，无则等待
• 分区个数随机变化

主存分配表

使用链表维护：

• 已分配区表：记录每个已分配区的起址、长度、占用进程
• 未分配区表：记录每个空闲区的起址、长度

四种分配算法

算法	英文	策略	特点
最先适应	First Fit	从头开始找第一个够大的空闲区	简单快速，倾向于在低地址产生碎片
邻近适应	Next Fit	从上次分配位置开始找	分布更均匀
最优适应	Best Fit	找最小的够用空闲区	最容易产生外零头
最坏适应	Worst Fit	找最大的空闲区	避免小碎片，但大空闲区消耗快

内存回收

回收进程 X 的内存时，需要考虑与相邻空闲区的合并（上邻、下邻、上下都邻、上下都不邻四种情况）。

地址转换与存储保护

• 使用基址寄存器和限长寄存器
• 逻辑地址 < 限长 → 绝对地址 = 基址 + 逻辑地址
• 逻辑地址 ≥ 限长 → 越界中断

内存零头问题

类型	产生原因
内存内零头（内部碎片）	固定分区方式，分配的分区大于实际需要
内存外零头（外部碎片）	可变分区方式，产生小的不可用内存分区

• 任何适配算法都不能避免外零头
• 最优适配算法最容易产生外零头

移动技术（程序浮动技术）

• 目的：移动分区以消除外零头，合并出连续大空闲区
• 前提：需要动态重定位支撑
• 流程：请求分配 → 无足够大空闲区 → 检查空闲区总和是否够 → 移动现有分区 → 修改基址/限长 → 分配

---

页式存储管理

页式存储管理的基本原理

核心思想

• 主存划分为多个大小相等的页框（frame）
• 程序的逻辑地址自然分成等大小的页（page）
• 不同的页可以放在不同页框中，不需要连续
• 页表维系进程的主存完整性（页号 → 页框号的映射）

地址结构

逻辑地址：| 页号 | 单元号(页内偏移) |
物理地址：| 页框号 | 单元号(页内偏移) |

地址转换过程：通过页号查页表得到页框号，拼接单元号形成物理地址。

内存分配/去配

• 使用位示图记录主存页框分配情况（0=空闲，1=已分配）
• 建立进程页表维护逻辑完整性

页的共享

• 数据共享：不同进程可以用不同页号共享数据页
• 程序共享：不同进程必须使用相同页号共享代码页
  • 原因：共享代码页中的 JMP <页内地址> 指令，不同页号无法正确跳转
  • 需要编译为位置无关代码（PIC）：gcc -fpic

分页寻址计算示例

页面与页框大小为 1024 字节，指令 MOV 2100, 3100：

• 2100 = 1024 × 2 + 52 → 页号 2，偏移 52 → 查页表得页框号 6 → 物理地址 = 6 × 1024 + 52 = 6196
• 3100 = 1024 × 3 + 28 → 页号 3，偏移 28 → 查页表得页框号 8 → 物理地址 = 8 × 1024 + 28 = 8220

---

页式存储管理的地址转换

地址转换代价问题

• 页表放在主存 → 每次地址转换需要访问两次主存：
  1. 按页号读出页框号
  2. 按绝对地址进行读写
• 问题：存取速度降低一倍
• 解决：利用 Cache 存放部分页表 → 快表（TLB）

快表（TLB, Translation Lookaside Buffer）

• 专用高速存储器（联想存储器），按内容寻址
• 存放页表的一部分（热点页表项）
• 表项内容：页号 → 页框号

引入快表后的性能计算

例：主存访问 200ns，快表访问 40ns，命中率 90%

平均地址转换代价 = (200 + 40) × 90% + (200 + 200 + 40) × 10% = 260ns

比两次访存（400ns）下降了 35%

快表地址转换流程

1. 按逻辑地址中的页号查快表
2. 命中：由页框号和单元号直接形成绝对地址
3. 未命中：查主存页表形成绝对地址，同时将该页登记到快表
4. 快表满时，按策略淘汰一个旧登记项

多道程序环境

• 进程表登记每个进程的页表起始地址和长度
• 进程运行时，页表起始地址和长度送入页表控制寄存器
• 地址转换时先比较页号是否越界（页号 ≥ 页表长度 → 越界中断）

---

页式虚拟存储管理

程序局部性原理

这是虚拟存储器的理论基础（Denning, 1968）：

• 时间局部性（temporal locality）：最近访问的代码和数据，很快又被访问
• 空间局部性（spatial locality）：某存储单元被使用，其相邻单元很快也被使用

局部性的来源：

1. 程序大量顺序执行指令
2. 循环结构——少量代码多次执行
3. 过程调用深度有限，指令引用局限在少量过程中
4. 数组等数据结构的连续引用
5. 程序某些部分彼此互斥，不是每次都用到

抖动（Thrashing）

• 定义：页面刚被淘汰就又要调入，CPU 大部分时间用于交换页面而非执行指令
• 原因：分配给进程的页框数不够，或页面调度算法不当

基本思想

1. 进程全部页面装入虚拟存储器（辅存）
2. 执行时先把部分页面装入主存
3. 根据执行行为动态调入不在主存的页
4. 必要时调出暂时不用的页
5. 请求页式：首次只装入进程第一页

扩充的页表项

| 标志位 | 主存块号 | 辅助存储器地址 |

标志位包括：

• 主存驻留标志：该页是否在主存中
• 写回标志（修改位）：该页是否被修改过
• 保护标志：读/写/执行权限
• 引用标志：是否被访问过
• 可移动标志

地址转换流程（含缺页处理）

按逻辑地址查快表
  ├── 命中 → 形成绝对地址 → 继续执行
  └── 未命中 → 查页表
        ├── 该页在主存 → 形成绝对地址 + 登记入快表
        └── 该页不在主存 → 发缺页中断
              ├── 有空闲页框 → 调入页面 → 更新页表/快表
              └── 无空闲页框 → 选择淘汰页
                    ├── 淘汰页已修改 → 写回辅存
                    └── 淘汰页未修改 → 直接覆盖
                    → 调入新页 → 更新页表/快表 → 重执指令

---

页面调度

基本概念

• 页面调度：主存空间已满时，选择淘汰页的工作
• 缺页中断率 f = F / A
  • F：不成功访问次数（缺页次数）
  • A：总访问次数
  • 是衡量存储管理性能和用户编程水平的重要依据

影响缺页中断率的因素

1. 分配的页框数：越多 → 缺页率越低
2. 页面大小：越大 → 缺页率越低
3. 用户编程方法：大数据量下影响显著

用户编程示例

仅分得 1 个页框，页面 128 字，数组 A[128][128] 按行存放：

// 按列访问：每次赋值都缺页
for(j=0; j<128; j++)
  for(i=0; i<128; i++)
    A[i][j] = 0;
// 缺页次数：128×128 - 1 = 16383 次

// 按行访问：每换一行才缺页
for(i=0; i<128; i++)
  for(j=0; j<128; j++)
    A[i][j] = 0;
// 缺页次数：128 - 1 = 127 次

关键启示：数据按行存放时，按行访问符合空间局部性，缺页率大幅降低。

---

页面调度算法

1. OPT（最佳算法，Belady 算法）

• 淘汰以后不再访问的页，或距现在最长时间后再访问的页
• 只可模拟，不可实现（需要预知未来的访问序列）
• 作为其他算法性能评估的理论下界

2. FIFO（先进先出）

• 淘汰最先调入主存的页（驻留时间最长的页）
• 模拟程序执行的顺序性，有一定合理性
• Belady 异常：增加页框数反而可能导致缺页率增加（FIFO 特有）

3. LRU（最近最少使用）

• 淘汰最近一段时间最久未被访问的页
• 模拟程序的局部性：既考虑循环性又兼顾顺序性
• 严格实现代价大（需要维持特殊队列记录访问顺序）
• 模拟实现：
  • 每页设引用标志位
  • 设置时间间隔中断：中断时引用标志置 0
  • 地址转换时引用标志置 1
  • 淘汰时从引用标志为 0 的页中随机选择

4. LFU（最不常用）

• 淘汰最近一段时间访问次数最少的页
• 每页设一个计数器
• 时间间隔中断时所有计数器清 0
• 每访问一次计数器加 1
• 淘汰计数值最小的页

5. CLOCK（时钟算法）

• 采用循环队列构造页面队列（环形结构）
• 使用页引用标志位
• 工作流程：
  1. 页面调入/访问时，引用标志位置 1
  2. 淘汰时从指针当前位置开始扫描：
     • 引用位 = 1 → 清 0，跳过
     • 引用位 = 0 → 淘汰该页，指针推进一步

算法性能比较

性能（缺页率低 → 高）：OPT > LRU ≈ LFU > CLOCK > FIFO

注意：这是整体比较，个案中 CLOCK 可能优于 LRU。

Belady 异常

• 现象：FIFO 算法中，增加页框数反而导致更多缺页
• 原因：FIFO 不考虑页面的使用频率，仅按进入顺序淘汰
• 注意：LRU 和 OPT 不存在 Belady 异常

---

页的大小设计

页面大小	优点	缺点
较小	内部碎片少	页数多 → 页表大 → 页表可能要放入虚存
较大	适合磁盘大块传输；页表小	内部碎片多

• 极端情况：页面极大 → 退化为固定分区；页面覆盖全部 → 全部装载
• 部分系统支持多种页面大小以灵活利用 TLB

---

补充：伙伴系统（Buddy System）

基本原理（Knuth, 1973）

• 任何大小为 2^i 的空闲块可以分为两个大小为 2^(i-1) 的伙伴
• 两个伙伴可以合并成原来的 2^i 空闲块
• 是固定分区和可变分区的折中方案

Linux 中的伙伴系统

• mem_map[] 数组：以 page 结构为元素
• free_area 数组：以 free_area_struct 为元素
• 位图数组（bitmap）记录伙伴状态

Linux Slab 分配器

问题：伙伴系统以页框为基本分配单位，但内核常需要远小于页框的内存（如 inode、task_struct 等）

解决：基于伙伴系统的 Slab 分配器（源自 SunOS）

• 思想：为常用小对象建立缓存，申请/释放通过 slab 管理，缓存不够时才向伙伴系统申请
• 优点：减少内部碎片、对象管理局部化、减少与伙伴系统交互
• 结构：
  • 多个 cache，每个 cache 管理特定类型对象
  • 每个 cache 包含三类 slab：满 slab、半满 slab、空 slab
  • 13 种通用缓存：32B, 64B, 128B, …, 128KB（2 的幂次增长，碎片率 ≤ 50%）

关键操作：

• kmem_cache_create()：创建专用 cache
• kmem_cache_alloc() / kmem_cache_free()：分配/释放对象
• kmem_cache_grow() / kmem_cache_reap()：向伙伴系统申请/回收 slab
• kmalloc() / kfree()：通用缓冲区的申请/释放

---

补充：局部页面替换算法

1. 局部最佳页面替换算法（MIN，Prieve, 1976）

• 类似 OPT，需事先知道页面引用串
• 思想：进程在时刻 t 访问某页面后，如果该页在时间间隔 (t, t+τ) 内未被再次引用，则移出；否则保留
• τ 为系统常量，(t, t+τ) 称为滑动窗口
• 驻留集大小动态变化
• 向前看（看未来）

2. 工作集模型（Denning, 1968）

• 工作集 W(t, Δ)：时刻 (t-Δ, t) 内进程所访问的页面集合
• Δ 称为工作集窗口尺寸
• 工作集中的页面数称为工作集尺寸
• 向后看（看过去），模拟局部最佳算法

工作集替换算法：

1. 在时刻 t，检查 (t-Δ, t) 窗口内被引用的页面
2. 不在窗口内引用过的页面被移出驻留集
3. 驻留集大小随命中率动态调整

工作集的应用：

• 监视每个进程的工作集
• 定期从驻留集中删除不在工作集中的页面
• 仅当工作集在主存时，进程才能执行

缺页频率策略（PFF）：

• 定义缺页率上界 U 和下界 L
• 缺页率 > U → 分配更多页框
• 缺页率 < L → 减少页框
• 驻留集大小应接近工作集大小 W

---

反置页表

多级页表

问题：32 位地址空间，4KB 页面 → 2^20 个页 → 页表占 4MB 连续空间，多进程下开销巨大

解决：多级页表

• 二级页表：页目录表（一级） + 页表页（二级）
• 逻辑地址结构：| 页目录 | 页表页号 | 偏移 |
• 本质：多级不连续导致多级索引
  • 页目录项 → 页表页的索引
  • 页表页项 → 程序页面的索引
• 代价：增加寻址时间（时间换空间）
• SUN SPARC 使用三级分页结构

反置页表（Inverted Page Table, IPT）

问题：传统页表大小与虚拟地址空间成正比

核心思想：

• 不按虚拟页号建表，而是针对内存中的每个页框建立一个表项
• 按页框号排序
• 表项包含：进程标识、页号、特征位、哈希链指针
• 不论多少进程和虚拟页，页表大小固定 = 物理页框数

地址转换过程：

1. 用进程标识 + 虚页号经哈希函数得到哈希值
2. 哈希值指向哈希表中的一个表目
3. 遍历哈希链找到匹配的进程标识和页号
4. 该表项的索引即为页框号
5. 页框号 + 偏移 → 物理地址
6. 未找到匹配项 → 缺页中断

应用：PowerPC, UltraSPARC, IA-64

---

段式存储管理

段式存储管理

段式程序设计

• 程序由若干段组成，每段从 0 开始编址，段内地址连续
• 逻辑地址：段号 : 段内偏移
• 典型分段：主程序段、子程序段、工作区段、数据段

基本思想

• 基于可变分区存储管理，一个进程占用多个分区
• 硬件增加段地址寄存器（代码段、数据段、堆栈段、附加段）
• 段表：每段一个表项
  • 段始址、段限长
  • 存储保护、可移动、可扩充标志位

地址转换流程

段表控制寄存器 → 获取当前段表
  → 按逻辑地址中段号查段表
  → 获得段始址和段长
  → 单元号 < 段长？
      ├── 是 → 绝对地址 = 段始址 + 单元号
      └── 否 → 越界中断

段的共享

• 不同进程段表中的项指向同一个段基址
• 共享段需要保护（如只读），不满足保护条件则产生保护中断

分段寻址计算示例

段号 2，段内偏移 100，查段表得段 2 的基址为 8K：

• 物理地址 = 8K + 100 = 8192 + 100 = 8292

---

段式虚拟存储管理

基本思想

• 所有分段存放在辅存
• 运行时装入当前需要的段
• 访问不在主存的段时动态装入
• 由 OS 自动实现，对用户透明（区别于段覆盖技术——用户控制）

扩充的段表

| 段号 | 特征位 | 存取权限 | 扩充位 | 标志位 | 主存始址 | 限长 | 辅存始址 |

• 特征位：00=不在内存，01=在内存，11=共享段
• 存取权限：00=可执行，01=可读，11=可写
• 扩充位：0=固定长，1=可扩充
• 标志位：00=未修改，01=已修改，11=不可移动

地址转换流程

访问 S 段 B 单元
  → S 段在内存？
      ├── 是 → B < S 段长度？
      │         ├── 是 → 符合存取权限？
      │         │         ├── 是 → 形成绝对地址
      │         │         └── 否 → 保护中断
      │         └── 否 → S 段可扩充？
      │                   ├── 是 → 检查相邻空闲区 → 扩充
      │                   └── 否 → 地址错
      └── 否 → 缺段中断 → OS 处理
                ├── 有足够连续空闲区 → 装入 S 段
                └── 无 → 移动或调出其他段 → 装入 S 段

---

3.4.3 段页式存储管理

基本思想

• 段式 + 页式的结合
• 每一段不必占据连续存储空间，可存放在不连续的页框中
• 可扩充为段页式虚拟存储管理（装入部分段，或段中部分页面）

段表和页表

• 段表：每段一个表项，包含页表长度和页表始址
• 页表：每段有自己的页表，记录该段各页的页框号

逻辑地址：| 段号 | 页号 | 单元号 |

地址转换

1. 按段号查段表 → 获得该段的页表始址和页表长度
2. 按页号查该段的页表 → 获得页框号
3. 页框号 + 单元号 → 物理地址
4. 配合快表加速：快表项包含 段号 | 页号 | 块号

段页式虚拟存储管理的地址转换

查快表（段号+页号）
  ├── 命中 → 形成绝对地址
  └── 未命中 → 查段表
        ├── 无该段页表 → 缺段中断
        └── 有 → 页号超出页表长？
              ├── 是 → 越界中断
              └── 否 → 该页在主存？
                    ├── 是 → 形成绝对地址
                    └── 否 → 缺页中断

---

分段与分页的比较

比较维度	分页	分段
本质	信息的物理单位	信息的逻辑单位
与源程序关系	与逻辑结构无关	由源程序逻辑结构决定
用户可见性	不可见	可见
大小	系统确定，固定	用户指定，可变
起始地址	页大小整倍数	任意地址
连接装配后地址	变为一维结构	保持二维结构